Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


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.

Sedm mostů Königsbergu
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.

Sedm mostů Königsbergu
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ů).

The Icosian Game
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
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).


Úvod

Základní pojmy

Vybrané problémy

Procvičování