Teória grafov. História vzniku a vývoja teórie grafov História grafov

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. Obsahovala 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 cez každý most? ? 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.

Za zakladateľa teórie grafov sa považuje matematik Leonhard Euler (1707-1783). Históriu tejto teórie možno vysledovať prostredníctvom korešpondencie veľkého vedca. Tu je preklad latinského textu, ktorý je prevzatý z Eulerovho listu talianskemu matematikovi a inžinierovi Marinonimu, zaslaného z Petrohradu 13. marca 1736 [pozri. s. 41-42]:

"Raz sa ma spýtali na problém týkajúci sa ostrova, ktorý sa nachádza v meste Königsberg a je obklopený riekou, cez ktorú je prehodených sedem mostov. Otázkou je, či ich niekto môže obchádzať nepretržite, pričom cez každý most prejde iba raz. A potom som informoval, že sa to ešte nikomu nepodarilo, ale nikto nepreukázal, že je to nemožné. Táto otázka, hoci triviálna, sa mi však zdala byť hodná pozornosti, pretože ani geometria, ani algebra, ani kombinatorické umenie postačujúce na jeho vyriešenie... Po dlhom premýšľaní som našiel ľahké pravidlo, podložené úplne presvedčivým dôkazom, pomocou ktorého je možné pri všetkých problémoch tohto druhu okamžite určiť, či sa takáto obchádzka dá urobiť cez nejaký počet mostov umiestnených akýmkoľvek spôsobom alebo nie, aby ich bolo možné znázorniť na nasledujúcom obrázku[obr.1] , v ktorom A označuje ostrov a B, C a D - časti kontinentu, oddelené od seba riečnymi ramenami. Sedem mostíkov je označených a, b, c, d, e, f, g."

(OBRÁZOK 1.1)

Pokiaľ ide o metódu, ktorú objavil na riešenie problémov tohto druhu, Euler napísal [pozri. s. 102-104]:

„Toto riešenie svojou povahou zjavne nemá veľa spoločného s matematikou a nerozumiem, prečo by sme toto riešenie mali očakávať skôr od matematika než od akejkoľvek inej osoby, pretože toto rozhodnutie je podložené iba úvahou a neexistuje Na nájdenie tohto riešenia je potrebné zapojiť všetky zákony matematiky. Neviem teda, ako sa ukázalo, že otázky, ktoré majú s matematikou len veľmi málo spoločného, ​​budú s väčšou pravdepodobnosťou riešiť matematici ako iní."

Je teda možné obísť Königsbergské mosty tak, že cez každý z týchto mostov prejdete iba raz? Aby sme našli odpoveď, pokračujme v Eulerovom liste Marinonimu:

0 "Otázkou je určiť, či je možné obísť všetkých týchto sedem mostov, pričom cez každý prejdete len raz, alebo nie. Moje pravidlo vedie k nasledovnému riešeniu tejto otázky. V prvom rade sa musíte pozrieť na to, koľko úseky sú tam oddelené vodou - tie, ktoré nemajú iný prechod z jedného do druhého okrem mosta. V tomto príklade sú takéto úseky štyri - A, B, C, D. Ďalej je potrebné rozlíšiť, či počet mosty vedúce do týchto jednotlivých úsekov sú párne alebo nepárne Takže v našom prípade vedie do úseku A päť mostov a na zvyšok po tri mosty, t.j. počet mostov vedúcich k jednotlivým úsekom je nepárny, a to samo osebe stačí vyriešiť Po určení tohto problému použijeme nasledujúce pravidlo: ak by bol počet mostov vedúcich ku každému samostatnému úseku párny, potom by bola predmetná obchádzka možná a zároveň by bolo možné začať túto obchádzku od ktorýkoľvek úsek. ak by boli nepárne, lebo len jeden nemôže byť nepárny, tak aj vtedy by sa prechod mohol dokončiť, ako je predpísané, ale určite treba vziať len začiatok obchádzky z jedného z tých dvoch úsekov, do ktorých je nepárny počet mosty vedie. Ak by konečne existovali viac ako dva úseky, ku ktorým vedie nepárny počet mostov, potom je takýto pohyb vo všeobecnosti nemožný ... ak by sa sem dali priniesť iné, vážnejšie problémy, tento spôsob by mohol byť ešte väčším prínosom a mal by nezanedbať."

Zdôvodnenie vyššie uvedeného pravidla možno nájsť v liste L. Eulera jeho priateľovi Ehlerovi z 3. apríla toho istého roku. Nižšie prerozprávame úryvok z tohto listu.

Matematik napísal, že prechod je možný, ak na rázcestí rieky nie sú viac ako dve oblasti, ku ktorým vedie nepárny počet mostov. Aby sme si to ľahšie predstavili, zmažeme už prejdené mosty na obrázku. Je ľahké skontrolovať, že ak sa začneme pohybovať v súlade s Eulerovými pravidlami, prejdeme cez jeden most a vymažeme ho, potom obrázok ukáže úsek, kde opäť nie sú viac ako dve oblasti, do ktorých vedie nepárny počet mostov, a ak sú oblasti s nepárnym počtom mostov, budeme sa nachádzať v jednom z nich. Keď budeme takto pokračovať ďalej, raz prejdeme všetky mosty.

Príbeh o mostoch mesta Königsberg má moderné pokračovanie. Otvorme si napríklad školskú učebnicu matematiky v redakcii N.Ya. Vilenkina pre šiestu triedu. V nej na strane 98 pod hlavičkou rozvíjania pozornosti a inteligencie nájdeme problém, ktorý priamo súvisí s tým, ktorý kedysi riešil Euler.

Problém č.569. Na jazere je sedem ostrovov, ktoré sú navzájom prepojené, ako je znázornené na obrázku 1.2. Na ktorý ostrov by mala loď vziať cestujúcich, aby mohli prejsť cez každý most a iba raz? Prečo sa cestujúci nemôžu prepraviť na ostrov? A?

Riešenie. Keďže tento problém je podobný problému Königsbergských mostov, pri jeho riešení použijeme aj Eulerovo pravidlo. Výsledkom je nasledujúca odpoveď: loď musí dopraviť cestujúcich na ostrov E alebo F aby mohli prejsť každý most raz. Z rovnakého Eulerovho pravidla vyplýva, že požadovaná obchádzka nie je možná, ak začína z ostrova A.

Na záver poznamenávame, že problém Königsbergských mostov a podobné problémy spolu so súborom metód na ich štúdium tvoria z praktického hľadiska veľmi dôležité odvetvie matematiky, nazývané teória grafov. Prvá práca o grafoch patrila L. Eulerovi a objavila sa v roku 1736. Následne na grafoch pracovali Koenig (1774-1833), Hamilton (1805-1865) a moderní matematici C. Berge, O. Ore, A. Zykov.

Materiál z Wikipédie – voľnej encyklopédie

Teória grafov- odvetvie diskrétnej matematiky, ktoré študuje vlastnosti grafov. Vo všeobecnom zmysle je graf reprezentovaný ako množina vrcholov(uzly) pripojené rebrá. V striktnej definícii sa takáto dvojica množín nazýva graf. $G\; =\; (V,\; E)$, Kde $V$ je podmnožinou ľubovoľnej spočítateľnej množiny a $E$- podmnožina $V\backslash krát\; V$.

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.

Terminológia teórie grafov

Znázornenie grafov na rovine

Pri zobrazovaní grafov na výkresoch sa najčastejšie používa nasledujúci systém zápisu: vrcholy grafu sú znázornené ako bodky alebo pri špecifikovaní významu vrcholu obdĺžniky, ovály atď., kde je význam vrcholu odhalený vo vnútri. obrázok (grafy vývojových diagramov algoritmov). Ak je medzi vrcholmi hrana, potom sú príslušné body (tvary) spojené čiarou alebo oblúkom. V prípade orientovaného grafu sú oblúky nahradené šípkami alebo je explicitne vyznačený smer hrany. Niekedy sú vedľa hrany umiestnené vysvetľujúce nápisy, ktoré odhaľujú význam hrany, napríklad v prechodových grafoch konečných automatov. Existujú rovinné a nerovinné grafy. Rovinný graf je graf, ktorý je možné znázorniť na obrázku (rovine) bez pretínajúcich sa hrán (najjednoduchšie sú trojuholník alebo dvojica spojených vrcholov), inak je graf nerovinný. V prípade, že graf neobsahuje cykly (obsahujúce aspoň jednu cestu raz prechádzanie hrán a vrcholov s návratom do pôvodného vrcholu), zvyčajne sa nazýva „strom“. Dôležitými typmi stromov v teórii grafov sú binárne stromy, kde každý vrchol má jednu vstupnú hranu a práve dva výstupné, alebo je konečný – nemá žiadne výstupné hrany a obsahuje jeden koreňový vrchol bez vstupnej hrany.

Obrázok grafu by sa nemal zamieňať so samotným grafom (abstraktná štruktúra), pretože k jednému grafu môže byť priradených viac ako jedno grafické zobrazenie. Obrázok má len ukázať, ktoré dvojice vrcholov sú spojené hranami a ktoré nie. V praxi je často ťažké odpovedať na otázku, či sú dva obrázky modelmi toho istého grafu alebo nie (inými slovami, či sú grafy zodpovedajúce obrázkom izomorfné). V závislosti od úlohy môžu niektoré obrázky poskytovať jasnejšie informácie ako iné.

Niektoré problémy teórie grafov

• Problém siedmich mostov Königsbergu je jedným z prvých výsledkov v teórii grafov, ktorý publikoval Euler v r.
• Štvorfarebný problém bol sformulovaný v roku 1852, ale neklasický dôkaz bol získaný až v roku 1976 (4 farby stačia na mapu na gule (rovine)).
• Problém cestujúceho obchodníka je jedným z najznámejších problémov NP-úplného.
• Problém kliky je ďalším NP-úplným problémom.
• Nájdenie minimálneho kostry.
• Izomorfizmus grafu – je možné získať ďalší prečíslovaním vrcholov jedného grafu?
• Rovinnosť grafu - je možné zobraziť graf na rovine bez priesečníkov hrán (alebo s minimálnym počtom vrstiev, čo sa používa pri sledovaní prepojení prvkov dosiek plošných spojov alebo mikroobvodov).

Aplikácia teórie grafov

pozri tiež

Napíšte recenziu na článok "Teória grafov"

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.. - NY: Springer-Verlag, 2005. - S. 422.
• Basaker R., Saati T.
• Belov V.V., Vorobiev E.M., Šatalov V.E. Teória grafov. - M.: Vyššie. škola, 1976. - S. 392.
• Berge K.
• 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.)
• Zykov A.A.. - M.: “Univerzitná kniha”, 2004. - S. 664. - ISBN 5-9502-0057-8.(M.: Nauka, 1987. 383c.)
• Chemické aplikácie topológie a teórie grafov. Ed. R. Kráľ. Za. z angličtiny M.: Mir, 1987.
• Kirsanov M. N. Grafy v Maple. M.: Fizmatlit, 2007. 168 s. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Christofides N.
• Cormen T. H. a kol.Časť VI. Algoritmy pre prácu s grafmi // Algoritmy: konštrukcia a analýza = Introduction to Algorithms. - 2. vyd. - M.: Williams, 2006. - S. 1296. - ISBN 0-07-013151-1.
• Ruda O.. - 2. vyd. - M.: Veda, 1980. - S. 336.
• Salii V. N. Bogomolov A. M.. - M.: Fyzikálna a matematická literatúra, 1997. - ISBN 5-02-015033-9.
• Swami M., Thulasiraman K.
• Tutt W.
• Wilson R.
• Harari F.. - M.: Mir, 1973.(Vyd. 3, M.: KomKniga, 2006. - 296 s.)
• Harari F., Palmer E.. - Svet, 1977.
• Sergej Melnikov// Veda a život . - 1996. - Vydanie. 3. - s. 144-145.Článok je o grafickej hre Sim, ktorú vynašiel Gustav Simmons.

Odkazy

• : program, ktorý používateľovi poskytuje širokú škálu nástrojov a metód na vizualizáciu a vyhľadávanie informácií v grafoch

Úryvok charakterizujúci teóriu grafov

Na Bagrationovom pravom boku o deviatej sa obchod ešte nezačal. Keďže princ Bagration nechcel súhlasiť s Dolgorukovovou požiadavkou začať podnikať a chcel od seba odvrátiť zodpovednosť, navrhol, aby bol Dolgorukov poslaný, aby sa na to spýtal vrchného veliteľa. Bagration vedel, že vzhľadom na vzdialenosť takmer 10 verst oddeľujúcich jeden bok od druhého, ak vyslaného nezabili (čo bolo veľmi pravdepodobné), a aj keby našiel hlavného veliteľa, čo bolo veľmi ťažké, vyslaný by sa nestihol vrátiť skôr večer.
Bagration sa rozhliadol po svojom sprievode svojimi veľkými, bezvýraznými očami bez spánku a Rostovova detská tvár, mimovoľne zamrznutá vzrušením a nádejou, bola prvá, ktorá ho upútala. Poslal to.
- Čo ak stretnem Jeho Veličenstvo pred vrchným veliteľom, Vaša Excelencia? - povedal Rostov a držal ruku na priezore.
"Môžete to odovzdať Vášmu Veličenstvu," povedal Dolgorukov a rýchlo prerušil Bagrationa.
Po uvoľnení z reťaze sa Rostovovi podarilo zaspať niekoľko hodín pred ránom a cítil sa veselý, odvážny, rozhodný, s tou elasticitou pohybov, dôverou v jeho šťastie a v nálade, v ktorej sa všetko zdá ľahké, zábavné a možné.
Všetky jeho želania sa v to ráno splnili; bola vybojovaná všeobecná bitka, zúčastnil sa na nej; Okrem toho bol poriadkom pod najodvážnejším generálom; Okrem toho cestoval na pochôdzku do Kutuzova a možno aj k samotnému panovníkovi. Ráno bolo jasné, kôň pod ním bol dobrý. Jeho duša bola veselá a šťastná. Keď dostal rozkaz, nasadol na koňa a cválal pozdĺž čiary. Najprv išiel pozdĺž línie Bagrationových jednotiek, ktoré ešte nevstúpili do akcie a stáli nehybne; potom vstúpil do priestoru obsadeného Uvarovovou kavalériou a tu si už všimol pohyby a známky príprav na prípad; Keď prešiel okolo Uvarovovej kavalérie, už zreteľne počul zvuky kanónov a streľby pred sebou. Streľba zosilnela.
Na čerstvom rannom vzduchu sa už neozývali, ako predtým, v nepravidelných intervaloch dva, tri výstrely a potom jeden alebo dva výstrely a pozdĺž svahov hôr, pred Pratzenom, sa ozývali prerušované valy streľby. tak častými výstrelmi z pištolí, že niekedy už niekoľko výstrelov z kanónov nebolo od seba oddelených, ale splývalo sa do jedného spoločného rachotu.
Bolo vidieť, ako sa dym z diel akoby rozbiehal po svahoch, dobiehali sa navzájom a ako sa dym z diel víril, rozmazával a splýval jeden s druhým. Z lesku bajonetov medzi dymom bolo vidieť pohybujúce sa masy pechoty a úzke pásy delostrelectva so zelenými krabicami.
Rostov na chvíľu zastavil koňa na kopci, aby preskúmal, čo sa deje; ale bez ohľadu na to, ako veľmi napínal svoju pozornosť, nemohol ani pochopiť, ani rozoznať nič z toho, čo sa deje: niektorí ľudia sa tam pohybovali v dyme, nejaké plachty vojska sa pohybovali vpredu aj vzadu; ale prečo? SZO? Kde? nedalo sa to pochopiť. Tento pohľad a tieto zvuky v ňom nielen nevzbudzovali tupý či bojazlivý pocit, ale naopak mu dodávali energiu a odhodlanie.
"No, viac, daj viac!" - V duchu sa obrátil k týmto zvukom a znova začal cválať pozdĺž línie a prenikal ďalej a ďalej do oblasti jednotiek, ktoré už vstúpili do akcie.
"Neviem, ako to tam bude, ale všetko bude v poriadku!" pomyslel si Rostov.
Po prejdení niekoľkých rakúskych jednotiek si Rostov všimol, že ďalšia časť línie (bola to stráž) už vstúpila do akcie.
„Tým lepšie! Pozriem sa bližšie,“ pomyslel si.
Jazdil takmer po frontovej línii. Cválalo k nemu niekoľko jazdcov. Boli to naši životní kopijníci, ktorí sa vracali z útoku v neusporiadaných radoch. Rostov prešiel okolo nich, mimovoľne zbadal jedného z nich zakrvaveného a cválal ďalej.
"Toto ma nezaujíma!" myslel si. Predtým, ako za ním prešiel niekoľko stoviek krokov, po jeho ľavej strane sa po celej dĺžke ihriska objavila obrovská masa jazdcov na čiernych koňoch v lesklých bielych uniformách, ktorí klusali priamo k nemu. Rostov dal svojho koňa do plného cvalu, aby týmto jazdcom zišiel z cesty, a bol by im ušiel, keby zachovali rovnakú chôdzu, no stále zrýchľovali, takže niektoré kone už cválali. Rostov počul ich dupot a rinčanie zbraní čoraz zreteľnejšie a ich kone, postavy a dokonca aj tváre boli čoraz viditeľnejšie. Boli to naše jazdecké stráže, ktoré išli do útoku na francúzsku jazdu, ktorá sa pohybovala smerom k nim.
Stráže jazdy cválali, no stále držali svoje kone. Rostov už videl ich tváre a počul príkaz: "pochod, pochod!" vyslovil dôstojník, ktorý v plnej rýchlosti vypustil svojho krvavého koňa. Rostov, ktorý sa obával, že bude rozdrvený alebo zlákaný do útoku na Francúzov, cválal pozdĺž frontu tak rýchlo, ako jeho kôň dokázal, a napriek tomu sa mu nepodarilo prejsť okolo nich.
Posledný strážca kavalérie, obrovský muž s posiatkami, sa nahnevane zamračil, keď pred sebou zbadal Rostova, s ktorým sa nevyhnutne zrazil. Táto jazdecká garda by určite zrazila Rostova a jeho beduína (sám Rostov sa zdal taký malý a slabý v porovnaní s týmito obrovskými ľuďmi a koňmi), keby ho nenapadlo švihnúť bičom do očí koňa jazdeckej gardy. Čierny, ťažký, päťcentimetrový kôň sa stiahol a zložil uši; ale poškriabaný jazdecký strážca jej vrazil do bokov obrovské ostrohy a kôň, mávajúc chvostom a naťahujúc krk, sa rútil ešte rýchlejšie. Len čo kavalérie prešli okolo Rostova, počul ich kričať: "Hurá!" a keď sa obzrel späť, videl, že ich predné rady sa miešajú s cudzincami, pravdepodobne Francúzmi, jazdcami v červených epoletách. Ďalej nebolo možné nič vidieť, pretože hneď nato začali odniekiaľ strieľať delá a všetko bolo zahalené dymom.
V tom momente, keď okolo neho jazdecké stráže zmizli v dyme, Rostov zaváhal, či má za nimi cválať, alebo ísť tam, kam potreboval. To bol ten brilantný útok kavalérie, ktorý prekvapil samotných Francúzov. Rostov sa neskôr zľakol, že z celej tej masy obrovských pekných ľudí, zo všetkých tých skvelých, bohatých mladých mužov, dôstojníkov a kadetov jazdiacich na tisíckach koní, ktorí okolo neho cválali, zostalo po útoku iba osemnásť ľudí.

