Jak sprawdzić czy dany graf zawiera cykl nieparzysty?
Jak wypisać z danego grafu dowolny cykl nieparzysty?
Z góry dzięki za wskazówki.
Pozdr.
0
0
Wskazówka nr 1: http://bit.ly/HUaCZ4 ;)
0
Sprawdzić czy nie jest dwudzielny : czyli pokolorować wierzchołkowo na 2 kolory. Jeżeli się nie da to ma cykl nieparzysty
liczba chromatyczna >= 3. A dwudzielny = 2
A co do wypisania dowolnego grafu, to i tak trzeba przejść po grafie... I DFSem sprawdać czy już się doszło do elementu odwiedzonego i trzeba numerować pokolei jak wychodzimy dfsem