Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 2.11.2020 (L) Vykreslete si svůj první matematický výraz přes MathJax!
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 07. 12. 2019 13:10

Matezu
Příspěvky: 41
Škola: VŠB-TUO, Fakulta elektrotechniky a informatiky
Pozice: Student
Reputace:   
 

Důkaz - teorie grafů pomocí eulerova vztahu, problém s nerovností

Zdravím, pracuji na důkazu jednoho tvrzení z teorie grafů a k tomu budu nejspíše potřebovat využít toto tvrzení (téměř jistě).

Jednoduchý rovinný graf na $v \ge  3$ vrcholech má nejvýše $3v - 6$ hran.
Důkaz: Můžeme předpokládat, že graf je souvislý, jinak bychom mohli přidat další hrany. V daném grafu G označíme počet stěn f a počet hran h. Jelikož graf neobsahuje smyčky ani násobné hrany, je každá stěna (v libovolném nakreslení grafu G) ohraničena alespoň 3 hranami. Každou hranu na hranici oblasti započítáme nejvýše dvakrát (ve dvou přilehlých stěnách). Platí tedy $2h \ge 3f$.

Vím, jak vypadá eulerův vzorec $v + f - h=2$. Já ale nějak prostě nejsem schopný rozluštit, jak se přišlo na nerovnost $2h \ge 3f$. Každá stěna je ohraničena alespoň 3 hranami z důvodu, že 3-cyklus je nejmenší cyklus, který dokáže graf rozdělit na dvě stěny. To však znamená, že když budeme mít méně než 3 hrany, bude stěna zajisté jen 1. Zato pokud budeme mít 3 nebo více hran, tak graf bude mít 1 nebo více stěn. Proto nechápu, proč ta nerovnost nevypadá $f\le 2h$ nebo $2f\ge 3h$. Asi nějak nechápu, co ta nerovnost představuje, když mi nedává smysl ani věta "Každou hranu na hranici oblasti započítáme nejvýše dvakrát". Jak můžeme jednu hranu počítat dvakrát?

Mohli byste mě, někdo, prosím naťuknout správným směrem? Děkuji

Offline

 

#2 07. 12. 2019 13:37

laszky
Příspěvky: 1925
Škola: MFF UK, FJFI CVUT
Reputace:   161 
 

Re: Důkaz - teorie grafů pomocí eulerova vztahu, problém s nerovností

↑ Matezu:

Ahoj, v rovinnem grafu jsou dva typy hran. Ty ktere tvori hranici mezi dvema stenami (mnozina $E_1$) a ty, ktere netvori hranici mezi dvema stenami (mnozina $E_2$). Velikost noziny $E_1$ muzeme odhadnout pomoci poctu sten. Protoze kazda stena je ohranicena minimalne tremi hranami, plati

$|E_1| \geq \frac{1}{2}\cdot 3f$

Cislo 3f musime vydelit 2, protoze kazda hrana z $E_1$ lezi ve dvou stenach a pocitali bychom ji tedy dvakrat. Celkem proto plati

$h = |E_1| + |E_2| \geq \frac{1}{2}\cdot 3f $

Takze $2h\geq 3f$.

Poznamka: Napriklad graf ve tvaru hvezdy (vsechny hrany maji jeden spolecny vrchol) je rovinny graf, ktery ma libovolny pocet hran, ale jen jednu stenu.
Je tedy jasne, ze pokud existuje nejaka nerovnost mezi h a f, musi byt tvaru $\alpha\, h\; {\color{red} \geq}\; \beta\,f$.

Offline

 

#3 07. 12. 2019 13:50

Matezu
Příspěvky: 41
Škola: VŠB-TUO, Fakulta elektrotechniky a informatiky
Pozice: Student
Reputace:   
 

Re: Důkaz - teorie grafů pomocí eulerova vztahu, problém s nerovností

↑ laszky:
Díky moc, konečně mi to vlezlo do hlavy, stačilo se na to podívat z trošku jiného úhlu.
Jinak v mém případě jde o 2-souvislý rovinný graf s obvodem minimálně 6, takže množina hran, které neoddělují dvě stěny je 0. Samozřejmě v mém důkaze nebude figurovat fakt, že stěny oddělují minimálně 3 hrany, ale 6 hran, ale principiálně je to stejné. Ještě jednou děkuji

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson