Grafy proste, liczba grafów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Omnius
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 13 kwie 2008, o 22:14
Płeć: Mężczyzna
Lokalizacja: DG

Grafy proste, liczba grafów

Post autor: Omnius » 25 maja 2008, o 21:18

Znajdź dokładną liczbę grafów prostych mających \(\displaystyle{ n}\) etykietowanych wierzchołków i \(\displaystyle{ k}\) krawędzi.

Ktoś może pomóc? Bo to chyba nie jest tak proste jak użycie wzoru na kombinacje bez powtórzeń?

Z góry dziękuje.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2626 razy

Grafy proste, liczba grafów

Post autor: » 25 maja 2008, o 23:47

Skoro graf ma \(\displaystyle{ n}\) wierzchołków, to potencjalnych "miejsc" na krawędzie jest \(\displaystyle{ {n \choose 2}}\). A \(\displaystyle{ k}\) tych "miejsc" można wyznaczyć na \(\displaystyle{ {{n \choose 2} \choose k}}\) sposobów, tyle więc jest grafów o które pytamy.

Q.

ODPOWIEDZ