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 01. 12. 2010 23:52

Sedlak
Příspěvky: 29
Reputace:   
 

Projekt 3

Dobrý den (večer),
dneska jsem slyšel  o větě  kolik může být v jakémkoli grafu hran pokud graf neobsahuje trojúhelníky, nemůžu si ale vspomenout jak se ta věta jmenovala a kontakt na člověka který mi o ní říkal nemám. Pomohl byste mi prosím ze zaspomínání jaký je název té věty? 
děkuji Petr Sedláček

Offline

 

#2 02. 12. 2010 11:53

Fail
Zelenáč
Příspěvky: 4
Reputace:   
 

Re: Projekt 3

↑ Sedlak:
Myslim, ze taka veta nie je, ak ano tak ma opravte, velmi by to pomohlo aj mne keby taka bola :]
Asi si to pleties s dosledkom Eulerovho vzorca, tento dosledok hovori, ze v jednoduchom rovinnom grafe na  v=>3 vrcholoch bez trojuholnikov je najviac 2v-4 hran. Toto plati len pre rovinne grafy, ty sa vsak pytas ci nieco take plati pre "vseobecny" graf.

Presne tuto vetu pre vseobecny graf by som potreboval aj ja, s nou by bolo toto zadanie lahko riesitelne. Mozes vyuzit aj vyssie spomenuty dosledok, ale ten ti bude platit len po graf K5, tento kompletny graf uz nie je rovinny.
Ak sa mylim, opravte ma :]
Tymto sa chcem opytat, ci je mozne nejakym sposobom vyuzit tento dosledok aj pre kompletne grafy s v>5.
Dakujem

Offline

 

#3 02. 12. 2010 16:46

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

Re: Projekt 3

Zmíněná věta udávající OSTRÝ horní odhad počtu hran v grafu bez trojúhelníků existuje. Její tvrzení a zejména důkaz však jsou nad rámec našeho kurzu. To, co se po vás chce v projektu je výrazně jednodušší. Zatím nikdo neoperoval s nápovědou - použit metodu dvojího počítání.
Co se bude počítat dvěma způsoby?

Offline

 

#4 03. 12. 2010 12:02

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

Re: Projekt 3

Nápověda:
metodou dvojího počítání je vhodné použít tak, že dvěma způsoby spočítáme kolik existuje v kompletním grafu různých trojúhelníků $v_1, v_2, v_3$, které obsahují hranu $xy$.
Tuto nápovědu jsem přidal i na web do zadání projektu.

Offline

 

#5 03. 12. 2010 12:05 — Editoval Fail (03. 12. 2010 12:06)

Fail
Zelenáč
Příspěvky: 4
Reputace:   
 

Re: Projekt 3

↑ petrkovar:
Dalo by sa postupovat aj inym sposobom bez vyuzitia metody dvojiho pocitani ? Konkretne by som vyuzil kompletne bipartitne grafy. Neviem ci mozem rozpisovat viac aby som neodhalil mozne riesenie.
Dakujem

Offline

 

#6 03. 12. 2010 12:17

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

Re: Projekt 3

↑ Fail:Ne každý graf, který splňuje zadání úlohy je bipartitní a proto ani kompletní bipartitní.
Například Petersenův graf neobsahuje trojúhelník, ale není bipartitní. Proto ani řešení založené na argumentaci o úplných bipartitních grafech není správně (není úplné).

Offline

 

#7 03. 12. 2010 16:16

Platan
Zelenáč
Příspěvky: 2
Reputace:   
 

Re: Projekt 3

Sedím vcelku nad tím už dlouho, ale nemůžu pořád na nic přijít. Je ještě nějaká nápověda, která by mě nakopla a rozhýbala mě z mrtvého bodu??

Offline

 

#8 03. 12. 2010 16:57

kotipelto
Místo: Klimkovice
Příspěvky: 40
Škola: VŠB
Pozice: Z půli student z půli těžce pracující
Reputace:   
 

Re: Projekt 3

Ale pokud se nepletu, tak potřebujeme zjisti, kolik existuje všech trojúhelníků v kompletním grafu.

Offline

 

#9 03. 12. 2010 17:32

Fail
Zelenáč
Příspěvky: 4
Reputace:   
 

Re: Projekt 3

Viem zistit kolko je v kompletnom grafe roznych trojholnikov, viem spocitat 2 sposobmi v kolkych trojuholnikoch sa nachadza hrana xy, ale neviem co dalej :D.. Snad uz som blizko a staci si len daco vsimnut

Offline

 

#10 03. 12. 2010 20:33

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

Re: Projekt 3

↑ Fail:A jaký je počet hran je v našem grafu? Jaký je vztah tohoto počtu k počtu trojúhelníků?

Offline

 

#11 04. 12. 2010 12:03

zlamal89
Příspěvky: 26
Reputace:   
 

Re: Projekt 3

Lidi vůbec nevím jak tohle vypočítat. Marně v zadání hledám nějaké grafy nebo trojúhelníky.

Offline

 

#12 04. 12. 2010 12:11

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

Re: Projekt 3

↑ zlamal89:Zkuste si nejprve zodpovědět, s jakým grafu pracujeme.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson