História vzniku teórie grafov. História vzniku a vývoja teórie grafov. Teória grafov a najdôležitejšie moderné aplikované problémy

GRAPHS

Mnoho problémov sa týka uvažovania o množine objektov, ktorých podstatné vlastnosti sú opísané súvislosťami medzi nimi. Napríklad pri pohľade na cestnú mapu môže človeka zaujímať iba to, či existuje spojenie medzi určitými sídlami, ignorujúc konfiguráciu a kvalitu ciest, vzdialenosti a ďalšie podrobnosti. Pri štúdiu elektrických obvodov môže prísť do popredia povaha spojov jeho rôznych komponentov - rezistorov, kondenzátorov, zdrojov a pod.. Organické molekuly tvoria štruktúry, ktorých charakteristickými vlastnosťami sú spojenia medzi atómami. Zaujímavé môžu byť rôzne prepojenia a vzťahy medzi ľuďmi, udalosťami, stavmi a vo všeobecnosti medzi akýmikoľvek predmetmi.

V takýchto prípadoch je vhodné znázorniť uvažované objekty ako body a spojenia medzi nimi ako čiary ľubovoľnej konfigurácie. Takýto formalizovaný obrázok sa nazýva graf (z gréckeho grajw - píšem).

Ryža. 4.1 .

Prvú prácu o grafoch publikoval dvadsaťročný Leonhard Euler v roku 1736, keď pôsobil v Ruskej akadémii vied. Obsahoval riešenie problému Königsbergských mostov (obr. 4.1a): je možné urobiť prechádzku tak, že keď opustíte akékoľvek miesto v meste, vrátite sa naň prechádzkou presne raz po každom moste? ? Je jasné, že podľa podmienok problému nezáleží na tom, ako cesta prechádza časťami pozemku a, b, c, d, na ktorom sa nachádza mesto Koenigsberg (dnes Kaliningrad), takže môžu byť reprezentované ako vrcholy. A keďže spojenia medzi týmito časťami sa uskutočňujú iba cez sedem mostov, každý z nich je reprezentovaný hranou spájajúcou zodpovedajúce vrcholy. V dôsledku toho získame graf znázornený na obr. 4.1b. Euler na položenú otázku odpovedal záporne. Navyše dokázal, že takáto cesta existuje len pre graf, v ktorom je každý jeho vrchol spojený s párnym počtom hrán.

Teória grafov dostala svoj ďalší impulz takmer o 100 rokov neskôr s rozvojom výskumu elektrických sietí, kryštalografie, organickej chémie a iných vied. Spolu s mnohými hádankami a grafickými hrami sa zvažovali dôležité praktické problémy, z ktorých mnohé si vyžadovali sofistikované matematické techniky. Už v polovici minulého storočia Kirchhoff použil grafy na analýzu elektrických obvodov a Cayley preskúmal dôležitú triedu grafov na identifikáciu a zoznam izomérov nasýtených uhľovodíkov. Teória grafov ako matematická disciplína sa však sformovala až v polovici tridsiatych rokov minulého storočia vďaka práci mnohých bádateľov, z ktorých najväčšiu zásluhu má D. Koenig. Významne prispeli k teórii grafov sovietski vedci L. S. Pontryagin, A. A. Zykov, V. G. Vising a ďalší.

Bez toho, aby sme si to všimli, neustále sa stretávame s grafmi. Napríklad graf je schéma liniek metra. Bodky na ňom predstavujú stanice a čiary predstavujú trasy vlakov. Skúmaním našich predkov a ich vystopovaním až k našim predkom si budujeme rodokmeň. A tento strom je graf.

Grafy slúžia ako vhodný prostriedok na opis vzťahov medzi objektmi. Napríklad zvážením grafu zobrazujúceho sieť ciest medzi obývanými oblasťami môžete určiť trasu z bodu A do bodu B. Ak existuje niekoľko takýchto trás, chceli by ste si v určitom zmysle vybrať optimálnu, napr. najkratšie alebo najbezpečnejšie. Na vyriešenie problému výberu je potrebné vykonať určité výpočty na grafoch. Pri riešení takýchto problémov je vhodné použiť algebraické techniky a samotný koncept grafu je potrebné formalizovať.

Teória grafov má mocný nástroj na riešenie aplikovaných problémov zo širokej škály oblastí vedy a techniky. To zahŕňa napríklad analýzu a syntézu obvodov a systémov, návrh komunikačných kanálov a štúdium procesov prenosu informácií, konštrukciu kontaktných obvodov a štúdium konečných automatov, plánovanie a riadenie siete, operačný výskum, výber optimálnych trás a tokov v sieťach, štúdium náhodných procesov a mnoho ďalších úloh. Teória grafov úzko súvisí s takými odvetviami diskrétnej matematiky, ako je teória množín, matica, matematická logika a teória pravdepodobnosti.

V súčasnosti teória grafov pokrýva veľa materiálu, ale pri jej prezentovaní sa obmedzíme len na jej časť a vynecháme mnohé vety, zvážime len niekoľko základné pojmy.

Leonard Euler je považovaný za zakladateľa teórie grafov. V roku 1736 v jednom zo svojich listov sformuloval a navrhol riešenie problému siedmich Königsbergských mostov, ktorý sa neskôr stal jedným z klasických problémov teórie grafov.

Prvé problémy v teórii grafov súviseli s riešením matematických rekreačných problémov a hlavolamov. Tu je prerozprávanie úryvku z Eulerovho listu z 13. marca 1736: „Dostal som problém s ostrovom, ktorý sa nachádza v meste Königsberg a obklopuje ho rieka so 7 mostmi. Otázkou je, či ich niekto dokáže obchádzať nepretržite, pričom každý most prejde len raz. A potom som bol informovaný, že to ešte nikto nedokázal, ale nikto nedokázal, že je to nemožné. Táto otázka, aj keď triviálna, sa mi zdala byť hodná pozornosti, pretože na jej vyriešenie nestačí ani geometria, ani algebra, ani kombinatorické umenie. Po dlhom premýšľaní som našiel ľahké pravidlo, založené na úplne presvedčivom dôkaze, pomocou ktorého je možné pri všetkých problémoch tohto druhu okamžite zistiť, či je možné takúto obchádzku urobiť cez ľubovoľný počet a ľubovoľný počet mosty umiestnené akýmkoľvek spôsobom alebo nie.“ Königsbergské mosty možno schematicky znázorniť takto:

Eulerovo pravidlo:

1. V grafe, ktorý nemá vrcholy nepárnych stupňov, dochádza k prechodu všetkých hrán (a každá hrana sa prejde práve raz) počnúc ktorýmkoľvek vrcholom grafu.

2. V grafe, ktorý má dva a iba dva vrcholy s nepárnymi stupňami, je prechod, ktorý začína v jednom vrchole s nepárnym stupňom a končí v druhom.

3. V grafe, ktorý má viac ako dva vrcholy s nepárnymi stupňami, takýto prechod neexistuje.

S cestovaním po grafoch súvisí aj iný typ problému. Hovoríme o problémoch, v ktorých je potrebné nájsť cestu prechádzajúcu všetkými vrcholmi a nie viac ako raz cez každý. Cyklus, ktorý prechádza každým vrcholom raz a len raz, sa nazýva hamiltonovská čiara (podľa Williama Rowana Hamiltona, slávneho írskeho matematika minulého storočia, ktorý ako prvý študoval takéto čiary). Žiaľ, zatiaľ sa nenašlo všeobecné kritérium, pomocou ktorého by sa dalo rozhodnúť, či daný graf je hamiltonovský, a ak áno, nájsť na ňom všetky hamiltonovské čiary.

Formulované v polovici 19. storočia. Problém štyroch farieb tiež vyzerá ako zábavný problém, ale pokusy o jeho vyriešenie viedli k niekoľkým grafovým štúdiám, ktoré majú teoretický a aplikovaný význam. Štvorfarebný problém je formulovaný nasledovne: „Môže byť oblasť akejkoľvek plochej mapy zafarbená štyrmi farbami tak, aby dve susedné oblasti boli zafarbené rôznymi farbami? Hypotéza, že odpoveď je kladná, bola sformulovaná v polovici 19. storočia. V roku 1890 sa dokázalo slabšie tvrdenie, a to, že každá plochá mapa môže byť vyfarbená piatimi farbami. Priradením ľubovoľnej rovinnej mapy k jej duálnemu rovinnému grafu získame ekvivalentnú formuláciu úlohy v zmysle grafov: Je pravda, že chromatické číslo akéhokoľvek rovinného grafu je menšie alebo rovné štyri? Početné pokusy o vyriešenie problému ovplyvnili vývoj množstva oblastí teórie grafov. V roku 1976 bolo oznámené pozitívne riešenie problému pomocou počítača.

Ďalší starý topologický problém, ktorý bol dlho obzvlášť odolný voči riešeniu a prenasledoval mysle milovníkov hádaniek, je známy ako „problém dodávok elektriny, plynu a vody“. Túto formuláciu mu dal v roku 1917 Henry E. Dudeney. Plyn, elektrina a voda musia byť zavedené v každom z troch domov znázornených na obrázku.

Teória grafov. 1

História vzniku teórie grafov. 1

Eulerovo pravidlo. 1

Literatúra

1. Belovova teória grafov, Moskva, "Veda", 1968.

2. Nové pedagogické a informačné technológie E.S.Polat , Moskva, "Akademia" 1999

3. Kuznecov O.P., Adelson-Velsky G.M. Diskrétna matematika pre inžiniera. – M.: Energoatomizdat, 1988.

4. Cook D., Baze G. Počítačová matematika. – M.: Veda, 1990.

5. Nefedov V.N., Osipova V.A. Diskrétny kurz matematiky. – M.: Vydavateľstvo MAI, 1992.

6. Ruda O. Teória grafov. – M.: Veda, 1980.

7. Ismagilov R.S., Kalinkin A.V. Materiály na praktické vyučovanie v predmete: Diskrétna matematika

Teória grafov- kapitola diskrétna matematika, štúdium vlastností grafov . Vo všeobecnom zmysle je graf reprezentovaný ako množina vrcholov (uzlov) spojených hranami. V striktnej definícii sa takáto dvojica množín nazýva graf. G=(V,E), kde V je podmnožina ľubovoľnej spočítateľnej množiny a E je podmnožina V×V.

História teórie grafov
Leonard Euler je považovaný za zakladateľa teórie grafov. V roku 1736 v jednom zo svojich listov sformuloval a navrhol riešenie problému siedmich Königsbergských mostov, ktorý sa neskôr stal jedným z klasických problémov teórie grafov.
Prvé problémy v teórii grafov súviseli s riešením matematických rekreačných problémov a hlavolamov. Tu je prerozprávanie úryvku z Eulerovho listu z 13. marca 1736: „Dostal som problém s ostrovom, ktorý sa nachádza v meste Königsberg a obklopuje ho rieka so 7 mostmi. Otázkou je, či ich niekto dokáže obchádzať nepretržite, pričom každý most prejde len raz. A potom som bol informovaný, že to ešte nikto nedokázal, ale nikto nedokázal, že je to nemožné. Táto otázka, aj keď triviálna, sa mi zdala byť hodná pozornosti, pretože na jej vyriešenie nestačí ani geometria, ani algebra, ani kombinatorické umenie. Po dlhom premýšľaní som našiel ľahké pravidlo, založené na úplne presvedčivom dôkaze, pomocou ktorého je možné pri všetkých problémoch tohto druhu okamžite zistiť, či je možné takúto obchádzku urobiť cez ľubovoľný počet a ľubovoľný počet mosty umiestnené akýmkoľvek spôsobom alebo nie.“ Königsbergské mosty možno schematicky znázorniť takto:
Eulerovo pravidlo:

1. V grafe, ktorý nemá vrcholy nepárnych stupňov, dochádza k prechodu všetkých hrán (a každá hrana sa prejde presne raz), pričom sa začína v ľubovoľnom vrchole grafu.
2. V grafe, ktorý má dva a iba dva vrcholy s nepárnymi stupňami, je prechod, ktorý začína v jednom vrchole s nepárnym stupňom a končí v druhom.
3. V grafe, ktorý má viac ako dva vrcholy s nepárnymi stupňami, takýto prechod neexistuje.

školský rok 2016 rok

1. Úvod

2. História vzniku teórie grafov

3. Základné pojmy z teórie grafov

4. Základné vety teórie grafov

5. Metódy znázornenia grafov v počítači

6. Prehľad úloh teórie grafov

7. Záver

8. Referencie

Úvod

V poslednej dobe sa čoraz viac dostáva do popredia výskum v oblastiach tradične súvisiacich s diskrétnou matematikou. Spolu s takými klasickými časťami matematiky, ako je matematická analýza a diferenciálne rovnice, sa v učebných osnovách špecializácie „Aplikovaná matematika“ a mnohých ďalších špecializácií objavili časti o matematickej logike, algebre, kombinatorike a teórii grafov. Dôvody nie je ťažké pochopiť jednoduchým určením rozsahu problémov riešených na základe tohto matematického aparátu.

História vzniku teórie grafov.

1. Problém s mostami Königsberg. Na obr. 1 znázorňuje schematický plán centrálnej časti mesta Koenigsberg (teraz Kaliningrad), vrátane dvoch brehov rieky Pergola, dvoch ostrovov v nej a siedmich spojovacích mostov. Úlohou je obísť všetky štyri časti krajiny, každý most prejsť raz a vrátiť sa do východiskového bodu. Tento problém vyriešil (ukázalo sa, že riešenie neexistuje) Euler v roku 1736.

ryža. 1

2. Problém troch domov a troch studní. Sú tam tri domy a tri studne, ktoré sa nejako nachádzajú na rovine. Z každého domčeka ku každej studni nakreslite cestu tak, aby sa cesty nekrížili (obr. 2). Tento problém vyriešil (ukázalo sa, že riešenie neexistuje) Kuratovský v roku 1930.

ryža. 2

3. Problém štyroch farieb. Rozdelenie roviny na neprekrývajúce sa oblasti sa nazýva mapa. Oblasti na mape sa nazývajú susediace, ak majú spoločnú hranicu. Úlohou je vyfarbiť mapu tak, aby žiadne dve susediace plochy neboli natreté rovnakou farbou (obr. 3). Od konca predminulého storočia je známa hypotéza, že na to stačia štyri farby. V roku 1976 Appel a Heiken publikovali riešenie problému štyroch farieb, ktoré bolo založené na počítačovom vyhľadávaní. Riešenie tohto problému „programovo“ bolo precedensom, ktorý vyvolal búrlivú diskusiu, ktorá sa v žiadnom prípade neskončila. Podstatou publikovaného riešenia je vyskúšať veľký, ale konečný počet (asi 2000) typov potenciálnych protipríkladov k štvorfarebnej vete a ukázať, že ani jeden prípad nie je protipríkladom. Toto hľadanie ukončil program za približne tisíc hodín prevádzky superpočítača. Výsledné riešenie nie je možné kontrolovať „ručne“ – rozsah enumerácie ďaleko presahuje ľudské možnosti. Mnohí matematici si kladú otázku: možno takýto „programový dôkaz“ považovať za platný dôkaz? Koniec koncov, v programe môžu byť chyby... Metódy formálneho preukazovania správnosti programov nie sú použiteľné pre programy takej zložitosti, ako je ten, o ktorom sa diskutuje. Testovanie nemôže zaručiť absenciu chýb a v tomto prípade je vo všeobecnosti nemožné. Môžeme sa teda spoľahnúť len na programátorské schopnosti autorov a veriť, že všetko urobili správne.

Ryža. 3

Základné pojmy z teórie grafov

1) Graf G(V,E) je súborom dvoch množín – neprázdnej množiny V (množina vrcholov) a množiny E dvojprvkových podmnožín množiny V (E – množina hrán).

2) Orientovaný je graf, v ktorom je množina usporiadaných dvojíc vrcholov tvaru (x,y), kde x sa nazýva začiatok a y je koniec oblúka. Oblúk (x, y) sa často píše ako . Tiež hovoria, že oblúk vedie z vrcholu x k vrcholu y a vrcholu y priľahlé s vrcholom x.

3) Ak prvok množiny E môže byť pár identické(nerozlíšené) prvky V, potom sa takýto prvok množiny E nazýva slučka a graf sa volá graf so slučkami(alebo pseudograf).

4) Ak E nie je množina, ale nastaviť obsahujúce niekoľko rovnakých prvkov, potom sa tieto prvky nazývajú viaceré hrany a graf sa volá multigraf.

5) Ak prvky množiny E nemusia byť nevyhnutne dvojprvkové, ale ľubovoľné podmnožiny množiny V, potom sa takéto prvky množiny E nazývajú hyperoblúky a graf sa volá hypergraf.

6) Ak je funkcia špecifikovaná F: V → M a/alebo F: E → M, potom súpravu M volal súpravu poznámky a graf sa volá označené(alebo naložený). Súbor značiek sú zvyčajne písmená alebo celé čísla. Ak funkcia F je injektívny, to znamená, že rôzne vrcholy (hrany) majú rôzne označenia, potom sa graf nazýva tzv. očíslované.

7) Podgraf sa nazýva graf G′(V′,E′), kde a/alebo .

a) Ak V′ = V, potom sa nazýva G′ jadro podbod G.

b) Ak , potom sa volá graf G′ vlastné podgraf grafu G.

c) Podgraf G′(V′,E′) sa nazýva regulárny podgraf grafu G(V,E), ak G′ obsahuje všetky možné hrany G.

8) Stupeň (valencia) vrcholy je počet hrán spadajúcich do tohto vrcholu (počet vrcholov, ktoré k nemu priliehajú).

9) Trasa v grafe je striedavá postupnosť vrcholov a hrán, v ktorých sú akékoľvek dva susedné prvky incidentné.

a) Ak , potom trasa ZATVORENÉ, inak OTVORENÉ.

b) Ak sú všetky hrany rozdielne, potom sa volá trasa reťaz.

c) Ak sú všetky vrcholy (a teda hrany) rôzne, potom sa volá trasa jednoduchá reťaz.

d) Uzavretý okruh sa nazýva cyklu.

e) Uzavretý jednoduchý obvod sa nazýva jednoduchá slučka.

f) Volá sa graf bez cyklov acyklický.

g) Pri digrafoch sa reťazec nazýva podľa, a cyklus je obrys.

ryža. 4. Trasy, reťazce, cykly

Príklad

V grafe, ktorého diagram je znázornený na obr. 4:

1. v 1, v 3, v 1, v 4 – trasa, ale nie reťaz;

2. v 1, v 3, v 5, v 2, v 3, v 4 – reťaz, ale nie jednoduchá reťaz;

3. v 1, v 4, v 3, v 2, v 5 – jednoduchá reťaz;

4. v 1, v 3, v 5, v 2, v 3, v 4, v 1 – cyklus, ale nie jednoduchý cyklus;

