Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
miodzio1988

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: miodzio1988 »

1) Udowodnij, że:
\(\displaystyle{ \chi (G) \cdot \chi (G') \le \frac{1}{4} (n+1)^{2}}\)

\(\displaystyle{ G'}\) - dopełnienie grafu \(\displaystyle{ G}\)
\(\displaystyle{ \left|V(G) \right|=n}\)

2)Znajdź najmniejsze \(\displaystyle{ n}\) takie, że dla każdego grafu o \(\displaystyle{ n}\) wierzchołkach \(\displaystyle{ G}\) ma cykl lub \(\displaystyle{ G^{'}}\)
ma cykl

3)udowodnij:
Graf \(\displaystyle{ G}\) jest dwudzielny \(\displaystyle{ \Leftarrow}\) Każdy cykl w grafie \(\displaystyle{ G}\) ma parzystą długość.

Miłej zabawy
Zadania nie są trudne, więc wystarczy kilka "myków" i będą rozwiązane.
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: xiikzodz »

Najszybciej zapisać 2. |G|=n.

Dla n=4 wybieramy graf w kształcie litery "Z" - jego dopełnienie ma kształt "N".
Dalej zauważamy że drzewo rozpinające spójny graf o n wierzchołkach ma n-1 krawędzi, czyli w przypadku 5 graf i jego dopełnienie miałyby łącznie 8 krawędzi co jest mniej niż liczba krawędzi grafu pełnego o pięciu wierzchołkach, 10. Stąd odpowiedzią jest 5.
miodzio1988

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: miodzio1988 »

Jedno zrobione

1) przydaje się pewna sztuczka algebraiczna
3) W pewnym momencie trzeba zrobić dowod niewprost
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: xiikzodz »

3. można wprost. Zlepiamy wszystkie wierzchołki jednej partycji w jeden a potem drugiej partycji w drugi - topologicznie przestrzeń ilorazowa powstała z realizacji geometrycznej grafu przez podzielenie przez wierzchołki z dwóch partycji. Powstaje multigraf o dwóch wierzchołkach. Każdemy cyklowi w oryginalnym grafie odpowiada droga zamknięta równej długości w tym multigrafie o dwóch wierzchołkach, a te są oczywiście parzystej długości.

1. Wystarczy pokazać, że \(\displaystyle{ \chi(G)+\chi(G')\le n+1}\) następnie zastosować nierówność pomiędzy średnimi. To pierwsze łatwo przez indukcję. Dla \(\displaystyle{ n=1,2}\) jasne. Rozważmy więc dowolny graf \(\displaystyle{ G_{n+1}}\) o \(\displaystyle{ n+1}\) wierzchołkach oraz jemu odpowiadający \(\displaystyle{ G_{n+1}'}\). Zauważmy, że parę \(\displaystyle{ G_{n+1},G_{n+1}'}\) otrzymujemy z pary \(\displaystyle{ G_n,G_n'}\) otrzymanej przez usunięcie jednego wierzchołka. Na mocy założenia indukcyjnego \(\displaystyle{ \chi(G_n)+\chi(G_n)'\le n+1}\) ponadto dodanie jedego wierzchołka zwiększa \(\displaystyle{ \chi}\) maksymalnie o \(\displaystyle{ 1}\). Jeśli zatem dodanie wierzchołka zwiększy \(\displaystyle{ \chi}\) co najwyżej jednego z grafów \(\displaystyle{ G_n,G_n'}\) to

\(\displaystyle{ \chi(G_{n+1})+\chi(G_{n+1}')\le\chi(G_n)+\chi(G_n')+1\le n+1+1=n+2}\)

i gotowe. Jeśli \(\displaystyle{ \chi(G_{n+1})=\chi(G_n)+1}\) oraz \(\displaystyle{ \chi(G_{n+1})=\chi(G_n)+1}\), czyli dodanie wierzchołka zwiększyło obie liczby chromatyczne, to zauważamy, że musiało zachodzić:

\(\displaystyle{ \chi(G_n)+\chi(G_n')\le n}\)

Dodając bowiem jeden wierzchołek, dodajemy ogółem \(\displaystyle{ n}\) krawędzi łącznie do grafów \(\displaystyle{ G_n,G_n'}\), a skoro spowodowało to zwiększenie \(\displaystyle{ \chi}\) w obu grafach, to liczba dodanych do poszczególnych grafów krawędzi musiała być równa przynajmniej liczbom chromatycznym tych grafów. Stąd \(\displaystyle{ \chi(G_n)+\chi(G_n')\le n}\) i argument indukcyjny zamknięty.

(Proste do wymyślenia, paskudne w zapisie... to znaczy jak się nie dysponuje odpowiednim językem.)
miodzio1988

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: miodzio1988 »

Trzecie uznaję.
Do pierwszego się czepiam:
Zlepiamy wszystkie wierzchołki jednej partycji
Której partycji? Można się zapytac jakie są to wierzchołki? Tak konkretnie.
Dowód jest dla mnie trochę niezrozumowiały i wygląda mi na implikację w złą stronę
Proszę mnie poprawi jesli się mylę
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: xiikzodz »

A faktycznie. Niestety nie widzę implikacji w lewą stronę w ogóle, a dokładniej nie widzę w ogóle treści żadnego postu zawierającego taką implikację "Leftarrow". Dopiero po zacytowaniu widzę jego kod i jeśli założenie jest przestawione kolejnością z tezą, to istnieje wyjątkowo duża szansa pomyłki.

W drugą stronę - etykietujemy wierzchołki 0 i 1 tak, żeby sąsiednie miały różne etykiety, co można zrobić - w przeciwnym razie znajdziemy cykl nieparzystej długości. Etykiety dają podział dwudzielny.
miodzio1988

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: miodzio1988 »

W DUŻYM skrócie dobrze o to chodziło. Zrobione zadanie . Nie będę już się czepiał szczegółów
zamykam temat
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

Post autor: xiikzodz »

A że forum ma ponoć nieść oświaty kaganiec dopiszę o tym etykietowaniu (zachłannym). Wystarczy ograniczyć się do jednej składowej grafu, a składowe jedna po drugiej.

Wybieramy dowolny wierzchołek v_0, etykietujemy 0, następnie wybieramy dowolnego sąsiada v_1, etykietujemy 1, następnie wybieramy v_2 sąsiadujący z v_1 i kładziemy 0 itd. aż do momentu, w którym wszyscy sąsiedzi wybranego wierzchołka mają już etykietę. Z parzystości cykli ta etykieta wspólna dla sąsiadów wierzchołka jest różna od etykiety wierzchołka. Dalej indukcyjnie. Mając poetykietowany jakiś spójny podzbiór wierzchołków grafu wybieramy, o ile istnieje, wierzchołek sąsiadujący z jakimś wierzchołkiem tego podzbioru, etykietujemy go stosownie i postępujemy tak, jak poprzednio, czyli etykietujemy kolejnych sąsiadów aż do momentu, w którym wszyscy sąsiedzi już etykiety mają. I tak do wyczerpania wierzchołków grafu. Algorytm etykietuje poprawnie, bo jeśli w pewnym kroku dwóch sąsiadów wierzchołka ma tę samą etykietę, to przy założeniu dotychczasowego poprawnego etykietowania znajdziemy w grafie cykl długości nieparzystej w postaci poprawnie poetykietowanej drogi łączącej te dwa wierzchołki zlepionej w wierzchołku z nimi oboma sąsiadującym.

Jak widać prosty argument, za to wypracowanie długie. Można sobie nieco życie uprościć
ODPOWIEDZ