nieizomorficzne drzewa

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
parchimus
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

nieizomorficzne drzewa

Post autor: parchimus » 17 cze 2020, o 15:53

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 }\).

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7788
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3058 razy

Re: nieizomorficzne drzewa

Post autor: kerajs » 17 cze 2020, o 16:39

parchimus pisze:
17 cze 2020, o 15:53
Wyznaczyć liczbę drzew spinających grafu \(\displaystyle{ K_{2,4}}\) o wierzchołkach \(\displaystyle{ 1,2,3,4,5,6}\)

liczba drzew spinajacych grafu: \(\displaystyle{ 32 }\).
drzewa
parchimus pisze:
17 cze 2020, o 15:53
Czy drzewo o kodzie Prufera \(\displaystyle{ 3,2,3,2}\) jest drzewem spinajacym tego grafu?
Nie jest drzewem rozpinającym \(\displaystyle{ K_{2,4}}\) gdyż jego krawędzie to: 13,23,24,35,56 .

parchimus pisze:
17 cze 2020, o 15:53
Podać dwa nieizomorficzne drzewa spinajacego tego grafu.
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

parchimus
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

Re: nieizomorficzne drzewa

Post autor: parchimus » 17 cze 2020, o 17:34

a krawędzie w tym kodzie Prufera to nie:


31,35,32,26,24?

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7788
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3058 razy

Re: nieizomorficzne drzewa

Post autor: kerajs » 17 cze 2020, o 20:05

kerajs pisze:
17 cze 2020, o 16:39
Nie jest drzewem rozpinającym \(\displaystyle{ K_{2,4}}\) gdyż jego krawędzie to: 13,23,24,35,56 .
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.

ODPOWIEDZ