grafy - jedno krótkie zadanie

gawellus · Post autor: **gawellus** » 23 wrz 2006, o 16:23

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".

Sir George · Post autor: **Sir George** » 25 wrz 2006, o 12:55

gawellus pisze:co oznacza stwierdzenie "różne zbiory krawędzi"

To, że zbiory krawędzi nie są równe.
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

gawellus · Post autor: **gawellus** » 25 wrz 2006, o 13:08

wielkie dzięki