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
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
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 28. 07. 2011 13:43 — Editoval Eldain (28. 07. 2011 13:44)

Eldain
Zelenáč
Místo: Olomouc
Příspěvky: 3
Reputace:   
 

Zapeklitá úloha ze života, snad kombinatorická...

Ahoj, narazil jsem na problém, se kterým fakt nehnu. Není to nějaká domácí úloha, je to problém ze života, který potřebuji vyřešit nejen pro klid duše...


Máme n prvků.
Z této skupiny chceme vytvořit nejvyšší možný počet skupinek o rozsahu k, které splňují tyto podmínky:

- každý prvek může být přítomen v libovolném množství skupinek (kátic)
- skupinky jsou bez opakování (tedy v jedné kátici nemůže být žádný prvek více než jednou)
- žádné dva prvky se spolu nesmí potkat více než jednou napříč všemi káticemi (tedy existuje-li skupinka 1,2,3,4, takuž nelze vytvořit třeba skupinu 1,2,5,6)


Když jsem na problém narazil, řekl jsem si, že to bude nějaká snadná kombinatorika... po několika hodinách jsem zjistil, že to kombinatorika asi vůbec není a snadné to není rozhodně. Zkoušel jsem to pak řešit hrubou silou - vytvářet všechny možné kátice a zapisovat jen ty, které splňují podmínky. Bohužel, v tomhle zakopaný pes není - jde o to, zjistit v jakém pořadí kátice vytvářet, abychom si zablokovali co nejmenší počet jiných kátic. Fakt už nevím, jestli si nestojím na vedení, nebo jestli ta úloha je tak brutální. Nejen, že pořád nejsem schopen vypsat hledané kátice, ale ani nejsem schopen spočítat, kolik jich lze maximálně vytvořit!

Pokud byste mě někdo nakopli, jak na to, jsem vašim dlužníkem:-)

Offline

 

#2 28. 07. 2011 14:02

Cheop
Místo: okres Svitavy
Příspěvky: 8209
Škola: PEF VŠZ Brno (1979)
Pozice: důchodce
Reputace:   366 
 

Re: Zapeklitá úloha ze života, snad kombinatorická...

↑ Eldain:
co takto?
Odkaz


Nikdo není dokonalý

Offline

 

#3 28. 07. 2011 14:49 — Editoval petrkovar (28. 07. 2011 14:53)

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

Re: Zapeklitá úloha ze života, snad kombinatorická...

↑ Eldain:Pokud požadujeme, aby každý prvek se vyskytoval ve stejném počtu k-tic a každá dvojice by se objevila v právě jedné k-tici, tak se jedná o tzv. "kombinatorický design", dokonce o speciální případ - Steinerovské čtveřice. Takový systém existuje jen pro některé počty prvků (2 nebo 4 mod 6).
Pokud nebudou naše požadavky tak striktní, dvojice se budou vyskytovat nejvýše jednou a ne každý prvek musí být ve stejném počtu k-tic, zase bude řešení záviset na n. Pro konkrétní hodnotu n bych zkoušel "napakovat" kompletní grafy $K_4$ do $K_n$. Google "packing complete graphs".

Edit: rozumím tomu dobře, že jde  ot to sestavit takový systém k-tic, nikolv jen určit nejvyšší počet k-tic, že?

Offline

 

#4 28. 07. 2011 16:44 — Editoval Eldain (28. 07. 2011 17:01)

Eldain
Zelenáč
Místo: Olomouc
Příspěvky: 3
Reputace:   
 

Re: Zapeklitá úloha ze života, snad kombinatorická...

Děkuji za bleskové odpovědi! Doufal jsem, že podobný problém je už zdokumnetovaný a zkušené oko jej rozezná a pojmenuje.

Ta podmínka, aby se každý prvek vyskytoval ve stejném počtu k-tic, se mi líbí - už když jsem psal svůj dotaz, tak jsem zvažoval, že ji zařadím mezi podmínky, ale říkal jsem si, že by to bylo už trochu moc komplikované:-) Takže tímto bych ji přidal mezi výše uvedené požadavky.

K dotazu - ano potřeboval bych ten systém k-tic sesatvit, ale i jen samotné určení jejich počtu a stanovení podmínek, kdy má příklad řešení, je poloviční výhra.

Jen poznámka k tomu Steinerovskému systému, jestli jsem jej správně pochopil (mám humanitní vzdělání, na matematickém se chystám zapracovat až od září, takže proukousat se přes matematické zápisy mi činí někdy potíže).
Opravte mě, jestli se mýlím: Steinerův systém (t = 3, k = 4, v = 8) znamená, že máme prvky 1,2,3,4,5,6,7,8 (v) a děláme z nich čveřice (k), v nichž se nesmí opakovat žádná trojice (t), nikoli dvojice, že? Jestli je to pravda, pak hledám řešení systému (t = 2, k, v), protože se žádné dva prvky nesmí potkat víc než jednou.

Když jsem hledal řešení hrubou silou, tak jsem pracoval se systémem (t = 2, k = 4, v = 64), takže ho můžeme nadále používat jako úkázku.

Nevíte o nějakém programu (či online rozhraní), co dokáže sám vypisovat řešení steinerovských systémů?

Offline

 

#5 29. 07. 2011 10:46

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

Re: Zapeklitá úloha ze života, snad kombinatorická...

↑ Eldain:Pravda ve Steinerovských systémech se nesmí opakovat trojice, špatně jsem to předtím napsal.
O on-line nástroji nevím. Odborné články jsou často k dispozici na webu.

Offline

 

#6 29. 07. 2011 14:28

Eldain
Zelenáč
Místo: Olomouc
Příspěvky: 3
Reputace:   
 

Re: Zapeklitá úloha ze života, snad kombinatorická...

Díky, stáhl jsem si knížku od Stinsona Combinatorial Designs, myslím, že tam už odpovědi najdu. Já jsem ten problém řešil kvůli designu výzkumu, takže myslím, že už jsem na dobré stopě.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson