Matematické Fórum

Návodná otázka: kolik má k-pravidelný graf na n vrcholech hran?

A hele, příklad ze sedmé sady.
↑ Olin: Nápověda je odpovídající, díky.

Mohlo by to byt takto?:
k=3, n=6 |E(G)|=9
Je mozne, ze by to platilo, pokud n=2k
Ale spise to bude mit neco spolecneho s kompletnim grafem

↑ petrkovar:
Z nejakeho duvodu, je v zadani k>=3, cili 1 a 2 muzeme vyloucit.

Pokud k = 1 (vsechny vrcholy jsou stupne 1), pak n je libovolne velikosti na mnozine celych kladnych cisel.
Pokud k = 2, pak nejmensi pocet vrcholu, ktery muze tvorit nas graf jsou 3, hrany mame take 3.
Pokud k = 3, pak nejmensi pocet vrcholu je 4 a nejvetsi pocet hran 6.
pokud si sestavim rovnici, tak mi to vychazi pro k, n takove, kdyz je jejich soucin roven dvojnasobku poctu hran:
1/2(k*n) = |E(G)|

↑ petrkovar:
Ano, veta 6.3. s tim souvisi.
Rekl bych, ze se jako odpoved ocekava predevsim teoreticke zduvodneni, dost mozna s tim souvisi sudost - viz. zminovana veta.
Takze bych odpovedel nejak takto:
2*|E(G)| je nasobek soucinu k*n prave tehdy, kdyz je n sude.
V zadani je k>=3 zrejme proto, ze takovy graf ma nutne alespon 4 vrcholy a ty jsou sude. Pokud by tam toto omezeni nebylo, pak by nasobek poctu hran nebyl napr. pri grafu zvanem trojuhelnik (hrany jen 3 - liche, stupne 2)

↑ petrkovar:
Odpoved vychazi primo z vety 6.3. "Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran." ... a proc tomu tak tedy je ?
Protoze jinak bychom dany graf nemohli nakreslit.
(proti)priklad:
(3,3,3,3,3) - soucet lichych stupnu v grafu je lichy
Nakreslime si 5 vrcholu a pri kresleni hran zjistime, ze na posledni "nevyjde".

nestačilo by napsat že pro k pravidelný graf vtesi jak 3 ma byt pocet vrcholu alespon k+1 a součet stupňu jednotlivych vrcholu sudy...?

↑ petrkovar:no tak napr kdyz mam 7-pravidelny graf o min. 7+1 vrcholech tak pokud mam takovyto graf (7,7,7,7,7,7,7,7) a 56 - pocet hran  je delitelny 7 to same kdzby bylo tech vrcholu vice jak 8 vice

↑ petrkovar:tak pro k sude musi byt pocet vrcholu n taky sudy a alespon k+1, pro k liche musi byt pocet vrcholu n sudy a minimalne k+1 to taky vyplyva z vety 6.3

↑ petrkovar:ja sem  tam jeste psal ze pro k sude musi byt n taky sude aby to dělilo, pro k liche plati to same

Proc vlastne v DIM pocitame nejake priklady kdyz se po nas vlastne chce teorie? Ja mel vzdy vzato ze nekazdy je nadany pisatel, ze staci kdyz to umim spocitat, vim k cemu to je dobre a rozumim tomu. Neekal jsem ze clovek muze vyhoret na vysvetlovani (nehlede na to ze vysvetlovat slovne je pro kazdeho jednoduzsi nez pisemne jelikoz opravujici se hned na misete muze zeptat jak to mysli). Ne kazdy umi vysvetlit tak at kazdy pochopi.