szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 mar 2017, o 20:56 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Witam,
treść mojego zadania przedstawia się następująco.

Niech k > 1 będzie liczbą naturalną. Wykaż, że każde niepuste n-wierzchołkowe drzewo posiada co najmniej n - \frac{n-2}{k-1} wierzchołków stopnia mniejszego niż k.

Jakieś wskazówki co do rozwiązania tego zadania?
Pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 22 mar 2017, o 23:17 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Załóżmy nie wprost, że graf ma mniej niż n - \frac{n-2}{k-1} wierzchołków stopnia mniejszego niż k. To znaczy, że ten graf ma więcej niż \frac{n - 2}{k - 1} wierzchołków stopnia nie mniejszego niż k.
Załóżmy, że ma \frac{n - 2}{k - 1} + a wierzchołków stopnia nie mniejszego niż k, gdzie a > 0. Pozostałe n -  \frac{n - 2}{k - 1} - a wierzchołków ma stopień mniejszy niż k, ale równy co najmniej 1.
Drzewo o n wierzchołkach ma n - 1 krawędzi, czyli suma stopni wierzchołków to 2n - 2. Policzmy sumę stopni wierzchołków tego drzewa - jest ona nie mniejsza niż:
\left( \frac{n - 2}{k - 1} + a \right)  \cdot k + \left( n - \frac{n - 2}{k - 1} - a\right)   \cdot  1 = 2n - 2 + ak - a
2n - 2  \ge 2n - 2 + ak - a
a(k - 1)  \le  0
k > 1, czyli a  \le  0, sprzeczność, cnd.
Góra
Mężczyzna Offline
PostNapisane: 23 mar 2017, o 00:07 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Dzięki wielkie! Dedukcja jak najbardziej w porządku, wyhaczyłem tylko jeden błąd. W wyrażeniu:
\left( \frac{n - 2}{k - 1} + a \right)  \cdot k + n -  \left( \frac{n - 2}{k - 1} - a\right)   \cdot  1 = 2n - 2 + ak - a

Powinno być n -  \left( \frac{n - 2}{k - 1} + a\right) zamiast n -  \left( \frac{n - 2}{k - 1} - a\right)

Zimne piwko dla Ciebie!
Pozdrawiam
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 rekurencja drzewa  Liar  0
 Drzewa ukorzenione  Elminster1-11  0
 Drzewa spinające grafu połączonego krawędzią z cyklem  iks2011  0
 Drzewa zadania  somas3k  2
 Na ile sposobów można wysadzić drzewa??  kasia2303  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl