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: 43
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

drzewa

Post autor: parchimus »

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: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: drzewa

Post autor: kerajs »

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: 43
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

Re: drzewa

Post autor: parchimus »

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: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: drzewa

Post autor: kerajs »

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