szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 sty 2010, o 14:25 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
Treść zadania : Niech d = ( a_{1} ,a_{2},...,a_{n} ) będzie ciągiem liczb naturalnych. Wykaż, że d jest ciągiem stopni wierzchołków pewnego drzewa o n wierzchołkach wtedy i tylko wtedy, gdy \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 n wierzchołkach ma n-1 krawędzi, ale wciąż nie wiem jak udowodnić, że suma stopni jest właśnie 2(n-1).

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

Ok, mam juz dowód \Rightarrow, ale nie wiem jak udowodnić w drugą stronę. Ktoś wie ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 17 sty 2010, o 20:19 
Użytkownik

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

Prawa strona zawsze prawdziwa to i lewa musi być prawdą. :)
Góra
Mężczyzna Offline
PostNapisane: 17 sty 2010, o 22:15 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
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ć?
Góra
Mężczyzna Offline
PostNapisane: 17 sty 2010, o 23:41 
Użytkownik
Avatar użytkownika

Posty: 4105
Lokalizacja: Poznań
QlaSzpiegula napisał(a):
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.

QlaSzpiegula napisał(a):
Ok, mam juz dowód =>, ale nie wiem jak udowodnić w drugą stronę. Ktoś wie ?

Czyli jak mniemam trzeba udowodnić coś takiego:
Niech d = (a_{1} ,a_{2},...,a_{n}) będzie ciągiem liczb naturalnych. Jeżeli w grafie o n wierzchołkach \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.
Góra
Mężczyzna Offline
PostNapisane: 1 lip 2017, o 20:35 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Inkwizytor napisał(a):
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 2(n - 1) przechodziłby, a dla niego nie istnieje drzewo.
Przyjmijmy dodatkowo, że n  \ge 2.

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

Dowód przez indukcję po n.
I krok. Ciąg ma długość n = 2, czyli jego suma to 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 n o sumie 2(n - 1) istnieje drzewo. Pokażemy, że istnieje drzewo dla dowolnego ciągu stopni o długości n + 1 i sumie 2n.
W tym ciągu długości n + 1 musi istnieć liczba równa 1. Wpp. gdyby wszystkie były \ge 2 to jego suma byłaby równa 2n + 2, sprzeczność.
W tym ciągu musi istnieć liczba \ge 2. Wpp. gdyby wszystkie były równe 1 to jego suma byłaby równa n + 1 < 2n, sprzeczność.
Usuwamy tą liczbę 1 z ciągu i zmniejszamy dowolny z elementów większych od 1 o 1. W ten sposób dostajemy ciąg spełniający warunki zadania długości n o sumie 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 1 (dokładamy nowy liść do drzewa). Dostajemy drzewo dla naszego ciągu, cnd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kombinatoryka i drzewa  niczeQ  1
 Teoria grafów - drzewa  Arecki123  1
 doskonały schemat eliminacji wierzchołków  nati10222  1
 Nieizomorficzne drzewa i ścieżka Eulera.  somas3k  1
 Liczba wierzchołków grafu jest podzielna - na wzór Eulera  Malina015  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl