stopnie wierzchołków drzewa

[QlaSzpiegula]

Treść zadania : Niech \(\displaystyle{ d = ( a_{1} ,a_{2},...,a_{n} )}\) będzie ciągiem liczb naturalnych. Wykaż, że \(\displaystyle{ d}\) jest ciągiem stopni wierzchołków pewnego drzewa o \(\displaystyle{ n}\) wierzchołkach wtedy i tylko wtedy, gdy \(\displaystyle{ \sum_{i=1}^{n} d_{i} = 2(n-1)}\).
Proszę o rozw, bądź wskazówkę.

-- 17 sty 2010, o 16:51 --

Wiem, że drzewo to graf nieskierowany, spójny, bez cykli, i że drzewo o \(\displaystyle{ n}\) wierzchołkach ma \(\displaystyle{ n-1}\) krawędzi, ale wciąż nie wiem jak udowodnić, że suma stopni jest właśnie \(\displaystyle{ 2(n-1)}\).

-- 17 sty 2010, o 17:10 --

Ok, mam juz dowód \(\displaystyle{ \Rightarrow}\), ale nie wiem jak udowodnić w drugą stronę. Ktoś wie ?

[adriano321]

Ja to bym zrobił coś takiego.
\(\displaystyle{ \sum_{i=0}^{n}di=2(n-1)}\)
\(\displaystyle{ \sum_{i=0}^{n}di = 2|E(G)|}\) -> korzystając z lematu o uściskach dłoni
\(\displaystyle{ n-1 = |E(G)|}\) -> prawda korzystając z twierdzeń o drzewach
(Ciag ( \(\displaystyle{ a_{1} ,...,a_{n}}\)) jest ciągiem stopni wierzchołków) \(\displaystyle{ \Leftrightarrow \sum_{i=0}^{n}di=2(n-1)}\)

Prawa strona zawsze prawdziwa to i lewa musi być prawdą.

[QlaSzpiegula]

a to nie jest tak, że nie musi być, że skoro prawa strona jest zawsze prawdą, to lewa też, bo nie możemy chyba skorzystać z tej równoważności, bo ją właśnie trzeba udowodnić?

[Inkwizytor]

Wiem, że drzewo to graf nieskierowany, spójny, bez cykli, i że drzewo o n wierzchołkach ma n-1 krawędzi, ale wciąż nie wiem jak udowodnić, że suma stopni jest właśnie 2(n-1)

Każda krawędź ma 2 końca, więc każda dodana krawędź w grafie generuje +2 do sumy stopni. Patrz macierz incydencji w grafie nieskierowanym. Sumowanie po wierszach i kolumnach.

Ok, mam juz dowód =>, ale nie wiem jak udowodnić w drugą stronę. Ktoś wie ?

Czyli jak mniemam trzeba udowodnić coś takiego:
Niech d = (\(\displaystyle{ a_{1} ,a_{2},...,a_{n}}\)) będzie ciągiem liczb naturalnych. Jeżeli w grafie o n wierzchołkach \(\displaystyle{ \sum_{i=1}^{n} d_{i} = 2(n-1) \Rightarrow}\) d jest ciągiem stopni wierzchołków pewnego drzewa o n wierzchołkach.

Dowód "nie wprost"
Załóżmy że suma stopni jest taka jak podana, graf jest spójny, ale nie jest drzewem.
Jeżeli nie jest drzewem to istnieje przynajmniej jeden cykl. Jeżeli istnieje cykl to możemy wyrzucic przynajmniej jedną krawędź i nadal mieć nadal graf spójny. Powstaje nowy graf G' o n wierzchołkach, ale o sumie stopni 2(n-2). Ale taka suma stopni powoduje, że mamy tylko n-2 krawędzie. A żeby połączyć n wierzchołków w graf spójny potrzebujemy n-1 krawędzi. Czyli rozspójniliśmy nasz graf. Jest to sprzeczność. Czyli graf spójny o n wierzchołkach i n-1 krawędziach nie może mieć cyklu.

p.s. Piszę z pamięci, więc jeśli pominąłem jakiś istotny element to z góry przepraszam, ale jestem pewien, że trzeba iść tym tropem.

[Mruczek]

Dowód "nie wprost"
Załóżmy że suma stopni jest taka jak podana, graf jest spójny, ale nie jest drzewem.
Jeżeli nie jest drzewem to istnieje przynajmniej jeden cykl. Jeżeli istnieje cykl to możemy wyrzucic przynajmniej jedną krawędź i nadal mieć nadal graf spójny. Powstaje nowy graf G' o n wierzchołkach, ale o sumie stopni 2(n-2). Ale taka suma stopni powoduje, że mamy tylko n-2 krawędzie. A żeby połączyć n wierzchołków w graf spójny potrzebujemy n-1 krawędzi. Czyli rozspójniliśmy nasz graf. Jest to sprzeczność. Czyli graf spójny o n wierzchołkach i n-1 krawędziach nie może mieć cyklu.

Ten dowód to blef. Nie możemy założyć, że istnieje jakikolwiek graf o takiej sumie stopni. Musimy to pokazać.

W treści zadania trzeba założyć dodatkowo, że liczby ciągu są całkowite dodatnie. Bez tego założenia ciąg składający się z samych zer i jednej liczby \(\displaystyle{ 2(n - 1)}\) przechodziłby, a dla niego nie istnieje drzewo.
Przyjmijmy dodatkowo, że \(\displaystyle{ n \ge 2}\).

Dowód implikacji w prawo jest prosty, implikacja w lewo:

Dowód przez indukcję po \(\displaystyle{ n}\).
I krok. Ciąg ma długość \(\displaystyle{ n = 2}\), czyli jego suma to \(\displaystyle{ 2}\). Ten graf składa się z jednej krawędzi, oczywiście jest drzewem.
II krok. Zał, że dla dowolnego ciągu stopni długości \(\displaystyle{ n}\) o sumie \(\displaystyle{ 2(n - 1)}\) istnieje drzewo. Pokażemy, że istnieje drzewo dla dowolnego ciągu stopni o długości \(\displaystyle{ n + 1}\) i sumie \(\displaystyle{ 2n}\).
W tym ciągu długości \(\displaystyle{ n + 1}\) musi istnieć liczba równa \(\displaystyle{ 1}\). Wpp. gdyby wszystkie były \(\displaystyle{ \ge 2}\) to jego suma byłaby równa \(\displaystyle{ 2n + 2}\), sprzeczność.
W tym ciągu musi istnieć liczba \(\displaystyle{ \ge 2}\). Wpp. gdyby wszystkie były równe \(\displaystyle{ 1}\) to jego suma byłaby równa \(\displaystyle{ n + 1 < 2n}\), sprzeczność.
Usuwamy tą liczbę \(\displaystyle{ 1}\) z ciągu i zmniejszamy dowolny z elementów większych od \(\displaystyle{ 1}\) o \(\displaystyle{ 1}\). W ten sposób dostajemy ciąg spełniający warunki zadania długości \(\displaystyle{ n}\) o sumie \(\displaystyle{ 2(n - 1)}\). Z założenia indukcyjnego tworzymy dla niego drzewo, dokładamy do niego wierzchołek i łączymy go z tym któremu zmniejszyliśmy wartość o \(\displaystyle{ 1}\) (dokładamy nowy liść do drzewa). Dostajemy drzewo dla naszego ciągu, cnd.