Úvod

Začiatok teórie grafov ako matematickej disciplíny položil Euler vo svojej slávnej diskusii o Königsbergských mostoch. Tento Eulerov papier z roku 1736 bol však jediný takmer sto rokov. Záujem o problémy teórie grafov ožil okolo polovice minulého storočia a sústreďoval sa najmä v Anglicku. Dôvodov pre toto oživenie v štúdiu grafov bolo veľa. Prírodné vedy mali na to vplyv prostredníctvom štúdia elektrických obvodov, kryštálových modelov a molekulárnych štruktúr. Rozvoj formálnej logiky viedol k štúdiu binárnych vzťahov vo forme grafov. Veľké množstvo populárnych hádaniek bolo formulovaných priamo v podobe grafov, čo viedlo k pochopeniu, že mnohé problémy tohto druhu obsahujú nejaké matematické jadro, ktorého dôležitosť presahuje konkrétnu otázku. Najznámejším z týchto problémov je štvorfarebný problém, ktorý prvýkrát položil matematikom De Morgan okolo roku 1850. Žiadny problém nevygeneroval toľko dômyselných prác v oblasti teórie grafov.

Súčasné storočie je svedkom neustáleho rozvoja teórie grafov, ktorá za posledných desať až dvadsať rokov vstúpila do nového obdobia intenzívneho rozvoja. V tomto procese je zreteľne badateľný vplyv požiadaviek z nových oblastí: teórie a programovania hier, teórie prenosu správ, elektrických sietí a kontaktných obvodov, ako aj problémov psychológie a biológie.

V dôsledku tohto vývoja je téma teórie grafov už taká rozsiahla, že všetky jej hlavné smery nemožno predstaviť v jednom zväzku. V tomto prvom zväzku navrhovanej dvojzväzkovej práce sa kladie dôraz na základné koncepty a výsledky mimoriadneho systematického záujmu.

Teoretická časť

História teórie grafov

1. Problém o Königsbergských mostoch. 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 žiadne riešenie neexistuje) Kuratovský v roku 1930.

Ryža. 2

3. Problém o štyroch farbách. 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.

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.