Witam
mam jedno zadanie z ojego egzaminu, z którym sobie nie radze
"ile jest różnych, niepustych grafów na 10 wierzchołkach {1,2...10}? Grafy mogą być izomorficzne, ale muszą mieć różne zbiory krawędzi."
Jeśli mógłbym, to jeszcze proszę mi wytłumaczyć co oznacza stwierdzenie "różne zbiory krawędzi".
grafy - jedno krótkie zadanie
- Sir George
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
grafy - jedno krótkie zadanie
To, że zbiory krawędzi nie są równe.gawellus pisze:co oznacza stwierdzenie "różne zbiory krawędzi"
Dla przykładu dwa grafy z Twoje zadania: graf o jednej tylko krawędzi {1,2} jest izomorficzny z grafem o jednej krawędzi {2,3}, ale mają różne zbiory krawędzi.
Stąd narzuca się rozwiązanie. Wszystkich krawędzi jest 45 (tyle ile podzbiorów dwuelementowych zbioru 10-elementowego). Jak rozumiem graf niepusty to taki, który ma przynajmniej jedną krawędź. Nie ma mowy o jego spójności, zatem graf { {1,2,...,10}, { {2,3} } } należy do rozwiązania.
Zatem wszystkich niepustych grafów jest tyle, ile jest różnych, niepustych podzbiorów zbioru wszystkich krawędzi,
czyli 2^45 - 1