Matematické Fórum

lucinka1991 · 05. 12. 2011 11:29

ahoj,som zo Slovenska a mam problem s jednim zadanim na Teoriu grafov.Uz som uplne zufala tak hladam nejakeho dobreho cloveka co by mi pomohol.
Zadanie znie: Určte, pre ktoré hodnoty a,b,c je graf $K_{a},_{b},_{c}$ hamiltonovský.
Prosim pomozte mi,mam z toho len klasifikovany zapocet a je za to 20 bodov...
Vopred vdaka.

petrkovar · 05. 12. 2011 11:40

↑ lucinka1991:Nápověda: je hamiltonovský graf $K_{1,1,3}$ a $K_{1,2,3}$ ? A co $K_{1,4,100}$ ?

lucinka1991 · 05. 12. 2011 11:49

↑ petrkovar:
Ja praveze neviem zistit co znamenaju tie indexy, $K_{3},_{3}$ viem ako vyzera ale ked tam su 3 cisla...

petrkovar · 05. 12. 2011 21:33

↑ lucinka1991:Jedná se o tzv. kompletní tripartitní graf.
Popíšeme $K_{1,2,3}$ . Máme tři množiny vrcholů, 1-prvkovou, 2-prvkovou a 3-prvkovou.
Dva vrcholy spojíme hranou právě tehdy, když patří do různých partit. Zkuste si graf nakreslit. Kolik bude mít hran? Mělo by jich v obrázku být 11.

lucinka1991

↑ petrkovar:
ano nakreslila som, a vyslo mi 11 hran.tento ale asi nie je hamiltonovsky ked nema stupen vrchola delitelny 2?A pri K1,1,3 mi vysiel pocet hran 7.

petrkovar · 05. 12. 2011 23:56

↑ lucinka1991:Pozor, neplést eulerovské grafy a hamiltonovské grafy.
Graf $K_{1,2,3}$ hamiltonovký je. Označím vrcholy v nejmenší partitě $u_1$ , v druhé partitě $v_1, v_2$ a v největší partitě $w_1, w_2, w_3$ . Cyklus $u_1, w_1, v_1, w_2, v_2. w_3, u_1$ je hamiltonovský, protože obsahuje všechny vrcholy grafu.

lucinka1991 · 06. 12. 2011 00:40

↑ petrkovar: aj K 1,1,3 je hamiltonovsky?pretoze sa mi to nejak nedari nakreslit,stale sa mi bud hrany pretnu alebo cez jeden vrchol prejdem 2x.

petrkovar · 07. 12. 2011 19:06

↑ lucinka1991:Ne, graf $K_{1,1,3}$ hamiltonovský není.V největší partitě jsou tři vrcholy. Mezi nimi není žádná hrana. Proto musíme z každého ze tří vrcholů jít do jiného vrcholu ve zbývajících partitách. To nejde.

lucinka1991 · 07. 12. 2011 21:05

↑ petrkovar: mohla by tam platit podmienka $b+c\ge a , a+c\ge b , a+b\ge c$ ??

petrkovar · 08. 12. 2011 11:51

Ano, tato podmínka je nutná.
Ale je i dostatečná, jak se dá ukázat ptřeba pomocí Diracovy nebo Oreho věty.

lucinka1991 · 08. 12. 2011 13:36

↑ petrkovar:
cize to je vlastne riesenie tej ulohy?

petrkovar · 08. 12. 2011 19:22

Já bych čekal, že ještě je nutno stanovit intervaly pro $a,b,c$ . Přitom budou muset být splněné podmíny uvedené výše.

lucinka1991 · 08. 12. 2011 20:35

↑ petrkovar:
hm tak to ma vobec nic nenapada, bude to mat nieco spolocne s hranami(ci je parny pocet alebo neparny?)?

petrkovar · 08. 12. 2011 21:47

Ale kdepak. Ale jistě musí každý z parametrů $a,b,c$ být přirozené číslo (ne záporná čísla, desetinná, ani 0).

lucinka1991 · 08. 12. 2011 21:51

↑ petrkovar:
no to mi je jasne,ale netusim teda ako tie intervaly vytvorit...

petrkovar · 09. 12. 2011 19:15

Řekl jsem to neobratně. Množina přirozených čísel je "interval" celých čísel.
Zkrátka musíme vymezit, co za $a,b,c$ dosadit můžeme a co ne. No a správná formulace je už v mém předchozím příspevku. Pokud v vyřešení stačí *říct* nikoliv *dokázat* nutnos a dostatečnosot nerovností $b+c\ge a , a+c\ge b , a+b\ge c$ , tak je příklad vyřešen.

lucinka1991 · 09. 12. 2011 21:46

↑ petrkovar:
hm,tak v zadani pisu len ,ze Urcte pre ktore hodnoty,tak neviem. Ten dokaz je zlozity? Alebo cim by som mala zacat?

petrkovar · 10. 12. 2011 15:59

