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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

Ćwiczenie 1

Wykaż, że dla dowolnego grafu , co najmniej jeden z grafów , jest spójny.

Wskazówka
Rozwiązanie

Ćwiczenie 2

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

Wskazówka
Rozwiązanie

Ćwiczenie 3

Pokaż, że dla , istnieje takie, że w dowolnym podziale zbioru liczb na podzbiorów, jest podzbiór zawierający liczy spełniające .

Wskazówka
Rozwiązanie

Ćwiczenie 4

Pokaż, że dla -argumentowej liczby Ramseya zachodzi:



Wskazówka
Rozwiązanie

Ćwiczenie 5

Graf doskonały to graf posiadający maksymalną klikę o rozmiarze równym liczbie chromatycznej . Oszacuj liczbę Ramseya dla grafów doskonałych.

Wskazówka
Rozwiązanie

Ćwiczenie 6

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

Wskazówka
Rozwiązanie


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

<div.thumbcaption>5. Grafy oraz

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

<div.thumbcaption>2. Grafy oraz


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

<div.thumbcaption>4. Grafy oraz


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

<div.thumbcaption>6. Grafy oraz

Załóżmy, że ani sześcioelementowy graf , ani jego dopełnienie nie zawiera czteroelementowego cyklu. Z drugiej strony, ponieważ , to lub zawiera trójkąt. Bez straty ogólności załóżmy, że to zawiera trójkąt, powiedzmy . Rysunek 1 przedstawia grafy oraz , gdzie szarymi liniami zaznaczyliśmy naszą niewiedzę dotyczącą istnienia krawędzi.

Gdyby teraz któryś z wierzchołków byłby połączony z co najmniej dwoma wierzchołkami ze zbioru , to wraz z tymi wierzchołkami tworzyłby czteroelementowy cykl. A zatem każdy z wierzchołków ma co najwyżej jednego sąsiada w zbiorze .Tym samym, w grafie , każdy z wierzchołków ma przynajmniej dwu sąsiadów w zbiorze .Bez straty ogólności załóżmy, że to sąsiaduje z oraz , jak przedstawiono na rysunku 2.

Aby uniknąć niepożądanego cyklu w , wierzchołek musi więc być sąsiedni z oraz , a wierzchołek z oraz (patrz rysunek 3).

Analizując dalej graf zauważamy, że nie może on mieć żadnej z krawędzi (patrz Rysunek 4).

Krawędzie te muszą więc być w grafie . Ale, ich istnienie zabrania krawędzi w . Tym samym w grafie mamy cykl

jak na rysunku 5.

Pięcioelementowy graf taki, że ani on sam ani jego dopełnienie nie ma czteroelementowego cyklu, jest przedstawiony na rysunku 6.