uzycie grafow

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
agatarowerowicz
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 13 maja 2019, o 19:51
Płeć: Kobieta
Lokalizacja: Grudziądz

uzycie grafow

Post autor: agatarowerowicz » 13 maja 2019, o 19:54

Przy użyciu grafów pokazać, iż pośród grupy składającej się z 9 osób zawsze są takie trzy osoby, które znają się nawzajem lub takie cztery osoby, z których żadna nie zna trzech pozostałych.

Mruczek
Użytkownik
Użytkownik
Posty: 1110
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 155 razy

Re: uzycie grafow

Post autor: Mruczek » 18 maja 2019, o 20:41

Osoby to wierzchołki. Wierzchołki łączymy, jeżeli dwie osoby znają się nawzajem. Chcemy pokazać, że istnieje trójkąt lub zbiór niezależny wielkości co najmniej \(\displaystyle{ 4}\).
Jeżeli istnieje wierzchołek A stopnia co najmniej \(\displaystyle{ 4}\) to rozpatrujemy jego sąsiadów. Jeżeli wśród nich co najmniej dwa są połączone, to tworzą trójkąt z A i koniec. Wpp. wsród sąsiadów A żadne dwa nie są połączone krawędzią i tworzą one zbiór niezależny wielkości \(\displaystyle{ 4}\), koniec.
Jeżeli istnieje wierzchołek B o stopniu co najwyżej \(\displaystyle{ 2}\) to nie jest połączony z co najmniej \(\displaystyle{ 6}\) pozostałymi. Znanym faktem jest, że w grafie o \(\displaystyle{ 6}\) wierzchołkach są trzy tworzące trójkąt lub trzy tworzące zbiór niezależny. Jeżeli jest tam zbiór niezależny wielkości co najmniej \(\displaystyle{ 3}\) to razem z B tworzą zbiór niezależny wielkości co najmniej \(\displaystyle{ 4}\).
W pozostałych przypadkach każdy z wierzchołków ma stopień co najwyżej \(\displaystyle{ 3}\) i co najmniej \(\displaystyle{ 3}\), czyli dokładnie \(\displaystyle{ 3}\). Wierzchołków jest \(\displaystyle{ 9}\), więc suma stopni w tym grafie to \(\displaystyle{ 27}\), ale suma stopni zawsze jest parzysta (znany fakt), czyli sprzeczność, cnd.

ODPOWIEDZ