Dany jest 1000-elementowy zbiór \(\displaystyle{ X}\). Zbiór ten jest zbiorem wierzchołków grafu G, który składa się z 5 składowych, a każda składowa jest grafem pełnym. Ile takich grafów możemy utworzyć na zbiorze X? Które z nich mają najwięcej krawędzi? Ile ich jest?
W jakich sposób mogę podejść do tego zadania?
Graf 5 skladowych
-
MatXXX
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Graf 5 skladowych
Zbiór wierzchołków trzeba podzielić na pięć niepustych podzbiorów. Poczytaj o liczbach Stirlinga. Przy szukaniu maksymalnej ilości krawędzi pomyśl, kiedy mamy więcej krawędzi, jak mamy dużo wierzchołków w jednej składowej, czy może kiedy są one w jakiś sposób podzielone.