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 ?
stopnie wierzchołków drzewa
-
- Użytkownik
- Posty: 4
- Rejestracja: 2 lis 2009, o 18:16
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
stopnie wierzchołków drzewa
Ostatnio zmieniony 1 lip 2017, o 22:43 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
-
- Użytkownik
- Posty: 2
- Rejestracja: 10 sty 2010, o 17:33
- Płeć: Mężczyzna
- Lokalizacja: Abc
stopnie wierzchołków drzewa
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ą.
\(\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ą.
-
- Użytkownik
- Posty: 4
- Rejestracja: 2 lis 2009, o 18:16
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
stopnie wierzchołków drzewa
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
- Użytkownik
- Posty: 4105
- Rejestracja: 16 maja 2009, o 15:08
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 1 raz
- Pomógł: 428 razy
stopnie wierzchołków drzewa
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.QlaSzpiegula pisze: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)
Czyli jak mniemam trzeba udowodnić coś takiego:QlaSzpiegula pisze: Ok, mam juz dowód =>, ale nie wiem jak udowodnić w drugą stronę. Ktoś wie ?
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.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
stopnie wierzchołków drzewa
Ten dowód to blef. Nie możemy założyć, że istnieje jakikolwiek graf o takiej sumie stopni. Musimy to pokazać.Inkwizytor pisze: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.
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.