Witam potrzebje jakiejs metody znajdowania WSZYSTKICH cykli w grafie nieskierowanym. Wiem ze pojedyncze cykle mozna znalezc dzieki prostemu przeszukiwaniu grafu wglab ale trzeba by to jakps ulepszyc. Macie pomysl?
Cykl w grafie nieskierowanym
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
0
ja bym spróbował znaleźć wszystkie cykle rozmiaru 3 a potem dołączał do nich kolejne wierzchołki
- Rejestracja: dni
- Ostatnio: dni
0
- Minimalne drzewo rozpiętości z istniejących krawędzi.
- Każda krawędź która nie weszła do drzewa rozpiętości zamyka cykl - najkrótsza droga w minimalnym drzewie rozpiętości.
- Jeżeli dwa cykle mają wspólną krawędź, to można z nich złożyć jeden większy.
- Rejestracja: dni
- Ostatnio: dni
0
- Każda krawędź która nie weszła do drzewa rozpiętości zamyka cykl - najkrótsza droga w minimalnym drzewie rozpiętości.
A jeżeli są 2 takie krawędzie? Czy to coś zmienia? Zobaczmy tutaj:
http://www.algorytm.org/images/grafy/minimalne_drzewo_rozpinajace.gif
Między wierzchołkami e, f, d jest cykl, jednak są tam 2 krawędzie, które nie wchodzą do drzewa rozpinającego. I mam tak sobie składać te cykle aż zostanie tylko jeden (lub nie będę mógł już łączyć)?