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ć?
Grafy - planarność
- jutrvy
- 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ść
Przypadki \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) to nie są dowody nieplanarności grafów!!!
PS mam dla Ciebie złą wiadomość - graf 2 jest planarny
PS mam dla Ciebie złą wiadomość - graf 2 jest planarny