Witam,
graf trójkątny jest spójny oraz każda jego dwuspójna składowa jest 3-cyklem.
a) Udowodnij, że każdy graf trójkątny jest 3-kolorowalny
Więc powiem tak:
Rozbijmy graf na 2spójne. Wierzchołek, który należy do więcej niż jednej dwuspójnej (trójkąta) malujemy na czerwono. Pozostałe dwa w obrębie jednego trójkąta, które występują tylko w jednej spójnej składowej na niebiesko i zielono.
Ponownie składamy graf. Teraz czerwono wierzchołki się pozlewają, zaś niebieskie i zielone nie naruszą kolorowania - bo gdyby tak było oznacza to, że istnieje krawędź pomiędzy dwoma zielonymi (niebieskimi) - a wtedy istnieje większa dwuspójna niż trójkąt - sprzeczność.
b) Podaj efektywny algorytm 3-kolorowania grafów trójkątnych:
1. Rozbij graf na 2spójne
2. Wierzchołki, które należą do więcej niż jednej 2spójnej składowej pomaluj na czerwono
3. Pozostałe wierzchołki pokoloruj w obrębie każdego z trójkątów - jeden na niebiesko, drugi na zielono.
Czy to jest ok( a) i b) )?