Matematické Fórum

Matezu · 07. 12. 2019 13:10

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

laszky · 07. 12. 2019 13:37

↑ 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$ .

Matezu · 07. 12. 2019 13:50

↑ 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

Matematické Fórum

#1 07. 12. 2019 13:10

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

#2 07. 12. 2019 13:37

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

#3 07. 12. 2019 13:50

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

Zápatí