szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 mar 2017, o 00:36 
Użytkownik

Posty: 2
Graf prosty o 21 wierzchołkach. Dla dowolnej pary wierzchołków x, y zachodzi warunek d(x)+d(y) \ge 20. Czy graf jest spójny?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 mar 2017, o 14:17 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
Załóżmy, że nie jest spójny. To znaczy, że ma przynajmniej dwie spójne składowe. Któraś ze spójnych musi zawierać co najwyżej 10 wierzchołków. Jeżeli jest wśród nich spójna wielkości 1 to bierzemy wierzchołek z tej spójnej i dowolny inny (który ma co najwyżej 19 sąsiadów) - wtedy d(x) + d(y)  \le  0 + 19 = 19, sprzeczność. Wpp. istnieje spójna, która ma więcej niż 1 i nie więcej niż 10 wierzchołków. Weźmy dowolne dwa wierzchołki z tej spójnej - wtedy d(x) + d(y)  \le 9 + 9 = 18 - stopień każdego z tych wierzchołków nie może przekraczać wielkości spójnej minus 1, czyli 9, sprzeczność.

To znaczy, że jest spójny.
Góra
Mężczyzna Offline
PostNapisane: 26 mar 2017, o 15:18 
Użytkownik

Posty: 2
Dlaczego, ktoras ze spojnych musi zawierac co najwyzej 10 wierzcholkow?
Góra
PostNapisane: 26 mar 2017, o 15:30 
Użytkownik
alto de aitana napisał(a):
Dlaczego, ktoras ze spojnych musi zawierac co najwyzej 10 wierzcholkow?


No bo masz 21 wierzchołków. Czyli jak jedna ma 15 wierzchołków to kolejna ma co najwyżej 10 itd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Spójność grafu - zadanie 4  piotrekgym  1
 Spójność grafu  Arst  0
 Spójność grafu - zadanie 2  Paragon16  1
 Spójność grafu - zadanie 3  Annoyer13  1
 Ściany grafu  Gui  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl