Teória grafov

Vznik a rozvoj teórie grafov

Teória grafov patrí medzi najmladšie matematické disciplíny. Skúma matematické štruktúry nazývané grafy, ktoré sú určené dvomi disjunktnými množinami:

• Množina vrcholov: $\small V = \lbrace{v_1, v_2,\dots , v_n}\rbrace$
• Množina hrán: $\small H = \lbrace{h_1, h_2,\dots , h_k}\rbrace$

Každá hrana je jednoznačne určená dvojicou vrcholov, ktoré nemusia byť rôzne. Graf môžeme znázorniť diagramom, kde hrany (čiary) spájajú vrcholy (krúžky).

Neorientované grafy so 4 až 6 vrcholmi. Otvorte si applet na kreslenie grafov Tu.

Priekopníci teórie grafov

Uveďme mená piatich priekopníkov teórie grafov a roky ich prác:

• L. Euler (1736)
• G. Kirchhoff (1847)
• J. B. Listing (1848)
• A. Cayley (1857)
• W. R. Hamilton (1859)

Problém siedmich mostov V 18. storočí ležalo mesto Kráľovec (Königsberg, Kaliningrad) na brehoch a dvoch ostrovoch rieky Pregel. Jednotlivé časti mesta boli pospájané siedmimi mostmi tak, ako je to ukazuje mapa na obrázku.

Niekto vymudroval úlohu pochodiť mestom tak, aby chodec prešiel každým mostom práve raz a po ukončení promenády sa vrátil na pôvodné miesto. text

O tejto úlohe sa dozvedel aj švajčiarsky matematik Leonard Euler (1707-1783), ktorý v tom čase pôsobil v Petrohrade na Akadémii.
Eulerovi sa podarilo ukázať, že spomínaná úloha je neriešiteľná.
Euler si uvedomil, že vyriešenie úlohy nezávisí ani od tvaru jednotlivých častí mesta, ani od dĺžky mostov, ale od toho, ktoré časti koľkými mostmi sú spojené.
Euler nahradil dva brehy a dva ostrovy mesta bodmi (krúžkami). Mosty, ktoré ich spájajú, spojnicami (čiarami) medzi bodmi.

Nájsť trasu požadovanej prechádzky potom mohol interpretovať ako geometrickú úlohu:
„Nakresliť obrázok jedným „ťahom“ .
V roku 1848 J. B. Listing vyslovil tvrdenie, že:

Tvrdenie (Kreslenie grafu).
Graf možno nakresliť jedným ťahom, ak má buď všetky vrcholy párneho stupňa, alebo práve dva nepárneho stupňa.