Matematické Fórum

PeterSheldon · 07. 01. 2010 13:57

Pro každý rovinný graf s právě k komponentami souvislosti odvoďte následující variantu Eulerovy formule:
n + f = e + 1 + k.
Čísla n, f a e označují po řadě počet vrcholů, počet stěn, počet hran rovinného grafu.

Poraďte mi prosím s tímto příkladem, měl jsem ho v zápočtovém testu a nepodařilo se mi ho spočítat..

Olin · 07. 01. 2010 14:14

Zkusil bych indukci podle počtu komponent. Co se stane, když k rovinnému grafu přidáme nějakou další komponentu?

PeterSheldon · 07. 01. 2010 14:18

↑ Olin:

přiznám se, že netuším... Moc jsem grafům neporozuměl.. Hledal jsem informace na wikipedii ale nic závratného jsem tam nenašel..

Olin · 07. 01. 2010 15:07 — Editoval Olin (07. 01. 2010 15:25)

Pro k=1 je to Eulerův vzorec, který platí. Předpokládejme platnost pro k, chceme dokázat pro k+1. Nechť G je nějaký rovinný graf s k komponentami, vyberme nějakou z nich a označme ji $G'$ . Jestliže z grafu G odebereme všechny hrany a vrcholy z $G'$ , dostaneme nový graf, $\check{G}$ , který je rovinný a má právě k komponent, takže pro něj platí indukční předpoklad: $n_{\check{G}} + f_{\check{G}} = e_{\check{G}} + 1 + k$ . Graf $G'$ je sám o sobě rovinný graf s jednou komponentou, takže pro něj platí Eulerův vzorec $n_{G'} + f_{G'} = e_{G'} + 2$ . Dále víme, že platí:
$n = n_{\check{G}} + n_{G'}\nl e = e_{\check{G}} + e_{G'}$
Platí však $f = f_{\check{G}} + f_{G'}$ ? Proč (ne)? Jak musíme tento vztah upravit, abychom dostali to, co chceme dokázat?

EDIT: Ještě mě napadá, že si můžeme usnadnit práci tím, že nebudeme komponentu $G'$ volit úplně libovolně, ale jen z těch komponent, jejichž některá hrana sousedí s "neomezenou" stěnou - tím zbytkem roviny okolo grafu.

Kondr · 08. 01. 2010 01:53

Pokud můžeme použít Eulerův vzorec, tak se dá použít jednoduchý trik: přidáme jeden vrchol, z něj hranu do každé komponenty. Dostaneme tak souvislý rovinný graf s v+1 vrcholy, e+k hranami a f oblastmi splňující Eulerův vzorec: (v+1)-(e+k)+f=2. Že "upravíme do poža..." už ani nebudu psát.

Pokud Eulerův vzorec použít nemůžeme, tak si najdeme jeho důkaz (indukcí přes počet vrcholů) a změníme bázový krok: místo "pro jeden vrchol tvrzení triviálně platí" napíšeme "pro k vrcholů, z nichž žádné dva nejsou spojené, tvrzení triviálně platí". Zbytek může zůstat přibližně stejný.

Olin · 08. 01. 2010 16:08

Trik s přidáním vrcholu podle mě nebude fungovat vždy - když třeba vezmeme 3 trojúhelníky a nakreslíme je dovnitř sebe (jako že ten nejmenší je uvnitř prostředního který je uvnitř největšího). Proto ten můj EDIT.

Kondr · 08. 01. 2010 17:16

↑ Olin: Máš pravdu, nedokázal jsem, že jde o invariant vzhledem k nakreslení toho grafu.

petrkovar · 08. 01. 2010 20:46

Dva postřehy:
1) jednak lze každou stěnu udělat vnější stěnou tak, že si celý graf z roviny stereometrickou projekcí zobrazíme na kouli (bez jednoho bodu, "severního pólu"), potom kouli pootočíme tak, aby kýžená oblast byla kolem severního pólu a opět stereometrickou projekcí zobrazíme zpět do roviny. Protože zobrazení je spojité, tak se zachová počet vrcholů, hran i oblastí.
2) nemusíme přidávat pomocný vrchol, ale vždy můžeme nějaké dvě komponenty spojit vhodně (snadno domyslíte jak) jednou hranou v jednu větší komponentu. Kolik bychom museli přidat hran, aby vznikl souvislý graf si snadno domyslíte.

