Katedra aplikované matematiky

Kombinatorika a teorie grafů

Zde bude paginace a název tématu

Zkusíme představit naši disciplínu prostřednictvím několika „hádanek“ – krátkých problémků, o kterých můžete zkusit přemýšlet. Kombinatorika a teorie grafů je šťastná disciplína – je zde blízko od takovýchto hádanek k řešení skutečných problémů. Chcete to taky zkusit? Zkušenosti ukazují, že je to zábava, ale i dobrá průprava pro mnohá pracovní uplatnění.

Úhlopříčky Nakreslíme všechny úhlopříčky v nepravidelném (konvexním) mnohoúhelníku. Protože mnohoúhelník byl úplně nepravidelný, žádné tři úhlopříčky se neprotnou v jednom bodě. Na obrázku je to nakresleno pro šestiúhelník, kdy dostaneme celkem 15 průsečíků (červené body). Kolik průsečíků dostaneme pro dvacetiúhelník?

Počítání stromů Na obrázku je všech pět „binárních stromů se třemi vrcholy“. Kolik je binárních stromů se čtyřmi, pěti, ... vrcholy? Jde to zjistit bez kreslení všech možností?

Ramseyova čísla V každé skupině šesti lidí je trojice, kde se všichni navzájem znají nebo trojice, kde nikdo nezná nikoho. (Proč?) Pro skupinu pěti lidí toto neplatí. (Proč?) Toto zapíšeme R(3)=6. O dost těžší je ukázat R(4)=18. Spočítat R(5) nikdo neumí. Ví se ale, že každá velká struktura obsahuje nějakou pravidelnost.

Barvení grafů Každá mapa, kde každý stát má souvislé území, jde vybarvit čtyřmi barvami tak, že sousední státy mají různou barvu (sousedství „přes roh“ se nepočítá). Tohle je pravda, ale matematikům trvalo téměř 150 let, než objevili zdůvodnění, které je správné a obecně uznávané. Jeden z autorů tohoto důkazu, Robin Thomas, je bývalý student naší fakulty. Podaří se vám najít zdůvodnění pro lehčí verzi s pěti (šesti, …) barvami?

Web: http://kam.mff.cuni.cz

Významné projektyEU projekt Graph Drawings and Representations (2011-2013) http://kam.mff.cuni.cz/gradr/

Téma: vizualizace grafů

EU projekt Classes of Combinatorial Objects - from Structure to Algorithms (2010-2015)

http://kam.mff.cuni.cz/ccosa/

Téma: struktura kombinatorických objektů

Institut teoretické informatiky

(2000-2011)

http://iti.mff.cuni.cz/

Studenti jsou partneřikam.mff.cuni.cz/prezentace

Zapojení do vědy a výzkumu Studenti jsou zapojováni do práce na výzkumných projektech. Některým se již během bakalářského studia podaří publikovat články v prestižních časopisech a jezdí na mezinárodní workshopy a konference.

Jarní škola kombinatoriky Pravidelná akce pro naše studenty.

Netradiční výuka youtu.be/PEBUYt8LgkY

Zde bude paginace a název tématu

Příběh z vězení Ve věznici ve městě N hraje ředitel se všemi svými 100 vězni tuto krutou hru. Do 100 skříněk ve své pracovně umístil jejich jména, jedno v každé skříňce, a postupně si k sobě vězně povolává. Každý smí nahlédnout do některých 50 skříněk, pak jsou uzavřeny a vězeň musí opustit ředitelovu pracovnu a s ostatními se nemůže domlouvat. Pokud každý ze sta vězňů v některé z otevřených skříněk najde své jméno, budou všichni propuštěni na svobodu. Pokud však byť i jeden z nich selže a v padesáti otevřených skříňkách své jméno nenalezne, budou všichni vězňové popraveni. Mohou si vězňové předem domluvit vhodný postup, který jim dá alespoň nějakou šanci na přežití?

Vězeň A: Každý otevřeme prvních 50 skříněk, je to všechno jedno.

Vězeň B: Pak nás jistě všechny popraví!

Vězeň C: Každý otevřeme nějakých 50 skříněk, třeba náhodně. S 50% šancí nalezneme své jméno. Celkem máme šanci na přežití (1/2) krát (1/2) krát ... krát (1/2) (100 krát), neboť vzájemně nezávislé šance se násobí. Vychází to zhruba nula celá nula, třicet nul, sedmička a nějaké drobné. Ne mnoho, ale lepší než nic ...

Ostatní vězni: Jdi do …

Vězeň D: Já znám mnohem lepší postup, který nám všem zajistí více než 30% šance na přežití. Není to 100% – to ani nelze – ale stále lepší než ta nula celá nula nula nic. Budeme postupovat takto …

Zkuste se zamyslet nad několika otázkami a zodpovědět je. Nejprve lehčí. Proč návrh Vězně A dává nulovou šanci přežití? Proč Vězeň C šance mezi sebou násobil? Věřili byste Vězni D, kdyby sliboval postup se 70% šancí na přežití? A teď ta nejtěžší a nejzajímavější – jaký postup tedy dává 30% šanci na přežití?

Některé z uvedených hádanek jsou lehčí, jiné těžší až velmi těžké. Jejich řešení lze nalézt na webu http://kam.mff.cuni.cz/resenihadanek

Kombinatorika a teorie grafů zkoumá konečné struktury, které modelují vztahy mezi konečným počtem objektů (třeba silnice mezi městy). Má četné aplikace – hledání nejkratší cesty (navigace, hledání v jízdních řádech), rozvrhování (předmětů ve škole, nebo realizaci proměnných v programu registry počítače), analýza chování datových struktur (četnost přístupů do paměti, očekávaná časová složitost), a další.

Kombinatorika a teorie grafů patří mezi disciplíny, ke kterým stačí papír a tužka; proto můžeme pořádat přednášky i na neobvyklých místech. Náš student Jan Hladký přednáší na Jarní škole ve Vysoké Lípě.