Cześć,
Długość cyklu to liczba krawędzi. Jako cykl rozumiem kółko (bez powtarzania węzłów)
Zastanawiają mnie takie problem: Sprawdź czy graf zawiera:
(a) Cykl nieparzystej długości
(b) Cykl parzystej długości
(c) Cykl długości trzy (trójkąt)
(a) Wystarczy sprawdzić czy graf jest dwudzielny (jak jest to graf nie ma cyklu nieparzystej długości, przeciwnie jest). Można to zrobić w czasie liniowym, jakimś algorytmem typu kolorowanie dwoma kolorami (jak sie nie uda pokolorwać - kolorujemy na przemian - to jest cykl nieparzysty).
(b) Tutaj bym sprawdził czy graf jest dwudzielny. Jeśli jest, to sprawdzę czy graf nie jest drzewem (DFS)
(c) Z tym się waham, ale chyba BFS przejdzie. Po prostu sprawdzamy jak daleko jest wierzchołek, którego krawędź sięga do odwiedzonego już wierzchołka.
Co o tym sądzicie ?