graf spójny planarny i drzewa

[SanczoPanczo]

Witam. Mam kilka pytań dot. GRAFÓW. Proszę o sprawdzenie moich odpowiedzi.

Pytania:
1) Czy istnieje spójny graf planarny składający się z 8 wierzchołków i 19 krawędzi ? Uzasadnij odpowiedź.
2) Jaki warunek powinny spełniać liczby naturalne \(\displaystyle{ d_1, d_2, ... , d_n}\) aby istniało drzewo o n-wierzchołkach oznakowanych liczbami \(\displaystyle{ 1,2,...,n}\) których stopnie są równe odpowiednio \(\displaystyle{ d_1, d_2, ... , d_n}\) ?
3) Ile jest drzew oznakowanych na zbiorze wierzchołków \(\displaystyle{ \left\{ 1,2,...,n\right\}}\) , których stopnie wynoszą odpowiednio \(\displaystyle{ d_1, d_2, ... , d_n}\) ?
4) Wyznacz wszystkie drzewa na zbiorze wierzchołków \(\displaystyle{ \left\{ 1,2,3,4,5,6\right\}}\) takie, że \(\displaystyle{ d\left( 1\right) =1}\) , \(\displaystyle{ d\left( 2\right) =2}\) , \(\displaystyle{ d\left( 3\right) =1}\) , \(\displaystyle{ d\left( 4\right) =3}\) , \(\displaystyle{ d\left( 5\right) =1}\) , \(\displaystyle{ d\left( 6\right) =2}\). (d(i) oznacza stopień wierzchołka i)

Moje odpowiedzi:

ad1)Z własności grafu planarnego (wzór Eulera) mamy, że \(\displaystyle{ |E|\leq3\cdot|V|-6}\)

W naszym przypadku \(\displaystyle{ |E| = 19}\) oraz \(\displaystyle{ |V| = 8}\) , a więc nierówność: \(\displaystyle{ 19\leq3\cdot8-6}\) nie jest prawdziwa, czyli nie istnieje taki graf planarny.

ad2) Takich drzew jest \(\displaystyle{ n^{n-2}}\)

ad3) Odpowiedzią na to pytanie jest wzór Cayleya, czyli takich drzew jest:

\(\displaystyle{ {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1} = {(n-2)! \over {(d_1-1)! (d_2-1)! \cdots (d_n-1)!}}}\)

dla \(\displaystyle{ n \ge 2}\).

ad4)Ze wzoru Caleya:

\(\displaystyle{ \frac{\left( 6-2\right)! }{\left( 1-1\right) !\left( 2-1\right)!\left( 1-1\right)!\left( 3-1\right)!\left( 1-1\right)!\left( 2-1\right)!} = 12}\)

No i teraz pozostaje narysować te 12 drzew, ale to dosyć czasochłonne jest, bo trzeba sprawdzać czy wszystko się zgadza wzg. stopni wierzchołka itp... a to zadanie jest zadaniem egzaminacyjnym, a więc jest jakaś "technika" rysowania takich drzew ? Jaka jest zasada przy rysowaniu tych 12 drzew ? Każdy wierzchołek ma wystąpić obok każdego innego wierzchołka ? Próbowałem narysować te 12 drzew, ale nie udało mi się to, bo powtarzały się wierzchołki non stop.



Proszę o weryfikację moich odpowiedzi.

Grafy mam w przedmiocie matematyka dyskretna, a działu dla grafów nie znalazłem, a więc mam nadzieję, że dobrze wybrałem dział