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?
0
0
ja bym spróbował znaleźć wszystkie cykle rozmiaru 3 a potem dołączał do nich kolejne wierzchołki
0
Aha sprecyzuje - bo zalezy mi tylko na najdluzszym cyklu prostym
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.
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ć)?
0
Minimalne drzewo rozpiętości jest dobrze wyznaczone.