dowody z grafami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
autonomous
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 30 sty 2012, o 17:04
Płeć: Kobieta
Lokalizacja: Gdańsk

dowody z grafami

Post autor: autonomous »

1. Pokazać na rysunku, że istnieje 6 z dokładnością do izomorfizmu drzew o sześciu wierzchołkach i 11 drzew o siedmiu wierzchołkach.

2. Uzasadnić, że graf prosty o co najmniej dwóch wierzchołkach zawsze ma przynajmniej dwa wierzchołki tego samego stopnia.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

dowody z grafami

Post autor: norwimaj »

Ad 1.

Na zachętę, sześciowierzchołkowe drzewa, w których najdłuższa ścieżka ma długość \(\displaystyle{ 5}\) lub \(\displaystyle{ 4}\) krawędzie.

\(\displaystyle{ \begin{picture}(120,140)
\multiput(10,30)(40,0){3}{\multiput(0,0)(0,20){5}{\circle*{4}}}
\put(10,10){\circle*{4}}
\multiput(70,50)(40,20){2}{\circle*{4}}
\multiput(10,30)(40,0){3}{\line(0,1){80}}
\put(10,10){\line(0,1){20}}
\multiput(50,50)(40,20){2}{\line(1,0){20}}
\put(0,0){$.$}
\put(130,120){$.$}
\end{picture}}\)


Pozostałe \(\displaystyle{ 3}\) możliwe drzewa chyba wymyślisz?

Ad 2.
Jaki stopień może mieć wierzchołek w grafie \(\displaystyle{ n}\)-wierzchołkowym?
ODPOWIEDZ