5. v 1 , v 3 , v 4 , v 1 – jednoduchý cyklus.

10) Ak má graf cyklus (nie nevyhnutne jednoduchý) obsahujúci všetky hrany grafu raz, potom sa takýto cyklus nazýva eulerovský cyklu.

11) Ak má graf jednoduchý cyklus obsahujúci všetky vrcholy grafu (po jednom), potom sa takýto cyklus nazýva Hamiltonián cyklu.

12) strom nazývaný súvislý graf bez cyklov.

13) kostra Strom obsahujúci všetky vrcholy grafu sa nazýva.

14) Zhoda je množina hrán, v ktorých žiadne dve nesusedia.

15) Zhoda sa nazýva maximálne, ak žiadna jeho nadmnožina nie je nezávislá.

16) Dva vrcholy v grafe pripojený, ak ich spája jednoduchá reťaz.

17) Voláme graf, v ktorom sú všetky vrcholy spojené koherentný.

18) Volá sa graf pozostávajúci len z izolovaných vrcholov dosť nesúrodé.

19) Dĺžka trasy počet hrán v ňom sa nazýva (s opakovaniami).

20) Vzdialenosť medzi vrcholmi u a v sa nazýva dĺžka najkratšieho reťazca a samotný najkratší reťazec sa nazýva geodetický.

21) Priemer grafu G sa nazýva dĺžka najdlhšej geodetiky.

22) Výstrednosť vrchol v v súvislom grafe G(V,E) je maximálna vzdialenosť od vrcholu v k ostatným vrcholom grafu G.

23) Polomer grafu G sa nazýva najmenšia z excentricity vrcholov.

24) Vertex v sa nazýva centrálny, ak sa jeho excentricita zhoduje s polomerom grafu.

25) Množina stredových vrcholov sa nazýva stred graf.

ryža. 5 Excentricity vrcholov a stredov grafov (zvýraznené).

Súvisiace informácie.

Teória grafov nachádza uplatnenie napríklad v geografických informačných systémoch (GIS). Za vrcholy sa považujú existujúce alebo novonavrhované domy, stavby, bloky a pod., za hrany sa považujú cesty, inžinierske siete, elektrické vedenia a pod. Použitie rôznych výpočtov vykonaných na takomto grafe umožňuje napríklad nájsť najkratšiu obchádzkovú trasu alebo najbližší obchod s potravinami alebo naplánovať optimálnu trasu.

Teória grafov obsahuje veľké množstvo nevyriešených problémov a zatiaľ neoverených hypotéz.

História teórie grafov

Leonard Euler je považovaný za zakladateľa teórie grafov. V roku 1736 v jednom zo svojich listov sformuloval a navrhol riešenie problému siedmich mostov v Königsbergu, ktorý sa neskôr stal jedným z klasických problémov teórie grafov. Termín „graf“ prvýkrát vytvoril Sylvester, James Joseph v roku 1878 vo svojom článku v Nature [ ] .

Terminológia teórie grafov

Aplikácia teórie grafov

pozri tiež

Poznámky

Literatúra

• Distel R. Teória grafov Trans. z angličtiny - Novosibirsk: Vydavateľstvo Ústavu matematiky, 2002. - 336 s. ISBN 5-86134-101-X.
• Diestel R. Teória grafov, elektronické vydanie. - NY: Springer-Verlag, 2005. - S. 422.
• Basaker R., Saati T. Konečné grafy a siete. M.: Nauka, 1974. 368c.
• Belov V.V., Vorobiev E.M., Šatalov V.E. Teória grafov. - M.: Vyššie. škola, 1976. - S. 392.
• Berge K. Teória grafov a jej aplikácie. M.: IL, 1962. 320c.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Prednášky z teórie grafov. M.: Nauka, 1990. 384 s. (Vyd. 2, upravené M.: URSS, 2009. 392 s.)