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.
Grafy proste, liczba grafów
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Grafy proste, liczba grafów
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.
Q.