Teória grafov: základné pojmy a úlohy. Grafy ako dátová štruktúra. Praktická aplikácia teórie grafov Aplikovaný význam teórie grafov

1736, Koenigsberg. Mestom preteká rieka Pregelya. V meste je sedem mostov, ktoré sú umiestnené tak, ako je znázornené na obrázku vyššie. Obyvatelia Königsbergu sa už od pradávna borili s hádankou: Je možné prejsť cez všetky mosty a každý z nich prejsť iba raz? Tento problém bol vyriešený teoreticky, na papieri aj v praxi na prechádzkach - prechádzaním práve po týchto mostoch. Nikto nedokázal, že je to nemožné, ale nikto nemohol urobiť takú „tajomnú“ prechádzku cez mosty.

Problém sa podarilo vyriešiť slávnemu matematikovi Leonhardovi Eulerovi. Navyše vyriešil nielen tento konkrétny problém, ale prišiel so všeobecnou metódou riešenia podobných problémov. Pri riešení problému Königsbergských mostov Euler postupoval nasledovne: krajinu „stlačil“ do bodov a mosty „natiahol“ do línií. Takýto obrazec pozostávajúci z bodov a čiar spájajúcich tieto body sa nazýva COUNT.

Graf je súbor neprázdnej množiny vrcholov a spojení medzi vrcholmi. Kruhy sa nazývajú vrcholy grafu, čiary so šípkami sú oblúky a čiary bez šípok sú hrany.

Typy grafov:

1. Orientovaný graf(krátko digraf) - ktorých okrajom je priradený smer.

2. Neorientovaný graf je graf, v ktorom nie je žiadny smer čiar.

3. Vážený graf– oblúky alebo hrany majú váhu (dodatočné informácie).

Riešenie problémov pomocou grafov:

Úloha 1.

Riešenie: Označme vedcov ako vrcholy grafu a nakreslite čiary z každého vrcholu do štyroch ďalších vrcholov. Získame 10 riadkov, ktoré sa budú považovať za podanie rúk.

Úloha 2.

V areáli školy rastie 8 stromov: jabloň, topoľ, breza, jarabina, dub, javor, smrekovec a borovica. Jarabina je vyššia ako smrekovec, jabloň je vyššia ako javor, dub je nižší ako breza, ale vyšší ako borovica, borovica je vyššia ako jarabina, breza je nižšia ako topoľ a smrekovec je vyšší ako jabloň. Usporiadajte stromy od najkratších po najvyššie.

Riešenie:

Vrcholy grafu sú stromy označené prvým písmenom názvu stromu. V tejto úlohe sú dva vzťahy: „byť nižší“ a „byť vyšší“. Zvážte vzťah „byť nižší“ a nakreslite šípky z nižšieho stromu na vyšší. Ak problém hovorí, že horský popol je vyšší ako smrekovec, potom dáme šípku z modřínu do horského popola atď. Získame graf, ktorý ukazuje, že najkratším stromom je javor, za ním nasleduje jabloň, smrekovec, jarabina, borovica, dub, breza a topoľ.

Úloha 3.

Natasha má 2 obálky: obyčajnú a leteckú a 3 známky: obdĺžnikovú, štvorcovú a trojuholníkovú. Koľkými spôsobmi si môže Nataša vybrať obálku a známku na odoslanie listu?

Riešenie:

Nižšie je uvedený rozpis úloh.

OBECNÝ SAMOSTATNÝ VÝCHOVNÝ ÚSTAV STREDNÁ ŠKOLA č.2

Pripravené

Legkokonets Vladislav, žiak triedy 10A

Praktická aplikácia teórie grafov

Dozorca

L.I. Nosková, učiteľka matematiky

Art. Bryukhovetskaya

2011

1.Úvod……………………………………………………………………………………………….………….3

2. História vzniku teórie grafov……………………………………………….………..4

3. Základné definície a vety teórie grafov……………………………………….………6

4. Úlohy riešené pomocou grafov………………………………..………………………..8

4.1 Známe problémy………………………………………………………………...8

4.2 Niekoľko zaujímavých problémov………………………………….…………………..9

5. Aplikácia grafov v rôznych oblastiach života ľudí………………………………………...11

6. Riešenie problémov………………………………………………………………………………………………...12

7. Záver………………………………………………………………………………………………………..13

8. Zoznam referencií………….……………………………………………………………………………… 14

9. Dodatok ……………………………………………………………………………….. 15

Úvod

Teória grafov, ktorá sa zrodila z riešenia hádaniek a zábavných hier, sa teraz stala jednoduchým, prístupným a výkonným nástrojom na riešenie otázok týkajúcich sa širokého spektra problémov. Grafy sú doslova všadeprítomné. Vo forme grafov môžete napríklad interpretovať cestné mapy a elektrické obvody, geografické mapy a molekuly chemických zlúčenín, prepojenia medzi ľuďmi a skupinami ľudí. Za posledné štyri desaťročia sa teória grafov stala jedným z najrýchlejšie sa rozvíjajúcich odvetví matematiky. To je poháňané požiadavkami rýchlo sa rozširujúcej oblasti použitia. Používa sa pri návrhu integrovaných obvodov a riadiacich obvodov, pri štúdiu automatov, logických obvodov, programových blokových schém, v ekonómii a štatistike, chémii a biológii, v teórii plánovania. Preto relevantnosť Tému určuje na jednej strane obľúbenosť grafov a súvisiacich výskumných metód a na druhej strane nerozvinutý holistický systém ich implementácie.

Riešenie mnohých problémov v živote si vyžaduje dlhé výpočty a niekedy ani tieto výpočty neprinesú úspech. To je čo výskumný problém. Vynára sa otázka: či je možné nájsť jednoduché, racionálne, krátke a elegantné riešenie na ich vyriešenie. Je riešenie problémov jednoduchšie, ak používate grafy? Toto určilo téma môjho výskumu: "Praktická aplikácia teórie grafov"

Účel Výskum mal pomocou grafov naučiť, ako rýchlo riešiť praktické problémy.

Výskumná hypotéza. Grafová metóda je veľmi dôležitá a široko používaná v rôznych oblastiach vedy a ľudskej činnosti.

Ciele výskumu:

1. Preštudujte si literatúru a internetové zdroje k tejto problematike.

2.Skontrolujte účinnosť metódy grafu pri riešení praktických úloh.

3. Urobte záver.

Praktický význam štúdie je, že výsledky nepochybne vzbudia záujem mnohých ľudí. Neskúšal niekto z vás zostaviť si svoj rodokmeň? Ako to urobiť správne? Šéf dopravného podniku zrejme musí riešiť problém výhodnejšieho využívania dopravy pri preprave tovaru z miesta určenia do viacerých sídiel. Každý školák sa stretol s logickými problémami s transfúziou. Ukazuje sa, že sa dajú ľahko vyriešiť pomocou grafov.

V práci sa používajú tieto metódy: pozorovanie, vyhľadávanie, výber, analýza.

História teórie grafov

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.

„Raz som dostal problém s ostrovom, ktorý sa nachádza v meste Königsberg a obklopuje ho rieka so siedmimi mostami.

[Príloha Obr. 1] 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 jednoduché 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 mostov, ktoré sa nachádzajú alebo nie. Mosty Koenigsberg sú umiestnené tak, že ich možno znázorniť na nasledujúcom obrázku [Príloha Obr. 2], v ktorom A označuje ostrov a B, C a D - časti kontinentu oddelené od seba riečnymi ramenami

Pokiaľ ide o metódu, ktorú objavil na riešenie problémov tohto druhu, Euler napísal:

„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:

"Otázkou je určiť, či je možné obísť všetkých týchto sedem mostov, pričom každý prechádza len raz, alebo nie. Moje pravidlo vedie k nasledovnému riešeniu tejto otázky. V prvom rade sa treba pozrieť na to, koľko oblastí je sú oddelené vodou - také , ktoré nemajú žiadny iný prechod z jedného do druhého okrem mosta. V tomto príklade sú štyri takéto úseky - A, B, C, D. Ďalej je potrebné rozlíšiť, či počet počet mostov vedúcich k týmto jednotlivým úsekom je párny alebo nepárny. 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 stačí. Po určení tohto problému použijeme nasledujúce pravidlo: ak by bol počet mostov vedúcich ku každému oddelenému úseku párny, potom by bola možná obchádzka a zároveň by bolo možné začať túto obchádzka z ktoréhokoľvek úseku. Ak by však boli dve z týchto čísel, ak by boli nepárne, lebo len jedno nemôže byť nepárne, tak aj vtedy by sa prechod mohol dokončiť, ako je predpísané, ale určite treba brať len začiatok obchádzky z r. jeden z tých dvoch úsekov, ku ktorým vedie nepárny počet mostov. 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ť."

Základné definície a vety teórie grafov

Teória grafov je matematická disciplína vytvorená úsilím matematikov, preto jej prezentácia zahŕňa potrebné striktné definície. Poďme teda k organizovanému predstaveniu základných pojmov tejto teórie.

Definícia 1. Graf je súbor konečného počtu bodov, ktoré sa nazývajú vrcholy grafu, a párových čiar spájajúcich niektoré z týchto vrcholov, ktoré sa nazývajú hrany alebo oblúky grafu.

Táto definícia môže byť formulovaná rôzne: graf je neprázdna množina bodov (vrcholov) a segmentov (hran), ktorých oba konce patria danej množine bodov.

V ďalšom budeme označovať vrcholy grafu 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. Vrcholy grafu, ktoré nepatria k žiadnej hrane, sa nazývajú izolované.

Definícia 3. Graf pozostávajúci iba z izolovaných vrcholov sa nazýva nulový - počítať .

Zápis: O "– graf s vrcholmi, ktorý nemá hrany

Definícia 4. Graf, v ktorom je každá dvojica vrcholov spojená hranou, sa nazýva úplný.

Označenie: U" – graf pozostávajúci z n vrcholov a hrán spájajúcich všetky možné dvojice týchto vrcholov. Takýto graf môže byť reprezentovaný ako n-uholník, v ktorom sú nakreslené všetky uhlopriečky

Definícia 5. Stupeň vrcholu je počet hrán, ku ktorým vrchol patrí.

