szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 cze 2013, o 00:35 
Gość Specjalny
Avatar użytkownika

Posty: 4435
Lokalizacja: Toruń
Cześć : )

Potrzebuję Waszej pomocy odnośnie dowodu faktu, iż każde drzewo(acykliczny spójny graf) posiada co najmniej dwa liście(wierzchołki stopnia jeden).

Z góry dziękuję za pomoc : )
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
PostNapisane: 10 cze 2013, o 09:42 
Użytkownik
Wujka google pytales?
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2013, o 09:55 
Gość Specjalny
Avatar użytkownika

Posty: 4435
Lokalizacja: Toruń
miodzio1988, pytałem, ale albo wychodzą głupoty niezwiązane z teorią grafów albo po prostu definicje. Znalazłem jeden dowód w książce. Bardzo krótki. Ale go nie rozumiem. Byłbym wdzieczny kolego gdybyś mi dodał kilka słów rozjaśniających : )

DOWÓD:

Wiemy, że:

\sum_{v \in V} \delta_{i}= 2\left| E\right| = 2\left( \left| V\right| -1\right)

Gdzie \delta_i to stopień wierzchołka. \left| E\right| to liczba krawędzi, a \left| V\right| to liczba wierzhcołków.

Ponadto wiemy, że \delta_{i}  \ge 1. Wynika to ze spójności drzewa.

Jeżeli w T nie ma liści to \delta_i  \ge 2 dla każdego i.

Stąd wnioskujemy, że :
\sum_{v \in V} \delta_i  \ge 2\left| V\right|

Co prowadzi nas do sprzeczności. A sprzecznośc uzyskaliśmy zakładając, że drzewo nie ma ani jednego liścia. \square

Nie rozumiem tutaj tej części:
\sum_{v \in V} \delta_{i}= 2\left| E\right| = 2\left( \left| V\right| -1\right)

skąd wzięła się ta równość ? Ja jedynie wiem, że \sum_{v \in V} \delta_{i}= 2\left| E\right|. I że w każdym drzewie jest o jedną krawędź mniej niż liczba wierzchołków.
Góra
PostNapisane: 10 cze 2013, o 10:34 
Użytkownik
ehem, to włącz myślenie i zobaczysz skąd...

Cytuj:
I że w każdym drzewie jest o jedną krawędź mniej niż liczba wierzchołków.
Góra
Mężczyzna Offline
PostNapisane: 22 sty 2016, o 17:16 
Użytkownik

Posty: 84
Lokalizacja: Sosnowiec, Polska
Sorki za odświeżanie problemu ale dochodzę do momentu gdy \sum_{ v\in V }^{}   \delta_{i}  \ge 2. Wiedząc, że \left| V\right|  \ge 2 i \delta_{i} \ge 1 mogę już wnioskować, że drzewo ma przynajmniej dwa liście? Chcąc z sumy otrzymać najmniejszą wartość tej nierówności czyli 2 muszę zsumować minimum 2 wierzchołki ponieważ wiemy, że \left| V\right|  \ge 2 czyli muszę zsumować dwa wierzchołki o stopniu 1 czyli liście. Czy to wystarcza?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Drzewo o n wierzchołkach  adamjunior  6
 Drzewo - graf planarny  katbest  1
 Każda kulka w złym pudełku  Marcincz  4
 Dane jest drzewo o „n” wierzchołkach.  stg  0
 grafy - drzewo  dusia17  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl