zadanie:
Wyznaczyć liczbę drzew spinających grafu \(\displaystyle{ K_{2,4}}\) o wierzchołkach \(\displaystyle{ 1,2,3,4,5,6}\).
Czy drzewo o kodzie Prufera \(\displaystyle{ 3,2,3,2}\) jest drzewem spinajacym tego grafu?
Podać dwa nieizomorficzne drzewa spinajacego tego grafu.
liczba drzew spinajacych grafu: \(\displaystyle{ 32 }\).
nieizomorficzne drzewa
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: nieizomorficzne drzewa
drzewa
Nie jest drzewem rozpinającym \(\displaystyle{ K_{2,4}}\) gdyż jego krawędzie to: 13,23,24,35,56 .
Ponieważ nadal nie wiadomo jak numerowane są wierzchołki, więc przyjmuję iż zbiór dwuelementowy zawiera wierzchołki A i B, a czteroelementowy wierzchołki: a,b,c,d.
Nieizomorficzne są grafy w których stopnie dużych liter to:
I) 3 i 2
II) 4 i 1
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: nieizomorficzne drzewa
Zwykła pomyłka przy przepisywaniu. Zamiast czerwonej piątki wstaw 2 i masz zestaw z kodu.
A swoją drogą, skoro znasz krawędzie to umiesz stwierdzić czy uzyskany graf zawiera cykl, czy jest dwudzielny oraz ile wierzchołków zawierają rozdzielne zbiory.