graf planarny - jak sprawdzic

assimar · Post autor: **assimar** » 9 cze 2009, o 20:39

Witam,
jest to mój pierwszy post na tym forum więc chciałbym wszystkich serdecznie powitać,

Jestem po wykładzie na temat grafów i dopiero teraz na spokojnie przetwarzając wyniknął mi problem: dajmy że mamy graf kopertę (rys. 1) można go przedstawić na dwa sposoby, pierwszy z przecinającymi się krawędziami i drugi bez "skrzyżowań", na podstawie tw w+s-k=2 stwierdzam ze graf ten jest planarny, jednak ściany mogłem odczytać tylko z drugiej wersji koperty. Teraz dajmy, że mam jakiś inny graf, którego nie potrafię przedstawić bez "skrzyżowań" (rys. 2), jak mam sprawdzić czy jest planarny?

miodzio1988 · Post autor: **miodzio1988** » 9 cze 2009, o 20:47

No łatwo możesz pokazać, że planarny on nie jest. Jesli nie spełnia tw Eulera to nie jest planarny. Musiałeś mieć na wykładzie też wnioski z tw Eulera, nie? Czy ten graf spełnia te wnioski ? ( poszukaj w necie tych wniosków, bo bardzo sie przydają w takich sprawach).

assimar · Post autor: **assimar** » 9 cze 2009, o 20:55

ok, tu masz racje ze tw eulera załatwi sprawę, ale to ze graf jest eulerowski nie Leftrightarrow jest planarny, czy istnieje jakaś uniwersalna metoda sprawdzania polarności?

miodzio1988 · Post autor: **miodzio1988** » 9 cze 2009, o 20:56

Uniwersalna? No są różne twierdzenia, które nam mówią o planarności(albo o jej braku). Poznasz je na wykładach.

assimar · Post autor: **assimar** » 9 cze 2009, o 21:00

Sorki, że nie ująłem tego w pierwszym poście, ale ja jestem w I liceum, a wykład był gościnnym wiec nie będę miał okazji zapyta osoby go prowadzącej. Czy mógłbyś mi napisać nazwy tych twierdzeń, które mogą się tu przydać, resztę wygoogluje już sam

miodzio1988 · Post autor: **miodzio1988** » 9 cze 2009, o 21:04

"Grafy planarne" - google już zrobi resztę. A kto u Was gościł?

assimar · Post autor: **assimar** » 9 cze 2009, o 21:16

Chłopak, który zdobył I miejsce w OM - Kuba Oćwieja

miodzio1988 · Post autor: **miodzio1988** » 9 cze 2009, o 21:17

assimar pisze:Chłopak, który zdobył I miejsce w OM - Kuba Oćwieja

Nie znam No ale spoko. Wszystko zatem wyjaśnione?

assimar · Post autor: **assimar** » 9 cze 2009, o 21:22

jak na razie tak, jak by coś wynikło to będę pytać dalej, dzięki.