k-kolorowalność grafu.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
k-kolorowalność grafu.
Udowodnij, że graf jest \(\displaystyle{ k}\)-kolorowany wtw gdy można tak acyklicznie zorientować krawędzie, że nie istnieje ścieżka zorientowana długości \(\displaystyle{ k}\).
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
k-kolorowalność grafu.
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem
Także tutaj:
Obóz OM 2016, str. 63: