Matematyka dyskretna 2/Ćwiczenia 3: Własności podziałowe i Twierdzenie Ramsey'a

From Studia Informatyczne

Własności podziałowe i Twierdzenie Ramsey'a

Ćwiczenie 1

Wykaż, że dla dowolnego grafu \displaystyle \mathbf{G} , co najmniej jeden z grafów \displaystyle \mathbf{G} , \displaystyle \overline{\mathbf{G}} jest spójny.

Wskazówka

Rozważ graf \displaystyle \overline{\mathbf{G}} w przypadku, gdyby \displaystyle \mathbf{G} nie był spójny, czyli posiadał co najmniej dwie spójne składowe.

Rozwiązanie

Zakładając, że \displaystyle \mathbf{G} nie jest spójny, czyli ma co najmniej dwie spójne składowe, pokażemy, że \displaystyle \overline{\mathbf{G}} jest spójny. Niech \displaystyle u,v\in{\sf V}\!\left(\overline{\mathbf{G}}\right)={\sf V}\!\left(\mathbf{G}\right) . Jeżeli \displaystyle u oraz \displaystyle v leżą w dwu różnych spójnych składowych grafu \displaystyle \mathbf{G} , to \displaystyle uv\not\in{\sf E}\!\left(\mathbf{G}\right) , czyli \displaystyle uv\in{\sf E}\!\left(\overline{\mathbf{G}}\right) . Niech więc \displaystyle u wraz z \displaystyle v leżą w tej samej spójnej składowej \displaystyle C grafu \displaystyle \mathbf{G} . Graf \displaystyle \mathbf{G} ma jednak przynajmniej jeszcze jedną spójną składową \displaystyle \emptyset\neq C'\neq C . Wtedy wierzchołek \displaystyle w\in C' nie jest sąsiadem (w \displaystyle \mathbf{G} ) ani \displaystyle u , ani \displaystyle v . A zatem, \displaystyle uw, vw \not\in {\sf E}\!\left(\mathbf{G}\right) , czyli \displaystyle uw, vw \in {\sf E}\!\left(\overline{\mathbf{G}}\right) . Wtedy \displaystyle u\to w\to v jest ścieżką między \displaystyle u i \displaystyle v w grafie \displaystyle \overline{\mathbf{G}} .

Ćwiczenie 2

Znajdź ośmiowierzchołkowy graf bez trójelementowych klik i czteroelementowych antyklik.

Wskazówka

Przeanalizuj wierzchołki ośmiokąta połączone bokami oraz przekątnymi łączącymi naprzeciwległe wierzchołki.

Rozwiązanie

<flash>file=Cw ramsey 8w.swf|width=250|height=150</flash>

Graf \displaystyle \mathbf{G}_1 oraz jego dopełnienie \displaystyle \overline{\mathbf{G}_1}

Graf \displaystyle \mathbf{G}_1 przedstawiony na rysunku spełnia warunki zadania.

Ćwiczenie 3

Pokaż, że dla \displaystyle k\in \mathbb{N} , istnieje \displaystyle n\in \mathbb{N} takie, że w dowolnym podziale zbioru liczb \displaystyle \left\lbrace 1,2,\ldots,n \right\rbrace na \displaystyle k podzbiorów, jest podzbiór zawierający liczy \displaystyle a,b,c spełniające \displaystyle a+b=c .

Wskazówka

Przetłumacz podział zbioru \displaystyle \left\lbrace 1,2,\ldots,n \right\rbrace na \displaystyle k podzbiorów, na podział rodziny \displaystyle \mathscr{P}_{2}\!\left( \left\lbrace 1,2,\ldots,n \right\rbrace \right) na \displaystyle k podrodzin i skorzystaj z Twierdzenia Ramseya 3.3.

Rozwiązanie

Niech \displaystyle \left\lbrace 1,2,\ldots,n \right\rbrace= V_1\cup V_2 \cup \ldots,V_k . W grafie pełnym \displaystyle \mathcal{K}_{n} o wierzchołkach \displaystyle 1,2,\ldots,n zdefiniujmy podział zbioru krawędzi \displaystyle {\sf E}\!\left(\mathcal{K}_{n}\right)=\mathscr{P}_{2}\!\left( \left\lbrace 1,2,\ldots,n \right\rbrace \right) na podzbiory \displaystyle E_1,E_2,\ldots,E_k\subseteq{\sf E}\!\left(\mathcal{K}_{n}\right) poprzez:


\displaystyle  ab\in E_i wtedy i tylko wtedy, gdy \displaystyle \left\vert a-b \right\vert\in V_i
.


Na mocy Twierdzenia Ramseya 3.3 otrzymujemy, że przy odpowiednio dużym \displaystyle n , istnieje taki zbiór \displaystyle \left\lbrace a,b,c \right\rbrace , którego krawędzie należą do któregoś \displaystyle E_i , czyli \displaystyle ab,bc,ac\in E_i . Bez straty ogólności załóżmy, że \displaystyle a>b>c . Wtedy, z definicji \displaystyle E_i , mamy:


\displaystyle \left( a-b \right),\ \left( b-c \right),\ \left( a-c \right)\ \in\ V_i,


i oczywiście


\displaystyle \left( a-b \right) + \left( b-c \right) = \left( a-c \right).


Ćwiczenie 4

Pokaż, że dla \displaystyle k -argumentowej liczby Ramseya \displaystyle {\sf R}\!\left( a_1,a_2,\ldots,a_k \right) zachodzi:


\displaystyle 2^k<{\sf R}\!\left( 3,3,\ldots,3 \right)\leq3k!.


Wskazówka

Zauważ że, szukana wartość \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right) to najmniejsza liczność grafu pełnego \displaystyle \mathcal{K}_{n} , w którym po dowolnym pomalowaniu krawędzi na \displaystyle k kolorów, istnieje trójkąt złożony z krawędzi tego samego koloru. W oszacowaniu od góry zastosuj indukcję po \displaystyle k . Rozważ dowolny wierzchołek \displaystyle v i najliczniejszy zbiór krawędzi oraz ich drugich końców incydentnych z \displaystyle v .

Rozwiązanie

  • \displaystyle 2^k<{\sf R}\!\left( 3,3,\ldots,3 \right)

Niech wierzchołkami kliki \displaystyle \mathcal{K}_{2^k} będą \displaystyle k -elementowe ciągi \displaystyle \left( a_1,a_2,\ldots,a_k \right) , gdzie \displaystyle a_i=0,1 . Pokolorujmy krawędzie \displaystyle \mathcal{K}_{2^k} na \displaystyle k kolorów w następujący sposób:

    • pierwszym kolorem pokolorujmy wszystkie krawędzie postaci

\displaystyle \left( \left( 0,a_2,\ldots,a_k \right)\left( 1,b_2,\ldots,b_k \right) \right)

    • drugim kolorem pokolorujmy wszystkie krawędzie postaci

\displaystyle \left( \left( 0,0,a_3,\ldots,a_k \right)\left( 0,1,b_3,\ldots,b_k \right) \right) oraz postaci
\displaystyle \left( \left( 1,0,a_3,\ldots,a_k \right)\left( 1,1,b_3,\ldots,b_k \right) \right)

    • i w ogólności, \displaystyle i -tym kolorem wszystkie krawędzie postaci

\displaystyle \left( \left( c_1,\ldots,c_{i-1},0,a_{i+1},\ldots,a_k \right)\left( c_1,\ldots,c_{i-1},1,b_{i+1},\ldots,b_k \right) \right)

Nietrudno zauważyć, że po usunięciu z grafu \displaystyle \mathcal{K}_{2^k} wszystkich krawędzi poza krawędziami o z góry ustalonym kolorze, otrzymujemy graf dwudzielny, a więc bez trójkątów. Graf \displaystyle \mathcal{K}_{2^k} wraz ze zdefiniowanym kolorowaniem świadczy więc, że \displaystyle k -argumentowa liczba Ramseya \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right) jest większa niż \displaystyle 2^k .

  • \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right)\leq3k!

Pokażemy, że dowolnie kolorując krawędzie grafu pełnego \displaystyle \mathcal{K}_{3k!} na \displaystyle k kolorów, znajdziemy trójkąt o krawędziach tego samego koloru. Dowód będzie przeprowadzony indukcyjnie ze względu na \displaystyle k . Dla \displaystyle k=1 nierówność jest oczywista. Rozważmy więc graf pełny \displaystyle \mathcal{K}_{3k!} , gdzie \displaystyle k>1 . Ponadto rozważmy dowolne kolorowanie krawędzi \displaystyle {\sf E}\!\left(\mathcal{K}_{3k!}\right) na \displaystyle k barw. Wierzchołek \displaystyle v\in{\sf V}\!\left(\mathcal{K}_{3k!}\right) jest incydentny z \displaystyle 3k!-1 krawędziami. Z Uogólnionej Zasady Szufladkowej otrzymujemy, że musi istnieć \displaystyle 3\left( k-1 \right)! krawędzi tego samego koloru, powiedzmy \displaystyle c , incydentnych z \displaystyle v . Niech \displaystyle V' będzie zbiorem wierzchołków połączonych z \displaystyle v za pomocą krawędzi o kolorze \displaystyle c . Jeśli dla jakichś dwu wierzchołków \displaystyle u,w \in V' krawędź \displaystyle uw ma kolor \displaystyle c , to trójkąt o wierzchołkach \displaystyle u,v,w jest monochromatyczny. Niech zatem kolorowanie krawędzi pomiędzy wierzchołkami z \displaystyle V' nie używa koloru \displaystyle c . Kolorowanie to używa więc tylko \displaystyle k-1 barw. Ponieważ \displaystyle \left\vert V' \right\vert\geq 3\left( k-1 \right)! , to założenie indukcyjne daje w \displaystyle V' trójkąt złożony z krawędzi o tym samym kolorze.

Ćwiczenie 5

Graf doskonały to graf \displaystyle \mathbf{G} posiadający maksymalną klikę o rozmiarze równym liczbie chromatycznej \displaystyle \chi\!\left( \mathbf{G} \right) . Oszacuj liczbę Ramseya \displaystyle {\sf R}\!\left( n,m \right) dla grafów doskonałych.

Wskazówka

Zbiór wierzchołków grafu \displaystyle \mathbf{G} jednego koloru tworzą antyklikę, więc liczba chromatyczna \displaystyle \chi\!\left( \mathbf{G} \right) jest liczbą antyklik, którymi można pokryć graf \displaystyle \mathbf{G} .

Rozwiązanie

Jednokolorowe wierzchołki grafu \displaystyle \mathbf{G} tworzą antyklikę, więc liczba chromatyczna \displaystyle \chi\!\left( \mathbf{G} \right) jest liczbą antyklik, którymi można pokryć graf \displaystyle \mathbf{G} . A zatem dla \displaystyle n=\chi\!\left( \mathbf{G} \right) istnieją parami rozłączne antykliki \displaystyle A_1, A_2, \ldots, A_n takie, że


\displaystyle {\sf V}\!\left(\mathbf{G}\right)=A_1\cup A_2\cup\ldots\cup A_n.


Oznaczając przez \displaystyle m rozmiar najliczniejszej antykliki w grafie \displaystyle \mathbf{G} otrzymujemy


\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq n\cdot m.


Graf \displaystyle \mathbf{G} jest doskonały, więc liczba chromatyczna \displaystyle \chi\!\left( \mathbf{G} \right)=n jest rozmiarem najliczniejszej kliki. A zatem graf doskonały, w którym kliki nie są liczniejsze niż \displaystyle n , a antykliki nie są liczniejsze niż \displaystyle m , ma co najwyżej \displaystyle n\cdot m wierzchołków. Graf doskonały o co najmniej \displaystyle n m+1 elementach musi więc mieć klikę \displaystyle n+1 elementową lub antyklikę \displaystyle m+1 elementową. A zatem:


