Poznámka k histórii

Prvú monografiu z teórie grafov napísal v roku 1936 D. König (Theorie der endlichen und unendlichen Graphen). Sporadicky sa objavovali výsledky z teórie grafov už oveľa skôr. V roku 1736 L. Euler uverejnil článok o riešení problému siedmich mostov mesta Kráľovca, v ktorom objavil prvé poznatky o teórii grafov. Kirchhoff v roku 1847 používal grafy pri svojich úvahách o elektrických sieťach.

Ohodnotený graf
V praxi sa často stretávame s dopravnými problémami, ako je určenie najkratšej cesty medzi dvoma mestami, po ktorej možno najlacnejšie previezť tovar z jedného mesta do druhého. V takýchto situáciách sa mestá nahrádzajú vrcholmi a spojenia medzi nimi hranami grafu. Ak hranám priradíme číselné hodnoty vyjadrujúce vzdialenosť medzi mestami resp. križovatkami, potom takéto grafy nazveme ohodnotené grafy. Presvedčte sa, že v grafe znázornenom na obrázku č. 7 najkratšia cesta medzi mestami A a G vedie cez mestá C a F.