[Algorytmy] Trójkolorowanie grafu

Dumel
Użytkownik
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

Post autor: Dumel » 21 sie 2011, o 16:40

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.

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

[Algorytmy] Trójkolorowanie grafu

Post autor: Zordon » 31 sie 2011, o 10:30

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

ODPOWIEDZ