Zliczanie grafów, sprawdzenie poprawności rozwiązania.

donmaciej · Post autor: **donmaciej** » 15 sty 2013, o 02:49

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

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

Czy to są poprawne odpowiedzi? Z góry dziękuję za sprawdzenie, pozdrawiam.

yorgin · Post autor: **yorgin** » 15 sty 2013, o 11:49

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 \(\displaystyle{ n}\) wierzchołkach?

donmaciej · Post autor: **donmaciej** » 15 sty 2013, o 13:15

Masz rację przecież w drugim ilość miejsc do rozstawienia zależy od n, więc czy dobrą odpowiedzią będzie: \(\displaystyle{ {n \choose 2} \left( {n \choose 2} - 1 \right) \left( {n \choose 2} - 2 \right) ... \left( {n \choose 2} - m + 1 \right)}\) ?

yorgin · Post autor: **yorgin** » 15 sty 2013, o 14:30

Wydaje się prawie dobrze.

Pierwszą krawędź wybierasz na \(\displaystyle{ {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 \(\displaystyle{ {n \choose 2}}\) można wybrać \(\displaystyle{ m}\) krawędzi? Kolejność, w jakiej dostajemy te krawędzie, nie ma dla nas znaczenia. Co więc najbardziej będzie pasować?

donmaciej · Post autor: **donmaciej** » 15 sty 2013, o 15:24

Ale wierzchołki są oznakowane, więc krawędzie są rozróżnialne

yorgin · Post autor: **yorgin** » 15 sty 2013, o 17:50

Wierzchołki masz oznakowane, czyli krawędzie też. Ale chodzi mi o coś innego.

Wybierasz najpierw krawędz \(\displaystyle{ a}\), potem \(\displaystyle{ b}\) i dalej \(\displaystyle{ c ,d ,e}\) (przypadek 5 krawędzi). Jak to się ma do wyboru krawędzi w takiej kolejności: \(\displaystyle{ 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?

donmaciej · Post autor: **donmaciej** » 15 sty 2013, o 20:25

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 \(\displaystyle{ {n \choose 2}}\) par.

yorgin · Post autor: **yorgin** » 15 sty 2013, o 20:32

Czyli wybierasz pierwszą jedynkę na \(\displaystyle{ {n\choose 2}}\) sposobów. Kolejną na \(\displaystyle{ {n\choose 2}-1}\) sposobów. Itd aż wybierzesz \(\displaystyle{ 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.

donmaciej · Post autor: **donmaciej** » 15 sty 2013, o 21:03

Więc wg ciebie odpowiedzią jest : \(\displaystyle{ { {n \choose 2} \choose m}}\) ?

Dodano: Rozpatrzyłem to jeszcze raz i jestem pewien, że masz rację, dzięki, pozdrawiam

yorgin · Post autor: **yorgin** » 15 sty 2013, o 23:21

Przepraszam - byłem zajęty trochę. Stąd późna odpowiedź.

Dopiszę argument wynikający z mojego rozwiązania dla grafów o \(\displaystyle{ m}\) krawędziach.

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

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

a powyższe wyrażenie pięknie sumuje się do \(\displaystyle{ 2^{{n\choose 2}}}\), czyli do uzyskanego wcześniej wyniku.