i

Aktuální číslo:

2019/11

Téma měsíce:

Ceny Neuron

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

Č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...

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...

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

Sekvenační data pomáhají odhalit globální rozšíření hub

Sekvenační data pomáhají odhalit globální rozšíření hub

Petr Baldrian  |  14. 11. 2019
Pokud vezmeme v úvahu, kolik dat získaných sekvenačními metodami (tzv. high-throughput-sequencing) je v současné době k dispozici, je možné se...
Probouzení nesmrtelnosti

Probouzení nesmrtelnosti

Marek Janáč  |  11. 11. 2019
Nesmrtelnost – věčná touha a hybatelka dějin života na planetě Zemi. V biologickém slova smyslu žene k plození potomstva, ve smyslu duchovním k...
Zabití ekonomikou

Zabití ekonomikou

Lucie Kalousová  |  11. 11. 2019
„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...

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é