Závěrečná práce

Moje závěrečná práce je o grafech a nese název ´Introduction to Graph Colouring and Random Walks on Graphs'. Graf je, nepřesně řečeno, matematický objekt používaný k modelování párových vztahů mezi objekty. Nechci zabíhat do detailů o výsledcích mé práce, ale rád bych se s Vámi podělil alespoň o jednu zajímavost ze světa teorie grafů:

Představte si, že pořádáte oslavu nebo jinou akci pro lidi, které neznáte – to může znít velice zvláštně, ale mnoho lidí to alespoň jednou za život udělat musí. Představte si, že chcete, aby na té oslavě byla skupina alespoň tří lidí, kteří se vůbec neznají nebo skupina alespoň tří lidí, kteří se dobře znají – to chcete, protože skupinka lidí, kteří se dobře znají, může vaši oslavu zachránit, skupinka lidí, kteří se neznají, může naopak oslavu udělat zajímavější z hlediska získávání nových kontaktů. Nyní si představte, že se ptáte sami sebe: 'Kolik lidí musím pozvat, abych měl jistotu, že tu bude skupina tří vzájemně neznámých lidí nebo skupina tří dobrých známých?' A možná už se taky slyšíte odpovídat: 'Já nevím.'

Po chvíli přemýšlení Vám dokonce může připadat, že není ani trochu zřejmé, že vůbec nějaké takové konkrétní číslo existuje. Ale ono existuje! S pomocí teorie grafů je docela jednoduché ukázat, že odpověď na naši otázku 'Kolik lidí musím pozvat, abych měl jistotu, že tu bude skupina tří vzájemně neznámých lidí nebo skupina tří dobrých známých?' je šest. Pokud bychom chtěli mít na oslavě skupinu čtyř lidí, kteří se vzájemně neznají, nebo čtyř dobrých známých, museli bychom pozvat 18 lidí.

Nyní se Vám může zdát, že zodpovědět obecně na tuto otázku není nikterak složité. Není tomu tak. Velký matematik minulého století, Paul Erdos, prý kdysi vyprávěl tento bonmot: „Představte si, že mimozemšťani oblehnou zemi a řeknou, že jí do roka zničí, pokud jim nedáme číslo R(5, 5) – počet lidí, které musíme pozvat na oslavu, abychom měli jistotu, že na ní je skupina pěti dobrých známých nebo skupina pěti lidí, kteří se vzájemně neznají. Pokud seženeme ty nejlepší hlavy naší doby a nejmodernější počítače, budeme pravděpodobně schopni do roka toto číslo najít. Pokud ale mimozemšťani budou vyžadovat číslo R(6, 6), je s námi konec.“ Paul Erdos toto řekl před více než třiceti lety, přesto stále neznáme R(5, 5). Taková lehká otázka: 'Kolik lidí musím pozvat na oslavu, abych měl jistotu, že tu bude skupina pěti vzájemně neznámých lidí nebo skupina pěti dobrých známých?' A stále odpověď neznáme. Náš svět je stále ještě plný tajemství, o tom není třeba pochybovat.