Matematyka.pl

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 : )

Wujka google pytales?

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:

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

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

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

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

Stąd wnioskujemy, że :
\(\displaystyle{ \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. \(\displaystyle{ \square}\)

Nie rozumiem tutaj tej części:
\(\displaystyle{ \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 \(\displaystyle{ \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.

ehem, to włącz myślenie i zobaczysz skąd...

I że w każdym drzewie jest o jedną krawędź mniej niż liczba wierzchołków.

Sorki za odświeżanie problemu ale dochodzę do momentu gdy \(\displaystyle{ \sum_{ v\in V }^{} \delta_{i} \ge 2}\). Wiedząc, że \(\displaystyle{ \left| V\right| \ge 2}\) i \(\displaystyle{ \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 \(\displaystyle{ \left| V\right| \ge 2}\) czyli muszę zsumować dwa wierzchołki o stopniu 1 czyli liście. Czy to wystarcza?