Matematické Fórum

Sprata · 02. 12. 2008 12:19

Opět nevím odkud začít:-)? Dik moc za pomoc.

Na večírku je alespoň 6 osob. Někteří se znají a někteří ne. POZOR! Zde chápeme relaci "býti známý s" jako symetrickou relaci, tedy zná-li se x s y, tak y se zná s x. Dokažte, že mezi těmito lidmi je určitě nějaká trojice lidí, kteří se všichni navzájem znají, nebo trojice lidí, kteří se všichni navzájem neznají.
Návod: Představte si kompletní graf Kn, n≥6, jehož vrcholová množina představuje jednotlivé lidi na večírku a má dva druhy hran. Jedny symbolizují, že se koncové vrcholy znají, druhé, že se koncové vrcholy neznají.

Kondr · 03. 12. 2008 01:57

Uvažme vrchol v takovém grafu a pojmenujme ho Karel. Ostatní vrcholy jde rozdělit do dvou množin. Některé jsou s Karlem spojeny "zná se" hranou, některé "nezná se" hranou. Jedna z těchto množin je početnější, bez újmy na obecnosti ta první. Ta má alespoň tři prvky. Pokud jsou všechny vrcholy v této množině navzájem spojeny "nezná se" hranou, TADADÁ a pokud jsou mezi nimi dva spojené zná se hranou TYDYDÝ.

Co se má doplnit místo TADADÁ a TYDYDÝ? Je jasné, že jsou takto rozebrány všechny případy?

Sprata · 03. 12. 2008 09:29

Mohl by tedy tento graf vypadat nějak takhle???

Kondr · 03. 12. 2008 10:38

↑ Sprata:V zadání je napsáno, že se má uvažovat úplný graf, tedy tomu tvému nějaké hrany chybí. Po jejich doplnění by to byl jeden z možných grafů.

Folwik · 07. 12. 2008 19:52 — Editoval Folwik (07. 12. 2008 20:12)

Ahoj, mám stejné zadání a vůbec si s tím nevím rady.

Z toho, co tu psal Kondr jsem to moc nepochopil, hlavně to "Jedna z těchto množin je početnější, bez újmy na obecnosti ta první. Ta má alespoň tři prvky." ... "tadadá" a "tydydý" mi taky moc nepomohlo ... Mohly by někdo pomoct s tím jak ten příklad dokázat ... předem díky moc!

Kondr · 07. 12. 2008 20:21

Tadadá, tydydý! Takže:

Uvažme vrchol v takovém grafu a pojmenujme ho Karel. Ostatní vrcholy jde rozdělit do dvou množin. Některé jsou s Karlem spojeny "zná se" hranou, některé "nezná se" hranou. Je vidět, že pokud zaměníme pojmy "zná se" a "nezná se", projeví se to jen přejmenováním hran. Pokud je víc těch, kteří jsou s Karlem spojeni "nezná se" hranou, tak pojmy "zná se" a "nezná se" zaměníme. Odeď je víc těch, co se s Karlem znají. Aby tvožili většinu (z celkového počtu 5), musí být alespoň 3. Pokud má referát vypadat nabušeně, řekneme, že to plyne z Dirichletova principu.

Teď máme tři lidi, co se znají s Karlem. Pokud se žádní dva z nich neznají tak - tadadá - našli jsme trojici lidí, z nichž každí dva jsou spojeni "nezná se" hranou. Pokud je mezi nimi dvojice spojená "zná se" hranou, pak tato dvojice spou s Karlem tvoří trojici lidí spojených pouze "zná se" hranami.

Tadadá a tydydý mi přišlo jako zajímavý test mých "pedagogických" schopností, tedy jestli někdo pochopí můj výklad tak, aby byl s to pokračovat. Evidentně jsem selhal. Sorry.

Folwik · 07. 12. 2008 20:50

↑ Kondr:
aha .. díky moc !!!! dost mi to pomohlo :)

Slaby_matematik · 22. 11. 2009 10:43

↑ Kondr:

Dobrý den, jestli jsem to správně pochopila, tak graf od Sprata představuje jednu z možných možností, ale je neúplný. Podle mě by měla být mezi každým bodem grafu vazba (zná, nezná). Uvažuji správně? Jak by měl prosím vypadat správný graf? Lze tento příklad zapsat i nějakou obecnou matematickou rovnicí?

Děkuji za opověď

Wotton · 22. 11. 2009 19:23

↑ Kondr:
Neselhal jsi, já jsem to pochopil i s Tadadá a Tydydý:-)

Slaby_matematik · 23. 11. 2009 23:06

Ahoj, tak kdyz jsi to pochopil, tak mohl by jsi to tu vysvetlit pro mene chapave. dik

Wotton · 24. 11. 2009 10:01

Čemu přesně nerozumíš na tomhle↑ Kondr:?

Slaby_matematik · 24. 11. 2009 17:12

Jak jsem už psala dříve, tak tenhle graf představuje jednu z možných variant, ale měl by mít pro správnost všechny hrany. Je to tak? Pochopila jsem i to spojení zná se, nezná se. Ale zajímalo by mě jestli se dá tento příklad zapsat i nějakou obecnou matematickou rovnicí, když to jak píše Kondr plyne z Dirichletova principu.

Kondr · 24. 11. 2009 17:25

↑ Slaby_matematik:Ano, v grafu musí být všechny hrany. Pokud jde o rovnici, žádná mě nenapadá. Dirichletův princip říká akorát to, že když máme 5 hran dvou druhů, tak alespoň od jednoho druhu jich jsou alespoň 3. Anglicky se tomu říká pigeonhole principle. Nicméně je to zřejmé, proto jsem psal, že ani není nutné to zmiňovat jako Dirichletův princip.

Slaby_matematik · 25. 11. 2009 11:36

Děkuji za vysvětlení.

petrkovar

↑ Kondr:Tuším, v čem byl zádrhel. Dirichletův princip NENÍ rovnice. Nicméně Kondra by mohlo zajímat, že mne jedna rovnice napadá (jsem zvědam, zda následující text doputuje až do nějakého projektu). Pokud by v grafu G_1 "znají se" a G_2 "neznají se" neměl být indukovaný trojúhelník, tak by se jednalo o graf BEZ TROJÚHELNÍKŮ (anglicky "triangle -free" graf). Pro každý bychom odhadli maximální počet hran z Eulerova vzorce. Na 6-ti vrcholech tak můžeme použít předpoklad že jediný takový triangle-free graf, pro který Eulerův vztah neplatí = K_3,3. No a pak by šlo o to zjistit, zda mohu nacpat dva triangle-free grafy do K_6, tedy ověří jestli Eulerův vzorec neomezí počet hran grafů G_1 a G_2. Odpověď je záporná: neomezí, K_6 ma 15 hran a z Eulerova vztahu bychm dostali horní odhad 2*8 = 16, což je bohužel víc. Možná by úvaha šla použít pro K_7, ale tam zase bude více grafů, které jsou triangle free a nejsou planární, tedy pro ně nemůžeme použít Eulerův vzorec.

Matematické Fórum

#1 02. 12. 2008 12:19

Teorie grafu

#2 03. 12. 2008 01:57

Re: Teorie grafu

#3 03. 12. 2008 09:29

Re: Teorie grafu

#4 03. 12. 2008 10:38

Re: Teorie grafu

#5 07. 12. 2008 19:52 — Editoval Folwik (07. 12. 2008 20:12)

Re: Teorie grafu

#6 07. 12. 2008 20:21

Re: Teorie grafu

#7 07. 12. 2008 20:50

Re: Teorie grafu

#8 22. 11. 2009 10:43

Re: Teorie grafu

#9 22. 11. 2009 19:23

Re: Teorie grafu

#10 23. 11. 2009 23:06

Re: Teorie grafu

#11 24. 11. 2009 10:01

Re: Teorie grafu

#12 24. 11. 2009 17:12

Re: Teorie grafu

#13 24. 11. 2009 17:25

Re: Teorie grafu

#14 25. 11. 2009 11:36

Re: Teorie grafu

#15 01. 12. 2009 17:21 — Editoval petrkovar (01. 12. 2009 17:21)

Re: Teorie grafu

Zápatí