Matematické Fórum

Vergil · 11. 01. 2008 10:45

Dobrý den tyto příklady jsou u nás jako zápočtové:

Kombinatorika
Trenér fotbalového družstva má k dispozici o obránců, z záložníků a u útočníků, kde o,z,u ∈ N, o,z,u≥4. Dále k záložníků, k∈ N, 3 ≤ k ≤ z, může hrát i v útoku. Kolik různých sestav může trenér vytvořit, pokud hraje systém 4-3-3, tedy 4 obránci, 3 záložníci, 3 útočníci?

Teorie grafů
Nech? každé dva cykly v souvislém cyklickém grafu G mají nejvýše jeden společný vrchol. Najděte vztah mezi počtem koster tohoto grafu a délkami jednotlivých cyklů.
Návod: Označte si délky cyklů například m1,m2,... ,mk pro k≥1 a dokažte, že pokud dva cykly C a C' nemají žádný společný vrchol, pak existuje jediná dvojice vrcholů u∈ C, v∈ C' taková, že v G existuje přesně jedna (u,v)-cesta. Tento fakt vám napoví jaká je struktura grafu.

Děkuji za jakoukoli pomoc!

Fanouš

Už dlouho jsem kombinatoriku nedělal, ale možná by ten první příklad mohl vypadat takhle:

Ale rozhodně se na to prosím někdo mrkněte, protože mi to přijde takhle nějak moc jednoduchý... A pokud je to špatně, tak mi moc nenadávejte :)

Uvažoval jsem tak, že jsem do zálohy stavěl postupně 0x záložník/útočník a 3x čisté záložníky, 1x záložník/útočník a 2x čisté záložníky a pak 2x záložník/útočník a 1x čisté záložníky a poslední jsou 3 záložník/útočník a 0 čisté záložníky. Zbytel záložníko/útočníků jsem kombinoval s útočníky do útoku. Obrana je snad dobře...

plisna · 11. 01. 2008 13:42

podle mne by to mohlo byt takto: ${o \choose 4}{z \choose 3}{u \choose 3} + {o \choose 4}{z-k \choose 3}{u \choose 2}{k \choose 1} + {o \choose 4}{z-k \choose 3}{u \choose 1}{k \choose 2} + {o \choose 4}{z-k \choose 3}{k \choose 3}$ . prvni clen rika, ze vybiram 4 obrance, 3 zalozniky a 3 utocniky, druhy clen: 4 obrance, 3 cisti zaloznici a do utoku 2 utocnici a jeden zaloznik/utocnik, analogicky zbytek, snad je to spravne.

Kondr · 11. 01. 2008 16:46

Tak já taky přidám svůj odhad:
${o \choose 4}{z \choose 3}{u \choose 3} + {o \choose 4}{z-1 \choose 3}{u \choose 2}{k \choose 1} + {o \choose 4}{z-2 \choose 3}{u \choose 1}{k \choose 2} + {o \choose 4}{z-3 \choose 3}{k \choose 3}$
Kombinatorika mi nikdy nešla, ale chybu v ůvaze taky nevidím.
1) řekněme že do útoku pošleme právě i záložníků.
2) do obrany máme (o nad 4) možností.
3) do útoku vybereme i záložníků (k nad i) způsoby a 3-i útočníků (u nad 3-i) způsoby,
máme tedy (k nad i)*(u nad 3-i) možných útoků.
4) zbylo nám z-i záložníků, z těch vybereme zálohu (z-i nad 3) způsoby
5) přes všechna možná i (tj. od 0 do 3) sečteme součiny počet_záloh*počet_útoků*počet_obran

A ke grafům: všimněme si, že pokud odstraníme z jednoho cyklu jednu hranu, počet cyklů klesne o 1. Pokud z cyklu ostraníme dvě hrany, zrušíme spojitost.

plisna · 11. 01. 2008 17:19

@ Kondr: souhlasim s tebou a tvym vysledkem, v me uvaze byla chybicka

Vergil · 11. 01. 2008 17:57

↑ Kondr:
Děkuji moc za kombinatoriku :-) Ale nejsem si zcela jist jestli chápu to s těmi grafy...Nešlo by to trošku rezvést?

Fanouš · 11. 01. 2008 18:39

Ke kombinatorice pro Kondr a Plisna:
pokud bude o=4, z=4, u=4 a k=3 (asi nejjednodušší možnost, aby to splnilo zadání), tak dle tvého vzorce budou poslední dva členy součtu 0, takže bude počet možností bude dle tvého vzoce 1.4.4+1.1.12.3=52.

Uvažujeme-li tohle triviální zadání a nasadím-li 4 obránce (1 možnost), do zálohy dám jen čisté záložníky (4 možnosti), tak podle mě, můžu nakombinovat do útoku všechy útočníky a všechy záložníko-útočníky a těch je 4+3=7 (takže 7 nad 3 = 35), takže to už je 1.4.35=140 možností a to je pouze část všech možností (podle mě)...

Co myslíte?

Kondr · 11. 01. 2008 21:37

↑ Fanouš:Myslím, že jsi špatně pochopil zadání. Záložníků je celkem z a k z nich umí hrát v útoku. Proto pro tu nejjednoduěěí možnost bude těch kombinací poměrně málo.

Kondr · 11. 01. 2008 21:47

Ke grafům: je zřejmé, že žádné dva cykly nemají společnou hranu. Každá jeho kostra vznikne tak, že z každého cyklu odstraníme právě jednu hranu (protože si můžeme vybrat jakou, máme celkem m1*m2*...*mn možných koster). Nástin důkazu: Pokud z některého cyklu žádnou hranu neodstraníme, cyklus tam zůstane a nemáme kostru. Pokud odstraníme hrany dvě, zrušíme spojitost.

Fanouš · 11. 01. 2008 22:31

↑ Kondr:
Pokud je to takhle, tak je to jasný, ale myslím, že to zadaní jde chápat dvojím způsobem, ale z té podmínky pro to k to bude jak píšeš. To slovo "Dále" jsem prostě pochopil jako další hráče...

Vergil · 12. 01. 2008 21:58

↑ Kondr:
Pokud to tedy správně chápu tak pro zadanou možnost systému 4-3-3, tedy 4 obránci, 3 záložníci, 3 útočníci bude celkem 52 možností jak sestavit tým?

Kondr · 13. 01. 2008 02:24

↑ Vergil:pokud bude systém 4-3-3 a současně o=4, z=4, u=4 a k=3, bude možností 52.

Vergil · 13. 01. 2008 18:48 — Editoval Vergil (13. 01. 2008 22:21)

↑ Kondr:
Ještě bych se chtěl ujistit jestli uvažuji správně. Pokud napíši že počet koster tomto grafu je roven - (délka cyklu 1 nad 1) * (délka cyklu 2 nad 1) * (délka cyklu n nad 1). Je moje uvaha správná?

A ještě to tvrzení, že pokud odebereme z cyklu 2 hrany přerušíme tím spojitost -> Opravdu je tomu tak vždy? A pokud ano proč?

Ještě jednou moc děkuji

Kondr · 14. 01. 2008 19:06

Vergil napsal(a):
Je moje uvaha správná?

Ano (ikdyž místo (x nad 1) stačí psát x).

Vergil napsal(a):
Opravdu je tomu tak vždy?

Pouze pokud platí, že v grafu mají dva cykly společný nejvýše jeden vrchol.

Vergil napsal(a):
A pokud ano proč?

Protože odstranění hrany (a,b) a (c,d) ze stejného cyklu způsobí, že se tímto cyklem už z a do b nedostaneme. Pokud se tam dostaneme jiným cykem, měly dva cykly společnou hranu.

Matematické Fórum

#1 11. 01. 2008 10:45

2 zápočtové příklady - kombinatorika, teorie grafů

#2 11. 01. 2008 13:19 — Editoval Fanouš (11. 01. 2008 13:24)

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#3 11. 01. 2008 13:42

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#4 11. 01. 2008 16:46

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#5 11. 01. 2008 17:19

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#6 11. 01. 2008 17:57

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#7 11. 01. 2008 18:39

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#8 11. 01. 2008 21:37

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#9 11. 01. 2008 21:47

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#10 11. 01. 2008 22:31

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#11 12. 01. 2008 21:58

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#12 13. 01. 2008 02:24

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#13 13. 01. 2008 18:48 — Editoval Vergil (13. 01. 2008 22:21)

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

#14 14. 01. 2008 19:06

Re: 2 zápočtové příklady - kombinatorika, teorie grafů

Vergil napsal(a):

Vergil napsal(a):

Vergil napsal(a):

Zápatí