drzewa
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: drzewa
pewnie 26, ale:
Co to jest drzewo spinające?
Przypuszczam, że to numeracja wierzchołków. Stosujesz jakąś konwencję przypisującą numer wierzchołkowi?
-
- Użytkownik
- Posty: 43
- Rejestracja: 28 maja 2020, o 18:02
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 6 razy
Re: drzewa
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.
Dodano po 3 minutach 51 sekundach:
drzewo spinajace - graf spinajacy wszystkie wierzcholki grafu po usunieciu cykli z tego grafu.
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: drzewa
drzewo spinające=drzewo rozpinające
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.