szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 18 cze 2016, o 14:28 
Użytkownik
Avatar użytkownika

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.
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2016, o 22:56 
Użytkownik

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
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 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
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl