Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Sprawdzenie czy graf jest planarny, hamiltonowski, planarny

Strona 1 z 1

[ Posty: 2 ]

Autor

Wiadomość

Lyzka

Tytuł: Sprawdzenie czy graf jest planarny, hamiltonowski, planarny

Napisane: 18 cze 2016, o 14:28

Posty: 521
Lokalizacja: Polska

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

Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018

Góra

Slup

Tytuł: Sprawdzenie czy graf jest planarny, hamiltonowski, planarny

Napisane: 20 cze 2016, o 22:56

Posty: 306
Lokalizacja: Warszawa

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:
$d(v)=10$
już tutaj zakładasz, że graf jest prosty.
Potem wyznaczasz liczbę krawędzi:
$|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 $n$ i każdy wierzchołek ma stopień $\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) $|E|\leq 3|V|-6$ dla prostego grafu planarnego. W Twoim grafie:
$|E|=105>3\cdot 21-6=3|V|-6$
czyli nie jest on planarny.

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 2 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Ile jest dzielnikow liczby	Anonymous	6
ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?	Anonymous	1
permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie	alamakota	3
ile jest liczb trzycyfrowych, mniejszych od 555	Anonymous	1
Dany jest zbiór A={a,b,c,d}	Nanu	3

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]