Twierdzenie Ramseya

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Liczby Ramseya)
Skocz do: nawigacji, wyszukiwania

Twierdzenie Ramseya – twierdzenie matematyczne, dotyczące teorii grafów, udowodnione przez F. Ramseya.

Treść twierdzenia[edytuj | edytuj kod]

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ę żadna z żadną. Wtedy n=R(k) i jest k-tą liczbą Ramseya.

Przedstawienie graficzne[edytuj | edytuj kod]

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 grafie pełnym znajdziemy jednokolorową klikę o k wierzchołkach.

Liczby Ramseya[edytuj | edytuj kod]

Definicja[edytuj | edytuj kod]

Liczbą Ramseya  R (q_1, q_2, q_3, \ldots, q_k ) dla k, q_1, q_2, \ldots, q_k \in N i k \geqslant 2 nazywamy najmniejszą liczbę n, taką że dla dowolnego k-pokolorowania krawędziowego n-wierzchołkowego grafu pełnego istnieje i, 1 \leqslant i \leqslant k, takie, że w pokolorowanym grafie jest klika rozmiaru q_i, której wszystkie krawędzie są w kolorze i.

Przykład[edytuj | edytuj kod]

Dwukolorowanie krawędzi grafu K5 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[edytuj | edytuj kod]

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:

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 Radziszowski, 1995
R(3,3,3) 17 Greenwood i Gleason, 1955
30 \leqslant R(3,3,4) \leqslant 31 (nie wyznaczono dokładnej wartości)
51 \leqslant R(3,3,3,3) \leqslant 62 jw.
43 \leqslant R(5,5) \leqslant 49 jw.
102 \leqslant R(6,6) \leqslant 165 jw.
205 \leqslant R(7,7) \leqslant 540 jw.
282 \leqslant R(8,8) \leqslant 1870 jw.
565 \leqslant R(9,9) \leqslant 6588 jw.
798 \leqslant R(10,10) \leqslant 23556 jw.

źródło: "Optymalizacja dyskretna, modele i metody kolorowania grafów." pod redakcją Marka Kubale, WNT 2002.

Algorytm kwantowy[edytuj | edytuj kod]

W roku 2011 zaproponowany został kwantowy algorytm obliczania dwukolorowych liczb Ramseya R(m,n)[1]. Algorytm został następnie użyty eksperymentalnie do wyliczenia liczb R(2,4), R(2,5), R(2,6), R(2,7), R(2,8) i R(3,3) używając komputera kwantowego o 84 kubitach[2]. Minimalna liczba kubitów niezbędna do wyliczenia dwukolorowej liczby Ramseya wynosi N(N-1)/2 gdzie N jest wartością wyliczanej liczby[1]. Zaproponowany algorytm kwantowy sprawdza, czy dla danej liczby wierzchołków wszystkie grafy mają własność podaną w definicji. Dla znalezienia liczby Ramseya algorytm uruchamiany jest kolejno dla coraz większych N, szukaną wartością R(m,n) jest najniższe N dla którego zwróci on odpowiedź pozytywną.

Nieklasyczne liczby Ramseya[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 Frank Gaitan, Lane Clark. Ramsey numbers and adiabatic quantum computing. „Phys. Rev. Lett.”. 108, s. 010501, 2012. doi:10.1103/PhysRevLett.108.010501.  arXiv:1103.1345 (ang.)
  2. ZhengBing Bian, Fabian Chudak, Wiliam G. Macready, Frank Gaitan i inni. Experimental determination of Ramsey numbers with quantum annealing. , 2012.  arXiv:1201.1842 (ang.)

Bibliografia[edytuj | edytuj kod]

  • "mmm" nr 3/2008
  • Tomasz Bartnicki. Czy 11 jest największą liczbą na świecie?. „Matematyka Społeczeństwo Nauczanie”. 39, s. 33, 34, styczeń 2007.