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

Posty: 134
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.
Góra
Mężczyzna Offline
PostNapisane: 11 mar 2018, o 17:19 
Użytkownik

Posty: 1088
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 
 Teoria matematyka dyskretna.  dejna  0
 udowodnić problem, zasada szufladkowa  ewelina6382  3
 silny produkt grafów  ZychFryd  0
 [Teoria Grafów] Maksymalne cięcie w g. Petersena  karl153  0
 Suma grafów, składowe grafów.  snowjay  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl