Twierdzenie Ramseya – twierdzenie matematyczne dotyczące teorii grafów, a w szczególności tematu kolorowania krawędziowego grafów pełnych.
Zostało ono udowodnione przez angielskiego matematyka i filozofa, Franka Ramseya.
Przedstawienie graficzne Narysujmy sobie na płaszczyźnie punktów i połączmy je na zasadzie każdy z każdym, przy użyciu zestawu dokładnie dwóch kolorów. Wtedy, będziemy chcieli przyjmować następującą konwencję nazewniczą (definicję):
Liczbę będziemy nazywać -tą liczbą Ramseya, wtedy i tylko wtedy, gdy prawdą będzie (dla powyższej sytuacji), że na takim właśnie grafie pełnym (jaki to powstał nam w wyniku opisanego w powyższym akapicie, rysowania) będziemy w stanie wtedy znaleźć jednokolorową klikę, o dokładnie wierzchołkach (por. także: poniżej, Liczby Ramseya).
Liczby Ramseya mały|Dwukolorowanie krawędzi grafu K5 bez monochromatycznej kliki rozmiaru 3. Dowód, że
Definicja Liczbą Ramseya ozn. , dla i , nazywamy najmniejszą liczbę , taką (jednocześnie) że: dla dowolnego -pokolorowania krawędziowego dla -wierzchołkowego grafu pełnego; istnieje , spełniające nierówność: , oraz takie, że w pokolorowanym grafie jest klika rozmiaru , której wszystkie krawędzie są w kolorze .
Przykład Aby znaleźć na przykład wartość liczby Ramseya , 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 prawdziwa jest w istocie równość: .
Dowód powyższej równości:
Dowód równości przeprowadzimy przez pokazanie poszczególnie, zachodzenia dwóch nierówności:
Dowód koniunkcji zachodzenia dwóch powyższych nierówności, w naturalny sposób pozwoli nam wnioskować o tym, że musi być nawet, dokładnie: .
Najpierw, przedstawimy dowód dla pierwszej z tych nierówności. Wybierzmy dowolny punkt grafu pełnego o sześciu wierzchołkach. Wychodzi z niego pięć krawędzi, więc przynajmniej trzy mają wspólny kolor. Załóżmy bez utraty ogólności, że są to trzy czerwone krawędzie (sytuacje te charakteryzują się pełną symetrią). Krawędzie te prowadzą do trzech różnych punktów; te trzy nowe punkty są połączone między sobą trzema krawędziami. Jeżeli choć jedna z nowych krawędzi jest czerwona, powstaje czerwony trójkąt, w przeciwnym przypadku powstaje niebieski trójkąt. Wobec tego wartość liczby Ramseya , nie może być większa od liczby 6.
Rysunek po lewej dowodzi, że nie może być równe 5 ani mniejsze, więc istotnie jest równe 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 wyznaczanie kolejnych wartości liczb Ramseya, jest w istocie 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 Greenwood i Gleason, 1955 Greenwood i Gleason, 1955 Greenwood i Gleason, 1955 Greenwood i Gleason, 1955 Kery, 1964 Kalbfleich, 1966 Graver i Yachel, 1968 McKay i Zhang Ke Min, 1992 McKay i Radziszowski, 1995 Greenwood i Gleason, 1955 Codish, Frank, Itzhakov i Miller, 2016 (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości) (nie wyznaczono dokładnej wartości)
źródło: Optymalizacja dyskretna, modele i metody kolorowania grafów, pod redakcją Marka Kubale, WNT 2002.
Algorytm kwantowy W roku 2011 zaproponowany został kwantowy algorytm obliczania dwukolorowych liczb Ramseya . Algorytm został następnie użyty eksperymentalnie do wyliczenia następujących liczb Ramseya:
używając przy tym komputera kwantowego o 84 kubitach. Minimalna liczba kubitów niezbędna do wyliczenia dwukolorowej liczby Ramseya wynosi gdzie jest wartością wyliczanej liczby. Zaproponowany algorytm kwantowy sprawdza, czy dla danej liczby wierzchołków wszystkie grafy mają własność podaną w definicji. Dla znalezienia określonej liczby Ramseya, algorytm uruchamiany jest kolejno dla coraz większych ; zaś samą szukaną wartością jest wówczas najniższe dla którego zwróci on odpowiedź pozytywną.
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ż Teoria grafów Kolorowanie krawędzi Liczba Grahama
Uwagi
Przypisy
Bibliografia Magazyn Miłośników Matematyki 3/2008.
Linki zewnętrzne
Ramseya