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

drzewa

Post autor: parchimus » 16 cze 2020, o 19:23

Wyznaczyć liczbę drzew spinających grafu \(\displaystyle{ K_{2,4}}\) o wierzchołkach \(\displaystyle{ 1,2,3,4,5,6 }\).

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

Re: drzewa

Post autor: kerajs » 16 cze 2020, o 19:52

pewnie 26, ale:
parchimus pisze:
16 cze 2020, o 19:23
Wyznaczyć liczbę drzew spinających
Co to jest drzewo spinające?
parchimus pisze:
16 cze 2020, o 19:23
o wierzchołkach \(\displaystyle{ 1,2,3,4,5,6 }\).
Przypuszczam, że to numeracja wierzchołków. Stosujesz jakąś konwencję przypisującą numer wierzchołkowi?

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: drzewa

Post autor: parchimus » 16 cze 2020, o 20:22

tak to numeracja wierzchołków.

Dodano po 3 minutach 51 sekundach:
drzewo spinajace - graf spinajacy wszystkie wierzcholki grafu po usunieciu cykli z tego grafu.

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

Re: drzewa

Post autor: kerajs » 17 cze 2020, o 09:31

parchimus pisze:
16 cze 2020, o 20:26
drzewo spinajace - graf spinajacy wszystkie wierzcholki grafu po usunieciu cykli z tego grafu.
drzewo spinające=drzewo rozpinające
parchimus pisze:
16 cze 2020, o 20:26
tak to numeracja wierzchołków.
Szkoda, że nie odpowiedziałeś na zadane pytanie. Wprowadzę więc własne oznaczenia. Zbiór dwuelementowy zawiera wierzchołki A i B, a czteroelementowy wierzchołki: a,b,c,d.

1) Aby nie było cykli, to nie mogą istnieć dwa (lub więcej) wierzchołki o małych literach połączone krawędzią zarówno z A, jak i B.
2) Aby graf był spójny, to musi istnieć co najmniej jeden wierzchołek o małej literze połączony krawędzią zarówno z A, jak i B, a pozostałe muszą mieć krawędź z A lub B.

Oba warunki spełniają grafy w których jeden wierzchołek o małej literze jest stopnia 2, a pozostałe stopnia 1.
Ilość grafów to \(\displaystyle{ {4 \choose 1} \cdot 2^3=32}\) (wybieram wierzchołek stopnia 2, a pozostałe wierzchołki można połączyć z A lub B)

PS
Pomyliłem się podając wynik 26. Ponieważ drzewa zawierają po 5 krawędzi to zliczałem tak : \(\displaystyle{ 3 \cdot 3 \cdot 2+4 \cdot 2=26}\) zamiast \(\displaystyle{ 4 \cdot 3 \cdot 2+4 \cdot 2=32}\) (stopnie dużych liter to (3 i 2) lub (4 i 1)). Tak to jest jak się rozwiązuje w pamięci. Sorki.

ODPOWIEDZ