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 : )
każda drzewo ma co najmniej 2 liscie
-
leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
-
leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
każda drzewo ma co najmniej 2 liscie
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.
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.
-
miodzio1988
każda drzewo ma co najmniej 2 liscie
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.
-
somas3k
- Użytkownik
- Posty: 84
- Rejestracja: 30 wrz 2013, o 19:16
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec, Polska
- Podziękował: 30 razy
każda drzewo ma co najmniej 2 liscie
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?