Na čo je to dobré?

Obrovský význam teórie grafov spočíva v tom, že veľmi veľa problémov ''zo života'' vieme popísať vhodne zvoleným grafom. Uveďme si niekoľko príkladov:

• Medziľudské vzťahy. Vrcholy budú predstavovať ľudí, hranou budú spojené tie dvojice, ktoré sa poznajú.
• Počítačová sieť. Vrcholy budú predstavovať počítače, huby, switche, inteligentné chladničky... no a hrany budú káble medzi nimi.
• Cestná sieť. Vrcholy budú predstavovať mestá v krajine, hrany budú cesty medzi nimi.
• Šach. Každý vrchol bude predstavovať jedno rozmiestnenie figúrok na šachovnici, hranou budú spojené tie vrcholy, medzi ktorých pozíciami sa dá prejsť jedným ťahom. (Tento graf je véééľmi veľký. Zatiaľ sa zďaleka nezmestí do pamäte počítača... a aj preto ešte počítače nevedia dokonale hrať šach.)
• Kreslenie jedným ťahom. Máme na papieri obrázok, ktorý chceme nakresliť jedným ťahom. Aj na ten sa vieme pozerať ako na graf: vrcholy budú priesečníky čiar, hrany budú samotné čiary.

Z informatického hľadiska to má napríklad nasledovný dôsledok: ak vymyslíme efektívny algoritmus pracujúci na grafoch, tento algoritmus potom môžeme použiť v rôznych situáciách, ktoré sa dajú reprezentovať grafmi a nemusíme vymýšľať riešenie pre každú situáciu zvlášť. Rovnaký algoritmus sa dá napríklad použiť na:

• Vyriešenie hry pätnástka na čo najmenej ťahov
• Nájdenie najkratšej cesty z Bratislavy do Košíc
• Vypočítanie, cez koľko najmenej známostí sa vie klebeta odo mňa dostať k Juhoafrickému prezidentovi