szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 mar 2018, o 12:53 
Użytkownik

Posty: 21
Lokalizacja: Polska
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.
Góra
Mężczyzna Offline
PostNapisane: 24 mar 2018, o 13:53 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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. 2 wierzchołków, z tego wynika, że każdy wierzchołek ma stopień przynajmniej 1 (aby graf był spójny), czyli liść ma stopień 1.
Niech l to liczba liści, a n to liczba wierzchołków drzewa. Wtedy każdy z pozostałych n - l wierzchołków nie będących liśćmi ma stopień przynajmniej 3.
Liczba krawędzi drzewa o n wierzchołkach to 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 2n - 2.
Z drugiej strony wierzchołki o stopniu przynajmniej 3 wnoszą do tej sumy stopni przynajmniej 3(n - l), a liście wnoszą l, czyli:
2n - 2 = suma \ stopni  \ge 3(n - l) + l = 3n - 2l
2n - 2 \ge 3n - 2l
2l  \ge n + 2
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Udowodnij indukcyjnie równanie.  stone80  0
 Ciąg, graf, drzewo, Euler... ;/  Szakal  2
 Udowodnij istnienie  Dario1  5
 Graf spojny a drzewo  profesorq  0
 udowodnij tożsamość - zadanie 37  pacia1620  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl