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
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗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
Stránky: 1 2
A hele, příklad ze sedmé sady.
↑ Olin: Nápověda je odpovídající, díky.
Offline
↑ petrkovar:
Z nejakeho duvodu, je v zadani k>=3, cili 1 a 2 muzeme vyloucit.
Offline
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)|
Offline
↑ pavelk:To jste jen jinak sformuloval princip sudosti (Věta 6.3., říkáme jí na přednášce také "Věta 1.1."). V každém grafu je součet stupňů roven dvojnásobku počtu hran.
Ale zpět k příkladu: třeba pro n=7 a k=2 má graf 7 hran, avšak |E(G)|=7 NENÍ násobek k=2.
Offline
↑ 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)
Offline
↑ 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".
Offline
↑ quardiola:A jak z toho plyne, že počet hran je dělitelný číslem k?
Všechny mysšenky se tu již objevily, stačí se správně sestavit dohromady (asi tři věty).
Máme k-pravidelný graf na n vrcholech, .... , proto je v tomto případě počet hran dělitelný číslem k.
To snad zvládne každý.
Offline
↑ 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
Offline
↑ quardiola:Ne, to není důkaz, ale jen příklad. Navíc 8-pravidelný graf na 9 vrcholech má 36 hran a 36 není násobkem 8.
Offline
↑ 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
Offline
↑ quardiola:Ano, ale to ještě není řešení zadaného příkladu 7.17. Vždyť v předchozím příspěvku máme k=8 sudé a n=9 (je alespoň k+1) a přitom k nedělí počet hran 36, že?
Offline
↑ 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
Offline
Máme k-pravidelný graf na n vrcholech, kde součin k*n je sudý (k >= 3) - každou hranu započítáme dva krát, jednou za každý její konec, proto je v tomto případě počet hran dělitelný číslem k.
Sice je to trochu neprehledne, ale veta 6.3 to rika jasne, proto si myslim, ze neni treba vetu jeste vice rozvadet.
sudé × sudé = sudé
sudé × liché = sudé
liché × sudé = sudé
liché × liché = liché
Offline
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.
Offline
↑ mysteriouss:Nějk mi není jasný předchozí OT příspěvek. (Možná zde sehrála roli i hodina příspěvku.)
Nevím o nikom, kdo by uměl VŠECHNO vypočítat a vyhořel jen díky tomu, že neumí na písemce napsat nějaké povídání o teorii. Na druhou stranu často někdo nedostale plný počet bodů, když ke svému (obvykle nepřehlednému) výpočtu nenapíše žádný komentář, přestože je v zadání požadováno, aby vysvětlil, proč někaké řešení je nebo není možné a jaké nástroje nebo vlastnosti použil (třeba Dirichletův princip, nezávoslost jevů, princip sudosti a pod.).
Offline
Stránky: 1 2