Grafy - planarność

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Akiro
Użytkownik
Użytkownik
Posty: 77
Rejestracja: 19 lis 2016, o 13:37
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 14 razy

Grafy - planarność

Post autor: Akiro »

Sprawdź planarność poniższych grafów:
(grafy w linku)

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ć?
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Re: Grafy - planarność

Post autor: jutrvy »

Przypadki \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) to nie są dowody nieplanarności grafów!!!

PS mam dla Ciebie złą wiadomość - graf 2 jest planarny
ODPOWIEDZ