Foto: Cmglee / CC BY-SA

Vedci desaťročia hľadali vhodný algoritmus na riešenie úloh z teórie grafov.

Začiatkom 90. rokov ju vyriešiť nedokázali, matematickú záhadu preto takpovediac odložili do zásuvky. Po niekoľkých desaťročiach sa o ňu opäť začala zaujímať dvojica dánskych vedcov. Mysleli si, že jej riešenie im potrvá aspoň 5 rokov, v skutočnosti však bez toho, aby o tom vôbec vedeli, práve publikovali jej riešenie.

Takmer sa vzdali, vedeli, že prišli na niečo zaujímavé, k finálovému riešeniu však stále odhadovali dlhých 5 rokov práce. Jacob Holme a Eva Rotenberg z Technickej univerzity v dánskej Kodani však teraz v tlačovej správe informujú o prvom veľkom matematickom objave od 80. rokoch v oblasti populárnej teórie grafov.

Teória grafov patrí medzi najznámejšie populárne oblasti matematiky, mnoho ľudí si to pritom ani neuvedomuje. Jej súčasťou sú totiž aj, zjednodušene povedané, matematické hlavolamy. V roku 1913 bol v časopise The Strand Magazine publikovaný prvý z nich. Nazýva sa Tri domy a tri studne.

Riešenie neexistuje

V modernejšom prevedení (z anglického originálu) znie problém Tri domy a tri studne nasledovne. Predstavte si tri domy a tri zdroje energie – vodu, elektrinu a plyn. Je možné spojiť každý dom ku každému zdroju bez toho, aby sa káble a potrubia navzájom pretli?

Foto: Cmglee / CC BY-SA

Hlavolam z rekreačnej matematiky je v skutočnosti dôležitou kapitolou matematickej oblasti nazývanej teória grafov. Z pohľadu teórie grafov riešenie neexistuje. Graf, akým možno úlohu zakresliť, nie je rovinný, jednotlivé cesty sa teda budú krížiť minimálne 1-krát. Riešenie úlohy z pohľadu matematiky definuje Kuratowského veta zo 70. rokov 20. storočia.

Ak by ste chceli úlohu riešiť samostatne, začali by ste si zrejme kresliť náčrty, čiarami skúšať spájať jednotlivé body tak, aby ste splnili zadanie problému. Pri hlavolame Troch domov a troch studní by to problém byť nemusel, ak by však úloha obsahovala viac bodov, ktoré treba spájať, bol by hlavolam násobne náročnejší.

Desaťročia hľadali algoritmus

Matematici sa desaťročia pokúšali nájsť vhodný algoritmus, ktorý by pomohol vykonávať v grafoch zmeny bez toho, aby sa museli znovu od začiatku presviedčať o tom, že žiadne dve cesty sa vzájomne nepretínajú. Grafy totiž možno upravovať dvoma spôsobmi, a to pridaním alebo odobratím jedného bodu. Doposiaľ však neexistoval rýchly a účinný spôsob, ako overiť, či sa celá štruktúra po takýchto krokoch neporušila.

Eva Rotenberg a Jacob Holm, Foto: University of Copenhagen

Ako uvádza portál ScienceAlert, posledným veľkým objavom v tejto oblasti bola práca na začiatku 90. rokoch 20. storočia. Dvojici dánskych matematikov a počítačových expertov sa však teraz podarilo aj s veľkou dávkou šťastia objaviť algoritmus, ktorý po troch desaťročiach opäť posúva teóriu grafov na novú úroveň.

Nový objav a výskumy v oblasti teórii grafov majú mimoriadne široké využitie. Obľúbené hlavolamy sú len populárnou formou prezentácie matematiky, teória grafov sa však uplatňuje napríklad pri projektovaní inžinierskych sietí, doprave, počítačovej elektronike či v mikročipoch.

0
Uložiť článok
Komentovať ( 0 )