szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 16 maja 2016, o 12:07 
Użytkownik

Posty: 47
Lokalizacja: Gdańsk
Mam problem z grafami. Znam teorie, tzn. definicje itp. Tylko nie wiem jak policzyć ile będzie grafów etykietowanych o wierzchołkach 1,2,..,n. Jest na to jakiś wzór lub metoda? Lub jak policzyć ile będzie grafów etykietowanych o wierzchołkach m i krawędzi k
a) grafy z pętlami
b) multigrafy, tzn. grafy z wielokrotnymi krawędziami?
Bardzo by mi zależało, by ktoś tak na chłopski rozum mi to wytłumaczył. Ponieważ to początek działu i chciałabym tą podstawę zrozumieć.
Pozdrawiam
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 26 maja 2016, o 02:38 
Użytkownik
Avatar użytkownika

Posty: 1227
Definicje znasz? Graf to para, nie? \Gamma = (V, E), gdzie V to zbiór wierzchołków, który masz dany, a E to zbiór krawędzi. Pytanie brzmi, ile jest możliwych różnych zbiorów krawędzi dla ustalonego n-elementowego zbioru wierzchołków.

Hint: w (a) każdy kij jest zrobiony z drzewa cisowego, jak łuk Robin Hood'a, więc można z tego kija zrobić okrąg i odpowiedzią nie będzie {n \choose 2}. Punkt (a) można zrobić pisząc odpowiednią rekurencję. Punkt (b) zresztą też, to chyba najprostsze sposoby, najmniej trzeba wtedy myśleć :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z grafami - zadanie 2  fakenmr  2
 Problem z grafami  robertm19  0
 Matematyka dyskretna- problem z paroma zadaniami  MaVerick236  2
 Problem z zadaniami  adi16123  1
 Nieszablonowy problem (ustawianie elementów w ciąg)  loonatic  10
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl