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.
Drzewo i kostka
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Drzewo i kostka
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.
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
- Posty: 568
- Rejestracja: 29 sty 2009, o 13:59
- Płeć: Mężczyzna
- Podziękował: 230 razy
Drzewo i kostka
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?
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?