Grafy-liczba chromatyczna, dopełnienia i dwudzielność
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
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.
\(\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.
-
- 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ść
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.
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.
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
Jedno zrobione
1) przydaje się pewna sztuczka algebraiczna
3) W pewnym momencie trzeba zrobić dowod niewprost
1) przydaje się pewna sztuczka algebraiczna
3) W pewnym momencie trzeba zrobić dowod niewprost
-
- 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ść
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.)
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.)
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
Trzecie uznaję.
Do pierwszego się czepiam:
Dowód jest dla mnie trochę niezrozumowiały i wygląda mi na implikację w złą stronę
Proszę mnie poprawi jesli się mylę
Do pierwszego się czepiam:
Której partycji? Można się zapytac jakie są to wierzchołki? Tak konkretnie.Zlepiamy wszystkie wierzchołki jednej partycji
Dowód jest dla mnie trochę niezrozumowiały i wygląda mi na implikację w złą stronę
Proszę mnie poprawi jesli się mylę
-
- 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ść
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.
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.
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
W DUŻYM skrócie dobrze o to chodziło. Zrobione zadanie . Nie będę już się czepiał szczegółów
zamykam temat
zamykam temat
-
- 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ść
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ć
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ć