[Algorytmy] Trójkolorowanie grafu
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
[Algorytmy] Trójkolorowanie grafu
Podobno istnieje jakiś algorytm, który dany graf trójkolorowalny koloruje używając trzech kolorów tak, że po usunięciu co najwyżej jednego wierzchołka jest to kolorowanie poprawne. Czy ktoś coś o tym wie? Moje poszukiwania nie przyniosły skutku.
Ostatnio zmieniony 23 sie 2011, o 15:57 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawka nazwy tematu.
Powód: Poprawka nazwy tematu.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Trójkolorowanie grafu
Rozumiem, że chodzi o algorytm wielomianowy . Nie wygląda mi to na wiarygodne. W szczególności oznaczałoby to, że każdy graf trójkolorowalny da się w czasie wielomianowym 4-kolorować, a to bym uznał za zadanie bardzo trudne.
edit: rzeczywiście jest to NP-trudne
edit: rzeczywiście jest to NP-trudne