Graf

definiujemy w następujący sposób: Zbiorem wierzchołków grafu

jest zbiór

wszystkich 2-elemntowych podzbiorów zbioru

. Jeśli

, to

, wtedy i tylko wtedy, gdy

Ile krawędzi i wierzchołków ma ten graf?



1. Czy jest to graf eulerowski?
Wg mnie nie, bo graf nie posiada cyklu eulera, tzn jest to zamkniętej marszruty, która przechodzi przez każdą krawędź grafu dokładnie raz (w tym grafie występują krawędzie podwójne).
2. Czy graf jest hamiltonowski?
Z tw. Diraca
Liczba wierzchołków: n=21
Stopień każdego wierzchołka:

Czy

---> fałsz
Zatem nie jest hamiltonowski. Poza tym, graf hamiltonowski musi być grafem prostym, a ten graf nie jest prosty, bo ma krawędzie wielokrotne.
3. Czy graf jest planarny?
Tak bo istnieje izomorficzny z nim graf płaski. Izomorficzny tzn mający taką samą strukturę.
btw. Czy wystarczy sprawdzić warunek:

żeby sprawdzić planarność grafu?
Czy może ktoś sprawdzić czy zadanie jest dobrze rozwiązane? W szczególności te trzy pytania o tym czy graf jest eulerowski, hamiltonowski i planarny.