\displaystyle {\sf R}\!\left( n,m \right)\leq\left( n-1 \right)\left( m-1 \right)+1=mn-n-m+2.


Ćwiczenie 6

Pokaż, że jeśli graf \displaystyle \mathbf{G} ma sześć wierzchołków, to on sam lub jego dopełnienie \displaystyle \overline{\mathbf{G}} ma czteroelementowy cykl. Czy o grafach pięcioelementowych da się powiedzieć to samo?

Wskazówka

Skorzystaj z faktu, że \displaystyle {\sf R}\!\left( 3,3 \right)=6 .

Rozwiązanie

<flash>file=Ramsey c4 1.swf|width=300|height=150</flash>

1. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}


<flash>file=Ramsey c4 3.swf|width=300|height=150</flash>

3. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}


<flash>file=Ramsey c4 5.swf|width=300|height=150</flash>

5. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}

<flash>file=Ramsey c4 2.swf|width=300|height=150</flash>

2. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}


<flash>file=Ramsey c4 4.swf|width=300|height=150</flash>

4. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}


<flash>file=Ramsey c4 pieciokat.swf|width=300|height=150</flash>

6. Grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}}

Załóżmy, że ani sześcioelementowy graf \displaystyle \mathbf{G} , ani jego dopełnienie nie zawiera czteroelementowego cyklu. Z drugiej strony, ponieważ \displaystyle {\sf R}\!\left( 3,3 \right)=6 , to \displaystyle \mathbf{G} lub \displaystyle \overline{\mathbf{G}} zawiera trójkąt. Bez straty ogólności załóżmy, że to \displaystyle \mathbf{G} zawiera trójkąt, powiedzmy \displaystyle \left\lbrace c,d,e \right\rbrace . Rysunek 1 przedstawia grafy \displaystyle \mathbf{G} oraz \displaystyle \overline{\mathbf{G}} , gdzie szarymi liniami zaznaczyliśmy naszą niewiedzę dotyczącą istnienia krawędzi.

Gdyby teraz któryś z wierzchołków \displaystyle a,b,f byłby połączony z co najmniej dwoma wierzchołkami ze zbioru \displaystyle \left\lbrace c,d,e \right\rbrace , to wraz z tymi wierzchołkami \displaystyle c,d,e tworzyłby czteroelementowy cykl. A zatem każdy z wierzchołków \displaystyle a,b,f ma co najwyżej jednego sąsiada w zbiorze \displaystyle \left\lbrace c,d,e \right\rbrace .Tym samym, w grafie \displaystyle \overline{\mathbf{G}} , każdy z wierzchołków \displaystyle a,b,f ma przynajmniej dwu sąsiadów w zbiorze \displaystyle \left\lbrace c,d,e \right\rbrace .Bez straty ogólności załóżmy, że to \displaystyle b sąsiaduje z \displaystyle d oraz \displaystyle e , jak przedstawiono na rysunku 2.

Aby uniknąć niepożądanego cyklu w \displaystyle \overline{\mathbf{G}} , wierzchołek \displaystyle a musi więc być sąsiedni z \displaystyle c oraz \displaystyle e , a wierzchołek \displaystyle f z \displaystyle c oraz \displaystyle d (patrz rysunek 3).

Analizując dalej graf \displaystyle \overline{\mathbf{G}} zauważamy, że nie może on mieć żadnej z krawędzi \displaystyle ef, ad, bc (patrz Rysunek 4).

Krawędzie te muszą więc być w grafie \displaystyle \mathbf{G} . Ale, ich istnienie zabrania krawędzi \displaystyle ab, af, bf w \displaystyle \mathbf{G} . Tym samym w grafie \displaystyle \overline{\mathbf{G}} mamy cykl

\displaystyle a\to b \to d \to f \to a,

jak na rysunku 5.

Pięcioelementowy graf \displaystyle \mathbf{H} taki, że ani on sam ani jego dopełnienie \displaystyle \overline{\mathbf{H}} nie ma czteroelementowego cyklu, jest przedstawiony na rysunku 6.