i

Aktuální číslo:

2020/5

Téma měsíce:

Sítě

Slavné kombinatorické problémy a počítačové důkazy

 |  11. 11. 2019
 |  Vesmír 98, 628, 2019/11
 |  Téma: Ceny Neuron

Představme si tři sousedy žijící ve třech domech. Každý z nich by rád připojil svůj dům ke zdroji vody, plynu a elektřiny, ale nikdo nechce, aby se některý ze spojů křížil s ostatními. Dokážeme pak v rovině domy se zdroji propojit?

Kombinatorika a teorie grafů jsou rozlehlými oblastmi matematiky a teoretické informatiky, které řeší řadu problémů majících uplatnění i v reálném životě, například při rozvrhování či hledání nejkratších cest v GPS navigaci. Nalezneme zde spoustu úloh, jejichž zadání je velmi snadno srozumitelné, a přesto najít jejich řešení může být nesmírně obtížné. Ukážeme si dva takové slavné problémy, které zůstávají i po desítkách let nevyřešené. U obou se ale v nedávné době podařilo dosáhnout významných pokroků, často za použití počítačů.

„Známe způsob, jak položit koleje s pravděpodobně minimálním počtem křížení, ale těžkou částí Turánova problému je ukázat, že lépe už to nejde.“

Grafová nakreslení a křížení

V úvodu popsaný problém, zvaný „problém inženýrských sítí“, je velmi starý a odpověď na něj je dobře známá: bez křížení není možné domy se zdroji propojit. Ať už spojení v rovině vedeme jakkoliv, vždy se aspoň jedno křížení objeví. Problém si můžeme představit abstraktněji. Máme šest bodů v rovině a tři z nich chceme spojit čárami s každým ze zbylých tří bodů. Neboli jsme problém přeformulovali jako otázku existence nakreslení grafu K3,3 bez křížení hran (graf zde není chápán jako graf funkce, ale jako kombinatorický objekt, který má vrcholy a některé páry vrcholů jsou v něm spojené hranou).

Nyní vidíte 17 % článku. Co dál:

Jsem předplatitel, mám plný přístup
Jsem návštěvník
Chci si přečíst celé číslo
Předplatným pomůžete zajistit budoucnost Vesmíru. Více o předplatném
TÉMA MĚSÍCE: Ceny Neuron
OBORY A KLÍČOVÁ SLOVA: Matematika

O autorovi

Martin Balko

RNDr. Martin Balko, Ph.D., (*1987) vystudoval MFF UK v Praze. Poté byl postdoktorandem v Alfréd Rényi Institute of Mathematics v Budapešti a na Ben Gurionově univerzitě v izraelské Beer Ševě. Nyní je odborným asistentem na katedře aplikované matematiky MFF UK, kde se věnuje kombinatorice, diskrétní geometrii a Ramseyově teorii. Roku 2017 dostal cenu Josefa Hlávky pro nejlepší studenty. V roce 2019 získal Cenu Neuron pro mladé nadějné vědce v oboru computer science.
Balko Martin

Další články k tématu

Zabití ekonomikou

„Silná ekonomika vám může zlomit srdce,“ napsal v roce 2007 americký ekonom Christopher Ruhm. [1] Narážel tím na dobře zdokumentovaný paradox...

Černí pasažéři: přehlížená invaze hubuzamčeno

Před více než 100 tisíci lety se moderní člověk začal šířit z Afriky do všech koutů světa. Migrace a cestování se od té chvíle staly jedněmi z...

Chvála pozitivní zpětné vazby

Ústředním tématem letního dvojčísla Vesmíru byla zpětná vazba. Nemohli jsme se věnovat zdaleka všem oblastem, v nichž hraje nějakou roli; mimo...

Nahoře, dole: polarita v rostlinné biologii

Každé malé dítě ví, že rostliny mají stonek či kmen s větvemi, listy a květy, které rostou vzhůru, a pod zemí kořeny rostoucí naopak směrem dolů....

Kde začíná a končí nádor?uzamčeno

Rakovina je velmi široký pojem, pod kterým se skrývá velké množství onemocnění s podobnou charakteristikou. Stejně tak samotný tumor netvoří pouze...

„Nové hvězdy“ na oblozeuzamčeno

„Nové hvězdy“ narušují zdánlivou neměnnost hvězdné oblohy. Jejich zkoumání fascinuje lidstvo odnepaměti, ale teprve v posledním století jsme...

Zdvojení genomu jako evoluční příležitostuzamčeno

Mutace jsou „palivem“ evoluce – vytvářejí genetickou variabilitu, z níž pak může selekce vybírat vhodné kombinace alel, což vede například k novým...

Doporučujeme

Čmeláci vyřešili Molyneuxův problém

Čmeláci vyřešili Molyneuxův problém audio

Jaroslav Petr  |  24. 5. 2020
„Když se nevidomý člověk naučí hmatem rozeznat různé předměty, pozná je na první pohled, když se mu navrátí zrak?“ ptal se už v roce 1688 William...
Jim Peebles a dospívání kosmologie

Jim Peebles a dospívání kosmologie

Giovanni Acquaviva  |  4. 5. 2020
Moderní kosmologie objevila nové složky hmoty a energie vesmíru. Za teoretické objevy v kosmologii byla v roce 2019 polovina Nobelovy ceny za...
Na pláže, pojďme na pláže…

Na pláže, pojďme na pláže…

Petr Jan Juračka  |  4. 5. 2020
Věřím, že mi Ivo Jahelka odpustí, že jsem si pro titulek k tomuto článku vypůjčil slova jeho slavného songu Případ nudisty Bédi Šulisty. Lepší...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné