szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 mar 2018, o 11:58 
Użytkownik

Posty: 130
Pokaż, że istnieje taka grupa pięciu osób, w której nie ma ani trzech osób znających się
nawzajem, ani trzech osób takich, że żadna z nich nie zna dwóch pozostałych.

Jak na razie doszedłem do tego, że 1 \le deg(v) \le 2 dla każdego wierzchołka (graf musi być spójny i żaden wierzchołek nie może mieć co najmniej 3 krawędzi, bo wtedy nie byłyby spełnione 2 warunki zadania jednocześnie. Natomiast rysowałem ten graf na milion sposobów i nie mogłem znaleźć takiego, który spełnia to, do czego doszedłem i warunków zadania.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 11 mar 2018, o 18:19 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
Masz poprawne obserwacje.

Weź cykl składający się z 5 wierzchołków. Nie zawiera on trójkątów (oczywiste). Nie zawiera też zbioru niezależnego składającego się z 3 wierzchołków. Można to pokazać rozpatrując wszystkie przypadki, albo w ten sposób:
Przypuśćmy, nie wprost, że zawiera taki zbiór niezależny. Niech bso. wierzchołek A do niego należy, wtedy żaden z jego sąsiadów B i C do niego nie należy, czyli musiałyby do niego należeć dwa pozostałe wierzchołki tego cyklu, czyli D i E, ale one są połączone krawędzią, sprzeczność.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zasada wlaczen i wylaczen - zadanie 2  leszczu450  6
 Zasada szufladkowa Dirichleta - zadanie 31  justdzo  2
 Zadasa Szufladkowa Dirichleta, dowód rozwinięcia dziesiętne  choko  6
 Zasada wlaczania i wylaczania - zadanie 3  Carlj28  2
 [Teoria grup] rozsadzenia wokół stołu  matinf  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl