Wikipedia

Twierdzenie Ramseya: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m lit.
+ integruj
Linia 1:
{{integruj|Liczby Ramseya}}
'''Klasyczne liczby Ramseya''' związane są z [[kolorowanie krawędzi|kolorowaniem krawędzi]] [[graf pełny|grafu pełnego]]:
== Treść twierdzenia ==
Dla każdej liczby naturalnej ''k'' istnieje taka liczba naturalna ''n'', że wśród dowolnych ''n'' osób zawsze znajdziemy ''k'' osób, które znają się z każda z każdą, lub ''k'' osób, które nie znają się.
Wtedy ''n''=R(''k'') i jest ''k''-tą [[liczba Ramseya|liczbą Ramseya]].
== Przedstawienie graficzne ==
Jeśli narysujemy ''n'' punktów i połączymy je każdy z każdym dwoma kolorami, to ''n'' jest ''k''-tą liczbą Ramseya wtedy i tylko wtedy, gdy ''n'' jest najmniejszą liczbą taką, że na takim [[graf pełny|grafie pełnym]] znajdziemy jednokolorową klikę o ''k'' wierzchołkach.
== Przykłady ==
* R(2)=2
* R(3)=6
* R(4)=18
* 43≤R(5)≤49
* 102≤R(6)≤165
* 205≤R(7)≤540
* 282≤R(8)≤1870
Źródło:[[Magazyn Miłośników Matematyki|"mmm"]] nr 3/2008
 
== DefinicjaZobacz też ==
[[liczby Ramseya|uogólnienie liczb Ramseya]]
Liczbą Ramseya <math> R (q_1, q_2, q_3, \ldots, q_k ) </math> dla <math>k, q_1, q_2, \ldots, q_k \in N</math> i <math>k \geqslant 2</math> nazywamy najmniejszą liczbę <math>n</math>, taką że dla dowolnego [[kolorowanie krawędzi|''k''-pokolorowania krawędziowego]] ''n''-wierzchołkowego [[graf pełny|grafu pełnego]]
dla pewnego ''i'', <math>1 \leqslant i \leqslant k</math>, w pokolorowanym grafie istnieje [[klika (teoria grafów)|klika]] rozmiaru <math>q_i</math>, której wszystkie krawędzie są w kolorze <math>i</math>.
 
== Przykład ==
[[Plik:RamseyTheory K5 no mono K3.PNG|right|frame|Dwukolorowanie krawędzi grafu K<sub>5</sub> bez monochromatycznej kliki rozmiaru 3. Dowód, że R(3,3)>5.]]
Aby znaleźć np. wartość R(3,3), kolorujemy krawędzie grafów pełnych dwoma kolorami (np. czerwonym i niebieskim), szukając najmniejszego grafu pełnego, dla którego przy dowolnym kolorowaniu znajdziemy albo trójkąt czerwony, albo trójkąt niebieski. Okazuje się, że R(3,3)=6. Ma to bardzo wygodną interpretację, mianowicie, w zbiorze 6 osób zawsze znajdziemy 3 osoby znające się wzajemnie lub 3 osoby, które się nie znają.
 
== Wyznaczanie wartości liczb Ramseya ==
Okazuje się, że wyznaczenie wartości liczb Ramseya jest bardzo trudnym obliczeniowo zadaniem. Często mamy do dyspozycji bardzo dokładne ich oszacowania, a nie jesteśmy w stanie określić ich wartości, mimo że nie są to wielkie liczby. Poniżej dotychczasowe osiągnięcia w tej dziedzinie:
 
{| class="wikitable"
!Liczba!!Wartość!!Odkrywca, rok
|-
|R(3,3)||6||Greenwood i Gleason, 1955
|-
|R(3,4)||9||Greenwood i Gleason, 1955
|-
|R(3,5)||14||Greenwood i Gleason, 1955
|-
|R(4,4)||18||Greenwood i Gleason, 1955
|-
|R(3,6)||18||Kery, 1964
|-
|R(3,7)||23||Kalbfleich, 1966
|-
|R(3,8)||28||Graver i Yachel, 1968
|-
|R(3,9)||36||McKay i Zhang Ke Min, 1992
|-
|R(4,5)||25||McKay i [[Stanisław Radziszowski|Radziszowski]], 1995
|-
|R(3,3,3)||17||
|-
|colspan="2"|<math>30 \leqslant R(3,3,4) \leqslant 31</math>||(nie wyznaczono dokładnej wartości)
|-
|colspan="2"|<math>51 \leqslant R(3,3,3,3) \leqslant 62</math>||jw.
|-
|colspan="2"|<math>43 \leqslant R(5,5) \leqslant 49</math>||jw.
|-
|colspan="2"|<math>109 \leqslant R(6,6) \leqslant 165</math>||jw.
|-
|colspan="2"|<math>205 \leqslant R(7,7) \leqslant 540</math>||jw.
|-
|colspan="2"|<math>282 \leqslant R(8,8) \leqslant 1870</math>||jw.
|-
|colspan="2"|<math>565 \leqslant R(9,9) \leqslant 6588</math>||jw.
|-
|colspan="2"|<math>798 \leqslant R(10,10) \leqslant 23581</math>||jw.
|}
 
''źródło: "Optymalizacja dyskretna, modele i metody kolorowania grafów." pod redakcją [[Marek Kubale|Marka Kubale]], WNT 2002''.
 
== Nieklasyczne liczby Ramseya ==
Klasyczne liczby Ramseya zdefiniowane są za pomocą kolorowania grafów pełnych, w których poszukujemy monochromatycznych klik (czyli podgrafów pełnych). Pojęcie można jednak uogólnić na poszukiwania dowolnych podgrafów monochromatycznych.
 
Zobacz też: [[kolorowanie krawędzi]].
 
== Linki zewnętrzne ==
* [http://www.combinatorics.org/Surveys/ds1/sur.pdf Small Ramsey numbers] Praca przeglądowa Stanisława Radziszowskiego
 
[[Kategoria:Teoria grafów]]
[[Kategoria:Twierdzenia matematyczne|Ramseya]]
 
[[de:Satz von Ramsey]]
[[en:Ramsey's theorem]]
[[ko:램지의 정리]]
[[he:משפט רמזי]]
[[hu:Ramsey-tétel]]
[[ja:ラムゼーの定理]]
[[ta:ராம்ஸே தேற்றம்]]
[[th:จำนวนแรมซีย์]]
[[zh:拉姆齐定理]]
Źródło: „https://pl.wikipedia.org/wiki/Twierdzenie_Ramseya”