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

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

Posty: 1091
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 grafów: Wielomian chromatyczny grafu  slodky  1
 Zasada szufladkowa - turniej  contact  3
 Zasada szufladkowa podciąg monotoniczny  joasia317  1
 Ciągi liczb wierchołków kolejnych stopni grafów?  Sonite  0
 produkt grafów doskonały  niebieska_biedronka  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl