Úvod do diskrétnej matematiky

Prvým grafovým algoritmom je Tarryho prieskum grafov, ktorý slúži na prehľadávanie labyrintov a pochádza z roku 1895. Je to vlastne postup pozostávajúci z dvoch jednoduchých pravidiel. V grafovej terminológii je to postup na nájdenie sledu s začínajúceho vo vrchole u0 a obsahujúceho všetky hrany súvislého grafu G. Použitie: preskúmanie obchodného centra, pričom prejdeme každou uličkou a preskúmame obe strany.

Podobný algoritmus je Trémauxov prieskum, ktorý vznikol v roku 1882 a je na rozdiel od Tarryho prieskumu doplnený a tretie pravidlo. Je to špeciálny druh tohto prieskumu a používa sa na prieskum labyrintov. Praktické použitie oboch postupov by som videl pri aplikácii na zisťovanie sledu nejakého vedenia napr. podlahové kúrenie, rozvod vody alebo vzduchu.

Algoritmus na prehľadanie grafu do hĺbky slúži na prehľadávanie súvislého aj nesúvislého grafu - systematické prehľadávanie všetkých vrcholov grafu. Prehľadanie do hĺbky je vlastne upravený Trémauxov prieskum a slúži na nájdenie kostry grafu. Praktické využitie by som videl napríklad pri použití pri montážnych prácach napr. vodovodu alebo kúrenia či požiarneho systému v budove kde sa treba pohybovať z miestnosti do miestnosti.