PeterSheldon · 14. 01. 2010 20:22

↑ Olin:

No chapu-li spravne, tak reseni to uplne neni; navrhl jsi dva postupy, oba jsou
skoro dobre. F_G !=F_G* + F_G', ale necemu trochu jinemu. . Jak
sam rikas -- cemu se to ma rovnat, aby to vyslo :-)? (A ono se to tomu fakt
asi rovna.)

Eulerova formule pro kazdou komponentu a pak vse secist je dobry napad, jen
nemusi byt nutne pravda, ze dve komponenty maji svou vnejsi stenu stejnou. Kdyby
meli, tak jsem vnejsi stenu zapoctial k-krat, presne jak rikas. Jenze se muze
stat i to, ze nejaka komponenta zije uvnitr nejake stejny, napr. si nakresli
nejakou triangulaci a do nejake steny si nakresli dalsi komponentu.

Kazdopadne jsou to sice vsechny ingredience k tomu, abys libovolny z techto smeru
usmernil spravnym smerem. (BTW, ono jsou oba ty smery v
podstate jeden a ten samy argument, akorat receny jinymi slovy

PS: "neomezene" stene se rika vnejsi.

Pochopil jsem to spravne tedy?:) Opravdu jsem velice rad za tvou pomoc, pokud v me uvaze neni chyba, zacina mi to byt jasne:)

Olin · 14. 01. 2010 22:28

↑ PeterSheldon:
Tak teď nevím, jestli si úplně rozumíme, ta otázka

Olin napsal(a):
Platí však $f = f_{\check{G}} + f_{G'}$ ? Proč (ne)? Jak musíme tento vztah upravit, abychom dostali to, co chceme dokázat?

není na mě, jelikož já odpověď znám. Je to otázka na tebe, protože tady na fóru zpravidla neposkytujeme kompletní řešení, ale třeba jen začátek a pak takovéto návodné otázky, které by mohly dovést k cíli.

Správná odpověď je, že to neplatí. Nechceme, aby to platilo, protože pak bychom součtem indukčního předpokladu a Eulerova vzorce pro komponentu $G'$ dostali
$n_{G'} + n_{\check{G}} + f_{G'} + f_{\check{G}} = e_{G'} + e_{\check{G}} + 2 + 1 + k\nl n + f = e + 3 + k$ ,
my však chceme
$n + f = e + 2 + k$
(dokazujeme pro k+1), tedy asi by mělo platit
$f = f_{\check{G}} + f_{G'} - 1$ .
Zbývá si jen rozmyslet, kam ta jedna stěna zmizí (asi "splyne" s jinou stěnou…?). Jak jsem již psal, situace se zjednoduší tím, že si volíme $G'$ sousedící s vnější stěnou. Ovšem jak praví kolega petrkovar, který je v této oblasti nesrovnatelně větším znalcem než já, vhodnou projekcí lze učinit každou stěnu vnější.

Ovšem druhý bod, který kolega poznamenává, je snad ještě přínosnější. Opravdu můžeme přidáním pár vhodných hran učinit zadaný graf souvislý a na stěnách, vrcholech a rovinnosti se nic nezmění.

Matematické Fórum

#1 07. 01. 2010 13:57

rovinné grafy

#2 07. 01. 2010 14:14

Re: rovinné grafy

#3 07. 01. 2010 14:18

Re: rovinné grafy

#4 07. 01. 2010 15:07 — Editoval Olin (07. 01. 2010 15:25)

Re: rovinné grafy

#5 08. 01. 2010 01:53

Re: rovinné grafy

#6 08. 01. 2010 16:08

Re: rovinné grafy

#7 08. 01. 2010 17:16

Re: rovinné grafy

#8 08. 01. 2010 20:46

Re: rovinné grafy

#9 14. 01. 2010 20:22

Re: rovinné grafy

#10 14. 01. 2010 22:28

Re: rovinné grafy

Olin napsal(a):

Zápatí