Kostka Qr

dyskretny · Post autor: **dyskretny** » 31 gru 2006, o 14:16

Bardzo proszę o pomoc w rozwiązaniu zadania:

Dla jakich wartości r kostka \(\displaystyle{ Q_r}\) jest grafem planarnym?

kuch2r · Post autor: **kuch2r** » 31 gru 2006, o 17:12

dla \(\displaystyle{ r\leq 3}\)

dyskretny · Post autor: **dyskretny** » 31 gru 2006, o 18:30

Czyli dla \(\displaystyle{ r=2}\)

Kod: Zaznacz cały

http://www.mFoto.pl/

a dla \(\displaystyle{ r=3}\)

Kod: Zaznacz cały

http://www.mFoto.pl/

Jak udowodnić, że dla \(\displaystyle{ r\geq 4}\) graf nie bedzie planarny?

kuch2r · Post autor: **kuch2r** » 31 gru 2006, o 19:09

hmm...
wystarczy wykazac ze graf \(\displaystyle{ Q_4}\) zawiera podgraf \(\displaystyle{ K_{3,3}}\) lub \(\displaystyle{ K_5}\). Łatwiej chyba bedzie wykazac ze graf \(\displaystyle{ Q_4}\) zawiera pograf \(\displaystyle{ K_{3,3}}\). Gdzie \(\displaystyle{ K_{3,3}}\) jest grafem pelnym prostym.

dyskretny · Post autor: **dyskretny** » 1 sty 2007, o 21:14

ok, dzięki.