Teória grafov je odvetvie diskrétnej matematiky, ktoré študuje objekty reprezentované ako samostatné prvky (vrcholy) a spojenia medzi nimi (oblúky, hrany).
Teória grafov pochádza z riešenia problému Königsbergského mosta v roku 1736 slávnym matematikom Leonard Euler(1707-1783: narodil sa vo Švajčiarsku, žil a pracoval v Rusku).
Problém Königsbergských mostov.
V pruskom meste Königsberg na rieke Pregal je sedem mostov. Je možné nájsť pešiu trasu, ktorá prechádza presne jedenkrát cez každý z mostov a začína a končí na rovnakom mieste?
Graf, v ktorom existuje trasa začínajúca a končiaca v rovnakom vrchole a prechádzajúca všetkými okrajmi grafu práve raz, sa nazývaEulerov graf.
Postupnosť vrcholov (môže sa opakovať), ktorými prechádza požadovaná trasa, ako aj samotná trasa, sa nazývaEulerov cyklus .
Problém troch domov a troch studní.
Sú tam tri domy a tri studne, nejako umiestnené na rovine. Nakreslite cestu z každého domu do každej studne tak, aby sa cesty nekrížili. Tento problém vyriešil (ukazuje sa, že riešenie neexistuje) Kuratovský (1896 - 1979) v roku 1930.
Problém štyroch farieb. Rozdelenie roviny na nepretínajúce sa oblasti sa nazýva kartu. Oblasti mapy sa nazývajú susedmi, ak majú spoločná hranica. Problém je vyfarbiť mapu tak, aby žiadne dve susedné oblasti neboli vyplnené rovnakou farbou. Od konca 19. storočia je známa hypotéza, že na to stačia štyri farby. Hypotéza sa zatiaľ nepotvrdila.
Podstatou publikovaného riešenia je vymenovať veľký, ale konečný počet (asi 2000) typov potenciálnych protipríkladov k teorému o štyroch farbách a ukázať, že žiadny prípad nie je protipríkladom. Tento výpočet vykonal program za približne tisíc hodín prevádzky superpočítača.
Nie je možné skontrolovať získané riešenie „ručne“ - množstvo enumerácie je nad rámec ľudských schopností. Mnohí matematici si kladú otázku: možno takýto „softvérový dôkaz“ považovať za platný dôkaz? Koniec koncov, v programe môžu byť chyby ...
Zostáva teda spoľahnúť sa na programátorskú kvalifikáciu autorov a veriť, že všetko urobili správne.
Definícia 7.1. počítať G= G(V, E) je súbor dvoch konečných množín: V - tzv veľa vrcholov a množiny E dvojíc prvkov z V, t.j. EÍV´V, tzv veľa hrán, ak sú páry nezoradené, príp veľa oblúkov ak sú páry objednané.
V prvom prípade graf G(V, E) volal neorientovaný, v druhom orientovaný.
PRÍKLAD. Graf s množinou vrcholov V = (a, b, c) a množinou hrán E = ((a, b), (b, c))
PRÍKLAD. Graf s V = (a, b, c, d, e) a E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),
Ak e=(v 1 ,v 2), eнE, potom hovoríme, že hrana e spája vrcholy v 1 a v 2 .
Volajú sa dva vrcholy v 1 , v 2 súvisiace ak ich spája hrana. V tejto situácii sa volá každý z vrcholov vedľajší zodpovedajúca hrana .
Dve rôzne rebrá priľahlé ak majú spoločný vrchol. V tejto situácii sa nazýva každá z hrán vedľajší zodpovedajúci vrchol .
Počet vrcholov grafu G označovať v a počet hrán - e:
.
Geometrická reprezentácia grafov je nasledovná:
1) vrchol grafu je bod v priestore (v rovine);
2) okraj neorientovaného grafu je segment;
3) oblúk orientovaného grafu je smerovaný segment.
Definícia 7.2. Ak v hrane e=(v 1 ,v 2) prebieha v 1 =v 2, potom sa hrana e nazýva slučka. Ak graf môže mať slučky, potom sa nazýva graf so slučkami alebo pseudograf .
Ak je dovolené, aby mal graf viac ako jednu hranu medzi dvoma vrcholmi, potom sa nazýva multigraf .
Ak je každý vrchol a (alebo) hrana grafu označený, potom sa takýto graf nazýva označené (alebo naložený ). Ako značky sa zvyčajne používajú písmená alebo celé čísla.
Definícia 7.3. Graf G (V , E ) volal podgraf (alebo časť ) počítať G(V,E), Ak V V, E E. Ak V = V, To G volal zahŕňajúci podgraf G.
Príklad 7 . 1 . Je uvedený neorientovaný graf.
Definícia 7.4. Gróf sa volá kompletný , Ak akýkoľvek dva jeho vrcholy sú spojené hranou. Kompletný graf s n vrcholy sú označené K n .
Gróf K 2 , TO 3, TO 4 a K 5 .
Definícia 7.5. Graf G=G(V, E) sa nazýva dvojdomá , Ak V možno chápať ako spojenie disjunktných množín, povedzme V=AB, takže každá hrana má tvar ( v i , v j), Kde v i A A v j B.
Každá hrana spája vrchol z A s vrcholom z B, ale žiadne dva vrcholy z A alebo dva vrcholy z B nie sú spojené.
Bipartitný graf je tzv plná dvojdomá počítať K m , n, Ak A obsahuje m vrcholy, B obsahuje n vrcholy a pre každý v i A, v j B máme ( v i , v j)E.
Teda pre každého v i A, A v j B spája ich hrana.
K 12 K 23 K 22 K 33
Príklad 7 . 2 . Vytvorte kompletný bipartitný graf K 2.4 a celý graf K 4 .
Jednotkový grafn-rozmerná kockaIN n .
Vrcholy grafu sú n-rozmerné binárne množiny. Hrany spájajú vrcholy, ktoré sa líšia rovnakou súradnicou.
Príklad: 
Medzi obyvateľmi Koenigsbergu bola bežná taká praktická hádanka: je možné prejsť cez všetky mosty cez rieku Pregolya bez toho, aby ste cez niektorý z nich prešli dvakrát? V roku 1736 sa o problém začal zaujímať významný matematik Leonhard Euler a v liste priateľovi podal prísny dôkaz, že to nie je možné. V tom istom roku dokázal pozoruhodný vzorec, ktorý spája počet vrcholov, plôch a hrán mnohostenu v trojrozmernom priestore. Vzorec je záhadne pravdivý aj pre grafy, ktoré sa nazývajú „rovinné“. Tieto dva výsledky položili základ pre teóriu grafov a sú dobrou ilustráciou smerovania jej vývoja dodnes.
O kurze
Tento kurz slúži ako úvod do moderná teória grafov. Graf ako matematický objekt sa ukazuje byť užitočný v mnohých teoretických a praktických problémoch. Ide možno o to, že zložitosť jeho štruktúry dobre zodpovedá schopnostiam nášho mozgu: táto štruktúra je vizuálna a zrozumiteľná, no na druhej strane dostatočne bohatá na to, aby zachytila mnohé netriviálne javy. Ak hovoríme o aplikáciách, potom, samozrejme, okamžite prídu na myseľ veľké siete: Internet, cestovná mapa, pokrytie mobilnej komunikácie a tak ďalej. Vyhľadávacie nástroje ako Yandex a Google sú založené na grafových algoritmoch. Okrem informatiky sa grafy aktívne používajú v bioinformatike, chémii a sociológii. V našom kurze budeme určite diskutovať o klasických problémoch, ale budeme hovoriť aj o novších výsledkoch a trendoch, napríklad o extrémnej teórii grafov.
Formátovať
Kurz pozostáva zo 7 študijných týždňov a skúšky. Na úspešné vyriešenie väčšiny úloh z testov stačí zvládnuť látku prednesenú na prednáškach. Semináre sa zaoberajú zložitejšími problémami, ktoré môžu zaujať poslucháča, ktorý už ovláda základy teórie grafov.
Informačné zdroje
- V. A. Emeličev, O. I. Meľnikov, V. I. Sarvanov, R. I. Tyškevič. Prednášky z teórie grafov. Moskva: Librocom Book House, 2009.
- A. A. Zykov. Teória konečných grafov. Novosibirsk: Nauka, 1969.
- M. Swami, K. Thulasiraman. Grafy, siete a algoritmy. M.: Mir, 1984.
- M. Aigner, G. M. Ziegler. Dôkazy Od THE KNIHA. Štvrté vydanie. Springer, 2009.
- B. Bollobás. Moderná teória grafov. Springer, 1998.
- J. A. Bondy, USA S. R. Murty. teória grafov. Springer, 2008.
Požiadavky
Materiál je prezentovaný od úplných základov a v prístupnom jazyku. Účelom tohto kurzu je nielen uviesť vás do problematiky a metód teórie grafov, ale aj rozvíjať kultúru matematického myslenia u nepripravených študentov. Preto je kurz prístupný širokému okruhu študentov. Na zvládnutie látky postačia znalosti z matematiky na dobrej školskej úrovni a základné znalosti z kombinatoriky.
Program kurzu
- Pojem graf a typy grafov.
- Rôzne aplikácie grafov: od Königsberských mostov po internet.
- Konektivita grafu, podgrafy a stupeň vrcholov.
- Ekvivalentné definície stromov.
- Planarita a Kuratovského kritérium
- Eulerov vzorec.
- Chromatické číslo rovinného grafu.
- Enumerácia stromu: Pruferov kód a Cayleyho vzorec.
- Vzorec pre počet unicyklických grafov.
- Eulerove cykly a Eulerove kritérium.
- Hamiltonove cykly. Diracovo kritérium a Khvatalovo kritérium.
- Zhoda. Hallova a Koenigova veta.
- Extrémna teória grafov. Turanova veta.
- Analóg Turanovej vety pre grafy v rovine.
- Ramseyho teória. Zoznamka medzi šiestimi ľuďmi.
- Definícia Ramseyho čísla.
- Dolná a horná hranica pre Ramseyho čísla.
Výsledky vzdelávania
V dôsledku úspešného absolvovania predmetu sa študent oboznámi s pojmom graf, s typmi a rozdielne vlastnosti a vlastnosti grafu. Poslucháč sa dozvie o problematike pravidelných vyfarbení a možnosti nakresliť daný graf na rovine bez kríženia hrán a naučí sa rôzne cesty identifikovať stromy a vyčísliť ich. Na záver sa poslucháč zoznámi s pojmami Eulerov a hamiltonovský cyklus, párovanie a dotkne sa aj problematiky extrémnej teórie grafov.
Neformálne sa dá na graf pozerať ako na množinu bodov a čiar spájajúcich tieto body so šípkami alebo bez nich.
Za prvé dielo teórie grafov ako matematickej disciplíny sa považuje Eulerov článok (1736), ktorý sa zaoberal problémom Köningsbergského mosta. Euler ukázal, že nie je možné obísť sedem mestských mostov a vrátiť sa do východiskového bodu tak, že prejdete cez každý most presne raz. 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.
S grafmi, bez toho, aby sme si to všimli, sme neustále konfrontovaní. Napríklad graf je schéma liniek metra. Body na ňom predstavujú stanice a čiary predstavujú trasy vlakov. Skúmaním nášho rodokmeňa a jeho povýšením na vzdialeného predka vytvárame takzvaný rodokmeň. A tento strom je graf.
Grafy slúžia ako vhodný prostriedok na opis vzťahov medzi objektmi. Predtým sme používali grafy ako spôsob vizualizácie konečných binárnych vzťahov.
Graf však v žiadnom prípade neslúži len na ilustráciu. Napríklad, ak vezmeme do úvahy graf zobrazujúci sieť ciest medzi nimi osady, vieme určiť trasu cesty z bodu A do bodu B. Ak je takýchto trás viacero, chceli by sme vybrať v určitom zmysle tú optimálnu, napríklad najkratšiu alebo najbezpečnejšiu. 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 musí byť formalizovaný.
Metódy teórie grafov sú široko používané v diskrétnej matematike. Nie je možné sa bez nich zaobísť pri analýze a syntéze rôznych diskrétnych prevodníkov: funkčných blokov počítačov, softvérových komplexov atď.
V súčasnosti teória grafov pokrýva množstvo materiálu a aktívne sa rozvíja. Pri jej prezentovaní sa obmedzujeme len na časť výsledkov a sústredíme sa na popis a zdôvodnenie niektorých široko používaných algoritmov grafovej analýzy, ktoré sa používajú v teórii formálnych jazykov.
Základné definície
Ako už bolo uvedené v príkladoch, grafy predstavujú spôsob, ako „vizualizovať" väzby medzi určitými objektmi. Tieto prepojenia môžu byť „smerové", ako napríklad v rodokmeni, alebo „nesmerové" (sieť obojsmerné cesty). V súlade s tým sa v teórii grafov rozlišujú dva hlavné typy grafov: riadené (alebo riadené) a neorientované.
Prezentačné metódy
Smerované a neorientované grafy sme doteraz definovali ich kreslením. Podľa definície je možné definovať graf ako pár množín, ale táto metóda je dosť ťažkopádna a je skôr teoreticky zaujímavá. Vývoj algoritmických prístupov k analýze vlastností grafov si vyžaduje iné spôsoby opisu grafov, ktoré sú vhodnejšie na praktické výpočty, vrátane počítačov. Zvážte tri najbežnejšie spôsoby znázornenia grafov.
Stromy
Definícia 5.5. Neorientovaný strom je súvislý a acyklický neorientovaný graf. Definícia 5.6. Usmernený strom sa nazýva bezkontúrový orientovaný graf, v ktorom je stupeň ktoréhokoľvek vrcholu najviac 1 a existuje práve jeden vrchol, nazývaný koreň orientovaného stromu, ktorého stupeň je 0.
Kosť s najmenšou hmotnosťou
Nasledujúci problém je v teórii grafov známy ako Steinerov problém: v rovine je daných n bodov; musíte ich spojiť s úsečkami tak, aby celková dĺžka segmentov bola najmenšia.
Metódy systematického prechádzania vrcholov grafu
Dôležitými problémami teórie grafov sú problémy globálnej analýzy neorientovaných aj orientovaných grafov. Medzi tieto úlohy patria napríklad úlohy hľadania cyklov alebo vrstevníc, výpočet dĺžok ciest medzi dvojicami vrcholov, výpis ciest s určitými vlastnosťami atď. Globálnu analýzu grafu treba odlíšiť od lokálnej, ktorej príkladom je problém určovania množín predchodcov a následníkov pevného vrcholu orientovaného grafu.
Problém cesty vo vážených orientovaných grafoch
Izomorfizmus grafu
Pre orientovaný graf (V, E) sa na množinu E oblúkov môžeme pozerať ako na graf binárnej priamej relace dosiahnuteľnosti definovanej na množine vrcholov. V neorientovanom grafe (V, E) je množina E hrán množinou neusporiadaných párov. Pre každý neusporiadaný pár (u, v) ∈ E môžeme predpokladať, že vrcholy u a v sú spojené symetrickým binárnym vzťahom p, t.j. (u, v) ∈ p a (v, u) ∈ p.
Topologické triedenie
Definícia 5.17. Orientovaná sieť (alebo jednoducho sieť) je orientovaný graf bez obrysu*. Keďže sieť je bezkontúrový graf, možno ukázať, že existujú vrcholy (uzly) siete s nulovým vonkajším stupňom, ako aj vrcholy (uzly) s nulovým vonkajším stupňom. Prvé sa nazývajú sinks alebo sieťové výstupy a druhé sa nazývajú sieťové zdroje alebo vstupy.
Prvky cyklomatiky
Pri diskusii o algoritme hĺbkového vyhľadávania v neorientovanom grafe sa zvažovala otázka nájdenia takzvaných základných cyklov grafu. Zároveň sa fundamentálny cyklus chápal ako cyklus obsahujúci presne jednu zadnú hranu a medzi základnými cyklami a zadnými hranami sa vytvorila korešpondencia jedna ku jednej, fundamentálne cykly vznikajú vždy, keď dôjde k ľubovoľnému rozdeleniu všetkých okraje neorientovaného grafu na stromové (tvoriace nejaký maximálny jednobodový les pôvodného grafu) sú pevné. graf) a inverzné a vo všeobecnom prípade môže byť toto rozdelenie špecifikované úplne nezávisle od algoritmu hĺbkového vyhľadávania. Depth-First Search je len jedným zo spôsobov implementácie takéhoto oddielu.
Kniha K. Berzha je prvou knihou o teórii grafov v ruštine. Medzitým v posledné roky Záujem o teóriu prudko vzrástol tak zo strany matematikov, ako aj predstaviteľov rôznych disciplín. Vysvetľuje to skutočnosť, že metódy teórie grafov úspešne riešia mnohé problémy teórie elektrické obvody, teória dopravných reťazcov, teória informácie, kybernetika atď.
V Bergeho knihe je teória grafov prezentovaná postupne, začínajúc od úplných základov. Predpokladá sa, že čitateľ má veľmi skromné matematické znalosti, hoci má určitú matematickú kultúru. V texte sú zahrnuté početné, často zábavné príklady. Kniha môže byť použitá na počiatočné štúdium teórie grafov. Veľa zaujímavostí v nej nájdu aj matematici-profesionáli.
Algoritmus na priamu identifikáciu Eulerovho cyklu.
[Fleury]. Zoberme si súvislý multigraf G, ktorého všetky vrcholy majú párny stupeň, a pokúste sa ho nakresliť jedným ťahom bez toho, aby ste sa uchýlili ku korekciám už nakreslenej časti trajektórie počas procesu konštrukcie. Stačí dodržiavať nasledujúce pravidlo:
1 Necháme ľubovoľný vrchol a; Každý prejdený okraj prečiarkneme.
2 Nikdy nejdeme po takej hrane u, ktorá je v súčasnosti úžinou (t. j. po odstránení ktorej sa graf tvorený neprekríženými hranami rozdelí na dve spojené zložky, z ktorých každá má aspoň jednu hranu),
Pri dodržaní tohto pravidla budeme vždy v priaznivej pozícii, pretože keď sme na x = a, graf (neprekrížených hrán) má dva vrcholy nepárneho stupňa: x a a; ak zahodíme izolované vrcholy, zostane nám súvislý graf, ktorý má na základe vety 1 Eulerovu cestu začínajúcu v x.
Obsah
Úvod
Kapitola 1. Základné definície
Množiny a viachodnotové mapovania
Graf. Cesty a obrysy
Reťaze a slučky
Kapitola 2
Kvázi-poradie definované grafom
Indukčný graf a bázy
Kapitola 3
Grundy pre nekonečný graf
Všeobecné úvahy o nekonečných grafoch
Ordinálna funkcia
Grandiho funkcie
Operácie na grafoch
Kapitola 4
Cyklomatické číslo
Chromatické číslo
Číslo internej stability
Číslo externej stability
Kapitola 5
Teorémy o existencii a jedinečnosti
Aplikácia na funkcie Grandi
Kapitola 6
Hra Nim
Všeobecná definícia hry (s úplnými podrobnosťami)
Stratégie
Kapitola 7
Procesy podľa etáp Niektoré zovšeobecnenia
Kapitola 8. Dopravné siete
Problém najväčšieho prietoku Problém najmenšieho prietoku
Problém viachodnotovo kompatibilného toku
Nekonečné dopravné siete
Kapitola 9
Stupeň výstupu a vstupu
Kapitola 10
Problém najväčšej zhody
Nedostatok jednoduchého grafu
maďarský algoritmus
Zovšeobecnenie na nekonečný prípad
Aplikácia na teóriu matíc
Kapitola 11. Faktory
Hamiltonovské dráhy a Hamiltonovské kontúry
Nájdenie faktora
Nájdenie čiastočného grafu s danými polstupňami
Kapitola 12
centrá
Polomer
Kapitola 13
Všeobecné vlastnosti silne spojených grafov bez slučiek
Priemer
Kapitola 14
Aplikácia konvenčných maticových operácií
Počítanie úloh
Problém vodcu
Aplikácia booleovských operácií
Kapitola 15
Úplne unimodulárne matice
Úplne unimodulárne systémy
Cyklomatické matice
Kapitola 16
Stromy
Analytická štúdia
veľké stromy
Kapitola 17
Eulerove cykly Eulerove kontúry
Kapitola 18
Teória striedavých obvodov
Nájdenie čiastočného grafu s danými stupňami vrcholov
Dokonalé zladenie
Aplikácia na číslo vnútornej stability
Kapitola 19
Hamiltonovské cykly a faktoroidy
Nevyhnutná a postačujúca podmienka existencie faktoroidu
Kapitola 20
artikulačné body
Grafy bez spojov
h-spojené grafy
Kapitola 21
Základné vlastnosti
Zovšeobecnenie
Prílohy
I. Všeobecná teória, hry
II. O dopravných úlohách
III. O využití, koncepciách potenciálu v dopravných sieťach
IV. Nevyriešené problémy a neoverené domnienky
V. O niektorých základných princípoch počítania (J. Riga)
VI. Dodatky k ruskému prekladu (A.A. Zykov a G.I. Kozhukhin)
Literatúra
Teória grafov a kniha K. Berzha (doslov k ruskému prekladu)
Index symbolov
menný index
Predmetový index.
Bezplatné stiahnutie elektronická kniha v pohodlnom formáte, sledujte a čítajte:
Stiahnite si knihu Teória grafov a jej aplikácie, Berge K. - fileskachat.com, rýchle a bezplatné stiahnutie.
ŠTÁTNA PEDAGOGICKÁ UNIVERZITA VLADIMÍRA
ABSTRAKT
"TEÓRIA GRAFOV"
Vykonané:
Zudina T.V.
Vladimír 2001
1. Úvod
2. História vzniku teórie grafov
3. Základné definície teórie grafov
4. Základné vety teórie grafov
5. Úlohy na aplikáciu teórie grafov
6. Aplikácia teórie grafov v školskom kurze matematiky
7. Aplikácia teórie grafov v rôznych oblastiach vedy a techniky
8. Nedávne pokroky v teórii grafov
§1. DEJINY TEÓRIE GRAFOV.
Za zakladateľa teórie grafov je považovaný matematik Leonhard Euler (1707-1783). Históriu vzniku 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 [viď. s. 41-42]:
"Raz mi bol ponúknutý problém 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 dokáže nepretržite obchádzať, pričom každý most prejde iba raz. doteraz to nedokázal. sa mi to podarilo, ale nikto nedokázal, že je to nemožné. Táto otázka, hoci banálna, sa mi však zdala hodná pozornosti, pretože na jej riešenie nestačí ani geometria, ani algebra, ani kombinatorické umenie... Po po dlhom uvažovaní som našiel ľahké pravidlo, založené na úplne presvedčivom dôkaze, pomocou ktorého sa pri všetkých problémoch tohto druhu dá okamžite určiť, či sa takýto obvod dá urobiť cez ľubovoľný počet a ľubovoľne umiestnených mostíkov alebo nie. aby ich bolo možné znázorniť na nasledujúcom obrázku[obr.1] , na ktorých A znamená ostrov a B , C a D sú časti kontinentu oddelené od seba riečnymi ramenami. Sedem mostov je označených písmenami 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]:
„Zdá sa, že toto riešenie svojou povahou nemá veľa spoločného s matematikou a nie je mi jasné, prečo by sa toto riešenie malo očakávať skôr od matematika než od akejkoľvek inej osoby, pretože toto riešenie je podporované iba rozumom a Na nájdenie tohto riešenia nie je potrebné zapájať žiadne zákony matematiky. Takže neviem, 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šené matematikmi ako inými."
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:
"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 si treba pozrieť, koľko úsekov sú oddelené vodou - také, ktoré nemajú žiadny iný prechod z jedného do druhého, s výnimkou mosta. V tomto príklade sú štyri takéto časti - A , B , C , D . Ďalej treba rozlišovať, či je počet mostov vedúcich k týmto jednotlivým úsekom párny alebo nepárny. Takže v našom prípade vedie do úseku A päť mostov a na zvyšok tri mosty, t. j. počet mostov vedúcich k jednotlivým úsekom je nepárny a tento už na vyriešenie problému stačí. Pri jeho zistení platí pravidlo: ak by bol počet mostov vedúcich ku každému jednotlivému úseku párny, potom by bol predmetný obchvat možný a zároveň by bolo možné začať tento obchvat z ktoréhokoľvek úseku. Ak by však boli dve z týchto čísiel nepárne, lebo len jedno nemôže byť nepárne, aj vtedy by sa prechod mohol uskutočniť, ako je predpísané, ale iba začiatok obchvatu sa musí nevyhnutne odobrať z jedného z tých dvoch úsekov, do ktorých nepárny počet vedie.mosty. Ak by napokon 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 tu dali uviesť iné, závažnejšie problémy, táto metóda by mohla byť ešte užitočnejšia a nemala by byť zanedbaný“.
Zdôvodnenie vyššie uvedeného pravidla možno nájsť v liste L. Eulera jeho priateľovi Elerovi 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 v rozvetvenom úseku rieky, ku ktorému vedie nepárny počet mostov, nie sú viac ako dve oblasti. Aby sme si to uľahčili, vymaž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 v prítomnosť oblastí s nepárnym počtom mostov sa budeme nachádzať v jednom z nich. Keď budeme pokračovať takto ďalej, raz prejdeme cez všetky mosty.
História mostov mesta Koenigsberg má moderné pokračovanie. Otvorme si napríklad školskú učebnicu matematiky v redakcii N.Ya. Vilenkin pre šiestu triedu. V nej na strane 98 pod hlavičkou rozvoja všímavosti a vynaliezavosti 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 cestujúci nemôžu byť doručení na ostrov A ?
(OBRÁZOK 1.2)
Riešenie. Keďže tento problém je podobný problému Königsbergského mosta, použijeme na jeho vyriešenie 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 aj nemožnosť požadovanej obchádzky, ak vychádza z ostrova A .
Na záver poznamenávame, že problém Königsbergského mosta 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. Neskôr Koenig (1774-1833), Hamilton (1805-1865) pracovali na grafoch medzi modernými matematikmi - K. Berzh, O. Ore, A. Zykov.
§2. HLAVNÉ TEÓRY TEÓRIE GRAFOV
Teória grafov, ako už bolo spomenuté vyššie, je matematická disciplína vytvorená úsilím matematikov, preto jej prezentácia zahŕňa potrebné rigorózne definície. Poďme teda k organizovanému predstaveniu základných pojmov tejto teórie.
Definícia 2.01. počítať je súbor konečného počtu bodov, tzv vrcholov graf, a párovo spájajúce niektoré z týchto vrcholov čiar, tzv rebrá alebo oblúky graf.
Táto definícia môže byť formulovaná rôzne: počítať sa nazýva neprázdna množina bodov ( vrcholov) a segmenty ( rebrá), ktorého oba konce patria danej množine bodov (pozri obr. 2.1).
(OBRÁZOK 2.1)
V nasledujúcom texte budú označené vrcholy grafu s latinskými písmenami A , B ,C ,D. Niekedy je graf ako celok označený jedným veľkým písmenom.
Definícia 2.02. Vrcholy grafu, ktoré nepatria k žiadnej hrane, sa nazývajú izolovaný .
Definícia 2.03. Nazýva sa graf pozostávajúci iba z izolovaných vrcholov nula - počítať .
Označenie: O " - graf s vrcholmi, ktorý nemá hrany (obr. 2.2).
(OBRÁZOK 2.2)
Definícia 2.04. Nazýva sa graf, v ktorom je každá dvojica vrcholov spojená hranou kompletný .
Označenie: U " – graf pozostávajúci z n vrcholy a hrany spájajúce všetky možné dvojice týchto vrcholov. Takýto graf môže byť reprezentovaný ako n- štvorec, v ktorom sú zakreslené všetky uhlopriečky (obr. 2.3).
(OBRÁZOK 2.3)
Definícia 2.05. stupňa vrcholov je počet hrán, ku ktorým patrí vrchol.
Označenie: p (A) – vrcholový stupeň A . Napríklad na obrázku 2.1: p (A)=2, p (B)=2, p (C)=2, p (D)=1, p (E)=1.
Definícia 2.06. Počet, stupeň všetkých k ktorých vrcholy sú rovnaké sa nazýva homogénne počítať stupňa k .
Obrázky 2.4 a 2.5 znázorňujú homogénne grafy druhého a tretieho stupňa.
(OBRÁZOK 2.4 a 2.5)
Definícia 2.07. Doplnok daný počítať sa nazýva graf pozostávajúci zo všetkých hrán a ich koncov, ktoré je potrebné pridať k pôvodnému grafu, aby sme získali úplný graf.
Obrázok 2.6 zobrazuje pôvodný graf G , pozostáva zo štyroch vrcholov a troch segmentov a na obrázku 2.7 - doplnok tohto grafu - graf G " .
(OBRÁZOK 2.6 a 2.7)
Na obrázku 2.5 vidíme rebrá AC A BD pretínajú v bode, ktorý nie je vrcholom grafu. Existujú však prípady, keď je potrebné daný graf znázorniť v rovine tak, aby sa jeho hrany pretínali iba vo vrcholoch (týmto problémom sa budeme podrobnejšie zaoberať neskôr, v odseku 5).
Definícia 2.08. Graf, ktorý možno znázorniť v rovine tak, že sa jeho hrany pretínajú iba vo vrcholoch, sa nazýva plochý .
Napríklad na obrázku 2.8 je znázornený rovinný graf, ktorý je izomorfný (rovnajúci sa) grafu na obrázku 2.5. Všimnite si však, že nie každý graf je rovinný, hoci opak je pravdou, t. j. každý rovinný graf možno znázorniť obvyklým spôsobom.
(OBRÁZOK 2.8)
Definícia 2.09. Mnohouholník rovinného grafu, ktorý vo vnútri neobsahuje žiadne vrcholy ani hrany grafu, sa nazýva hrana .