Liczby Ramseya

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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

Spis treści

1 Definicja
2 Przykład
3 Wyznaczanie wartości Liczb Ramseya
4 Nieklasyczne liczby Ramseya
5 Linki zewnętrzne

[edytuj] Definicja

Liczbą Ramseya $R (q 1, q 2, q 3,..., q k)$ nazywamy najmniejszą liczbę $n$ taką, że dla dowolnego pokolorowania krawędziowego n-wierzchołkowego grafu pełnego istnieje takie $i$ , że istnieje w pokolorowanym grafie klika rozmiaru $q i$ w kolorze $i$ . Gdzie $k$ i $n$ należą do $N$ oraz $k\geq2$ .

[edytuj] Przykład

Dwukolorowanie krawędzi grafu K5 bez monochromatycznej kliki rozmiaru 3. Dowód, że R(3,3)>5.

Dwukolorowanie krawędzi grafu K₅ 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 albo 3 osoby które się nie znają.

[edytuj] 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.

[edytuj] 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.