Wolna encyklopedia

Klasyczne Liczby Ramseya związane są z kolorowaniem krawędzi grafu pełnego:

Spis treści

Definicja

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 \geq 2 nazywamy najmniejszą liczbę n taką, że dla dowolnego k-pokolorowania krawędziowego n-wierzchołkowego grafu pełnego dla pewnego i, 1 \leq i \leq k, w pokolorowanym grafie istnieje klika rozmiaru qi, której wszystkie krawędzie są w kolorze i.

Przykład

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

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 dokładnie 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
30 \leq R(3,3,4) \leq 31 (nie wyznaczono dokładnej wartości)
51 \leq R(3,3,3,3) \leq 62 jw.
43 \leq R(5,5) \leq 49 jw.
109 \leq R(6,6) \leq 165 jw.
205 \leq R(7,7) \leq 540 jw.
282 \leq R(8,8) \leq 1870 jw.
565 \leq R(9,9) \leq 6588 jw.
798 \leq R(10,10) \leq 23581 jw.

źródło: "Optymalizacja dyskretna, modele i metody kolorowania grafów." pod redakcją 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

Źródło: „haslo,Liczby_Ramseya”