szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 cze 2017, o 15:38 
Użytkownik

Posty: 77
Lokalizacja: Wrocław
Sprawdź planarność poniższych grafów:
(grafy w linku) http://imgur.com/a/OQpLh

Graf jest planarny wtedy gdy spełnia dwa kryteria/twierdzenia:
1. Kuratowskiego
2. Eulera

I teraz prosił bym o zweryfikowanie moich uzasadnień dotyczących właśnie planarności powyższych grafów.

Graf nr 1:
- nie jest planarny, ponieważ gdy graf jest planarny to można go narysować na płaszczyźnie tak aby jego krawędzie nie przecinały się, więc nie sprawdzam nawet twierdzenia Eulera, które mówi, jeżeli od liczby wierzchołków liczbę krawędzi, a następnie dodamy liczbę ścian i to jest równe 2, to wtedy graf jest planarny.

Graf nr 2
- to samo co w grafie nr 1

Graf nr 3
- Da się go narysować na płaszczyźnie tak aby krawędzie nie przecinały się, zatem liczę wierzchołki: 8, krawędzie: 18, ściany: 12 (11 + ściana zewnętrzna). Teraz ze wzoru W-K+S=2 określam czy graf jest planarny. Po podstawieniu otrzymujemy faktycznie taką zależność, zatem graf nr 3 jest planarny.

Mógłby ktoś zweryfikować?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 5 cze 2017, o 21:33 
Użytkownik
Avatar użytkownika

Posty: 1229
Przypadki 1 i 2 to nie są dowody nieplanarności grafów!!! :D :D :D

PS mam dla Ciebie złą wiadomość - graf 2 jest planarny
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Grafy, liczba krawędzi  patry93  2
 Grafy proste nieskierowane  Matix16  1
 Grafy - Kod Prufera  rozpruwacz  0
 Trudne(?) grafy  rzexnik  2
 [grafy]składowe i kod Prufera  Bronia  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl