Sprawdzenie czy graf jest planarny, hamiltonowski, planarny

[Lyzka]

Graf \(\displaystyle{ G=(V,E)}\) definiujemy w następujący sposób: Zbiorem wierzchołków grafu \(\displaystyle{ G}\) jest zbiór \(\displaystyle{ V=P_2(X)}\) wszystkich 2-elemntowych podzbiorów zbioru \(\displaystyle{ X={1,2,3,4,5,6,7}}\). Jeśli \(\displaystyle{ A,B \in V}\), to \(\displaystyle{ \left\{ A,B \right\} \in E}\), wtedy i tylko wtedy, gdy \(\displaystyle{ A \cap B \neq \emptyset}\) Ile krawędzi i wierzchołków ma ten graf?
\(\displaystyle{ \left| V\right|= {7\choose 2} =21}\)
\(\displaystyle{ d \left( v \right) =10}\)
\(\displaystyle{ \left| E\right| = \frac{21 \cdot 10}{2} =105}\)
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: \(\displaystyle{ d \left( v \right) =10}\)
Czy \(\displaystyle{ 10 \ge \frac{21}{2}}\) ---> 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: \(\displaystyle{ e \le 3n-6}\) ż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.

[Slup]

To graf jest moim zdaniem prosty. Jeżeli nie, to powiedz ile jest krawędzi pomiędzy ustaloną parą wierzchołków.
Liczysz stopień każdego wierzchołka:
\(\displaystyle{ d(v)=10}\)
już tutaj zakładasz, że graf jest prosty.
Potem wyznaczasz liczbę krawędzi:
\(\displaystyle{ |E|=\frac{10\cdot 21}{2}=105}\)
Dzieląc przez dwa zakładasz, że każda krawędź jest liczona dwa razy, czyli, że jest jedna krawędź pomiędzy dwoma wierzchołkami.
Przy założeniu, że Twój graf jest prosty Twoje obliczenia są poprawne.
1) Jest to graf Eulerowski, bo każdy wierzchołek ma stopień parzysty, więc istnieje cykl Eulera.
2) Twierdzenie Diraca mówi, że jeżeli liczba wierzchołków grafu wynosi \(\displaystyle{ n}\) i każdy wierzchołek ma stopień \(\displaystyle{ \geq \frac{n}{2}}\), to graf jest Hamiltonowski. Twierdzenie Diraca podaje warunek wystarczający istnienia cyklu Hamiltona, ale nie jest to warunek konieczny.. Twoje rozumowanie nie jest poprawne.
3) \(\displaystyle{ |E|\leq 3|V|-6}\) dla prostego grafu planarnego. W Twoim grafie:
\(\displaystyle{ |E|=105>3\cdot 21-6=3|V|-6}\)
czyli nie jest on planarny.