Optimalizační a grafové problémy

Abstract

Mnoho situací kolem nás je možné si zjednodušit vhodným modelem. Vhodným prostředkem je právě graf, který dokáže modelovat vztahy mezi objekty. Oblasti, ve kterých se grafy používají, jsou různorodé - přes logistiku, počítačové sítě, dopravu, lingvistiku po biologii. Pro pochopení složitějších grafových algoritmů je nutné znát základní principy a přístupy, které se v praxi využívají. Představíme si základní algoritmy pro průchod grafem a řešení vybraných grafových problémů. Teorie grafů je také svázána s matematickou optimalizací. Práce seznamuje čtenáře s grafovými problémy také z pohledu optimalizace pomocí modelů celočíselného lineárního programování. Určité problémy se řadí do NP těžkých problémů a z toho důvodu je není možné efektivně v reálném čase vyřešit. Tento fakt ilustrujeme na ukázkách časové náročnosti naivních přístupů pro řešení takových problémů. Praktickou ukázkou jsou kódy v jazyce Python, které slouží jako názorná ukázka pro pochopení algoritmů. Práce také podrobně uvádí čtenáře do problematiky jednotlivých přístupů pomocí názorných obrázků a kroků jednotlivých algoritmů.