#1 05. 01. 2010 16:53
- SweetNelli
- Příspěvky: 110
- Reputace: -1
Eulerova formule
Prosím Vás jak se z Eulerovy formule odvodí, že rovinné grafy bez trojúhelníku s n >= 3 vrcholy mají nejvýše 2n - 4 hran?
Offline
#2 06. 01. 2010 16:02
Re: Eulerova formule
↑ SweetNelli:Využije se, že každá oblast rovinného grafu má na obvodu alespoň čtyři hrany. Proto 1/2*4*o<e (o..počet oblatí, e..počet hran)
Ta 1/2 je tam proto, že každá hrana se takto počítá dvakrát (proč?).
Offline
#3 06. 01. 2010 16:16
- PeterSheldon
- Příspěvky: 128
- Reputace: 0
Re: Eulerova formule
↑ petrkovar:
pročpak má na obvodu alespon 4 hrany?
Offline
#4 06. 01. 2010 16:38
Re: Eulerova formule
↑ PeterSheldon:protože je bez trojúhelníků (=cyklů délky tři).
Mimochodem, podobně se dá odvodit, že Petersenův graf není planární, pokud ovšem víme, že Petersenův graf má obvod 5 (obvod je délka nejkratšího cyklu v grafu).
Offline