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.
Cykl nieparzysty
- Rejestracja: dni
- Ostatnio: dni
0
- Rejestracja: dni
- Ostatnio: dni
- Postów: 1398
0
Wskazówka nr 1: http://bit.ly/HUaCZ4 ;)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 26
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