↑ lucinka1991:Doporučuji začít tím, že si vyhledáte Diracovu a Oreho větu. Brali jste ji?

lucinka1991 · 10. 12. 2011 16:03

↑ petrkovar:
bohuzial nie,nasla som si ich na wikipedii,tam je aj nejaky dokaz ale vobec mu nerozumiem.

petrkovar · 10. 12. 2011 16:28

A co ve skriptech? V učebnici?

lucinka1991 · 10. 12. 2011 16:47

↑ petrkovar: nemame ziadnu literaturu k tomuto predmetu,on to je volitelny predmet kde mame za projekt 50 bodov,za tuto ulohu 20 a pisomnu pracu 30(na tu sme sa ucili z poznamok z cviceni).Mame len klasifikovany zapocet cize nikto sa tomu velmi nevenoval do hlbky,tak ani spoluziaci mi nevedia pomoct.

petrkovar · 10. 12. 2011 21:59

Inu můžete se podívat na stranu 35 sem nebo na stranu 115 sem.

lucinka1991 · 12. 12. 2011 17:55

↑ petrkovar:
mame K1,2,3 ked na tento priklad aplikujeme Oreho vetu: dostanem pre moj priklad 2(b+c)>=a+b+c co je po uprave b+c>=a

cize plati Ka,b,c je hamilonovsky => b+c>=a
budem to dokazovat sporom cize znegujem vyrok: Ka,b,c je hamiltonovsky $\wedge$ b+c<a

Ak vezmem ze $a$ ma najvyssiu hodnotu a mozem ho spojit hranou iba s $b,c$ (kedze vrcholy rovnakej farby nemozu byt spojene) a sucet $b,c$ je mensi ako $a$ ,nakoniec sa dopracujem do bodu ked uz nebudem moct $a$ spojit s $b$ alebo $c$ a budem nutena ist do $a$ => spor,nie je hamiltonovska kruznica pritomna cize plati prvy predpoklad $b+c\ge a$

mohlo by to takto davat zmysel?

petrkovar · 12. 12. 2011 20:17

lucinka1991 napsal(a):
↑ petrkovar:
mame K1,2,3 ked na tento priklad aplikujeme Oreho vetu: dostanem pre moj priklad 2(b+c)>=a+b+c co je po uprave b+c>=a

cize plati Ka,b,c je hamilonovsky => b+c>=a

Ne. Oreho věta udává dostatečnou, nikoliv nutnou podmínku pro existenci hamiltonovského cyklu.
Oreho větu bych použil pro zdůvodnění implikace: pokud $b+c\geq a$ ( $a$ je největší), tak víme. že $K_{1,2,3}$ je hamiltonovský.

Naopak zbytek argumentace ukazuje, že pokud graf je hamiltonovský, musí být splněny nějaké nerovnosti.

lucinka1991 · 12. 12. 2011 20:27

↑ petrkovar:
aj ten dokaz je zle?ja uz potom fakt neviem ako to ma byt...

Matematické Fórum

#1 05. 12. 2011 11:29

Hamiltonovsky graf

#2 05. 12. 2011 11:40

Re: Hamiltonovsky graf

#3 05. 12. 2011 11:49

Re: Hamiltonovsky graf

#4 05. 12. 2011 21:33

Re: Hamiltonovsky graf

#5 05. 12. 2011 23:34 — Editoval lucinka1991 (05. 12. 2011 23:37)

Re: Hamiltonovsky graf

#6 05. 12. 2011 23:56

Re: Hamiltonovsky graf

#7 06. 12. 2011 00:40

Re: Hamiltonovsky graf

#8 07. 12. 2011 19:06

Re: Hamiltonovsky graf

#9 07. 12. 2011 21:05

Re: Hamiltonovsky graf

#10 08. 12. 2011 11:51

Re: Hamiltonovsky graf

#11 08. 12. 2011 13:36

Re: Hamiltonovsky graf

#12 08. 12. 2011 19:22

Re: Hamiltonovsky graf

#13 08. 12. 2011 20:35

Re: Hamiltonovsky graf

#14 08. 12. 2011 21:47

Re: Hamiltonovsky graf

#15 08. 12. 2011 21:51

Re: Hamiltonovsky graf

#16 09. 12. 2011 19:15

Re: Hamiltonovsky graf

#17 09. 12. 2011 21:46

Re: Hamiltonovsky graf

#18 10. 12. 2011 15:59

Re: Hamiltonovsky graf

#19 10. 12. 2011 16:03

Re: Hamiltonovsky graf

#20 10. 12. 2011 16:28

Re: Hamiltonovsky graf

#21 10. 12. 2011 16:47

Re: Hamiltonovsky graf

#22 10. 12. 2011 21:59

Re: Hamiltonovsky graf

#23 12. 12. 2011 17:55

Re: Hamiltonovsky graf

#24 12. 12. 2011 20:17

Re: Hamiltonovsky graf

lucinka1991 napsal(a):

#25 12. 12. 2011 20:27

Re: Hamiltonovsky graf

Zápatí