1. Úvod / Historie teorie grafů
18. století - Eulerova úloha / Sedm mostů města Königsbergu
Za zakladatele teorie grafů je považován Leonhard Euler (1707-1783), který roku 1736 publikoval řešení příkladu Sedmi mostů města Königsbergu (Královce).
Zadání úlohy znělo, zda je možné projít každým mostem ve městě právě jednou a vrátit se zpět do původního místa.
Obr. č. 1.2 - Sedm mostů města Königsbergu
Převedení situace na graf provedl Euler tak, že si každý břeh představil jako vrchol a každý most použil jako hranu, která břehy spojuje. Matematicky dokázal, že úloha není řešitelná. Více o problému jednotažek.
Obr. č. 1.3 - Sedm mostů města Königsbergu - znázornění pomocí grafu
19. století - fyzika a chemie
Grafy pak zůstávaly přes sto let na okraji zájmu matematiků - vrátili se k nim až roku 1847 Gustav Kirchhoff (1824-1887), když se zabýval výpočtem proudů v elektrických sítích pomocí počtu koster grafu, a 1857 Arthur Cayley (1821-1895), který pomocí grafů zjišťoval počty různých uskupení molekul alkanů (více o problému).
V roce 1857 vymyslel sir William Hamilton (1805-1865) hru, jejímž úkolem bylo pospojovat všechny vrcholy pravidelného dvanáctistěnu tak, aby byl každý vrchol použit právě jednou (viz obrázek č. 1.4) - podle toho vznikl pojem hamiltonovská kružnice jako kružnice, která projde právě jednou všemi vrcholy grafu. Hra byla pojmenována The Icosian Game (icosian = dvacítkový; dvanáctistěn má dvacet vrcholů).
Obr. č. 1.4 - Jedno z možných řešení The Icosian Game - [2]
Nejznámější úlohou teorie grafů v 19. století byl problém čtyř barev - otázka zněla, zda-li je možné každou mapu obarvit pomocí čtyř barev tak, aby sousední státy měly různé barvy (více o zadání a řešení problému), který byl kompletně vyřešen až roku 1976.
Obarvení mapy čtyřmi barvami - obrázek z Kapitoly 3, 3.6
20. století u nás
Ve 20. století docházelo k velkému rozvoji teorie grafů. Významných poznatků bylo dosaženo i v Československu. V roce 1926 publikoval Otakar Borůvka (1899-1995) svůj algoritmus pro nalezení minimální kostry. Tento problém měl praktický důvod - co nejvýhodnější výstavbu elektrických sítí. Stejný problém vyřešil (jiným algoritmem) v roce 1930 také Vojtěch Jarník (1897-1970).