szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 cze 2016, o 15:58 
Użytkownik

Posty: 67
Lokalizacja: Warszawa
Znajdz ilość drzew ze zbiorem wierzchołków [n] i maksymalnym stopniu wierzchołka:

a) n-1
b) n-2

Wydawało mi się że w pierwszym to będzie n \cdot (n-1) ale w odpowiedziach jest n
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2016, o 10:58 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Skoro pewien wierzchołek ma stopień n-1, to znaczy, że odchodzą od niego krawędzie do wszystkich pozostałych wierzchołków. W takim razie jak już narysujemy ten wierzchołek i połączymy go z resztą, to mamy całe drzewo. Nic więcej już nie możemy zrobić. Zatem takich drzew jest n, bo wystarczy zdecydować, który wierzchołek będzie tym wyróżnionym.
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2016, o 15:00 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
b) Tutaj jeden wierzchołek będzie miał n - 2 sąsiadów i dokładnie jeden z jego sąsiadów będzie miał jeszcze jednego sąsiada innego od tych n - 2. To będzie taka gwiazda z ogonkiem. Najpierw wybieramy wierzchołek największego stopnia na n sposobów, potem tych dwóch tworzących ogonek i permutujemy ich razy 2, czyli (n - 1)(n - 2) \cdot 2, a na koniec wybieramy kolejnych sąsiadów tych tworzących ogonek idąc np. zgodnie ze wskazówkami zegara na (n - 3)! sposobów, ale musimy to podzielić przez 2 bo nie ma znaczenia czy idziemy zgodnie, czy przeciwnie do wskazówek zegara. Łącznie n!.
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2016, o 16:14 
Użytkownik

Posty: 45
Mruczek napisał(a):
b) Tutaj jeden wierzchołek będzie miał n - 2 sąsiadów i dokładnie jeden z jego sąsiadów będzie miał jeszcze jednego sąsiada innego od tych n - 2. To będzie taka gwiazda z ogonkiem. Najpierw wybieramy wierzchołek największego stopnia na n sposobów, potem tych dwóch tworzących ogonek i permutujemy ich razy 2, czyli (n - 1)(n - 2) \cdot 2



Dlaczego mnożysz wyrażenie przez 2? Wtedy zliczamy chyba podwójnie każdy układ. Wybierasz wierzchołek o najwyższym stopniu na n sposobów, potem połączony z nim jedyny wierzchołek niebędący liściem na n-1 sposobów i ostatni z tej trójki na n-2 sposobów. Czyli w tym przypadku dostajemy np. takie układy (1,3,5,...) i (1,5,3...), a mnożac przez dwa niepotrzebnie permutujemy. I mam pytanie jeszcze co do tych pozostałych wierzchołków - czy jako to samo ustawienie uznajemy układ wtedy, kiedy każdy z liści bezpośrednio dołączonych do wierzchołka o najwyższym stopniu ma tych samych sąsiadów? Jeśli tak, to nie powinno być tych permutacji tyle, co ustawień wokół okrągłego stołu, czyli \frac{(n-3)!}{n-3} = (n-4)!?
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2016, o 16:22 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Tak, nie powinienem mnożyć przez 2.

Teraz mam wrażenie, że skoro w a) nie liczyła się kolejność liści, to i w b) kolejność liści może nie mieć znaczenia, czyli być może nie trzeba tego mnożyć wcale. Czyli że wynik to n(n - 1)(n - 2).
Wygląda na to, że tak jest, bo przy zliczaniu drzew za pomocą tw. Cayley'a właśnie tyle wychodzi - kolejność liści nie ma znaczenia.
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2016, o 17:48 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
A co by to miało znaczyć, że "kolejność liści ma znaczenie"? Formalnie zliczamy pary zbiorów postaci \left\langle [n],E\right\rangle. Pary te są różne, jeśli różnią się zbiorem krawędzi. A zbiór krawędzi "widzi" tylko, który numer z którym jest połączony. Nie ma więc miejsca na kolejność liści. Jak już ustalimy, że nasze drzewo oprócz wierzchołka stopnia n-2 musi się składać z n-2 liści i jednego wierzchołka stopnia 2, to po prostu musimy zdecydować, kto będzie miał stopień n-2, kto 2 i kto będzie liściem połączonym z wierzchołkiem stopnia 2. Reszta jest zadana. Dlatego odpowiedź to n(n-1)(n-2).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Losy - znajdź bład  Sylwek  4
 Wyznaczyć liczbę ciągów ternarnych  Michau13245  3
 Znajdź ciąg mając daną funkcję tworzącą.  1608  11
 Znajdź funkcje tworzącą ciag  k0b3  0
 Własności drzew, ciąg stopni grafu prostego  Szemek  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl