Teorie grafů patří mezi relativně mladé matematické disciplíny.
Její počátky sice nacházíme již v 18. a 19. století, ale první kniha zcela
věnovaná teorii konečných a nekonečných grafů byla napsána až v roce 1936
maďarským matematikem D. Königem. Bouřlivý rozvoj této disciplíny nastává
po 2. světové válce, kdy řada výsledků teorie grafů nalezla uplatnění v
jiných částech matematiky a zejména v praktických aplikacích. S grafy se
setkáváme např. ve fyzice, v elektrotechnice, v chemii, v ekonomii a v
lingvistice. K rozvoji teorie grafů v tomto období výrazně přispěli také
čeští a slovenští matematici.
Cílem této práce je zachytit vývoj teorie grafů
v období 1736-1963. Toto období je ohraničeno dvěma významnými událostmi.
V roce 1736 napsal L. Euler první článek, který řadíme k této teorii. Vyřešil
v něm známý problém königsbergských mostů. V roce 1963 se konala ve Smolenicích
na Slovensku první mezinárodní konference z teorie grafů pořádaná v Československu.
Naše práce má pět kapitol, které jsou věnovány historickému vývoji základních
problémů teorie grafů. Vycházíme přitom zejména z knih N. L. Biggs,
K. E. Lloyd, R. J. Wilson: Graph theory 1736-1936. Oxford 1976 a
D. König: Theorie der endlichen und unendlichen Graphen. Leipzig
1936 a z rozboru velkého množství původních prací, většinou z období
let 1936-1970.
V krátkém úvodu jsou definovány základní pojmy,
které potřebujeme k výkladu vlastní problematiky v další části. První kapitola
zachycuje historický vývoj pojmů eulerovský graf a hamiltonovský graf.
Seznamuje s problémem königsbergských mostů a s úlohou jezdce, které patří
k nejstarším problémům teorie grafů. V části věnované hamiltonovsky souvislým
grafům věnujeme pozornost výsledku brněnského matematika M. Sekaniny. Druhá
kapitola se zabývá otázkami kostry grafu. V první části je zachycen vývoj
pojmů strom, kostra grafu a fundamentální systém kružnic. Největší pozornost
je pak věnována problému nalezení minimální kostry grafu. Touto otázkou
se jako první zabývali čeští matematici O. Borůvka a V. Jarník ve 20. letech
tohoto století. Třetí kapitola je věnována otázkám barvení grafů. Podrobně
je zachycen vývoj problému čtyř barev od jeho vzniku v roce 1852 až do
roku 1976, kdy byl vyřešen. Tento problém významně ovlivnil řadu oblastí
teorie grafů. Část této kapitoly je věnována rovinným grafům a některým
problémům extrémální teorie grafů. Čtvrtá kapitola se zabývá faktorizací
grafů. Sleduje zejména otázky faktorizace pravidelných grafů v pracech
J. Petersena a D. Königa. Velká pozornost je věnována pracem slovenského
matematika A. Kotziga z 50. a 60. let. Pátá kapitola se krátce zabývá vlastnostmi
orientovaných grafů. Také k této části teorie grafů významným způsobem
přispěli čeští a slovenští matematici.
Součástí naší práce je rozsáhlá bibliografie. Práce
obsahuje dvě přílohy. První tvoří anotovaný seznam asi 300 nejstarších
prací z teorie grafů publikovaných v letech 1736-1936. Druhá obsahuje podobný
seznam asi 70 prací českých a slovenských autorů z období 1926-1962.