How many unique cycles of length 4 present in a complete Undirected graph of 6 vertices? My answer is 45 and i think its not correct because there are only 4 options 1)15 2)30 3)90 4)360 please share your view
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:56:30
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:56:30
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 22:38:32 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
What's source of the problem? It looks like test question.
the answer is 90, if we consider cycles 1 -> 2 -> 3 -> 1 and 1 -> 3 -> 2 -> 1 as different cycles (directed graph).
sorry i forgot to mention that graph is undirected.SO obviously 90 reduces to 45
It is not so obviously. Forget about directed graph or not, but we can go from x to y, and from y to x for any pair of vertices. The question is: consider we such cycles as one, or they are two different cycles? It is matter for you to go in order Paris, London, Moscow, Berlin, or Berlin, Moscow, London, Paris? Just example. John wants to bring souvenir from Paris to his grandmother in London. And Ivan want to go from Moscow to London. So, for John and Ivan order is matter. Especially if you need to bring a souvenir as soon as possible (perishable food e.g.)
If order and starting vertex don't matter, any set with 4 vertices will uniquely describe a cycle, won't it? The cycle certainly exists, since the graph is complete. So isn't the answer just (6 4) = 6!/(4!2!) = 15 ? [UPD: No, the answer is 90 because of permutations]
1 2 3 4, 1 3 4 2, 1 (any permutaion of 3 other vertices (2, 3, 4)). (6, 4) * 3! = 90
You're right, thanks. Another way of seeing the math is: Given a subset of 4 vertex, any permutation of its elements results in a different cycle (so the answer would be (6,4) * 4! = 360). However, "cyclic cycles" (like 1 2 3 4 and 2 3 4 1) are the same cycle, and are cleary counted exactly 4 times. So the answer is 360/4 = 90. Thank you very much!
you are considering directed graph ..I want solution for Undirected.with any 4 vertices there will be only 3 distinct cycles of length 4 .so answer comes out to be 45
It is not matter directed graph or not. Read carefully my comments above. Cycle is not set of edges. [Cycle](http://en.wikipedia.org/wiki/Cycle_(graph_theory)) is a closed path. [Path](http://en.wikipedia.org/wiki/Path_(graph_theory)) in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. If element of the sequence has next element in it, it means the order is matter. Path 1 -> 2-> 3 -> 4 and 4 -> 3 -> 2 -> 1 are two different pathes.