szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 03:49 
Użytkownik

Posty: 33
Ile jest grafów prostych o n oznakowanych wierzchołkach? Ile z nich ma dokładnie m krawędzi?

Co do pierwszego pytania: 2^{ {n \choose 2} } a do drugiego: n(n-1)(n-2)...(n-m-1)

Czy to są poprawne odpowiedzi? Z góry dziękuję za sprawdzenie, pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 12:49 
Gość Specjalny
Avatar użytkownika

Posty: 12762
Lokalizacja: Kraków
Pierwsza odpowiedź jest poprawna.

Co do drugiej - dostaję wynik bardziej złożony bazujący na pierwszym podpunkcie. Dlatego zapytam, jak doszedłeś do wyniku z grafami prostymi o n wierzchołkach?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 14:15 
Użytkownik

Posty: 33
Masz rację przecież w drugim ilość miejsc do rozstawienia zależy od n, więc czy dobrą odpowiedzią będzie: {n \choose 2} \left(   {n \choose 2} - 1  \right)   \left(   {n \choose 2} - 2  \right)  ...  \left(   {n \choose 2} - m + 1 \right) ?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 15:30 
Gość Specjalny
Avatar użytkownika

Posty: 12762
Lokalizacja: Kraków
Wydaje się prawie dobrze.

Pierwszą krawędź wybierasz na {n \choose 2} sposobów. Każdą kolejną z tego, co pozostało, itd.

Ale, czy biorąc w ten sposób krawędzie dostaniemy sytuację, w której pewne układy dublujemy? Pytanie sprowadza się do tego, na ile sposobów spośród {n \choose 2} można wybrać m krawędzi? Kolejność, w jakiej dostajemy te krawędzie, nie ma dla nas znaczenia. Co więc najbardziej będzie pasować?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 16:24 
Użytkownik

Posty: 33
Ale wierzchołki są oznakowane, więc krawędzie są rozróżnialne
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 18:50 
Gość Specjalny
Avatar użytkownika

Posty: 12762
Lokalizacja: Kraków
Wierzchołki masz oznakowane, czyli krawędzie też. Ale chodzi mi o coś innego.

Wybierasz najpierw krawędz a, potem b i dalej c ,d ,e (przypadek 5 krawędzi). Jak to się ma do wyboru krawędzi w takiej kolejności: b, a, c, d, e?

Nie upieram się, ze robisz źle. Chciałbym konstruktywnie dojść do wyniku, dlatego, że sam mam pewne wątpliwości. Wydaje mi się, że wybór krawędzi to nie będą wariacje bez powtórzeń, a kombinacje bez powtórzeń. Co o tym sądzisz?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 21:25 
Użytkownik

Posty: 33
W moim rozumowaniu ciąg (1,0,1,0,0,1,..,1) odpowiada kolejno istnieniu krawędzi między pierwszym a drugim wierzchołkiem, nie istnieniu krawędzi między pierwszym a drugim wierzchołkiem itd. aż obsłużymy wszystkie {n \choose 2} par.
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 21:32 
Gość Specjalny
Avatar użytkownika

Posty: 12762
Lokalizacja: Kraków
Czyli wybierasz pierwszą jedynkę na {n\choose 2} sposobów. Kolejną na {n\choose 2}-1 sposobów. Itd aż wybierzesz m jedynek.

Ale taki wybór nie uwzględnia tego, o czym pisałem wcześniej - wybór ciągu 1101 w kolejności obstawiania 124 jest równoważny wyborowi tego samego ciągu 1101 w kolejności 412. Zatem znów ten sam wybór krawędzi liczysz wielokrotnie.
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2013, o 22:03 
Użytkownik

Posty: 33
Więc wg ciebie odpowiedzią jest : { {n \choose 2}  \choose m} ?

Dodano: Rozpatrzyłem to jeszcze raz i jestem pewien, że masz rację, dzięki, pozdrawiam
Góra
Mężczyzna Offline
PostNapisane: 16 sty 2013, o 00:21 
Gość Specjalny
Avatar użytkownika

Posty: 12762
Lokalizacja: Kraków
Przepraszam - byłem zajęty trochę. Stąd późna odpowiedź.

Dopiszę argument wynikający z mojego rozwiązania dla grafów o m krawędziach.

Liczba wszystkich grafów o dowolnej liczbie krawędzi m=0,\ldots ,{n\choose 2} to

\sum\limits_{m=0}^{{n\choose 2}}{{n\choose 2}\choose m}

a powyższe wyrażenie pięknie sumuje się do 2^{{n\choose 2}}, czyli do uzyskanego wcześniej wyniku.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest grafów o n wierzchołkach i k krawędziach  dziubo1  6
 Potęgi grafów i cykle hamiltona  rubik1990  1
 Teoria grafów - podziel wierzchołki na dwie grupy.  Luxxar  1
 Zliczanie kolorowan czworoscianu  Gromo  6
 Ciągi liczb wierchołków kolejnych stopni grafów?  Sonite  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl