Matematyka.pl

Grafy nieskierowane tże, każda dwuspójna składowa jest trójkątem (cyklem długości \(\displaystyle{ 3}\)).

Czyli np: Ten graf nie może wyglądać inaczej ze względu na

1. Trójkąty mogą łączyć się wierzchołkami (lub krawędź między wierzchołkami), ale nie mogą mieć wspólnego boku bo powstaje \(\displaystyle{ 2}\)-spójna nie będąca trójkątem.

2. Dwa trójkąty mogą się łączyć ze sobą co najwyżej jedną krawędzią / wierzchołkiem - w przeciwnym razie mamy dwuspójną

a) Udowodnij, że graf jest \(\displaystyle{ 3}\)-kolorowalny w sensie wierzchołkowym.
Wierzchołki, które należą do więcej niż jednej dwuspójnej kolorujemy na czerwono. Następnie wierzchołki z innych trójkątów połączone krawędzią na zielono i niebiesko. Pozostałe na kolor zielony, albo niebieski - inny niż już jest w trójkącie.

b) Zaproponuj efektywny algorytm 3-kolorowania grafów trójkątnych:
Rozbijamy na dwuspójne składowe i wykonujemy to co w dowodzie.

To działa w czasie \(\displaystyle{ O(|V| + |E|)}\). Czyli czas podzielenia na dwuspójne - trójkąty, a następnie analiza tak jak napisałem.

c) zaproponuj algorytm, który obliczy rozmiar najliczniejszego skojarzenia.
Zauważamy, że zawsze opłaca się skojarzyć węzły mające stopień 2. Opłaca się, bo gdybyśmy ich nie skojarzyli, to jeden z tych węzłów traci szanse na skojarzenie, zupełnie niesłusznie, bo nie musi jej tracić. Po prostu jeśli skojarzymy je, to rozwiązanie się nie pogorszy.

Więc stopniowo skojarzamy takie wierzchołki, usuwamy skojarzone, aktualizujemy stopnie itd.
To można wykonać w czasie liniowym względem rozmiaru grafu.

Po wykonaniu tego algorytmu co pozostanie z grafu ?
Pozostaną dosłownie "słoneczka" i pojedyncze węzły. Trzeba więc doliczyć liczbę "słoneczek" (każde "słoneczko" to jedno skojarzenie).


Może ktoś sprawdzić ? Wychodzą algorytmy liniowe.

Mam nadzieję, że dobrze zrozumiałem to co (IMO dość chaotycznie) napisałeś.

2a)

Rozumiem, że zgodnie z twoim algorytmem pokolorowalibyśmy na czerwono wierzchołki A i B - jeśli tak to nie jest to poprawne 3-kolorowanie.
2c)

Jeśli dobrze zrozumiałem, to według tego algorytmu skojarzymy ze sobą wierzchołki B i C (obydwa mają stopień 2). Jeśli tak to jest problem, ponieważ optymalne (swoją drogą doskonałe) skojarzenie w tym grafie nie korzysta z tej krawędzi. Możesz zauważyć, że jeśli weźmiesz krawędź BC to rozbijemy graf na dwa grafy, z których każdy ma nieparzystą liczbę wierzchołków więc nie uda się tam znaleźć skojarzenia doskonałego.



Pozdrawiam

Ok, czyli popełniłem sporo błędów. W tym c) wynika to z tego, że przyjąłem niepoprawną definicję dwuspójnej składowej.

Wyjaśnijmy jaką przyjmujemy definicję dwuspójnej składowej:
Dwuspójna składowa to taki podgraf, że każde dowolne dwie krawędzie leżą na pewnym cyklu prostym.


Poprawiam a)
Oczywiście trójkąty można pokolorować. Przypuśćmy, że istnieje podgraf pełny romiaru nie mniejszego niż 4. Wówczas istniałaby dwuspójna inna niż trójkąt, a to przeczy założeniu.

Poprawiam b)
Jeszcze muszę przemyśleć.

Poprawiam c)
Nad tym jeszcze muszę pomyśleć. Chętnie też poznam wskazówki.

ab)

Niestety nie do końća jest tak, że jak graf nie ma kliki czterowierzchołkowej to będzie 3-kolorowalny. Owszem, jest to warunek konieczny, ale nie wystarczający, oto przykład:
Nie ma tu kliki 4-wierzchołkowej a nie da się go pokolorować 3 kolorami.

Hint:

Czy ten algorytm to nie jest jakaś heurystyka ?

Jest to heurystyka, ale jej właściwość jest taka, że dla każdego grafu istnieje taka kolejność wierzchołków, że jeśli będziemy rozpatrywać je w tej kolejności to first-fit da optymalną odpowiedź (polecam udowodnić). A w tym konkretnie grafie ta kolejność jest łatwa do wyznaczenia.

a)

Indukcja po dwuspójnych.
Załóżmy, że mamy \(\displaystyle{ k}\) dwóspojnych i istnieje kolorowanie za pomocą trzech kolorów.

Dokładamy kolejną dwuspójną. Ktoś dodaje jakieś dowolne krawędzie lub zespaja wierzchołkiem. I ja teraz twierdzę, że koloruje ten dołożony trójkąt dowolnie trzema kolorami.

Chodzi o to, że jeśli zaburzyłem sytuację w innych podgrafach to jestem w stanie ją natychmiast poprawić korzystając z zał. indukcyjnego. Skoro te mniejsze podgrafy mialy poprawne kolorowanie, to jeśli doszło do kolizji to po prostu przepermutuje kolory w starym podgrafie - co się da zrobić z uwagi na zał. ind.

Pomiędzy poszczególnymi podgrafami nie może istnieć kolizja kolorów - bo istniałby cykl.

Co nazywam podgrafami ? Są wzięte w pomarańczowe kółka:

Trochę ślisko opisane, ale chyba zrozumiałem i chyba nawet dobrze

b)

Alternatywny algorytm:

Ten graf to prawie drzewo, więc jest prawie dwudzielny,
więc wystarczą prawie dwa kolory. To jest silna intuicja.

DFS - dwudzielimy wierzchołki - te po lewej są niebieskie, te po prawej czerwone.
Powiedzmy, że z lewej do lewej pojawia się krawędź powrotna - zamykamy trójkąt. Wówczas
musimy pokolorować go na trzeci, zielony kolor.
(powrotne ze strony na strone są ok - choć nie mogą się pojawić)

To działa, bo jedyna sytuacja, że kolorowanie mogłoby się nie udać to gdy
po lewej i prawej mamy połączone węzły zielone. Jednak się to nie zdarzy,
bo wtedy graf miałby większą dwuspójną niż trójkątna.

Co Ty na to ?

Tak - to jest mniej więcej to, co było moim pomysłem - przechodzimy dfsem i zauważamy, że zawsze z wierzchołka (do już odwiedzonych przed nim wierzchołków) wychodzi tylko krawędź do ojca i ewentualnie jedna krawędź powrotna (więcej niż jedna krawędź powrotna sygnalizowałaby, że jest dłuższy cykl prosty). Więc algorytm first-fit o którym wcześniej wspominałem da nam kolor co najwyżej trzy (bo mamy co najwyżej dwóch pokolorowanych sąsiadów).