Cześć, mam problem z dwoma zadaniami z grafów, mianowicie nie wiem jak zapisać formalnie dowód, a jak wiadomo "na czuja" to za mało.
1. Wykaż, że drzewo bez wierzchołków stopnia 2 ma więcej liści niż innych wierzchołków. (Tutaj próbowałem się przyczepić lematu o uściskach dłoni, ale nie wiedziałem jak sformułować do końca).
2.Udowodnij, że drzewo jest grafem dwudzielnym. Jakie drzewa są grafamu pełnymi dwudzielnymi?
(Wiem jak to pokazać kolorując wierzchołki, ale to tylko przy konkretnych drzewach, a co z drzewem o n wierzchołkach?)
Proszę o pomoc, za każdą wskazówkę, czy wzór rozwiązania do przeanalizowania będę bardzo wdzięczny.
Udowodnij, że drzewo...
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Udowodnij, że drzewo...
1. Przez liść będę rozumiał wierzchołek stopnia co najwyżej jeden. W przypadku, gdy drzewo składa się z tylko jednego wierzchołka przyjmujemy, że ten wierzchołek jest liściem.
Dalej załóżmy, że drzewo składa się z min. \(\displaystyle{ 2}\) wierzchołków, z tego wynika, że każdy wierzchołek ma stopień przynajmniej \(\displaystyle{ 1}\) (aby graf był spójny), czyli liść ma stopień \(\displaystyle{ 1}\).
Niech \(\displaystyle{ l}\) to liczba liści, a \(\displaystyle{ n}\) to liczba wierzchołków drzewa. Wtedy każdy z pozostałych \(\displaystyle{ n - l}\) wierzchołków nie będących liśćmi ma stopień przynajmniej \(\displaystyle{ 3}\).
Liczba krawędzi drzewa o \(\displaystyle{ n}\) wierzchołkach to \(\displaystyle{ n - 1}\) (co można łatwo pokazać indukcyjnie i znajduje się w dowolnej książce do matematyki dyskretnej).
Każda krawędź ma dwa końce, więc suma stopni w drzewie to \(\displaystyle{ 2n - 2}\).
Z drugiej strony wierzchołki o stopniu przynajmniej \(\displaystyle{ 3}\) wnoszą do tej sumy stopni przynajmniej \(\displaystyle{ 3(n - l)}\), a liście wnoszą \(\displaystyle{ l}\), czyli:
\(\displaystyle{ 2n - 2 = suma \ stopni \ge 3(n - l) + l = 3n - 2l}\)
\(\displaystyle{ 2n - 2 \ge 3n - 2l}\)
\(\displaystyle{ 2l \ge n + 2}\)
\(\displaystyle{ l \ge \frac{n}{2} + 1}\), cnd.
2. Trzeba pokazać, że da się podzielić wierzchołki drzewa na dwa zbiory takie, że nie ma krawędzi pomiędzy dowolnymi dwoma wierzchołkami wewnątrz zbiorów. Ustalmy jakiś korzeń drzewa. Dla każdego wierzchołka wyznaczmy odległość tego wierzchołka od korzenia (wiemy, że jest dokładnie jedna ścieżka od korzenia do tego wierzchołka w przeciwnym przypadku byłby cykl). Teraz wierzchołki o parzystej odległości od korzenia wrzucamy do jednego zbioru, a o nieparzystej do drugiego. Między wierzchołkami o odległości tej samej parzystości nie ma krawędzi.
Graf pełny dwudzielny, który zawiera przynajmniej po dwa wierzchołki w obu zbiorach ma cykl - wybieramy po dwa wierzchołki (powiedzmy A, B z pierwszego zbioru i C, D z drugiego) z obu zbioru, tworzą one cykl (cykl: A, C, B, D, A), czyli taki graf nie jest drzewem.
To znaczy, że w przynajmniej jednym ze zbiorów jest co najwyżej jeden wierzchołek.
Jeżeli w jednym ze zbiorów nie byłoby wierzchołków to w drugim jest dokładnie jeden wierzchołek (gdyby były przynajmniej dwa to graf byłby niespójny, bo między nimi nie może być krawędzi, więc nie byłoby to drzewo).
Jeżeli w jednym ze zbiorów byłby dokładnie jeden wierzchołek to rozpatrzmy przypadek, że w drugim jest przynajmniej jeden. Może być w nim dowolna liczba wierzchołków i łącznie graf będzie tworzył drzewo.
Tak więc są dwa typy grafów pełnych dwudzielnych będących drzewami: sam wierzchołek oraz korzeń z dowolną liczbą liści.
Dalej załóżmy, że drzewo składa się z min. \(\displaystyle{ 2}\) wierzchołków, z tego wynika, że każdy wierzchołek ma stopień przynajmniej \(\displaystyle{ 1}\) (aby graf był spójny), czyli liść ma stopień \(\displaystyle{ 1}\).
Niech \(\displaystyle{ l}\) to liczba liści, a \(\displaystyle{ n}\) to liczba wierzchołków drzewa. Wtedy każdy z pozostałych \(\displaystyle{ n - l}\) wierzchołków nie będących liśćmi ma stopień przynajmniej \(\displaystyle{ 3}\).
Liczba krawędzi drzewa o \(\displaystyle{ n}\) wierzchołkach to \(\displaystyle{ n - 1}\) (co można łatwo pokazać indukcyjnie i znajduje się w dowolnej książce do matematyki dyskretnej).
Każda krawędź ma dwa końce, więc suma stopni w drzewie to \(\displaystyle{ 2n - 2}\).
Z drugiej strony wierzchołki o stopniu przynajmniej \(\displaystyle{ 3}\) wnoszą do tej sumy stopni przynajmniej \(\displaystyle{ 3(n - l)}\), a liście wnoszą \(\displaystyle{ l}\), czyli:
\(\displaystyle{ 2n - 2 = suma \ stopni \ge 3(n - l) + l = 3n - 2l}\)
\(\displaystyle{ 2n - 2 \ge 3n - 2l}\)
\(\displaystyle{ 2l \ge n + 2}\)
\(\displaystyle{ l \ge \frac{n}{2} + 1}\), cnd.
2. Trzeba pokazać, że da się podzielić wierzchołki drzewa na dwa zbiory takie, że nie ma krawędzi pomiędzy dowolnymi dwoma wierzchołkami wewnątrz zbiorów. Ustalmy jakiś korzeń drzewa. Dla każdego wierzchołka wyznaczmy odległość tego wierzchołka od korzenia (wiemy, że jest dokładnie jedna ścieżka od korzenia do tego wierzchołka w przeciwnym przypadku byłby cykl). Teraz wierzchołki o parzystej odległości od korzenia wrzucamy do jednego zbioru, a o nieparzystej do drugiego. Między wierzchołkami o odległości tej samej parzystości nie ma krawędzi.
Graf pełny dwudzielny, który zawiera przynajmniej po dwa wierzchołki w obu zbiorach ma cykl - wybieramy po dwa wierzchołki (powiedzmy A, B z pierwszego zbioru i C, D z drugiego) z obu zbioru, tworzą one cykl (cykl: A, C, B, D, A), czyli taki graf nie jest drzewem.
To znaczy, że w przynajmniej jednym ze zbiorów jest co najwyżej jeden wierzchołek.
Jeżeli w jednym ze zbiorów nie byłoby wierzchołków to w drugim jest dokładnie jeden wierzchołek (gdyby były przynajmniej dwa to graf byłby niespójny, bo między nimi nie może być krawędzi, więc nie byłoby to drzewo).
Jeżeli w jednym ze zbiorów byłby dokładnie jeden wierzchołek to rozpatrzmy przypadek, że w drugim jest przynajmniej jeden. Może być w nim dowolna liczba wierzchołków i łącznie graf będzie tworzył drzewo.
Tak więc są dwa typy grafów pełnych dwudzielnych będących drzewami: sam wierzchołek oraz korzeń z dowolną liczbą liści.