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

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

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 K_3,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).