Definícia 6. Graf, ktorého stupne všetkých k vrcholov sú rovnaké, sa nazýva homogénny stupňový graf .

Definícia 7. Doplnkom daného grafu je graf pozostávajúci zo všetkých hrán a ich koncov, ktoré je potrebné pridať do pôvodného grafu, aby sa získal úplný graf.

Definícia 8. Graf, ktorý možno v rovine znázorniť tak, že sa jeho hrany pretínajú iba vo vrcholoch, sa nazýva rovinný.

Definícia 9. Mnohouholník rovinného grafu, ktorý neobsahuje žiadne vrcholy ani hrany grafu, sa nazýva jeho plocha.

Pojmy rovinný graf a plocha grafu sa používajú pri riešení problémov so „správnym“ vyfarbením rôznych máp.

Definícia 10. Cesta A do X je postupnosť hrán vedúcich z A do X tak, že každé dve susedné hrany majú spoločný vrchol a žiadna hrana sa nevyskytuje viac ako raz.

Definícia 11. Cyklus je cesta, na ktorej sa začiatočný a konečný bod zhodujú.

Definícia 12. Jednoduchý cyklus je cyklus, ktorý neprechádza žiadnym z vrcholov grafu viackrát.

Definícia 13. Dĺžka cesty , položené na slučke , počet hrán tejto cesty sa nazýva.

Definícia 14. Dva vrcholy A a B v grafe sa nazývajú spojené (nespojené), ak existuje (neexistuje) cesta vedúca z A do B.

Definícia 15. Graf sa nazýva spojený, ak sú spojené každé dva jeho vrcholy; ak graf obsahuje aspoň jeden pár odpojených vrcholov, potom sa graf nazýva rozpojený.

Definícia 16. Strom je súvislý graf, ktorý neobsahuje cykly.

Trojrozmerný model stromového grafu je napríklad skutočný strom so zložito rozvetvenou korunou; rieka a jej prítoky tiež tvoria strom, ale už plochý - na povrchu zeme.

Definícia 17. Odpojený graf pozostávajúci výlučne zo stromov sa nazýva les.

Definícia 18. Strom, v ktorom je všetkých n vrcholov očíslovaných od 1 do n, sa nazýva strom s prečíslovanými vrcholmi.

Preskúmali sme teda základné definície teórie grafov, bez ktorých by nebolo možné dokázať vety a následne riešiť problémy.

Problémy riešené pomocou grafov

Slávne problémy

Problém obchodného cestujúceho

Problém obchodného cestujúceho je jedným z najznámejších problémov v teórii kombinatoriky. Bol predložený v roku 1934 a najlepší matematici si na ňom vylámali zuby.

Vyhlásenie o probléme je nasledovné.
Cestujúci obchodník (putujúci obchodník) musí opustiť prvé mesto, navštíviť mestá 2,1,3..n raz v neznámom poradí a vrátiť sa do prvého mesta. Vzdialenosti medzi mestami sú známe. V akom poradí treba obchádzať mestá, aby bola uzavretá cesta (prehliadka) obchodného cestujúceho čo najkratšia?

Metóda riešenia problému obchodného cestujúceho

Chamtivý algoritmus "choďte do najbližšieho (do ktorého ste ešte nezadali) mesta."
Tento algoritmus sa nazýva „chamtivý“, pretože v posledných krokoch musíte za chamtivosť tvrdo zaplatiť.
Zoberme si napríklad sieť na obrázku [Príloha Obr. 3], predstavujúci úzky kosoštvorec. Nechajte cestujúceho obchodníka začať od mesta 1. Algoritmus „prejsť do najbližšieho mesta“ ho zavedie do mesta 2, potom 3, potom 4; v poslednom kroku budete musieť zaplatiť za svoju chamtivosť a vrátiť sa pozdĺž dlhej diagonály diamantu. Výsledkom bude nie najkratšia, ale najdlhšia túra.

Problém s mostami Königsberg.

Problém je formulovaný nasledovne.
Mesto Koenigsberg sa nachádza na brehoch rieky Pregel a dvoch ostrovov. Jednotlivé časti mesta spájalo sedem mostov. V nedeľu sa obyvatelia mesta prechádzali po meste. Otázka: Je možné urobiť prechádzku tak, že keď odídete z domu, vrátite sa späť tak, že prejdete presne raz cez každý most?
Mosty cez rieku Pregel sú umiestnené ako na obrázku[Príloha Obr.1].

Zvážte graf zodpovedajúci diagramu mostíka [Príloha Obr. 2].

Na zodpovedanie otázky problému stačí zistiť, či je graf eulerovský. (Párny počet mostov musí siahať aspoň z jedného vrcholu). Nemôžete chodiť po meste a raz prejsť všetky mosty a vrátiť sa.

Niekoľko zaujímavých úloh

1. "Trasy".

Problém 1

Ako si pamätáte, lovec mŕtvych duší Čičikov raz navštívil slávnych vlastníkov pôdy. Navštívil ich v tomto poradí: Manilov, Korobochka, Nozdryov, Sobakevič, Pljuškin, Tentetnikov, generál Betriščev, Petuch, Konstanzholgo, plukovník Koshkarev. Našiel sa diagram, na ktorom Čičikov načrtol vzájomnú polohu panstiev a vidieckych ciest, ktoré ich spájajú. Určte, ktorá usadlosť patrí komu, ak Čičikov nejazdil po žiadnej z ciest viackrát [Príloha Obr. 4].

Riešenie:

Cestná mapa ukazuje, že Čičikov začal svoju cestu z panstva E a skončil s panstvom O. Všimli sme si, že do panstiev B a C vedú len dve cesty, takže Čičikov musel cestovať po týchto cestách. Označme ich hrubou čiarou. Boli identifikované úseky trasy prechádzajúcej cez A: AC a AB. Čičikov necestoval po cestách AE, AK a AM. Preškrtnime ich. Označme tučnou čiarou ED; Prečiarkneme DK. Prečiarkneme MO a MN; Označme tučnou čiarou MF; prečiarknuť FO; Označme FH, NK a KO hrubou čiarou. Nájdime jedinú možnú cestu za tejto podmienky. A dostaneme: panstvo E - patrí Manilovovi, D - Korobochka, C - Nozdryov, A - Sobakevič, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Príloha Obr. 5].

Problém 2

Na obrázku je znázornená mapa oblasti [Príloha Obr. 6].

Pohybovať sa môžete len v smere šípok. Každý bod môžete navštíviť maximálne raz. Koľkými spôsobmi sa môžete dostať z bodu 1 do bodu 9? Ktorá trasa je najkratšia a ktorá najdlhšia.

Riešenie:

Postupne „stratifikujeme“ obvod do stromu, začínajúc od vrcholu 1 [Príloha Obr. 7]. Zoberme si strom. Počet možných spôsobov, ako sa dostať od 1 do 9, sa rovná počtu „visiacich“ vrcholov stromu (je ich 14). Je zrejmé, že najkratšia cesta je 1-5-9; najdlhšia je 1-2-3-6-5-7-8-9.

2 "Skupiny, zoznamka"

Problém 1

Účastníci hudobného festivalu si po stretnutí vymenili obálky s adresami. Dokáž, že:

a) bol odovzdaný párny počet obálok;

b) počet účastníkov, ktorí si vymenili obálky nepárny počet krát, je párny.

Riešenie: Nech sú účastníci festivalu A 1, A 2, A 3. . . , A n sú vrcholy grafu a hrany spájajú dvojice vrcholov reprezentujúcich chlapcov, ktorí si vymieňajú obálky [Príloha Obr. 8]

Riešenie:

a) stupeň každého vrcholu A i ukazuje počet obálok, ktoré dal účastník A i svojim priateľom. Celkový počet prenesených obálok N sa rovná súčtu stupňov všetkých vrcholov grafu N = stupeň. Krok 1 +. A 2 + +. . . + krok. A n -1 + stupeň. A n, N =2p, kde p je počet hrán grafu, t.j. N – párne. Následne bol odovzdaný párny počet obálok;

b) v rovnosti N = stupeň. Krok 1 +. A 2 + +. . . + krok. A n -1 + stupeň. A n súčet nepárnych členov musí byť párny, a to môže byť len vtedy, ak je počet nepárnych členov párny. To znamená, že počet účastníkov, ktorí si vymenili obálky nepárny počet krát, je párny.

Problém 2

Jedného dňa sa Andrei, Boris, Volodya, Dasha a Galya dohodli, že pôjdu večer do kina. Rozhodli sa koordinovať výber kina a predstavenia cez telefón. Tiež sa rozhodlo, že ak sa nebude dať s niekým skontaktovať telefonicky, tak sa výlet do kina ruší. Večer sa v kine nezišli všetci, a preto bola návšteva kina zrušená. Na druhý deň začali zisťovať, kto komu volal. Ukázalo sa, že Andrey volal Boris a Volodya, Voloďa volala Boris a Dáša, Boris volal Andrej a Dáša, Dáša volala Andrej a Voloďa a Galya volala Andrej, Voloďa a Boris. Kto sa nevedel dovolať a teda neprišiel na stretnutie?

Riešenie:

Nakreslíme päť bodiek a označíme ich písmenami A, B, C, D, D. Toto sú prvé písmená mien. Spojme bodky, ktoré zodpovedajú menám chlapcov, ktorí volali.

[Príloha Obr. 9]

Z obrázku je zrejmé, že každý z chlapcov - Andrey, Boris a Voloďa - telefonoval všetkým ostatným. Preto títo chalani prišli do kina. Ale Galya a Dasha sa nedokázali navzájom dotelefonovať (body G a E nie sú spojené úsečkou), a preto v súlade s dohodou neprišli do kina.

Aplikácia grafov v rôznych oblastiach života ľudí

Okrem uvedených príkladov majú grafy široké využitie v stavebníctve, elektrotechnike, manažmente, logistike, geografii, strojárstve, sociológii, programovaní, automatizácii technologických procesov a výroby, psychológii, reklame. Takže zo všetkého vyššie uvedeného nevyvrátiteľne vyplýva praktická hodnota teórie grafov, ktorej dôkaz bol cieľom tejto štúdie.

V akejkoľvek oblasti vedy a techniky sa stretnete s grafmi. Grafy sú nádherné matematické objekty, s ktorými môžete riešiť matematické, ekonomické a logické úlohy, rôzne hlavolamy a zjednodušiť podmienky problémov vo fyzike, chémii, elektronike a automatizácii. Mnohé matematické fakty sa dajú pohodlne formulovať v jazyku grafov. Teória grafov je súčasťou mnohých vied. Teória grafov je jednou z najkrajších a najkrajších matematických teórií. Teória grafov v poslednej dobe nachádza čoraz viac aplikácií v aplikovanej problematike. Dokonca sa objavila aj výpočtová chémia – relatívne mladá oblasť chémie založená na aplikácii teórie grafov.

Molekulové grafy, používané v stereochémii a štruktúrnej topológii, chémii klastrov, polymérov atď., sú neorientované grafy zobrazujúce štruktúru molekúl [Príloha Obr. 10]. Vrcholy a hrany týchto grafov zodpovedajú zodpovedajúcim atómom a chemickým väzbám medzi nimi.

Molekulové grafy a stromy: [Príloha Obr. 10] a, b - multigrafy, resp. etylén a formaldehyd; hovoria izoméry pentánu (stromy 4, 5 sú izomorfné so stromom 2).

V stereochémii organizmov najviac. Často sa používajú molekulárne stromy - hlavné stromy molekulových grafov, ktoré obsahujú len všetky vrcholy zodpovedajúce atómom C. Zostavovanie množín mol. stromy a stanovenie ich izomorfizmu umožňujú určiť, že hovoria. štruktúry a nájdite celkový počet izomérov alkánov, alkénov a alkínov

Proteínové siete

Proteínové siete sú skupiny fyzicky interagujúcich proteínov, ktoré fungujú v bunke spoločne a koordinovane a riadia vzájomne prepojené procesy prebiehajúce v tele. [príloha obr. jedenásť].

Hierarchický systémový graf nazývaný strom. Charakteristickým rysom stromu je, že medzi akýmikoľvek dvoma jeho vrcholmi je len jedna cesta. Strom neobsahuje cykly ani slučky.

Strom reprezentujúci hierarchický systém má zvyčajne jeden hlavný vrchol, ktorý sa nazýva koreň stromu. Každý vrchol stromu (okrem koreňa) má len jedného predka – ním určený objekt je zahrnutý v jednej triede najvyššej úrovne. Ktorýkoľvek vrchol stromu môže generovať niekoľko potomkov - vrcholov zodpovedajúcich triedam nižšej úrovne.

Pre každý pár vrcholov stromov existuje jedinečná cesta, ktorá ich spája. Táto vlastnosť sa používa pri hľadaní všetkých predkov, napríklad v mužskej línii, akejkoľvek osoby, ktorej rodokmeň je reprezentovaný vo forme rodokmeňa, čo je „strom“ v zmysle teórie grafov.

Príklad môjho rodokmeňa [Príloha Obr. 12].

Ešte jeden príklad. Na obrázku je biblický rodokmeň [Príloha Obr. 13].

Riešenie problémov

1.Prepravná úloha. Nech je v meste Krasnodar základňa so surovinami, ktoré je potrebné distribuovať do miest Krymsk, Temryuk, Slavyansk-on-Kuban a Timashevsk v rámci jednej cesty, pričom minú čo najmenej času a paliva a vrátia sa späť do Krasnodaru .

Riešenie:

Najprv si urobme graf všetkých možných ciest [Príloha Obr. 14], berúc do úvahy skutočné cesty medzi týmito sídlami a vzdialenosť medzi nimi. Na vyriešenie tohto problému musíme vytvoriť ďalší graf, stromový [Príloha Obr. 15].

Pre pohodlie riešenia označujeme mestá číslami: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Výsledkom je 24 riešení, no potrebujeme len tie najkratšie cesty. Zo všetkých riešení sú vyhovujúce len dve, to je 350 km.

Podobne je možné a myslím si, že aj potrebné vypočítať reálnu prepravu z jednej lokality do druhej.

Logický problém týkajúci sa transfúzie. Vedro obsahuje 8 litrov vody a dve panvice s objemom 5 a 3 litre. musíte naliať 4 litre vody do päťlitrovej panvice a nechať 4 litre vo vedre, t.j. vodu nalejte rovnomerne do vedra a veľkej panvice.

Riešenie:

Situáciu v každom okamihu možno opísať tromi číslami [Príloha Obr. 16].

Výsledkom sú dve riešenia: jedno na 7 ťahov, druhé na 8 ťahov.

Záver

Aby ste sa naučili riešiť problémy, musíte pochopiť, čo sú, ako sú štruktúrované, z akých komponentov sa skladajú, aké sú nástroje, pomocou ktorých sa problémy riešia.

Pri riešení praktických úloh pomocou teórie grafov sa ukázalo, že v každom kroku, v každej fáze ich riešenia je potrebné uplatniť kreativitu.

Od samého začiatku, v prvej fáze, spočíva v tom, že musíte byť schopní analyzovať a zakódovať stav problému. Druhým stupňom je schematický zápis, ktorý pozostáva z geometrického znázornenia grafov, pričom v tomto štádiu je prvok tvorivosti veľmi dôležitý, pretože nie je ľahké nájsť zhody medzi prvkami podmienky a zodpovedajúcimi prvkami graf.

Pri riešení dopravného problému alebo úlohe zostaviť rodokmeň som dospel k záveru, že metóda grafov je určite zaujímavá, krásna a názorná.

Presvedčil som sa, že grafy sú široko používané v ekonomike, manažmente a technológiách. Teória grafov sa používa aj v programovaní. O tom sa v tejto práci nehovorilo, ale myslím si, že je to len otázka času.

Táto vedecká práca skúma matematické grafy, oblasti ich použitia a rieši niekoľko problémov pomocou grafov. Znalosť základov teórie grafov je potrebná v rôznych oblastiach súvisiacich s riadením výroby a obchodu (napríklad harmonogram výstavby siete, harmonogramy doručovania pošty). Okrem toho som si pri práci na vedeckej práci osvojil prácu na počítači pomocou textového editora WORD. Ciele vedeckej práce sú teda splnené.

Takže zo všetkého uvedeného nevyvrátiteľne vyplýva praktická hodnota teórie grafov, ktorej dôkaz bol cieľom tejto práce.

Literatúra

Berge K. Teória grafov a jej aplikácie. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J.Úvod do konečnej matematiky. -M.: IIL, 1963.

Ruda O. Grafy a ich aplikácia. -M.: Mir, 1965.

Harari F. Teória grafov. -M.: Mir, 1973.

Zykov A.A. Teória konečných grafov. -Novosibirsk: Veda, 1969.

Berezina L.Yu. Grafy a ich aplikácia. -M.: Školstvo, 1979. -144 s.

"Soros Educational Journal" č. 11 1996 (článok "Ploché grafy");

Gardner M. "Matematický voľný čas", M. "Svet", 1972 (kapitola 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. „Staré zábavné problémy“, M. „Veda“, 1988 (časť 2, oddiel 8; príloha 4);

Aplikácia

Ryža. 6

Ryža. 7

Ryža. 8

aplikácie

Aplikácia

Ryža. 14

aplikácie

Aplikácia

Spomedzi problémov spojených s riešením logických problémov priťahuje v posledných rokoch veľkú pozornosť výskumníkov otázka aplikácie teórie grafov na tento typ problémov.

Teória grafov je v súčasnosti intenzívne sa rozvíjajúcim odvetvím diskrétnej matematiky. Vysvetľuje to skutočnosť, že mnohé objekty a situácie sú opísané vo forme grafových modelov: komunikačné siete, obvody elektrických a elektronických zariadení, chemické molekuly, vzťahy medzi ľuďmi a oveľa viac.

Grafické úlohy majú množstvo výhod, ktoré umožňujú ich využitie na rozvoj fantázie a zlepšenie logického myslenia. Problémy s grafmi môžu byť prezentované zábavnou, hravou formou.

Predmet výskumu v tejto práci je riešenie logických úloh pomocou grafov.

Účel štúdie: použiť grafový aparát na riešenie logických problémov.

hypotéza: Podľa nášho názoru bude riešenie mnohých logických problémov menej náročné na prácu, použijeme na to teóriu grafov.

Ciele výskumu:

zvážiť riešenie problémov pomocou grafov;

naučiť sa prekladať problémy do jazyka grafov;

porovnať tradičné metódy riešenia problémov s metódami teórie grafov.

V roku 1736 našiel veľký matematik Leonhard Euler riešenie hádanky nazvanej Problém Königsbergského mosta. Rieka Pregel pretekajúca Kaliningradom (predtým sa mesto volalo Königsberg) obmýva dva ostrovy (obr. Obrázok 1 Obrázok 1). V Eulerových časoch boli brehy rieky a ostrovy spojené mostami, ako je znázornené na obrázku. Hádanka si vyžadovala nájsť cestu, ktorá raz prechádzala všetkými štyrmi pevninami a koniec a začiatok cesty sa musia zhodovať.

Obrázok 1

L. Euler dokázal, že neexistuje cesta, ktorá by spĺňala podmienky hlavolamu, a vypracoval teóriu na riešenie tohto druhu hlavolamu. Po znalosti materiálu v úvodnej časti kurzu „Úvod do grafov“ nie je ťažké reprodukovať myšlienku úvahy L. Eulera. Aby ste to dosiahli, musíte najskôr nahradiť obrázok 1 diagramom znázorneným na obrázku 2, kde sú ostrovy a pobrežia znázornené bodkami.

Obrázok 2

Diagram zobrazený na obrázku 2 nie je, striktne povedané, graf: má viacero hrán. Za rok zrodu teórie grafov sa však všeobecne považuje rok 1736, kedy bola táto hádanka vyriešená.

O viac ako sto rokov neskôr, v roku 1874, nemecký vedec G. Kirchhoff vyvinul účinnú metódu na určenie hodnoty prúdu v elektrickom obvode pomocou metód a konceptov, ktoré neskôr získali občianske práva v teórii grafov. O ďalších 10 rokov neskôr anglický matematik A. Keli (jeho matka bola Ruska, hovoril po rusky a sledoval ruskú matematickú literatúru; patril medzi tých pár matematikov, ktorí od samého začiatku rozumeli a podporovali myšlienky N.I. Lobačevského) rozvinul teóriu tzv. stromy spočítať počet izomérov nasýtených uhľovodíkov s daným počtom n atómov uhlíka.

V matematike je graf konečný súbor bodov nazývaných vrcholy; ktoré z nich sú navzájom spojené čiarami nazývanými hrany grafu.

Graf je množina bodov zobrazených na rovine (list papiera, doska), ktorých páry sú spojené čiarami. Body sa nazývajú vrcholy grafu, čiary sa nazývajú hrany. Stupeň vrcholu je počet hrán vychádzajúcich z vrcholu.

Pri pohľade na geografickú mapu okamžite upúta železničná sieť. Toto je typický graf: kruhy predstavujú stanice, ktoré sú vrcholmi grafu, a cesty, ktoré ich spájajú, predstavujú hrany.

Obrázok 3

Graf na Obr. Obrázok 3 znázorňuje diagram ciest medzi obcami M, A, B, C a D. Tu sú každé dva vrcholy spojené hranou. Takýto graf sa nazýva úplný. Čísla na obrázku označujú vzdialenosti medzi obcami pozdĺž týchto ciest. Nech je v obci M pošta a poštár musí doručovať listy do ostatných štyroch dedín. Existuje mnoho rôznych cestovateľských trás. Ako si vybrať ten najkratší? Najjednoduchším spôsobom je analyzovať všetky možnosti. Pomôže vám k tomu nový graf, ktorý vám umožní ľahko zobraziť možné trasy. Vrchol M na vrchole je začiatkom trás. Odtiaľ môžete začať cestu štyrmi rôznymi spôsobmi: do A, do B, do C alebo do D. Po návšteve jednej z dedín sú tri možnosti pokračovania v trase, potom dve, potom cesta do poslednej dediny a opäť do M. Spolu 43 21  24 spôsobov.

Podobné problémy často vznikajú pri hľadaní najlepších možností distribúcie tovaru do obchodov a materiálu na staveniská.

Zvážte jeden z najjednoduchších problémov: „Červené, modré, žlté a zelené ceruzky sú v štyroch škatuliach, po jednom. Farba ceruzky je iná ako farba krabičky. Je známe, že zelená ceruzka je v modrej krabici, ale červená ceruzka nie je v žltej. V ktorej škatuľke sú jednotlivé ceruzky?

Ceruzky a škatuľky označme bodkami. Plná čiara znamená, že ceruzka je v príslušnom rámčeku, a bodkovaná čiara znamená, že nie je. Potom, berúc do úvahy problém, máme G 1 (Obr. Obrázok 4).

Obrázok 4

Ďalej dokončíme graf podľa nasledujúceho pravidla: keďže v rámčeku môže ležať práve jedna ceruzka, z každého bodu by mala vychádzať jedna plná čiara a tri bodkované. Výsledkom je graf G 2 , ktorý ponúka riešenie problému.

Pri riešení problémov, ktoré sa v populárno-náučnej a metodickej literatúre zvyčajne nazývajú logickými, sa spravidla nijako výrazne neopierajú o školské vedomosti a zručnosti. V tomto smere sú tradične považované za meradlo vynaliezavosti, za ukazovateľ úrovne matematických schopností, bystrosti myslenia, schopnosti používať pamäť a často sa o nich diskutuje v školských matematických kluboch.

Riešenie mnohých logických problémov pomocou grafov je celkom prístupné mladším ročníkom. K tomu im stačí len intuitívne chápanie grafov a ich najzrejmejších vlastností.

Pozrime sa na príklady použitia grafov na riešenie niektorých známych problémov. V tomto prípade budeme objekty reprezentovať bodmi a vzťahy medzi nimi – segmentmi (polohy bodov a dĺžky segmentov sú ľubovoľné).

Objasnenie štruktúr logických problémov z hľadiska aplikovaných metód riešenia umožňuje izolovať určité triedy takýchto problémov.

Úloha 1. Rozprávajú sa traja priatelia: Belokurov, Černov a Ryzhov. Brunetka povedala Belokurovovi: "Je zvláštne, že jeden z nás je blond, ďalší je bruneta, tretí je červený, ale nikto nemá farbu vlasov, ktorá sa nezhoduje s jeho priezviskom." Akú farbu vlasov má každý z vašich priateľov?

Uveďme podrobné riešenie. Zostrojme graf vzťahu špecifikovaného v probléme. Aby sme to urobili, v prvom rade zvýraznime veľa priezvisk M a veľa farieb na vlasy TO, ktorých prvky budú označené bodkami. Stanovte body M nazvime ich písmenami B, Ch, R (Belokurov, Černov a Ryzhov); body druhej sady - b, br, p (blond, bruneta, červená). Ak bod z jednej množiny zodpovedá bodu z inej, spojíme ich plnou čiarou a ak nezodpovedá, spojíme prerušovanou čiarou. Stav problému naznačuje iba nezrovnalosti, preto by sa mal najskôr objaviť graf znázornený na obrázku 5.

Obrázok 5

Z podmienok úlohy vyplýva, že pre každý bod z množiny M je len jedna tonka z mnohých TO,čo zodpovedá prvému a naopak každému bodu z množiny TO zodpovedá iba jednému bodu z množiny M.Úlohou je nájsť túto jedinú možnú zhodu medzi prvkami množín M A TO, t.j. nájsť tri plné čiary spájajúce zodpovedajúce body množín.

Princíp riešenia problému je jednoduchý. Ak je nejaký bod spojený s dvoma bodmi inej množiny prerušovanými čiarami, potom musí byť spojený s jeho tretím bodom plnou čiarou. Preto je graf na obrázku 5 doplnený o plné čiary spájajúce body B a p, P a b (obrázok 6).

Obrázok 7

V grafe tohto obrázku teda automaticky čítame odpoveď: Belokurov je ryšavý, Černov je blond, Ryzhov je bruneta. Rovnakú techniku možno použiť napríklad na riešenie úloh 2 a 3.

Úloha 2. Pre Vanyu, Kolju a Miša sa piekli koláče: jeden s kapustou, druhý s ryžou, tretí s jablkami. Misha nemá rád jablkový koláč a neje ho s kapustou. Váňa nemá rád kapustnicu. Kto jedáva aký koláč?

Úloha 3. Traja priatelia pracujú v tej istej továrni: mechanik, sústružník a zvárač. Ich priezviská sú Borisov, Ivanov a Semenov. Zámočník nemá bratov ani sestry, je najmladší zo svojich priateľov. Semenov, ženatý s Borisovovou sestrou, je starší ako sústružník. Ako sa volá mechanik, sústružník a zvárač?

Vyššie uvedené problémy je možné úspešne vyriešiť pomocou tabuliek. Táto metóda alebo jej modifikácie sú odporúčané a rozoberané v mnohých populárno-náučných knihách a učebných pomôckach. Je však možné označiť triedy problémov, v ktorých sa použitie grafov reprezentovaných bodmi a segmentmi ukazuje ako vhodnejšie a opodstatnenejšie. Použitie metódy tabuliek, ako sú turnajové tabuľky alebo ich zovšeobecnenia v rozhodnutiach, si vynucuje, aby bola dôležitá časť zdôvodňovania vykonaná „ústne“. Zároveň sa musíte opakovane vracať k podmienkam problému, k priebežným výsledkom, veľa si zapamätať a použiť informácie prijaté v správnom čase. Tento typ problému zahŕňa problémy s tromi alebo viacerými skupinami posudzovaných objektov.

Úloha 4. Traja súdruhovia - Ivan, Dmitrij a Stepan - učí rôzne predmety (chémia, biológia, fyzika) na školách v Moskve, Leningrade a Kyjeve. Známe:

1. Ivan nepracuje v Moskve a Dmitrij nepracuje v Leningrade;

2. Moskvič neučí fyziku;

3. Ten, kto pracuje v Leningrade, učí chémiu;

4. Dmitrij neučí biológiu.

Aký predmet a v akom meste každý zo súdruhov učí?

Riešenie. Rozlišujme tri množiny: množinu mien, množinu objektov a množinu miest. Prvok každej množiny na obrázku 4 je daný vlastným bodom (písmená na tomto obrázku sú prvé písmená zodpovedajúcich slov). Ak dva body z rôznych množín charakterizujú vlastnosti rôznych ľudí, potom takéto body spojíme prerušovanou čiarou. Ak dva body z rôznych množín zodpovedajú vlastnostiam jednej osoby, potom takéto body spojíme do párov plnými čiarami. Je dôležité, aby podľa podmienok úlohy pre každý bod ktorejkoľvek množiny v každej z ostatných množín existoval jeden a len jeden bod, ktorý mu zodpovedá.

Obrázok 8

Graf na obrázku 8 teda obsahuje všetky prvky množín špecifikované v podmienke a vzťahy medzi nimi. Problém v jazyku grafov spočíva v nájdení troch „plných“ trojuholníkov s vrcholmi v rôznych množinách.

Pozrime sa na graf na obrázku 8. Prerušovaná úsečka XD sa sama o sebe naznačuje. A skutočne zodpovedá X a zároveň A nezodpovedá D, t.j. X nemôže zodpovedať D. Typická grafová operácia pre toto používa sa druh úlohy: ak trojuholník s vrcholmi v troch rôznych množinách, jedna strana je plná, druhá je prerušovaná, potom musí byť tretia prerušovaná. Z podmienok úlohy vyplýva, že ďalšia operácia na grafe je jednotná: ak je nejaký bod spojený čiarkovanými úsečkami s dvoma bodmi v druhej množine, potom by mal byť spojený s tretím bodom tejto množiny plnou úsečkou. Takto sa kreslí súvislý segment DF. Ďalej nakreslite prerušovanú úsečku DM (v trojuholníku DFM je strana DF plná a FM prerušovaná), DK je plná (DM a DL sú prerušované), Teraz spojíme body F a K plnou úsečkou. Ak v trojuholníku s vrcholmi v rôznych súboroch sú dve strany plné, potom bude aj tretia plná. Bol nájdený prvý „plný“ trojuholník DFK. Takže bez toho, aby sme sa vracali k textu úlohy, riadení len prirodzenými operáciami na grafe popísanom vyššie, nájdeme riešenie (obr. 9).

Obrázok 9

Všimnime si poradie, v ktorom boli segmenty uskutočnené: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. Vrcholy každého z troch výsledných „plných“ trojuholníkov určujú odpoveď na problém: Ivan učí chémiu v Leningrade, Dmitrij učí fyziku v Kyjeve a Stepan učí biológiu v Moskve.

V nasledujúcom probléme použitie grafov pomáha odhaliť prítomnosť dvoch riešení.

Úloha 5. Masha, Lida, Zhenya a Katya vedia hrať na rôzne nástroje (violončelo, klavír, gitara a husle), ale každá len na jednom. Hovoria aj rôznymi cudzími jazykmi (angličtina, francúzština, nemčina a španielčina), ale každý len na jednom Je známe:

1. dievča, ktoré hrá na gitare, hovorí po španielsky;

2. Lída nehrá na husle ani na violončelo a nevie po anglicky;

3. Máša nehrá na husle ani violončelo a nevie po anglicky;

4. dievča, ktoré hovorí po nemecky, nehrá na violončelo;

5. Zhenya vie po francúzsky, ale nehrá na husle.

Kto hrá na aký nástroj a aký cudzí jazyk ovláda?

Problémové podmienky zodpovedajú grafu na obrázku 10.

Obrázok 10

Zápis a princíp riešenia sú tu rovnaké ako v úlohe 4. Nakreslime postupne tieto telesové segmenty: KS, VZH, VF, AK (obr. 11).

Obrázok 11

Vzniknú tak dva „plné“ trojuholníky ZHVF a KSA. Vykonávame ďalší súvislý segment nosnej rakety. Teraz sme presvedčení, že podmienky úlohy nezabezpečujú jednoznačnú voľbu tretieho bodu pre každú z dvojíc RN a GI. Pre „plné“ trojuholníky sú možné nasledujúce možnosti: MGI a OSR alebo LGI a MRN. Problém má teda dve riešenia.

Uveďme problém, v ktorom graf umožňuje pomerne jednoducho odhaliť redundanciu podmienky.

Úloha 6. Šachového turnaja sa zúčastnilo šesť partnerov z rôznych profesií: sústružník, mechanik, strojár, učiteľ, lekár a vodič. Známe:

1. v prvom kole hral Andreev s lekárom, učiteľ s Borisovom a Grigoriev s Evdokimovom;

2. v druhom kole hral Dmitriev s turnerom a doktor s Borisovom;

3. v treťom kole hral Evdokimov s inžinierom;

4. na konci turnaja sa miesta rozdelili takto - Borisovjamiesto, zdieľali Grigoriev a inžinierIIAIIImiesta, obsadil DmitrievIVmiesto a Zolotarev s mechanikom si rozdelili piate a šieste miesto.

Aké povolania mali Grigoriev, Dmitriev a Evdokimov?

Text práce je uverejnený bez obrázkov a vzorcov.
Plná verzia diela je dostupná v záložke „Pracovné súbory“ vo formáte PDF

ÚVOD

"V matematike si netreba pamätať vzorce, ale proces myslenia..."

E. I. Ignatiev

Teória grafov je v súčasnosti intenzívne sa rozvíjajúcim odvetvím matematiky. Vysvetľuje to skutočnosť, že mnohé objekty a situácie sú popísané vo forme grafových modelov, čo je veľmi dôležité pre normálne fungovanie spoločenského života. Práve tento faktor určuje relevantnosť ich podrobnejšieho štúdia. Preto je téma tejto práce dosť aktuálna.

Cieľ výskumná práca: zistiť znaky aplikácie teórie grafov v rôznych oblastiach poznania a pri riešení logických problémov.

Cieľ identifikoval nasledovné úlohy:

zoznámiť sa s históriou teórie grafov;

študovať základné pojmy teórie grafov a hlavné charakteristiky grafov;

ukázať praktickú aplikáciu teórie grafov v rôznych oblastiach poznania;

Zvážte spôsoby riešenia problémov pomocou grafov a vytvorte si vlastné problémy.

Objekt výskum: sféra ľudskej činnosti pre aplikáciu metódy grafu.

Položka Výskum: časť matematiky „Teória grafov“.

Hypotéza. Predpokladáme, že učenie sa teórie grafov môže študentom pomôcť vyriešiť logické úlohy v matematike, čo bude formovať ich budúce záujmy.

Metódy výskumná práca:

Počas nášho výskumu boli použité nasledujúce metódy:

1) Práca s rôznymi zdrojmi informácií.

