Czytaj więcej"/> Drukuj

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

Przykłady

Źródło:"mmm" nr 3/2008
Materiał wydrukowany z portalu zgapa.pl dnia 2020-07-06 01:36:25