Drzewo i kostka

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
owen1011
Użytkownik
Użytkownik
Posty: 568
Rejestracja: 29 sty 2009, o 13:59
Płeć: Mężczyzna
Podziękował: 230 razy

Drzewo i kostka

Post autor: owen1011 » 11 cze 2010, o 19:47

mam problem z takimi zadaniami, a zbliza sie kolokwium, wiec z gory dzieki za pomoc

1) Wykaz, ze drzewo bez wierzcholkow stopnia 2 ma wiecej lisci niz innych wierzcholkow.

2) Pokaz, ze kostka \(\displaystyle{ H _{n}}\) jest grafem dwudzielnym.

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

Drzewo i kostka

Post autor: Zordon » 11 cze 2010, o 19:51

1. indukcja
2. Dwupodział będze taki:
niech \(\displaystyle{ g}\) to jakiś ustalony wierzchołek:
\(\displaystyle{ A=\{h:\mbox{można dojsc od g do h po scieżce parzystej długości}\}}\)
\(\displaystyle{ B=\{h:\mbox{można dojsc od g do h po scieżce nieparzystej długości}\}}\)

Trzeba pokazać, że te zbiory są rozłączne.

owen1011
Użytkownik
Użytkownik
Posty: 568
Rejestracja: 29 sty 2009, o 13:59
Płeć: Mężczyzna
Podziękował: 230 razy

Drzewo i kostka

Post autor: owen1011 » 12 cze 2010, o 18:49

dzieki, ale jeszcze mam problem:

1) nie zabardzo rozumiem jak z indukcja, w rozwiazaniach z wykladu mam cos takiego, ale nie rozumiem skad to sie bierze:

2 * E = l*1 + \(\displaystyle{ \sum_{0}^{n-l} l_{i} \ge}\)l+3(n-l)

2(n-1) \(\displaystyle{ \ge}\) l+3(n-l)
skad te dzialamnia sie biora?

2) ok, pokazalem ze istnieje u mnie zbior B, ale nie moge znalezc zadnej sciezki parzystej pomiedzy g i h, czy ona napewno jest?

ODPOWIEDZ