Drzewo i tw. Eulera dla spójnych grafów planarnych

[Sonite]

1. Podaj definicję i własności drzewa.

2. sformułuj i udowodnij twierdzenie Eulera dla spojnych grafów planarnych.

Edit by Arbooz: Wątek poprawiłem i przeniosłem. Zapoznaj się z zasadami tytułowania i pisz w odpowiednich działach.

[minus]

1 Drzewo - acykliczny graf spójny. Wlasności toto ma wiele. Wsród ważniejszych wymienilbym acykliczność (brak cykli ), fakt że dodanie dowolnej krawędzi utworzy nam jakiś cykl a wyjęcie jednej spowoduje rozspójnienie na dwie skladowe, fakt że pomiędzy każdymi dwoma wiercholkami isnieje dokladnie jedna ścieżka, każda krawędź jest mostem ... hmmm .... i inne, które latwo samemu zauważyć, np. n-1 krawedzi przy n wiercholkach czy co istnienie conajmniej DELTA liści ... warto porysować sobie kilka drzew i przyjrzeć się. W ten sposób dojdziesz do rożnych bardziej czy mniej trywialnych wniosków.

2 Co do dowodu Eulera ... hmmm ... szczerze mówiąć nie pamiętam dokladnie jak to szlo. Pewnym pomyslem jest konstrukcja indukcyjna. Zaczynasz od dowolnego cyklu. Jęsli graf nie ma cyklu znaczy jest drzewem. (Albo zacząc od drzewa, wszakże każdy spójny graf ma rozpięte drzewo). I dalej rozpatrzyć możliwości dodawania krawędzi...

Ot co

[WhiteRabbit7]

Czy ktoś by mógł dać jakąś wskazówkę do podpunktu b) ? Wzór to ś+w-k=2, gdzie ś to liczba ścian grafu, w liczba wierzchołków, a k krawędzi. Chciałbym udowodnić to indukcyjnie, jednak nie wiem zbytnio jak się za to zabrać ;/

[MatXXX]

Przy ustalonej liczbie wierzchołków indukcyjnie po liczbie krawędzi. Zacznij indukcję od przypadku, kiedy \(\displaystyle{ k=w-1}\), czyli od drzewa. Potem dokładaj krawędzie. Zauważ, że kiedy dokładamy jedną krawędź, to pojawia się nam jedna ściana.

[WhiteRabbit7]

No tak, ogólnie to sprawa wygląda tak, że jeśli:
\(\displaystyle{ w=3}\) to \(\displaystyle{ ś = k-1}\)
\(\displaystyle{ w=4}\) to \(\displaystyle{ ś = k-2}\)
\(\displaystyle{ w=5}\) to \(\displaystyle{ ś = k-3}\)
itd.
Tylko nie wiem zbytnio jak to wszystko udowodnić, co ma być założeniem indykcyjnym, tezą indukcyjną itp.

[MatXXX]

Mamy graf planarny o \(\displaystyle{ w}\) wierzchołkach. Chcemy indukcyjnie udowodnić, że zachodzi \(\displaystyle{ s+w-k=2}\). Będziemy indukować po ilości krawędzi grafu planarnego dołożonych do jego podgrafu o \(\displaystyle{ w}\) wierzchołkach będącego drzewem.

Baza:
Podgraf będący drzewem. Jest \(\displaystyle{ w-1}\) krawędzi i jedna ściana. \(\displaystyle{ 1 + w - (w-1) = 2}\).

Krok:
Mamy pewien podgraf grafu planarnego, który powstał poprzez dołożenia do podgrafu będącego drzewem krawędzi z pierwotnego grafu planarnego, wszystkich krawędzi w nim jest \(\displaystyle{ n}\). Zakładamy, że zachodzi dla niego równość \(\displaystyle{ s+w-n=2}\).
Dołóżmy do niego jedną z krawędzi grafu planarnego. Podzieliła ona jedną ze ścian na dwie. Jest teraz \(\displaystyle{ n+1}\) krawędzi oraz \(\displaystyle{ s+1}\) ścian.
\(\displaystyle{ s+1+w-(n+1) = s+w-n = 2}\)

[WhiteRabbit7]

Czyli jednym słowem pokazujemy, że równanie jest prawdziwe dla pewnego grafu spełniającego wymagania określone w treści polecenia ( w tym przypadku spójnego grafu planarnego), a następnie pokazujemy, że jest prawdziwe również, gdy liczba krawędzi wzrośnie o jeden? I rozumiem, że na mocy indukcji matematycznej taki dowód jest wystarczający, aby udowodnić prawdziwość wzoru Eulera ?