Bardzo proszę o pomoc w rozwiązaniu zadania:
Dla jakich wartości r kostka \(\displaystyle{ Q_r}\) jest grafem planarnym?
Kostka Qr
-
- Użytkownik
- Posty: 4
- Rejestracja: 12 lis 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 1 raz
Kostka Qr
Czyli dla \(\displaystyle{ r=2}\)
a dla \(\displaystyle{ r=3}\)
Jak udowodnić, że dla \(\displaystyle{ r\geq 4}\) graf nie bedzie planarny?
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
- Użytkownik
- Posty: 2302
- Rejestracja: 18 paź 2004, o 18:27
- Płeć: Mężczyzna
- Lokalizacja: Wrocław/Ruda Śląska
- Podziękował: 9 razy
- Pomógł: 408 razy
Kostka Qr
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.
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.