2) Popis, zber, systematizácia materiálu.

3) Pozorovanie, analýza a porovnávanie.

4) Príprava úloh.

Teoretický a praktický význam Táto práca je daná tým, že výsledky je možné využiť v informatike, matematike, geometrii, kreslení a vyučovaní v triede, ako aj pre široký okruh čitateľov so záujmom o túto tému. Výskumná práca má jednoznačné praktické zameranie, keďže autor v práci uvádza množstvo príkladov využitia grafov v mnohých oblastiach poznania a vypracoval si vlastné úlohy. Tento materiál možno použiť na voliteľných hodinách matematiky.

KAPITOLA I. TEORETICKÝ PREHĽAD MATERIÁLU K TÉME VÝSKUMU

V matematike môže byť „graf“ znázornený ako obrázok, ktorý predstavuje niekoľko bodov spojených čiarami. „Gróf“ pochádza z latinského slova „graphio“ – píšem, ako známy šľachtický titul.

V matematike je definícia grafu daná takto:

Pojem „graf“ je v matematike definovaný takto:

Graf - toto je konečná množina bodov - vrcholov, ktoré môžu byť spojené čiarami - rebrá .

Príklady grafov zahŕňajú nákresy polygónov, elektrických obvodov, schematické znázornenia leteckých spoločností, metra, ciest atď. Rodokmeň je tiež graf, kde vrcholy sú členmi klanu a rodinné väzby fungujú ako okraje grafu.

Ryža. 1 Príklady grafov

Počet hrán, ktoré patria k jednému vrcholu, sa nazýva stupeň vrcholu grafu . Ak je stupeň vrcholu nepárne číslo, vrchol sa nazýva - zvláštny . Ak je stupeň vrcholu párne číslo, potom sa vrchol nazýva dokonca.

Ryža. 2 vrchol grafu

Nulový graf je graf pozostávajúci iba z izolovaných vrcholov, ktoré nie sú spojené hranami.

Kompletný graf je graf, v ktorom je každá dvojica vrcholov spojená hranou. Ako príklad úplného grafu môže slúžiť N-uholník, v ktorom sú nakreslené všetky uhlopriečky.

Ak vyberiete cestu v grafe, kde sa počiatočný a koncový bod zhodujú, potom sa takáto cesta nazýva cyklus grafov . Ak každý vrchol grafu prechádza maximálne raz, potom cyklu volal jednoduché .

Ak sú každé dva vrcholy v grafe spojené hranou, potom toto pripojený graf. Graf sa volá nesúvisiace , ak obsahuje aspoň jeden pár nesúvislých vrcholov.

Ak je graf spojený, ale neobsahuje cykly, potom sa takýto graf nazýva strom .

Grófska cesta je postupnosť, v ktorej sa každé dve susedné hrany, ktoré zdieľajú spoločný vrchol, vyskytujú iba raz.

Dĺžka najkratšieho reťazca vrcholov a a b sa nazýva vzdialenosť medzi vrcholmi a a b.

Vertex A volal stred graf, ak je vzdialenosť medzi vrcholmi A a akýkoľvek iný vrchol je najmenší možný. Je tam taká vzdialenosť polomer graf.

Maximálna možná vzdialenosť medzi akýmikoľvek dvoma vrcholmi grafu sa nazýva priemer graf.

Farbenie a aplikácia grafu.

Ak sa pozriete pozorne na geografickú mapu, môžete vidieť železnice alebo diaľnice, čo sú grafy. Okrem toho je na mape graf, ktorý pozostáva z hraníc medzi krajinami (okresmi, regiónmi).

V roku 1852 dostal anglický študent Francis Guthrie za úlohu vyfarbiť mapu Veľkej Británie a zvýrazniť každý kraj samostatnou farbou. Kvôli malému výberu farieb ich Guthrie znovu použil. Farby vybral tak, aby tie kraje, ktoré zdieľali spoločnú časť hranice, boli nevyhnutne natreté rôznymi farbami. Vyvstala otázka, aké minimálne množstvo farby je potrebné na vyfarbenie rôznych máp. Francis Guthrie navrhol, hoci nemohol dokázať, že štyri farby by boli dostatočné. O tomto probléme sa búrlivo diskutovalo v študentských kruhoch, no neskôr sa naň zabudlo.

„Problém štyroch farieb“ vzbudil čoraz väčší záujem, no nikdy ho nevyriešili ani významní matematici. V roku 1890 anglický matematik Percy Heawood dokázal, že päť farieb by stačilo na vyfarbenie akejkoľvek mapy. Až v roku 1968 dokázali, že na vyfarbenie mapy, ktorá zobrazuje menej ako štyridsať krajín, by stačili 4 farby.

V roku 1976 tento problém pomocou počítača vyriešili dvaja americkí matematici Kenneth Appel a Wolfgangt Haken. Aby sa to vyriešilo, všetky karty boli rozdelené do 2000 typov. Bol vytvorený počítačový program, ktorý skúmal všetky typy s cieľom identifikovať karty, na vyfarbenie ktorých by štyri farby nestačili. Počítač nedokázal študovať len tri druhy máp, a tak ich matematici študovali sami. Výsledkom bolo zistenie, že na vyfarbenie všetkých 2000 druhov kariet by stačili 4 farby. Oznámili riešenie problému štyroch farieb. V tento deň dala pošta na univerzite, kde Appel a Haken pracovali, na všetky známky pečiatku so slovami: „Stačia štyri farby.

Problém štyroch farieb si môžete predstaviť trochu inak.

Na tento účel zvážte ľubovoľnú mapu, ktorá ju prezentuje vo forme grafu: hlavné mestá štátov sú vrcholy grafu a okraje grafu spájajú tie vrcholy (hlavné mestá), ktorých štáty majú spoločnú hranicu. Na získanie takéhoto grafu je formulovaný nasledujúci problém: je potrebné vyfarbiť graf pomocou štyroch farieb tak, aby vrcholy, ktoré majú spoločnú hranu, boli zafarbené rôznymi farbami.

Eulerove a Hamiltonovské grafy

V roku 1859 vydal anglický matematik William Hamilton hlavolam – drevený dvanásťsten (dvanásťsten), ktorého dvadsať vrcholov bolo označených cvočkami. Každý vrch mal názov jedného z najväčších miest sveta – Kanton, Dillí, Brusel atď. Úlohou bolo nájsť uzavretú cestu, ktorá vedie pozdĺž okrajov mnohostenu, pričom každý vrchol navštívime iba raz. Na označenie cesty sa používala šnúra, ktorá sa zaháčkovala na klince.

Hamiltonov cyklus je graf, ktorého dráha je jednoduchý cyklus, ktorý raz prechádza všetkými vrcholmi grafu.

Mesto Kaliningrad (predtým Koenigsberg) leží na rieke Pregel. Rieka obmývala dva ostrovy, ktoré boli medzi sebou a s brehmi spojené mostami. Staré mosty tam už nie sú. Spomienka na nich zostáva len na mape mesta.

Jedného dňa sa obyvateľ mesta spýtal svojho priateľa, či je možné prejsť cez všetky mosty, navštíviť každý iba raz a vrátiť sa na miesto, kde sa prechádzka začala. Tento problém zaujímal veľa obyvateľov mesta, ale nikto ho nedokázal vyriešiť. Táto problematika vzbudila záujem vedcov z mnohých krajín. Riešenie problému získal matematik Leonhard Euler. Okrem toho sformuloval všeobecný prístup k riešeniu takýchto problémov. Aby to urobil, premenil mapu na graf. Vrcholy tohto grafu boli zemou a hrany boli mosty, ktoré ju spájali.

Pri riešení problému Königsbergského mosta sa Eulerovi podarilo sformulovať vlastnosti grafov.

Ak sú všetky vrcholy grafu párne, je možné nakresliť graf tak, že začnete od jedného vrcholu a skončíte v tom istom vrchole jedným ťahom (bez kreslenia pozdĺž tej istej čiary dvakrát a bez zdvihnutia ceruzky z papiera).

Ak existuje graf s dvoma nepárnymi vrcholmi, potom jeho vrcholy môžu byť tiež spojené jedným ťahom. Aby ste to dosiahli, musíte začať od jedného a skončiť na druhom, ľubovoľnom nepárnom vrchole.

Ak existuje graf s viac ako dvoma nepárnymi vrcholmi, potom graf nemožno nakresliť jedným ťahom.

Ak tieto vlastnosti aplikujeme na problém mostov, vidíme, že všetky vrcholy skúmaného grafu sú nepárne, čo znamená, že tento graf nemožno spojiť jedným ťahom, t.j. Nie je možné prejsť všetky mosty raz a skončiť cestu na mieste, kde začala.

Ak má graf cyklus (nie nevyhnutne jednoduchý) obsahujúci všetky hrany grafu raz, potom sa takýto cyklus nazýva Eulerov cyklus . Eulerov reťazec (cesta, cyklus, obrys) je reťazec (cesta, cyklus, obrys) obsahujúci raz všetky hrany (oblúky) grafu.

KAPITOLA II. POPIS ŠTÚDIE A JEJ VÝSLEDKOV

2.1. Etapy štúdie

Na testovanie hypotézy zahŕňala štúdia tri fázy (tabuľka 1):

Etapy výskumu

Stôl 1.

		Použité metódy
Teoretické štúdium problému	Študovať a analyzovať náučnú a vedeckú literatúru.	- samostatné myslenie;  štúdium informačných zdrojov; - vyhľadávanie potrebnej literatúry.
Praktický výskum problému	Zvážiť a analyzovať oblasti praktickej aplikácie grafov;	- pozorovanie; - analýza; - porovnanie; - prieskum.
3. fáza Praktické využitie výsledkov	Zhrňte preštudované informácie;	- systematizácia;  správa (ústna, písomná, s ukážkou materiálov)	september 2017

2.2. Oblasti praktickej aplikácie grafov

Grafy a informácie

Teória informácie vo veľkej miere využíva vlastnosti binárnych stromov.

Napríklad, ak potrebujete zakódovať určitý počet správ vo forme určitých sekvencií núl a jednotiek rôznej dĺžky. Kód sa považuje za najlepší pre danú pravdepodobnosť kódových slov, ak je priemerná dĺžka slova najmenšia v porovnaní s inými rozdeleniami pravdepodobnosti. Na vyriešenie tohto problému Huffman navrhol algoritmus, v ktorom je kód reprezentovaný ako stromový graf v rámci teórie vyhľadávania. Pre každý vrchol je navrhnutá otázka, na ktorú môže byť odpoveď „áno“ alebo „nie“ – čo zodpovedá dvom hranám vychádzajúcim z vrcholu. Konštrukcia takéhoto stromu je dokončená po založení toho, čo bolo potrebné. To sa dá využiť pri rozhovoroch s viacerými ľuďmi, keď odpoveď na predchádzajúcu otázku nie je vopred známa, plán rozhovoru je reprezentovaný ako binárny strom.

Grafy a chémia

A. Cayley sa zaoberal aj problémom možných štruktúr nasýtených (alebo nasýtených) uhľovodíkov, ktorých molekuly sú dané vzorcom:

CnH 2n+2

Všetky atómy uhľovodíkov sú 4-mocné, všetky atómy vodíka sú 1-valentné. Štruktúrne vzorce najjednoduchších uhľovodíkov sú znázornené na obrázku.

Každá molekula nasýteného uhľovodíka môže byť reprezentovaná ako strom. Keď sú odstránené všetky atómy vodíka, zostávajúce atómy uhľovodíkov vytvoria strom s vrcholmi, ktorých stupeň nie je vyšší ako štyri. To znamená, že počet možných požadovaných štruktúr (homológov danej látky) sa rovná počtu stromov, ktorých vrcholové stupne nie sú väčšie ako 4. Tento problém sa redukuje na problém enumerácie stromov určitého typu. D. Polya uvažoval o tomto probléme a jeho zovšeobecneniach.

Grafy a biológia

Proces rozmnožovania baktérií je jedným z typov procesov vetvenia, ktoré sa nachádzajú v biologickej teórii. Nechajte každú baktériu po určitom čase buď zomrieť, alebo sa rozdelí na dve časti. Preto pre jednu baktériu získame binárny strom rozmnožovania jej potomstva. Otázka problému je nasledovná: koľko prípadov obsahuje? k potomkovia v n-tej generácii jednej baktérie? Tento vzťah v biológii sa nazýva Galton-Watsonov proces, ktorý označuje požadovaný počet požadovaných prípadov.

Grafy a fyzika

Zložitou a únavnou úlohou pre každého rádioamatéra je vytváranie plošných spojov (doska z dielektrika - izolačného materiálu a leptané stopy vo forme kovových pásikov). K priesečníku stôp dochádza iba v určitých bodoch (umiestnenia triód, rezistorov, diód atď.) podľa určitých pravidiel. Výsledkom je, že vedec stojí pred úlohou nakresliť plochý graf s vrcholmi

Všetko uvedené teda potvrdzuje praktickú hodnotu grafov.

Internetová matematika

Internet je celosvetový systém vzájomne prepojených počítačových sietí na ukladanie a prenos informácií.

Internet môže byť reprezentovaný ako graf, kde vrcholy grafu sú internetové stránky a okraje sú odkazy (hyperlinky) smerujúce z jednej stránky na druhú.

Webový graf (internet), ktorý má miliardy vrcholov a hrán, sa neustále mení – stránky spontánne pribúdajú a miznú, odkazy miznú a pribúdajú. Internet má však matematickú štruktúru, riadi sa teóriou grafov a má niekoľko „stabilných“ vlastností.

Webový graf je riedky. Obsahuje len niekoľkonásobne viac hrán ako vrcholov.

Napriek svojej riedkosti je internet veľmi preplnený. Môžete prejsť z jednej stránky na druhú pomocou odkazov za 5 - 6 kliknutí (slávna teória „šesť podaní rúk“).

Ako vieme, stupeň grafu je počet hrán, ku ktorým patrí vrchol. Stupne vrcholov webového grafu sú rozdelené podľa určitého zákona: podiel stránok (vrcholov) s veľkým počtom odkazov (hran) je malý a podiel stránok s malým počtom odkazov je veľký. Matematicky sa to dá zapísať takto:

kde je podiel vrcholov určitého stupňa, je stupeň vrcholu, je konštanta nezávislá od počtu vrcholov vo webovom grafe, t.j. sa nemení počas procesu pridávania alebo odstraňovania lokalít (vrcholov).

Tento mocenský zákon je univerzálny pre zložité siete – od biologických až po medzibankové.

Internet ako celok je odolný voči náhodným útokom na stránky.

Keďže k deštrukcii a vytváraniu stránok dochádza nezávisle a s rovnakou pravdepodobnosťou, webový graf si s pravdepodobnosťou blízkou 1 zachová svoju integritu a nezničí sa.

Na štúdium internetu je potrebné zostaviť model náhodného grafu. Tento model by mal mať vlastnosti skutočného internetu a nemal by byť príliš zložitý.

Tento problém ešte nie je úplne vyriešený! Vyriešenie tohto problému – vybudovanie kvalitného modelu internetu – nám umožní vyvinúť nové nástroje na zlepšenie vyhľadávania informácií, identifikáciu spamu a šírenie informácií.

Konštrukcia biologických a ekonomických modelov začala oveľa skôr, ako vznikla úloha zostrojiť matematický model internetu. Pokroky vo vývoji a štúdiu internetu však umožnili zodpovedať mnohé otázky týkajúce sa všetkých týchto modelov.

Internetovú matematiku žiadajú mnohí odborníci: biológovia (predpovedajú rast bakteriálnych populácií), finančníci (riziká kríz) atď. Štúdium takýchto systémov je jedným z ústredných odvetví aplikovanej matematiky a informatiky.

Murmansk pomocou grafu.

Keď človek príde do nového mesta, spravidla je prvou túžbou navštíviť hlavné atrakcie. Zároveň je však často obmedzený čas a v prípade služobnej cesty veľmi malý. Preto je potrebné si prehliadku naplánovať vopred. A grafy budú skvelým pomocníkom pri zostavovaní vašej trasy!

Ako príklad si vezmite typický prípad prvého príchodu z letiska do Murmanska. Plánujeme navštíviť tieto atrakcie:

1. Morský pravoslávny kostol Spasiteľa na vode;

2. Katedrála svätého Mikuláša;

3. Oceanárium;

4. Pamätník mačky Semyon;

5. Jadrový ľadoborec Lenin;

6. Park Lights of Murmansk;

7. Park Valley of Comfort;

8. Kolský most;

9. Múzeum histórie Murmanskej lodnej spoločnosti;

10. Štvorec piatich rohov;

11. Námorný obchodný prístav

Najprv nájdime tieto miesta na mape a získajme vizuálnu reprezentáciu polohy a vzdialenosti medzi atrakciami. Cestná sieť je dosť rozvinutá a cestovanie autom nebude ťažké.

Atrakcie na mape (vľavo) a výsledný graf (vpravo) sú znázornené na príslušnom obrázku v PRÍLOHE č.1. Prišelec teda najskôr prejde v blízkosti mosta Kola (a ak je to potrebné, môže ho prejsť tam a späť); potom si oddýchne v Lights of Murmansk Park a Valley of Comfort a pôjde ďalej. V dôsledku toho bude optimálna trasa:

Pomocou grafu si môžete tiež predstaviť schému na vykonávanie prieskumov verejnej mienky. Príklady sú uvedené v PRÍLOHE č.2. V závislosti od odpovedí sa respondentovi kladú rôzne otázky. Napríklad, ak v sociologickom prieskume č. 1 respondent považuje matematiku za najdôležitejšiu z vied, dostane otázku, či sa cíti sebavedomo na hodinách fyziky; ak si myslí opak, druhá otázka sa bude týkať dopytu po humanitných vedách. Vrcholy takéhoto grafu sú otázky a okraje sú možnosti odpovede.

2.3. Aplikácia teórie grafov na riešenie problémov

Teória grafov sa používa na riešenie problémov z mnohých oblastí predmetov: matematika, biológia, informatika. Naštudovali sme si princíp riešenia úloh pomocou teórie grafov a vytvorili si vlastné problémy na tému výskumu.

Úloha č.1.

Piati spolužiaci si podali ruky na stretávke zo strednej školy. Koľko podaní rúk bolo vykonaných?

Riešenie: Označme spolužiakov vrcholmi grafu. Spojme každý vrchol čiarami so štyrmi ďalšími vrcholmi. Dostaneme 10 riadkov, toto sú podanie rúk.

Odpoveď: 10 podaní rúk (každý riadok znamená jedno podanie ruky).

Úloha č.2.

V dedine mojej starej mamy pri jej dome rastie 8 stromov: topoľ, dub, javor, jabloň, smrekovec, breza, jarabina a borovica. Jarabina je vyššia ako smrekovec, jabloň je vyššia ako javor, dub je nižší ako breza, ale vyšší ako borovica, borovica je vyššia ako jarabina, breza je nižšia ako topoľ a smrekovec je vyšší ako jabloň. V akom poradí budú stromy usporiadané na výšku od najvyššieho po najnižší?

Riešenie:

Stromy sú vrcholy grafu. Označme ich prvým písmenom v kruhu. Nakreslíme šípky z nízkeho stromu na vyšší. Hovorí sa, že jarabina je vyššia ako smrekovec, potom dáme šípku z smrekovca do jarabiny, breza je nižšia ako topoľ, potom šípku z topoľa dáme na brezu atď. Dostaneme graf, kde môžeme vidieť, že najkratší strom je javor, potom jabloň, smrekovec, jarabina, borovica, dub, breza a topoľ.

Odpoveď: javor, jabloň, smrekovec, jarabina, borovica, dub, breza a topoľ.

Úloha č.3.

Mama má 2 obálky: obyčajnú a leteckú a 3 známky: štvorcové, obdĺžnikové a trojuholníkové. Koľkými spôsobmi môže mama vybrať obálku a známku, aby poslala list otcovi?

Odpoveď: 6 spôsobov

Úloha č.4.

Medzi osadami A, B, C, D, E sú vybudované cesty. Musíte určiť dĺžku najkratšej cesty medzi bodmi A a E. Pohybovať sa môžete len po cestách, ktorých dĺžka je vyznačená na obrázku.

Úloha č.5.

Traja spolužiaci - Maxim, Kirill a Vova sa rozhodli ísť do športu a prešli výberom športových sekcií. Je známe, že 1 chlapec sa prihlásil do basketbalového oddielu a traja chceli hrať hokej. Maxim sa zúčastnil konkurzu iba na sekciu 1, Kirill bol vybraný do všetkých troch sekcií a Vova do sekcie 2. Ktorý z chlapcov bol vybraný do ktorej športovej sekcie?

Riešenie: Na vyriešenie úlohy použijeme grafy

Basketbal Maxim

Futbalový Kirill

Hokej Vova

Od do basketbal ide iba jedna šípka, potom bol do sekcie vybraný Kirill basketbal. Potom Kirill nebude hrať hokej, čo znamená v hokej sekciu vybral Maxim, ktorý robil konkurz len na túto sekciu, potom bude Vova futbalista.

Úloha č.6.

Kvôli chorobe niektorých učiteľov je potrebné, aby riaditeľ školy zostavil časť školského rozvrhu aspoň na jeden deň s prihliadnutím na tieto okolnosti:

1. Učiteľ bezpečnosti života súhlasí s tým, že dá len poslednú lekciu;

2. Učiteľ geografie môže dať druhú alebo tretiu vyučovaciu hodinu;

3. Matematik je pripravený dať buď len prvú alebo len druhú vyučovaciu hodinu;

4. Učiteľ fyziky môže vyučovať prvú, druhú alebo tretiu vyučovaciu hodinu, ale iba v jednej triede.

Aký rozvrh môže vytvoriť riaditeľ školy tak, aby vyhovoval všetkým učiteľom?

Riešenie: Tento problém sa dá vyriešiť prejdením všetkých možných možností, ale je to jednoduchšie, ak nakreslíte graf.

1. 1) fyzika 2. 1) matematika 3. 1) matematika

2) matematika 2) fyzika 2) geografia

3) geografia 3) geografia 3) fyzika

4) OBZH 4) OBZH 4) OBZH

Záver

V tejto výskumnej práci bola podrobne študovaná teória grafov, bola dokázaná hypotéza, že štúdium grafov môže pomôcť pri riešení logických problémov, okrem toho sa uvažovalo o teórii grafov v rôznych oblastiach vedy a zostavilo sa 7 problémov.

Používanie grafov pri výučbe študentov, ako nájsť riešenia problémov, umožňuje študentom zlepšiť ich grafické zručnosti a komunikovať uvažovanie v špeciálnom jazyku konečnej množiny bodov, z ktorých niektoré sú spojené čiarami. To všetko prispieva k práci učiť študentov myslieť.

Efektívnosť výchovno-vzdelávacej činnosti pri rozvíjaní myslenia vo veľkej miere závisí od stupňa tvorivej činnosti žiakov pri riešení matematických úloh. Preto sú potrebné matematické úlohy a cvičenia, ktoré by aktivizovali duševnú aktivitu školákov.

Aplikácia úloh a využívanie prvkov teórie grafov na výberových hodinách v škole presne sleduje cieľ aktivizácie duševnej činnosti žiakov. Veríme, že praktický materiál o našom výskume môže byť užitočný na voliteľných hodinách matematiky.

Cieľ výskumnej práce bol teda dosiahnutý, problémy vyriešené. V budúcnosti plánujeme pokračovať v štúdiu teórie grafov a rozvíjať vlastné trasy, napríklad pomocou grafu vytvoriť výletnú trasu pre školský autobus v ZATO Aleksandrovsk do múzeí a pamätných miest v Murmansku.

ZOZNAM POUŽITÝCH REFERENCIÍ

Berezina L. Yu. „Grafy a ich aplikácia“ - M.: „Osvietenie“, 1979

Gardner M. „Matematický voľný čas“, M. „Mir“, 1972

Gardner M. „Matematické hádanky a zábava“, M. „Mir“, 1971

Gorbačov A. „Zbierka problémov olympiády“ - M. MTsNMO, 2005

Zykov A. A. Základy teórie grafov. - M.: „Univerzitná kniha“, 2004. - S. 664

Kasatkin V. N. „Neobvyklé problémy matematiky“, Kyjev, „Radianska škola“, 1987

Matematická zložka / Redaktori a zostavovatelia N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M.: Nadácia "Matematické etudy" 2015 - 151 s.

Melnikov O. I. „Zábavné problémy v teórii grafov“, Mn. "TetraSystems", 2001

Melnikov O.I. Neviem v krajine grófov: Príručka pre študentov. Ed. 3., stereotypné. M.: KomKniga, 2007. - 160 s.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. „Staré zábavné problémy“, M. „Veda“, 1988

Ore O. „Grafy a ich aplikácie“, M. „Mir“, 1965

Harari F. Teória grafov / Preklad z angličtiny. a predslov V. P. Kozyreva. Ed. G. P. Gavrilová. Ed. 2. - M.: Úvodník URSS, 2003. - 296 s.

PRÍLOHA č.1

Vypracovanie optimálnej trasy pre návštevu hlavných atrakcií

Murmansk pomocou grafu.

Optimálna trasa bude:

8. Kolský most6. Parkové svetlá Murmansk7. Park Valley of Comfort2. Katedrála svätého Mikuláša10. Štvorec piatich rohov5. Jadrový ľadoborec Lenin9. Múzeum histórie Murmanskej lodnej spoločnosti11. Námorný obchodný prístav 1. Morský pravoslávny kostol Spasiteľa na vode4. Pamätník mačky Semyon3. Oceanárium.

SPRIEVODCA PO ATRAKCIÁCH MURMANSK

PRÍLOHA č.2

Sociologické prieskumy č.1,2

Vzdelávacie vydanie

Yuyukin Nikolay Alekseevič

LR č. Podpísané na pečať

Uch. Ed. l.., .

Voronežská štátna technická univerzita

394026 Voronež, Moskovsky Ave. 14

ADRESÁR MAGNETICKÉHO DISKU

Katedra vyššej matematiky a fyzikálno-matematického modelovania

NA. Yuyukin

DISKRÉTNA MATEMATIKA Časť 1. Základy teórie grafov

Návod

NA. Yuyukin

DISKRÉTNA MATEMATIKA Časť 1. Základy teórie grafov

Návod

Voronež 2004

ÚVOD

Túto príručku môžu využiť v kurze „Diskrétna matematika“ študenti VSTU, ktorí študujú v týchto odboroch:

090102 – Počítačová bezpečnosť;

090105 – Komplexné poskytovanie informačnej bezpečnosti automatizovaných systémov;

090106 - Informačná bezpečnosť telekomunikačných systémov.

Disciplína „Diskrétna matematika“ zabezpečuje získavanie vedomostí a zručností v súlade so štátnym, všeobecným vzdelávacím štandardom a zároveň podporuje získavanie základného vzdelania, formovanie svetonázoru a rozvoj logického myslenia.

Teória grafov je efektívnym nástrojom na formalizáciu moderných inžinierskych problémov spojených s diskrétnymi objektmi. Používa sa pri návrhu integrovaných obvodov a riadiacich obvodov, štúdiu automatov a logických obvodov, pri systémovej analýze, automatizovanom riadení výroby, pri vývoji počítačových a informačných sietí, pri návrhu obvodov a konštrukčno-topologickom návrhu atď.

Tutoriál načrtáva základy, základné metódy a algoritmy teórie grafov. Tu uvádzame n-grafy a digrafy; izomorfizmy; stromy; Eulerove grafy; rovinné grafy; krytiny a nezávislé súpravy; silná konektivita

V digrafy; analýza Markovovho reťazového grafu; algoritmy na hľadanie najkratších ciest v grafoch; Problém vyhľadávania Hamiltonovho cyklu

V graf; problém obchodného cestujúceho; vyčíslenie grafov a zobrazení; extrémne úlohy; optimalizačné problémy; univerzálne úlohy; metóda vetvenia a väzby; a tiež rozvíjať praktické zručnosti pri používaní vyššie uvedených pojmov.

Cieľom predmetu je rozvíjať teoretické vedomosti, praktické zručnosti a schopnosti študentov v oblasti modelovania procesov a javov v prírodných vedách a technike.

ke, so schopnosťou používať matematické symboly na vyjadrenie kvantitatívnych a kvalitatívnych vzťahov objektov potrebných na vykonávanie služobnej činnosti v oblasti informačnej bezpečnosti na vysokej odbornej úrovni.

Na dosiahnutie tohto cieľa slúžia tieto úlohy:

študovať čo najširšiu škálu konceptov teórie grafov;

získať zručnosti pri riešení vzdelávacích a praktických problémov;

zvládnuť optimalizačné metódy;

rozvíjať zručnosti pri nastavovaní a riešení informačných problémov, modelovaní a analýze informácií pomocou grafov.

Disciplína „Diskrétna matematika“ je jednou z aplikovaných matematických disciplín. Vychádza z poznatkov, ktoré študenti nadobudli štúdiom odborov „Algebra“ a „Matematická logika a teória algoritmov“. Pri štúdiu sa využívajú vedomosti a zručnosti získané štúdiom odboru „Diskrétna matematika“. všeobecný odborník a špeciálne disciplíny.

1. ZÁKLADNÉ POJMY TEÓRIE GRAFOV.

1.1. Problémy teórie grafov.

Teória grafov je oblasť matematiky, ktorá študuje systémy spojení medzi rôznymi objektmi, rovnako ako v prípade konceptu vzťahu. Nezávislá definícia grafu však zjednodušuje prezentáciu teórie a robí ju zrozumiteľnejšou a názornejšou.

Prvé problémy teórie grafov súviseli s riešením zábavných problémov a hlavolamov.

Prvá úloha. Problém Königsbergských mostov položil a vyriešil Euler v roku 1786. Mesto sa nachádzalo na brehoch a dvoch ostrovoch rieky Pregolya. Ostrovy boli medzi sebou a brehmi spojené siedmimi mostami, ako je znázornené na obrázku.

Vyvstala otázka: je možné opustiť dom a vrátiť sa späť cez každý most presne raz?

Druhá úloha. Problém troch domov a troch studní. Sú tu tri domy a tri studne.

Z každého domu je potrebné ku každej studni nakresliť cestu tak, aby sa cesty nekrížili. Úloha znela

riešil Pontrjagin a nezávisle od neho Kuratovský v r

Tretia úloha. Asi štyri farby. Vyfarbite akúkoľvek mapu v rovine štyrmi farbami tak, aby žiadne dve susediace oblasti neboli natreté rovnakou farbou.

Mnohé výsledky z teórie grafov sa využívajú na riešenie praktických problémov vo vede a technike. V polovici 19. storočia teda Kirchhoff použil teóriu grafov na výpočet zložitých elektrických obvodov. Ako matematická disciplína sa však teória grafov sformovala až v 30. rokoch 20. storočia. V tomto prípade sa grafy považujú za nejaké abstraktné matematické objekty. Používajú sa pri analýze a syntéze obvodov a systémov, pri plánovaní a riadení sietí, operačnom výskume, programovaní, modelovaní života organizmu a ďalších oblastiach.

1.2. Základné definície.

Graf G= (V,E) je súborom dvoch množín - neprázdnej množiny vrcholov V a množiny neusporiadaných a usporiadaných dvojíc vrcholov E. V ďalšom budeme uvažovať o konečných grafoch, t.j. grafy s konečnou množinou vrcholov a konečnou rodinou párov. Neusporiadaná dvojica vrcholov sa nazýva hrana a usporiadaná dvojica sa nazýva oblúk.

Typicky je graf reprezentovaný diagramom: vrcholy sú bodky (alebo kruhy), hrany sú čiary ľubovoľnej konfigurácie. Šípka navyše označuje jeho smer na oblúku. Všimnite si, že pri zobrazovaní grafu je nosná

Podstatné sú geometrické vlastnosti hrán (dĺžka, zakrivenie), ako aj vzájomná poloha vrcholov v rovine.

Vrcholy, ktoré nepatria žiadnej hrane (oblúku), sa nazývajú izolované. Vrcholy spojené hranou alebo oblúkom sa nazývajú susedné. Hrana (oblúk) a ktorýkoľvek z jej dvoch vrcholov sa nazývajú incidenty.

Hovorí sa, že hrana (u,v) spája vrcholy u a v a oblúk (u,v) začína vo vrchole u a končí vo vrchole v, pričom u sa nazýva začiatok a v koniec tohto oblúka.

Dvojica vrcholov môže byť spojená dvoma alebo viacerými hranami (oblúky v rovnakom smere). Takéto hrany (oblúky) sa nazývajú viacnásobné. Oblúk (alebo hrana) môže začínať alebo končiť v rovnakom vrchole. Takýto oblúk (hrana) sa nazýva slučka. Graf obsahujúci slučky sa nazýva pseudo graf. Graf, ktorý má viacero hrán (oblúkov), sa nazýva multigraf.

Graf bez slučiek alebo viacerých hrán sa nazýva jednoduchý. Jednoduchý graf sa nazýva úplný, ak pre ktorýkoľvek pár jeho vrcholov existuje hrana (oblúk), ktorá ich spája. Úplný graf s n vrcholmi označujeme K n. Ide napríklad o grafy

Graf pozostávajúci z jedného izolovaného vrcholu (K 1) sa nazýva triviálny.

Doplnkom grafu G je graf G, ktorý má rovnaké vrcholy ako graf G a obsahuje tie hrany, ktoré je potrebné pridať do grafu G, aby sa získal úplný graf.

Každému nedigrafovi kanonicky sa zhoduje orientovaný graf s rovnakou množinou vrcholov, v ktorom je každá hrana nahradená dvoma oblúkmi dopadajúcimi na rovnaké vrcholy s opačnými smermi.

1.3. Stupne vrcholov grafu.

Stupeň (valencia) (označenie d (v) alebo stupeň (v)) vrcholu v jednoduchého grafu G je počet hrán alebo oblúkov dopadajúcich na daný vrchol v. Pri výpočte valencie vrcholov pseudografu by sa každá slučka mala počítať dvakrát.

Ak sú stupne všetkých vrcholov n-grafu rovné k, potom sa nazýva graf pravidelný (jednotný) stupeň k. Ak je stupeň vrcholu 0, potom je izolovaný. Ak je stupeň vrcholu 1, potom sa vrchol nazýva terminálny vrchol (visiaci, mŕtvy koniec).

Pre digraf sa nazýva počet oblúkov vychádzajúcich z vrcholu v

sa líši polostupeň výsledku				(v), a prichádzajúce – polokrokové-

nový hovor d			(v), V tomto prípade platí vzťah d (v)=

	(v)+	(v).

Eulerova veta: Súčet stupňov vrcholov grafu je

dvojnásobný počet rebier, t.j.

d(vi)



			(v)

kde n je počet vrcholov; m – číslo

rebrá (oblúky). Toto tvrdenie dokazuje skutočnosť, že pri výpočte súčtu stupňov vrcholov sa každá hrana berie do úvahy dvakrát - pre jeden koniec hrany a pre druhý.

1.4. Izomorfizmus grafu.

Graf sa nazýva označený (alebo prečíslovaný), ak sa jeho vrcholy od seba nejakým spôsobom líšia.

štítky (čísla). Počíta sa úplne dané v užšom zmysle, ak je číslovanie jeho vrcholov a hrán pevné. V tomto prípade sa grafy G 1 a G 2 nazývajú rovnaké (označenie G 1 = G 2), ak sa ich množiny vrcholov a hrán zhodujú. Dva grafy alebo pseudografy G 1 = (V 1 ,E 1 ) a G 2 = (V 2 ,E 2 ) sú tzv.

	izomorfný (zápis G	ak existujú

	individuálne mapovania: 1)	: V 1 V 2
: E 1 E 2 také, že pre ľubovoľné dva vrcholy u, v v grafe
	platí vzťah ((u, v)) ((u), (v)).

	Dva jednoduché grafy (bez slučiek a viacerých hrán) G 1		a G2