grafy planarne

duch200 · Post autor: **duch200** » 19 kwie 2007, o 18:42

Graf jest planarny wtedy i tylko wtedy gdy nie zawiera podgrafu homeomorficznego z \(\displaystyle{ K_{5}}\) lub \(\displaystyle{ K_{3,3}}\)

Nie rozumiem tego - można to jakoś łatwiej powiedzieć kiedy graf jest planarny ?

Bo np. nie wiem dlaczego grafy \(\displaystyle{ K_{8}; K_{3,5}}\) nie są planarne a np. \(\displaystyle{ K_{2,77}}\) jest planarny ?

kuch2r · Post autor: **kuch2r** » 20 kwie 2007, o 13:14

duch200 · Post autor: **duch200** » 20 kwie 2007, o 16:35

czyli z wikipedii wynika że: graf jest planarny wtedy i tylko wtedy gdy liczba krawędzi jest mniejsza lub równa 3 razy liczba wierzchołków - 6

I mamy np. graf \(\displaystyle{ K_{5}}\) więc:
jego liczba krawędzie to: \(\displaystyle{ \left\ ( \begin{array}{c}
5 \\
2 \\

\end{array}\right)=10}\)

liczba wierzchołków to: 5

\(\displaystyle{ 10 }\)

kuch2r · Post autor: **kuch2r** » 20 kwie 2007, o 16:41

od kiedy graf \(\displaystyle{ K_5}\) jest planarny ?

duch200 · Post autor: **duch200** » 20 kwie 2007, o 16:52

przepraszam - pomyłka - ale i tak coś nie gra - graf \(\displaystyle{ K_{3,3}}\) - to graf dwudzielny

jego liczba krawędzie to: \(\displaystyle{ 3*3=9}\)

liczba wierzchołków to: 3+3=6

\(\displaystyle{ 9 }\)

kuch2r · Post autor: **kuch2r** » 20 kwie 2007, o 19:26

to ze zachodzi ta nierownosc nie wynika ze graf jest planarny.