szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 cze 2016, o 16: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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2016, o 11:58 
Użytkownik

Posty: 1427
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 16:00 
Użytkownik

Posty: 1086
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 17: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 17:22 
Użytkownik

Posty: 1086
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 18:48 
Użytkownik

Posty: 1427
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 
 Znajdz interpretacje kombinatoryczna - zadanie 2  teczowyplacek  2
 Znajdź funkcję tworzącą  nwnuinr  1
 Sadzenie 10 drzew.  pablopoz  3
 Pytania: brute force oraz drzew spinających  maly12345  0
 znaleźć najmniejszą oraz największą liczbę, tak aby...  matinf  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl