Teória grafov

Rozvíjanie kladného vzťahu k matematike znamená zahrňovať do vzdelávacieho programu všetky nové objavy, poznatky a informácie. Vysporiadať sa s týmto problémom znamená zamerať úsilie pedagóga na nové moderné spôsoby a trendy vo vzdelávaní, ktoré rešpektujú individualitu študujúceho. Dnes už nikoho nemusíme presviedčať, že vzdelávanie je celoživotnou záležitosťou každého, kto sa chce úspešne presadiť na trhu práce.

1. Práve matematika, ako abstraktná veda má veľa možností pripraviť človeka modernej spoločnosti práve na spracovávanie a vyhodnocovanie nových informácií, naučiť ho učiť sa. Prostredníctvom matematiky má učiteľ možnosť rozvíjať schopnosti študentov, ktoré sú využiteľné aj v bežnom živote
2. Študenti, a nielen študenti, sa prostredníctvom matematiky učia formulovať myšlienky, získavajú schopnosť argumentácie a schopnosť kriticky analyzovať a vyhodnocovať situácie, s ktorými sa predtým nestretli. Vyučovanie matematiky môže významne prispieť k osobnostnému rastu študujúceho, k jeho hodnotovému systému a k jeho vzťahu ku spo¬ločnosti. Toto považujeme za jeden z hlavných zmyslov vyučovania matematiky na každom stupni vzdelávania.
3. Ústrednou postavou výchovno-vzdelávacieho procesu bude aj naďalej učiteľ, ktorý musí študentom poskytnúť plnohodnotné vzdelanie spolu s vyššie uvedenými výchovnými zámermi. Preto ďalšou dôležitou otázkou je: „Aká má byť príprava učiteľa, aby naplnil nové moderné poslanie mate¬matiky vo výchove a vo vzdelávaní študentov?“

Vývoj v priebehu niekoľkých desaťročí viedol k prenikaniu nových vedných disciplín do pedagogického procesu. Jednou z takýchto vedných disciplín je aj teória grafov, ktorá umožňuje preniknúť do vnútornej štruktúry skúmaného systému a popísať jeho súčinnosť voči iným systémom. Preto si myslíme, že oblasť teórie grafov ako súčasť diskrétnej matematiky, musí byť predmetom skúmania budúcich učiteľov matematiky. To sú hlavné dôvody, ktoré nás viedli k napísanie tejto práce.

Predkladaná práca zahrňuje niektoré základné a východiskové témy, ktoré sme nemohli opomenúť pri písaní textu. V úvodných častiach práce sme sa venovali aj historickému pozadiu vzniku teórie grafov a problémom, ktoré inšpirovali slávnych matematikov akým bol Leonard Euler. Jeho slávny Problém siedmich mostov je aj po takmer troch storočiach inšpirujúcim pre začínajúcich matematikov. Jednu kapitolu sme venovali aj slovenským matematikom, ktorý zohrali veľmi významnú úlohu v rozvoji teórie grafov v celosvetovom meradle. Na tomto mieste si dovolíme vysloviť úctu profesorovi Štefanovi Známovi, ktorého zásluhou dnes má Slovensko mnohých významných „grafárov“ pôsobiacich po celom svete.

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.

Cesta okolo sveta
Slávny írsky matematik W. R. Hamilton sa v roku 1859 zaoberal hrou „cesta okolo sveta“, v ktorej hráč má za úlohu symbolicky „precestovať“ pravidelný dvanásťsten (dodekaéder) tak, aby prešiel každým vrcholom jedenkrát (pri cestovaní nemusíme prejsť všetkými cestami).

Pravidelný dvanásťsten

Názov problému - "hry" pochádza z toho, že vrcholy pravidelného dvanásťstena predstavovali význačné mestá sveta. Nájsť takúto cestu v prípade pravidelného dvanásťstena je veľmi ľahké, ale napriek tomu hra dala podnet na skúmanie význačného typu grafov, ktoré nazývame Hamiltonovské grafy.

Cvičenie.
Zistite, po ktorom z nasledujúcich grafov je možné symbolicky „precestovať“ tak, aby ste prešli každým vrcholom práve jedenkrát (pri cestovaní nemusíme prejsť všetkými hranami).

Graf vpravo sa nazýva Petersenov graf

Jedným z najznámejších problémov v teórii grafov je problém „štyroch farieb“. Teraz ho v krátkosti opíšeme z historického hľadiska. Pri tvorbe máp je požiadavka, aby dva susedné štáty boli zafarbené odlišnými farbami. Vzniká otázka, ktorá bola formulovaná ako hypotéza.

Problém štyroch farieb (Hypotéza - dnes už vyriešená).
Aký je najmenší počet farieb, ktorý stačí na vyfarbenie mapy, ktorú možno nakresliť na glóbuse?

Štáty nahraďme krúžkami, potom „susedné krúžky“ (štáty) spojme čiarou. Dostaneme graf, v ktorom máme zafarbiť vrcholy grafu tak, aby dva vrcholy spojené hranami boli zafarbené rôznymi farbami.

Mapa strednej Európy

Problém štyroch farieb zohral v teórii grafov mimoriadne závažnú úlohu.

1. V roku 1840 sa problémom štyroch farieb zaoberal Möbius.
2. O jeho riešenie sa pokúšal v roku 1850 de Morgan. Od tých čias sa vynaložilo mnoho energie na vyriešenie problému štyroch farieb.
3. Prvý dôkaz uverejnil v roku 1879 Kempe.
4. V roku 1890 Heawood v ňom našiel chybu.
5. Riešenie sa našlo až v roku 1976, keď Appel a Hacken dokázali správnosť hypotézy.

Celkove však bol problém štyroch farieb dôležitým katalyzátorom vývoja princípov teórie grafov. Vyústil v tridsiatych rokoch 20. storočia do vytvorenia systematickej teórie.

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.