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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 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 09. 11. 2010 18:04

Lukito
Zelenáč
Příspěvky: 14
Reputace:   
 

Teorie grafů ..příklad pro pravidelný graf G

Ahoj :)
prosím dokázali byste vyřešit nebo alespoň nastínit jak vyřešit tento příklad? Děkuju :)

http://www.sdilej.eu/pics/9be69eadb5cabed092ea04b6525112b0.jpg

Offline

 

#2 09. 11. 2010 18:06 — Editoval Olin (09. 11. 2010 18:07)

Olin
Místo: Brno / Praha
Příspěvky: 2823
Reputace:   81 
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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


Matematika = královna věd. Analýza = královna matematiky. (Teorie množin = bohatství matematiky.)
MKS Náboj iKS

Offline

 

#3 09. 11. 2010 18:16

Lukito
Zelenáč
Příspěvky: 14
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ Olin:

3? :P

Offline

 

#4 09. 11. 2010 20:17

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

Offline

 

#5 09. 11. 2010 20:18

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ Lukito:Kolik je hranv celém grafu, nejde o počet hran incidentních s jedním vrcholem.

Offline

 

#6 16. 11. 2010 15:28

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

Offline

 

#7 16. 11. 2010 15:48

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

pavelk napsal(a):

Je mozne, ze by to platilo, pokud n=2k

Nejen. Například pro n=6 a k=1,2,3,4,5 tvrzení platí.

Offline

 

#8 16. 11. 2010 16:04

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

Offline

 

#9 16. 11. 2010 16:23

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ pavelk:Ano, můžeme, nicméně tvrzení platí i v těchto případech ;)

Offline

 

#10 16. 11. 2010 16:47

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

 

#11 16. 11. 2010 16:57

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#12 16. 11. 2010 17:20 — Editoval pavelk (16. 11. 2010 17:48)

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf 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)

Offline

 

#13 16. 11. 2010 21:34

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ pavelk:Do písemky bych napsal "chybí vysvětlení PROČ".

Offline

 

#14 16. 11. 2010 22:58

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#15 16. 11. 2010 23:54

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

pavelk napsal(a):

Odpoved vychazi primo z vety 6.3.

Jak? To bych chtěl odvodit.

Offline

 

#16 17. 11. 2010 08:34

quardiola
Příspěvky: 50
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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...?

Offline

 

#17 17. 11. 2010 09:04

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#18 17. 11. 2010 09:12 — Editoval quardiola (17. 11. 2010 09:13)

quardiola
Příspěvky: 50
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#19 17. 11. 2010 09:30

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#20 17. 11. 2010 10:02 — Editoval quardiola (17. 11. 2010 10:04)

quardiola
Příspěvky: 50
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#21 17. 11. 2010 10:33

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#22 17. 11. 2010 10:58

quardiola
Příspěvky: 50
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

#23 17. 11. 2010 12:24 — Editoval pavelk (17. 11. 2010 12:45)

pavelk
Příspěvky: 123
Reputace:   
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

 

#24 30. 01. 2011 04:29

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: Teorie grafů ..příklad pro pravidelný graf G

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

 

#25 30. 01. 2011 15:03

petrkovar
Veterán
Místo: Ostrava/Paskov
Příspěvky: 995
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů ..příklad pro pravidelný graf G

↑ 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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson