Titov Maxim

1. Zvážte všetky trasy regiónu Nizhnegorsky.

2. Na základe údajov o trase vytvorte nové trasy.

3. Ukážte, či sú nové trasy Eulerovými grafmi.

4. Vytvorte maticu susednosti pre nové trasy.

5. Nájdite najkratšie vzdialenosti z dediny Nizhnegorskoye do obývaných oblastí.

Stiahnuť:

Ukážka:

ÚVOD……………………………………………………………………………………….. 3

ODDIEL 1. ZÁKLADNÉ DEFINÍCIE GRAFOV………………………………………5

1. Základné pojmy z teórie grafov.......................................................................5
2. Charakteristika Eulerových grafov…………………………………………7
3. Nájdenie najkratšej vzdialenosti v grafe (Dijkstreeov algoritmus)…………..8

ODDIEL 2. TRASY OBVODU NIŽNEGORSKY …………………………..……10

1. Trasy Nižnegorského okresu…..…..………………………………….10
2. Štúdia trás Nižnegorského okresu ……..………………..11

ZÁVER……………………………………………………………………………………………….. 17

ZOZNAM LITERATÚRY………………………………………….19

ÚVOD

Grafy sú nádherné matematické objekty, ktoré možno použiť na riešenie matematických, ekonomických a logických problémov. Môžete tiež riešiť rôzne hádanky a zjednodušiť podmienky problémov vo fyzike, chémii, elektronike a automatizácii. Grafy sa používajú pri zostavovaní máp a rodokmeňov. Grafy sú vývojové diagramy počítačových programov, grafy budovania siete, kde vrcholy sú udalosti označujúce dokončenie práce na určitom mieste a hrany spájajúce tieto vrcholy sú prácou, ktorá môže začať po výskyte jednej udalosti a musí byť dokončená, aby sa dokončila práca. ďalšie. Jedným z najbežnejších grafov sú diagramy liniek metra.

Existuje dokonca aj špeciálna sekcia v matematike s názvom „Teória grafov“. Teória grafov je súčasťou topológie aj kombinatoriky. To, že ide o topologickú teóriu vyplýva z nezávislosti vlastností grafu od umiestnenia vrcholov a typu čiar, ktoré ich spájajú. A pohodlnosť formulovania kombinatorických problémov z hľadiska grafov viedla k tomu, že teória grafov sa stala jedným z najsilnejších nástrojov kombinatoriky. Pri riešení logických úloh je zvyčajne dosť ťažké udržať si v pamäti množstvo faktov uvedených v podmienke, nadviazať medzi nimi súvislosti, vysloviť hypotézy, vyvodiť konkrétne závery a použiť ich.

Aktuálnosť témy spočíva v tom, že 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, všetky druhy dopravných schém a oveľa, oveľa viac. 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.

Účelom práce je študovať dopravné cesty v regióne Nizhnegorsky.

Ciele práce:

1 . Zvážte všetky trasy regiónu Nizhnegorsky.

2 . Na základe údajov o trase vytvorte nové trasy.

3. Ukážte, či sú nové trasy Eulerovými grafmi.

4. Vytvorte maticu susednosti pre nové trasy.

5. Nájdite najkratšie vzdialenosti z dediny Nizhnegorskoye do obývaných oblastí.

Predmetom štúdie je mapa dopravných trás Nižnegorského regiónu.

Praktický význam tejto práce je v tom, že sa dá použiť na hodinách pri riešení rôznych problémov, ako aj v rôznych oblastiach vedy a v modernom živote.

Použité metódy: vyhľadávanie zdrojov informácií, pozorovanie, porovnávanie, analýza, matematické modelovanie.

Štruktúra sekcií súvisí so všeobecnou myšlienkou diela. Hlavná časť pozostáva z troch kapitol. Prvá zahŕňa základné pojmy grafov. Druhá kapitola skúma trasy Nižnegorského regiónu.

Pri svojej práci som použil množstvo literárnych zdrojov: odbornú literatúru z teórie grafov, náučnú literatúru, rôzne populárno-náučné, náučné a odborné časopisy.

ODDIEL 1

ZÁKLADNÉ DEFINÍCIE GRAFOV

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

Graf je neprázdna množina bodov a množina segmentov, ktorých oba konce patria danej množine bodov. (Obr.1.1.)

Obr.1.1.

Vrchol grafu je bod, kde sa môžu hrany a/alebo oblúky zbiehať/vystupovať.

Hrana grafu - hrana spája dva vrcholy grafu.

Stupeň vrcholu je počet hrán vychádzajúcich z vrcholu grafu.

Vrchol grafu, ktorý má nepárny stupeň, sa nazýva nepárny a vrchol, ktorý má párny stupeň, sa nazýva párny.

Ak na smere spojenia záleží, potom sú čiary vybavené šípkami, v tomto prípade sa graf nazýva orientovaný graf, digraf. (Obr.1.2.)

Obr.1.2.

Vážený graf je graf, v ktorom je každej hrane priradená určitá hodnota (váha hrany). (Obr.1.3.)

Ryža. 1.3.

Grafy, v ktorých sú zostrojené všetky možné hrany, sa nazývajú úplné grafy. (Obr.1.4.)

Ryža. 1.4.

Graf sa nazýva spojený, ak ľubovoľné dva jeho vrcholy môžu byť spojené cestou, teda postupnosťou hrán, z ktorých každá začína na konci predchádzajúcej.

Matica susednosti je matica, ktorej prvok M[i] [j] sa rovná 1, ak existuje hrana od vrcholu i k vrcholu j, a rovná sa 0, ak takáto hrana neexistuje (obr. 1.5 pre graf na obr. 1.1).

1.2. Charakteristika Eulerových grafov

Graf, ktorý možno nakresliť bez zdvihnutia ceruzky z papiera, sa nazýva eulerovský graf. (Obr. 1.6.)

Tieto grafy sú pomenované po vedcovi Leonhardovi Eulerovi.

Vzor 1.

Nie je možné nakresliť graf s nepárnym počtom nepárnych vrcholov.
Vzor 2.

Ak sú všetky vrcholy grafu párne, môžete tento graf nakresliť bez toho, aby ste zdvihli ceruzku z papiera („jedným ťahom“) a pohybovali sa pozdĺž každej hrany iba raz. Pohyb môže začať z akéhokoľvek vrcholu a skončiť v rovnakom vrchole.
Vzor 3.

Graf s iba dvoma nepárnymi vrcholmi je možné nakresliť bez toho, aby ste zdvihli ceruzku z papiera a pohyb musí začať v jednom z týchto nepárnych vrcholov a skončiť v druhom z nich.
Vzor 4.

Graf s viac ako dvoma nepárnymi vrcholmi nemožno nakresliť „jedným ťahom“.
Obrázok (graf), ktorý možno nakresliť bez toho, aby ste zdvihli ceruzku z papiera, sa nazýva jednokurzálny.

Obr.1.6.

1.3. Nájdenie najkratšej vzdialenosti v grafe (Dijkstreeov algoritmus)

Problém: Je daná sieť ciest medzi mestami, z ktorých niektoré môžu mať jednosmernú premávku. Nájdite najkratšie vzdialenosti z daného mesta do všetkých ostatných miest (obr. 1.7).

Rovnaký problém: ak je daný súvislý graf s N vrcholmi, váhy hrán sú dané maticou W. Nájdite najkratšie vzdialenosti od daného vrcholu ku všetkým ostatným.

Dijkstrov algoritmus (E.W. Dijkstra, 1959):

1. Priraďte všetkým vrcholom označenie ∞.

2. Medzi neuvažovanými vrcholmi nájdite vrchol j s najmenším označením.

3. Pre každý nespracovaný vrchol i: ak je cesta k vrcholu i cez vrchol j menšia ako existujúci štítok, nahraďte štítok novou vzdialenosťou.

4. Ak ešte stále existujú nespracované vrcholy, prejdite na krok 2.

5. Značka = minimálna vzdialenosť.

Obr.1.7.

Obr.1.8. Riešenie problému

ODDIEL 2

TRASY OBVODU NIŽNEGORSKY

2.1. Trasy okresu Nizhnegorsky

Okres Nizhnegorsky sa nachádza v stepnej časti na severe Autonómnej republiky Krym. Okres Nizhnegorsky zahŕňa mesto Nizhnegorsky a 59 osád.

Cez okres Nizhnegorsky prechádzajú dve trasy: 2Р58 a 2Р64. Z Nizhnegorskaya A/S do iných osád vedie 8 trás. Vo svojej práci sa budem zaoberať týmito cestami:

1 trasa "Nižnegorsk - Krasnogvardejsk". Nasleduje: Nižnegorsk – Plodovoje – Mitofanovka – Burevestnik – Vladislavovka.

Trasa 2 „Nižnegorsk – Izobilnoje“: Nižnegorsk – Semennoe – Kirsanovka – Listvennoje – Ochotskoje – Cvetušče – ​​Emeljanovka – Izobilnoje.

Trasa 3 “Nižnegorsk – Velikoselye”: Nižnegorsk – Semennoje – Dvurechye – Akimovka – Lužki – Zalivnoje – Stepanovka – Lugovoje – Čkalovo – Velikoselye.

Trasa 4 „Nižnegorsk – Belogorsk (trasa 2P64)“: Nižnegorsk – Želyabovka – Ivanovka – Zarechye – Serovo – Sadovoe – Peny.

Trasa 5 “Nižnegorsk – Uvarovka”: Nižnegorsk – Semennoje – Novoivanovka – Uvarvka.

Trasa 6 “Nižnegorsk – Ľubimovka”: Nižnegorsk – Semennoe – Dvurechye – Akimovka – Lužki – Zalivnoe – Stepanovka – Lugovoe – Kovorovo – Dvorovoe – Lyubimovka.

Trasa 7 “Nižnegorsk – Pšeničnoe”: Nižnegorsk – Semennoje – Dvurechye – Akimovka – Lužki – Zalivnoje – Stepanovka – Lugovoe – Kovorovo – Dvorovoe – Slivyanka – Pshenichnoe.

Trasa 8 “Nižnegorsk – Zorkino (trasa 2P58)”: Nižnegorsk – Razlivy – Michajlovka – Kuntsevo – Zorkino.

Je veľa dedín, kde autobusové linky nezavolajú a ľudia sa musia do svojich osád dostať po vlastných, väčšinou pešo. Preto som stál pred úlohou: Je možné vytvoriť nové trasy a zahrnúť do nich osady, kam autobusy nechodia.

Trasy „Nižnegorsk – Uvarovka“ „Nižnegorsk – Lyubimovka“ „Nižnegorsk – Pshenichnoye“ sa nedajú zmeniť, pretože po ceste autobusy volajú do všetkých osád, takže tieto trasy nebudem brať do úvahy.

Pozrime sa na ďalších päť trás. Obývané oblasti označíme číslami - to sú vrcholy grafu a vzdialenosti medzi nimi - okrajmi grafu a dostaneme päť grafov. Pozrime sa na každý graf zvlášť.

2.2. Výskum trás Nižnegorského regiónu

Cesta 1: Nižnegorsk – Krasnogvardejsk.

Nižnegorsk – 1

Ovocie - 2

Mitrofanovka – 3

Červonoje – 6

Burevestnik – 4

Novogrigorievka – 7

Vladislavivka – 5

Nechodí do bodov 6, 7. Pridajme tieto osady do trasy.

Obr.2.1.

Graf nie je eulerovský. Nová trasa vyzerá takto: Nizhnegorsk – Plodovoye – Mitrofanovka – Burevestnik – Novogrigoryevka – Vladislavovka. Pribudla obec Novogrigorievka.

2 trasa: Nižnegorsk – Izobilnoje.

Nižnegorsk – 1

Semená - 2

Kirsanovka – 3

Listnaté - 4

Ochotskoje – 5

Kvitne - 6

Emelyanovka – 7

Bohaté - 8

Kulički – 9

Pružiny - 10

Neide o body 9,10. Pridajme tieto osady na trasu.

Obr.2.2.

Graf nie je eulerovský a spojený, takže nie je možné zostrojiť novú trasu. Trasa zostáva rovnaká.

Cesta 3: Nižnegorsk - Velikoselye

Nižnegorsk – 1

Semená - 2

Mezopotámia – 3

Akimovka – 4

lúky – 5

Želé - 6

Stepanovka – 7

Lugovoe – 8

Čkalovo – 9

Velikoselye – 10

Široký - 11

Nejde do bodu 11. Pridajme túto osadu do trasy.

Obr.2.3.

Graf nie je eulerovský. Trasa zostáva rovnaká.

Cesta 4: Nižnegorsk – Belogorsk (cesta 2Р64)

Nižnegorsk – 1 Kostochkovka – 12

Želyabovka – 2 Frunze – 13

Ivanovka - 3 Prirechnoye - 14

Zarechye – 4 perla – 15

Serovo - 5

Sadovoe – 6

Peny - 7

Lomonosovo – 8

kukurica - 9

Tambovka – 10

Tarasovka - 11

Neide o body 8-18. Pridajme tieto osady na trasu.

Obr.2.4.

Graf nie je eulerovský. Nová trasa vyzerá takto: Nižnegorsk – Želyabovka – Ivanovka – Zarechye – Tambovka – Tarsovka – Prirechnoye – Zhemchuzhina – Peny.

Cesta 5: Nižnegorsk – Zorkino (cesta 2Р58)

Nižnegorsk – 1

Rozliatie - 2

Michajlovka – 3

Kuncevo – 4

Zorkino – 5

Útulný - 6

Nižinskoje – 7

Neide o body 6,7. Pridajme tieto osady na trasu.

Obr.2.5.

Graf nie je eulerovský a spojený, takže trasa zostáva rovnaká.

ZÁVER

Fraktálna veda je veľmi mladá a má pred sebou veľkú budúcnosť. Krása fraktálov nie je ani zďaleka vyčerpaná a ešte nám dá mnoho majstrovských diel – tých, ktoré lahodia oku, aj tých, ktoré prinášajú skutočné potešenie do mysle. Toto je novinka diela.

Na záver by som chcel povedať, že po objavení fraktálov bolo mnohým vedcom zrejmé, že staré dobré formy euklidovskej geometrie sú oveľa horšie ako väčšina prírodných objektov, pretože v nich nie sú nejaké nepravidelnosti, neusporiadanosť a nepredvídateľnosť. Je možné, že nové myšlienky fraktálnej geometrie pomôžu študovať mnohé záhadné javy okolitej prírody. V súčasnosti fraktály rýchlo prenikajú do mnohých oblastí fyziky, biológie, medicíny, sociológie a ekonómie. Metódy spracovania obrazu a rozpoznávania vzorov, ktoré využívajú nové koncepty, umožňujú výskumníkom použiť tento matematický aparát na kvantitatívne opísanie obrovského množstva prírodných objektov a štruktúr.

Počas výskumného procesu sa vykonali tieto práce:

1. Bola analyzovaná a preštudovaná literatúra k výskumnej téme.

2. Zvažujú sa a študujú sa rôzne typy fraktálov.

3. Uvádzame klasifikáciu fraktálov.

4. Na úvod do sveta fraktálov bola zozbieraná zbierka fraktálových obrázkov.

5. Boli zostavené programy na zostavenie grafického obrazu fraktálov.

Pre mňa osobne sa štúdium témy „Nevyčerpateľné bohatstvo fraktálnej geometrie“ ukázalo ako veľmi zaujímavé a nezvyčajné. V procese bádania som pre seba urobil množstvo nových objavov, ktoré súvisia nielen s témou projektu, ale aj s okolitým svetom všeobecne. Táto téma ma veľmi zaujíma, a preto táto práca mimoriadne pozitívne ovplyvnila moje chápanie modernej vedy.

Po dokončení môjho projektu môžem povedať, že všetko, čo bolo naplánované, bolo úspešné. Budúci rok budem pokračovať v práci na téme „fraktály“, keďže táto téma je veľmi zaujímavá a mnohostranná. Myslím, že som vyriešil problém môjho projektu, keďže som dosiahol všetky svoje ciele. Práca na projekte mi ukázala, že matematika nie je len exaktná, ale aj krásna veda.

ZOZNAM POUŽITÝCH ZDROJOV

1. V.M. Bondarev, V.I. Rublinetsky, E.G. Kačko. Základy programovania, 1998

2. N. Christofides. Teória grafov: algoritmický prístup, World, 1978.

3. F.A. Novikov. Diskrétna matematika pre programátorov, Petrohrad, 2001.

4. V.A. Nošov. Kombinatorika a teória grafov, MSTU, 1999.

5. O. Ruda. Teória grafov, Veda, 1982.

Účel štúdie :

Zvážte možnosti využitia grafového aparátu pri riešení logických a kombinatorických úloh.

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.

Relevantnosť štúdie:

Grafy sa používajú vo všetkých oblastiach nášho života. Znalosť základov teórie grafov je potrebná v rôznych oblastiach týkajúcich sa riadenia výroby, podnikania (napríklad harmonogram výstavby siete, harmonogramy doručovania pošty), budovanie prepravných a doručovacích trás, riešenie problémov. Grafy sa využívajú v súvislosti s rozvojom teórie pravdepodobnosti, matematickej logiky a informačných technológií.

hypotéza:

Pomocou teórie grafov je riešenie mnohých logických a kombinatorických problémov menej náročné na prácu.

Obsah:

Úvod. Pojem grafu.

Základné vlastnosti grafu.

Základné pojmy z teórie grafov a ich dôkazy.

Vybrané úlohy.

Chromatické číslo grafu.

Literatúra.

Úvod. Pojem grafu.

Každý z nás má samozrejme pravdu,

Po zistení bez meškania,

Čo je on...obyčajný gróf

Z tyčiniek a bodiek.

Teória grafov je v súčasnosti intenzívne sa rozvíjajúcim odvetvím diskrétnej matematiky. Grafy a súvisiace výskumné metódy organicky prenikajú takmer do celej modernej matematiky na rôznych úrovniach. Jazyk grafov je jednoduchý, jasný a vizuálny. Problémy s grafmi majú množstvo výhod, ktoré umožňujú ich využitie na rozvoj uvažovania, zlepšenie logického myslenia a využitie vynaliezavosti. Grafy sú úžasné matematické objekty, s ich pomocou môžete vyriešiť množstvo rôznych, navonok odlišných problémov.

Existuje celá sekcia v matematike - teória grafov, ktorá študuje grafy, ich vlastnosti a aplikácie. Matematické grafy so šľachtickým titulom „gróf“ spája spoločný pôvod z latinského slova „graphio“ – píšem. Typickými grafmi sú diagramy leteckých spoločností, ktoré sú často umiestnené na letiskách, diagramy metra a na geografických mapách - obrázky železníc. Vybrané body grafu sa nazývajú jeho vrcholy a čiary, ktoré ich spájajú, sa nazývajú hrany. Jeden z grafov je Moskovčanom a hosťom hlavného mesta dobre známy - toto je schéma moskovského metra: vrcholy sú konečné stanice a prestupné stanice, okraje sú koľaje spájajúce tieto stanice. Rodokmeň grófa L. N. Tolstého je ďalším grófom. Vrcholy sú tu predkami pisateľa a okraje ukazujú rodinné väzby medzi nimi.

Obr.1 Obr. 2

Slovo „graf“ v matematike znamená obrázok, na ktorom je nakreslených niekoľko bodov, z ktorých niektoré sú spojené čiarami Pri znázornení grafu umiestnenie vrcholov v rovine, zakrivenie a dĺžka hrán (obr. 3). vrcholy grafov sú označené písmenami alebo prirodzenými číslami. Okraje grafu tvoria dvojice čísel.

ryža. 3

Grafy sú blokové diagramy počítačových programov, grafy konštrukcie siete, kde vrcholy sú udalosti označujúce dokončenie práce na určitej oblasti a hrany spájajúce tieto vrcholy sú prácou, ktorá sa môže začať po výskyte jednej udalosti a musí byť dokončená, aby sa dokončila ďalšia. .Vlastnosti grafov, ako aj ich obrázkov, nebudú závisieť a nebudú sa meniť od toho, či sú vrcholy spojené segmentmi alebo zakrivenými čiarami. To umožňuje študovať ich vlastnosti pomocou jednej z mladých vied – topológie, hoci samotné problémy teórie grafov sú typickými problémami kombinatoriky.

Čo spája topológiu a kombinatoriku? Teória grafov je súčasťou topológie aj kombinatoriky. To, že ide o topologickú teóriu vyplýva z nezávislosti vlastností grafu od umiestnenia vrcholov a typu čiar, ktoré ich spájajú. A pohodlnosť formulovania kombinatorických problémov z hľadiska grafov viedla k tomu, že teória grafov sa stala jedným z najsilnejších nástrojov kombinatoriky.

Ale kto prišiel s týmito grafmi? Kde sa používajú? Sú všetky rovnaké alebo existujú variácie?

História vzniku teórie grafov. Klasický problém Königsbergských mostov.

Základy teórie grafov ako matematickej vedy položil v roku 1736 Leonhard Euler s ohľadom na problém Königsbergských mostov.„Dostal som otázku týkajúcu sa ostrova, ktorý sa nachádza v meste Königsberg a je obklopený riekou so 7 mostmi cez ňu. Otázkou je, či ich môže niekto nepretržite obchádzať a prejsť cez každý most iba raz ... “ (Z listu L. Eulera talianskemu matematikovi a inžinierovi Marinonimu z 13. marca 1736)

Bývalý Koenigsberg (dnes Kaliningrad) sa nachádza na rieke Pregel. V rámci mesta rieka obmýva dva ostrovy. Mosty sa stavali z brehov na ostrovy. Staré mosty sa nezachovali, ale zostala mapa mesta, kde sú vyobrazené (obr. 4). Koenigsbergerovci ponúkli návštevníkom nasledujúcu úlohu: prejsť všetky mosty a vrátiť sa do východiskového bodu, pričom každý most musel navštíviť iba raz. Euler bol tiež pozvaný na prechádzku po mestských mostoch. Po neúspešnom pokuse o potrebnú obchádzku nakreslil zjednodušenú schému mostov. Výsledkom je graf, ktorého vrcholy sú časti mesta, oddelené riekou a okraje sú mosty (obr. 5).

ryža. 4, obr. 5

Pred odôvodnením možnosti požadovanej trasy Euler zvažoval iné, zložitejšie mapy. V dôsledku toho dokázal všeobecné tvrdenie: na to, aby bolo možné prejsť všetky hrany grafu raz a vrátiť sa do pôvodného vrcholu, je potrebné a postačujúce splniť tieto dve podmienky:

z ktoréhokoľvek vrcholu grafu musí viesť cesta pozdĺž jeho okrajov k akémukoľvek inému vrcholu (grafy, ktoré spĺňajú túto požiadavku, sa nazývajú spojené);

Z každého vrcholu musí vychádzať párny počet hrán.

„V dôsledku toho je potrebné dodržať nasledujúce pravidlo: ak je na niektorom výkrese nepárny počet mostov vedúcich do určitej oblasti, potom požadovaný prechod cez všetky mosty súčasne nemôže byť uskutočnený inak, než ak prechod začína buď alebo končí v tejto oblasti. A ak je počet mostov párny, nemôžu z toho vzniknúť žiadne ťažkosti, pretože ani začiatok, ani koniec prechodu nie je pevne daný. To vedie k nasledujúcemu všeobecnému pravidlu: ak sú viac ako dve oblasti prístupné nepárnym počtom mostov, potom sa požadovaný prechod vôbec nedá uskutočniť. Zdá sa totiž úplne nemožné, že prechod začína aj končí v ktorejkoľvek z týchto oblastí. A ak existujú iba dve oblasti tohto druhu (keďže nemožno zadať jednu oblasť tohto druhu alebo nepárny počet oblastí), potom je možné vykonať prechod cez všetky mosty, ale s takou podmienkou, že prechod začína v jednej a koniec v druhej z týchto oblastí. Keď na navrhovanom obrázku A a B sú oblasti, do ktorých vedie nepárny počet mostov a počet mostov vedúcich k C je párne číslo, potom sa domnievam, že prechod alebo budovanie mosta môže nastať, ak prechod začína buď z A alebo B, a ak chce niekto začať s prechodom z C, tak sa mu nikdy nepodarí dosiahnuť cieľ. V lokalite Königsbergských mostov mám štyri plochy A, B, C, D, navzájom oddelené vodou, z ktorých každá je vedená nepárnym počtom mostov (obr. 6).

ryža. 6

Preto môžeš byť presvedčený, najslávnejší človeče, že toto riešenie svojou povahou zjavne nemá veľa spoločného s matematikou, a nechápem, prečo by sme toto riešenie mali očakávať skôr od matematika než od iného človeka. riešenie je podporované samotným uvažovaním a na nájdenie tohto riešenia nie je potrebné zapájať žiadne zákony vlastné matematike. Takže neviem, ako sa to stane, že otázky, ktoré majú len veľmi málo spoločného s matematikou, budú s väčšou pravdepodobnosťou riešiť matematici ako iní [vedci]. Medzitým vy, najslávnejší muž, určujete miesto tejto otázky v geometrii polohy, a čo sa týka tejto novej vedy, priznám sa, že neviem, aké problémy s tým súvisiace boli žiaduce pre Leibniza a Wolfa. Preto vás prosím, ak si myslíte, že som schopný v tejto novej vede niečo vytvoriť, aby ste mi poslali niekoľko konkrétnych úloh, ktoré s tým súvisia...“

Základné vlastnosti grafu.

Pri riešení problému o Königsbergských mostoch Euler stanovil nasledujúce vlastnosti grafu:

Ak sú všetky vrcholy grafu párne, potom môžete nakresliť graf jedným ťahom (to znamená bez zdvihnutia ceruzky z papiera a bez kreslenia dvakrát pozdĺž tej istej čiary).

Jedným ťahom možno nakresliť aj graf s dvoma nepárnymi vrcholmi. Pohyb musí začať z akéhokoľvek nepárneho vrcholu a skončiť v inom nepárnom vrchole.

Graf s viac ako dvoma nepárnymi vrcholmi nemožno nakresliť jedným ťahom.

Koncept Eulerových a Hamiltonovských cyklov.

Uzavretá cesta, ktorá raz prejde všetkými hranami, sa stále nazýva Eulerov cyklus.

Ak zahodíme podmienku návratu do pôvodného vrcholu, potom môžeme predpokladať prítomnosť dvoch vrcholov, z ktorých vychádza nepárny počet hrán. V tomto prípade by mal pohyb začať od jedného z týchto vrcholov a skončiť v druhom.

V úlohe Königsbergských mostov sú všetky štyri vrcholy príslušného grafu nepárne, čo znamená, že nie je možné prejsť cez všetky mosty presne raz a cestu tam ukončiť.

Je veľmi jednoduché získať graf na kus papiera. Musíte si vziať ceruzku a nakresliť čokoľvek na tento kus papiera bez toho, aby ste zdvihli ceruzku z papiera a bez toho, aby ste kreslili dvakrát pozdĺž tej istej čiary. Označte „priesečníky“ a začiatočné a koncové body bodkami, ak sa nezhodujú s „priesečníkmi“. Výsledný údaj možno nazvať grafom. Ak sa začiatočné a koncové body kresby zhodujú, všetky vrcholy budú párne, ale ak sa začiatočné a koncové body nezhodujú, budú nepárne vrcholy a všetky ostatné budú párne.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í.V mnohých detských hádankách nájdete nasledujúce úlohy: nakreslite postavu bez toho, aby ste zdvihli ceruzku z papiera a bez kreslenia dvakrát pozdĺž tej istej čiary.

ryža. 7 a) b)

Obrázok 7 (a) má dva vrcholy (spodok), z ktorých vychádza nepárny počet hrán. Preto musí kresba začať jedným z nich a skončiť v druhom. Na obrázku 7(b) je eulerovský cyklus, pretože zo šiestich vrcholov grafu vychádza párny počet hrán.

V roku 1859 Sir William Hamilton, slávny írsky matematik, ktorý dal svetu teóriu komplexných čísel a kvaternionov, navrhol nezvyčajnú detskú hádanku, v ktorej bolo navrhnuté urobiť „výlet okolo sveta“ do 20 miest nachádzajúcich sa v rôznych častiach zemegule (obr. 8). Do každého vrcholu dreveného dvanásťstena bol zatĺkaný klinec, označený názvom niektorého zo známych miest (Brusel, Dillí, Frankfurt atď.), a na jeden z nich bolo potrebné vrcholy spojiť dvanásťstenu s touto niťou tak, aby prechádzala po jej okrajoch, pričom sa každý čap navíjal presne raz, a aby výsledná trasa nite bola uzavretá (cyklus každé mesto bolo spojené cestami s tromi susednými cestami tak, aby sa vytvorila cestná sieť). 30 hrán dvanástnika, na vrcholoch ktorého boli mestá a, b ... t. Predpokladom bola požiadavka navštíviť každé mesto, s výnimkou prvého, iba raz.

ryža. 8, obr. 9

Ak začneme cestu z mesta a, potom posledné mestá musia byť b, e alebo h, inak sa nebudeme môcť vrátiť do pôvodného bodu a. Priamy výpočet ukazuje, že počet takto uzavretých trás je 60. Môžete požadovať návštevu všetkých miest presne raz, vrátane prvého, t.j. výlet je možné ukončiť v ktoromkoľvek meste (predpokladá sa napríklad, že návrat do východiskového bodu bude možný lietadlom). Potom sa celkový počet reťazových trás zvýši na 162 (obr. 9).

V tom istom roku 1859 Hamilton navrhol majiteľovi továrne na výrobu hračiek v Dubline, aby ju uviedol do výroby. Majiteľ továrne prijal Hamiltonovu ponuku a zaplatil mu 25 guineí. Hračka pripomínala ešte nedávno veľmi populárnu Rubikovu kocku a zanechala výraznú stopu v matematike. Uzavretá cesta pozdĺž okrajov grafu, ktorá raz prechádza všetkými vrcholmi, sa nazýva hamiltonovský cyklus. Na rozdiel od Eulerovho cyklu ešte nie sú stanovené podmienky pre existenciu hamiltonovského cyklu na ľubovoľnom grafe.

Koncept úplného grafu. Vlastnosti rovinných grafov.

Je vždy možné zobraziť graf v rovine tak, aby sa jeho hrany nepretínali? Ukazuje sa, že nie. Grafy, pre ktoré je to možné, sa nazývajú ploché.Grafy, v ktorých nie sú zostrojené všetky možné hrany, sa nazývajú neúplné grafy a graf, v ktorom sú všetky vrcholy spojené všetkými možnými spôsobmi, sa nazýva úplný graf.

ryža. 10 obrázkov. 11

Obrázok 10 ukazuje graf s piatimi vrcholmi, ktorý sa nezmestí na rovinu bez pretínajúcich sa hrán. Každé dva vrcholy tohto grafu sú spojené hranou. Toto je kompletný graf. Obrázok 11 zobrazuje graf so šiestimi vrcholmi a deviatimi hranami. Hovorí sa tomu „domy – studne“. Pochádza zo starodávnej úlohy – hlavolamu. Traja kamaráti bývali v troch chatrčiach. Pri ich domoch boli tri studne: jedna so slanou vodou, druhá so sladkou vodou a tretia so sladkou vodou. Ale jedného dňa sa priatelia pohádali natoľko, že sa nechceli ani vidieť. A rozhodli sa položiť cesty od domov k studniam po novom, aby sa ich cesty nekrížili. Ako na to? Na obrázku 12 je nakreslených osem z deviatich ciest, no deviatu už nie je možné vysledovať.

Obr.12

Poľský matematik Kazimierz Kuratowski zistil, že neexistujú žiadne zásadne odlišné nerovinné grafy. Presnejšie, ak graf „nezmestí“ do roviny, potom v ňom „sedí“ aspoň jeden z týchto dvoch grafov (úplný graf s piatimi vrcholmi alebo „domami-studňami“), možno s ďalšími vrcholmi na okrajoch .

Lewis Carroll, autor Alice v krajine zázrakov, rád dával svojim priateľom nasledujúcu hádanku. Požiadal, aby obkreslil postavu zobrazenú na výkrese bez toho, aby zdvihol ceruzku z papiera a bez toho, aby kreslil dvakrát pozdĺž tej istej čiary. Po vypočítaní parity vrcholov sme presvedčení, že tento problém sa dá ľahko vyriešiť a môžete začať s prechodom z akéhokoľvek vrcholu, pretože sú všetky párne. Úlohu však skomplikoval požiadavkou, aby sa čiary pri trasovaní nepretínali. S týmto problémom sa môžete vysporiadať nasledujúcim spôsobom. Vyfarbíme figúrku tak, aby jej lemujúce časti boli rôznych farieb. Potom oddelíme pretínajúce sa čiary tak, aby vytieňovaná časť bola z jedného kusu. Teraz už zostáva len jedným ťahom obkresliť namaľovanú oblasť pozdĺž okraja – bude to požadovaná čiara (obr. 13).

ryža. 13

Základné pojmy z teórie grafov a ich dôkazy .

Rovinné grafy majú veľa zaujímavých vlastností. Euler teda objavil jednoduchú súvislosť medzi počtom vrcholov (B), počtom hrán (P) a počtom častí (G), na ktoré graf rozdeľuje rovinu.

B – P + G = 2.

1. Definícia . Počet hrán vychádzajúcich z jedného vrcholu sa nazýva stupeň tohto vrcholu.

Lema1. Počet hrán v grafe je presne 2-krát menší ako súčet stupňov vrcholov.

Dôkaz. Ľubovoľná hrana grafu je spojená 2 vrcholmi. To znamená, že ak spočítame počet stupňov všetkých vrcholov grafu, dostaneme dvojnásobný počet hrán, pretože každá hrana sa počítala dvakrát.

Lema2 . Súčet stupňov vrcholov grafu je párny .

Dôkaz. Podľa Lemy 1 je počet hrán v grafe 2-krát menší ako súčet stupňov vrcholov, čo znamená, že súčet stupňov vrcholov je párny (deliteľný 2).

2. Definícia . Ak je stupeň vrcholu párny, potom sa vrchol nazýva párny, ak stupeň nie je párny, potom sa vrchol nazýva nepárny.

Lema3 . Počet nepárnych vrcholov v grafe je párny.

Dôkaz. Ak graf obsahujendokonca aknepárne vrcholy, potom je súčet stupňov párnych vrcholov párny. Súčet stupňov nepárnych vrcholov je nepárny, ak je počet týchto vrcholov nepárny. Ale potom je celkový počet stupňov vrcholov tiež nepárny, čo nemôže byť. znamená,kdokonca.

Lema 4. Ak má úplný graf n vrcholov, potom sa počet hrán bude rovnať

Dôkaz. V plnom grafe snvychádzajú vrcholy z každého vrcholun- 1 rebrá. To znamená, že súčet stupňov vrcholov sa rovnán ( n-1). Počet hrán je 2-krát menší .

Vybrané úlohy.

Keď poznáte vlastnosti grafu získaného Eulerom, môžete teraz ľahko vyriešiť nasledujúce problémy:

Úloha 1. Z troch ľudí stojacich vedľa seba jeden hovorí vždy pravdu (pravdovravný), druhý vždy klame (klamár) a tretí podľa okolností hovorí buď pravdu alebo lož (diplomat). Ten, kto stál naľavo, dostal otázku: „Kto stojí vedľa teba? Odpovedal: "Hľadač pravdy." Ten, kto stál v strede, dostal otázku: "Kto si?" a on odpovedal: "Som diplomat." Keď sa toho, čo stál napravo, opýtali: "Kto stojí vedľa teba?", povedal: "Klamár." Kto kde stál?

Riešenie: Ak v tomto probléme okraj grafu zodpovedá miestu obsadenému jednou alebo druhou osobou, potom sa nám môžu zobraziť nasledujúce možnosti.

Zvážme prvú možnosť. Ak je „pravda“ vľavo, potom je vedľa neho, súdiac podľa jeho odpovede, aj „pravda“. Máme "klamára". V dôsledku toho toto usporiadanie nespĺňa podmienky problému. Po zvážení všetkých ostatných možností dospejeme k záveru, že pozícia „diplomat“, „klamár“, „pravdovravec“ túto úlohu spĺňa. Ak je totiž „pravdovravec“ napravo, tak podľa jeho odpovede stojí vedľa neho „klamár“, čo je splnené. Ten, kto stojí v strede, vyhlasuje, že je „diplomat“, a teda klame (čo je možné z podmienky), a klame aj ten, ktorý stojí vpravo. Tým sú splnené všetky podmienky problému.

Úloha 2. V 10-cifernom čísle tvoria každé dve po sebe nasledujúce číslice dvojciferné číslo, ktoré je deliteľné 13. Dokážte, že medzi týmito číslicami nie je 8.

Riešenie. Existuje 7 dvojciferných čísel, ktoré sú deliteľné 13. Označme tieto čísla bodkami a aplikujme definíciu grafu. Podľa podmienky každé 2 po sebe idúce číslice tvoria dvojciferné číslo, ktoré sú deliteľné 13, čiže číslice tvoriace 10-miestne číslo sa opakujú. Spojme vrcholy grafu s hranami tak, aby sa čísla zahrnuté v tomto grafe opakovali.

13 65

91 39 52

Zo zostrojených grafov je zrejmé, že medzi číslicami 10-miestneho čísla nemôže byť číslo 8.

Úloha 3. V obci je 10 domov a z každého vedie 7 ciest k ďalším domom. Koľko ciest je medzi domami?

Riešenie. Nech domy sú vrcholy grafu a cesty hranami. Podľa podmienky vychádza z každého domu (vrcholu) 7 ciest (hran), potom stupeň každého vrcholu je 7, súčet stupňov vrcholov je 7 × 10 = 70 a počet hrán je 70. : 2 = 35. Medzi domami teda prechádza 35 ciest.

Úloha 4: Bola zavedená vesmírna komunikácia medzi 9 planétami slnečnej sústavy. Rakety lietajú na týchto trasách: Zem-Merkúr, Pluto-Venuša, Zem-Pluto, Pluto-Merkúr, Merkúr-Venuša, Urán-Neptún, Neptún-Saturn, Saturn-Jupiter, Jupiter-Mars a Mars-Urán. Je možné dostať sa zo Zeme na Mars?

Riešenie. Nakreslíme diagram: planéty budú zodpovedať bodom a trasy, ktoré ich spájajú, budú zodpovedať čiaram, ktoré sa navzájom nepretínajú.

Po načrtnutí obrázka trás sme nakreslili graf zodpovedajúci podmienkam úlohy. Je vidieť, že všetky planéty slnečnej sústavy sú rozdelené do dvoch nesúvisiacich skupín. Zem patrí do jednej skupiny a Mars do druhej. Nie je možné letieť zo Zeme na Mars.

Klasický „problém obchodného cestujúceho“. "Nenásytné" algoritmy.

Jeden z klasických problémov v teórii grafov sa nazýva problém cestujúceho obchodníka alebo problém cestujúceho obchodníka. Predstavme si obchodného zástupcu, ktorý musí precestovať niekoľko miest a vrátiť sa späť. Je známe, aké cesty spájajú tieto mestá a aké sú vzdialenosti medzi týmito mestami pozdĺž týchto ciest. Musíte si vybrať najkratšiu trasu. Toto nie je úloha „hračky“. Napríklad vodič pošty, ktorý preberá listy zo schránok, by veľmi rád poznal najkratšiu cestu, rovnako ako vodič kamiónu rozvážajúci tovar do kioskov. Ale riešenie tohto problému je dosť ťažké, pretože počet vrcholov v grafe je veľmi veľký. Ale je tu ďalšia úloha, v istom zmysle opak úlohy obchodného cestujúceho. Plánuje sa vybudovanie železnice, ktorá spojí viacero veľkých miest. Pre každú dvojicu miest sú známe náklady na položenie cesty medzi nimi. Musíte nájsť najlacnejšiu možnosť výstavby. Algoritmus na nájdenie optimálnej možnosti konštrukcie je v skutočnosti pomerne jednoduchý. Ukážme si to na príklade cesty spájajúcej päť miest A, B, C,Da E. Náklady na položenie cesty medzi každou dvojicou miest sú uvedené v tabuľke (obr. 14) a umiestnenie miest na mape (obr. 15)

1,5

2,5

1,5

1,2

0,8

1,2

1,1

0,9

1,1

2,7

2,5 5

is.e, a umiestnenie miest každého vozidla A, B C a nákladného vozidla, div.

0,8

0,9

2,7

IN

A A

D D

E

S

Obr.14 Obr. 15

Najprv postavíme cestu, ktorá má najnižšie náklady. Toto je cesta B → E. Teraz nájdime najlacnejšiu linku spájajúcu B alebo E s ktorýmkoľvek z miest. Toto je cesta medzi E a C. Zahrnieme ju do diagramu. Ďalej postupujeme podobne - hľadáme najlacnejšiu z ciest spájajúcich jedno z miest B, C, E s jedným zo zvyšných - A resp.D. Ide o cestu medzi C a A. Ostáva už len napojiť mesto na železničnú sieťD.

Najlacnejšie je spojenie s S. Získame sieť železničných tratí (obr. 16).

ryža. 16

Tento algoritmus na nájdenie optimálnej možnosti výstavby železnice patrí do kategórie „chamtivých“: v každom kroku riešenia tohto problému vyberáme najlacnejšie pokračovanie trasy. Na túto úlohu je ako stvorený. Ale v probléme obchodného cestujúceho, chamtivý algoritmus neposkytne optimálne riešenie. Ak už od začiatku zvolíte tie “najlacnejšie” prvky, t.j. na najkratšie vzdialenosti, je možné, že nakoniec budete musieť použiť veľmi „drahé“ - dlhé a celková dĺžka trasy bude výrazne vyššia ako optimálna.

Takže na vyriešenie niektorých problémov môžete použiť metódu alebo algoritmus nazývaný „chamtivý“. Algoritmus „Greedy“ je algoritmus na nájdenie najkratšej vzdialenosti výberom najkratšej, ešte nevybranej hrany, za predpokladu, že netvorí cyklus s už vybranými hranami. Tento algoritmus sa nazýva „chamtivý“, pretože v posledných krokoch musíte za chamtivosť tvrdo zaplatiť. Pozrime sa, ako sa „chamtivý“ algoritmus správa pri riešení problému obchodného cestujúceho. Tu sa to zmení na stratégiu „ísť do najbližšieho (ešte nezadaného) mesta“. Chamtivý algoritmus je v tomto probléme zjavne bezmocný. Zoberme si napríklad sieť na obrázku 17, ktorá predstavuje ú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. V niektorých situáciách však „chamtivý“ algoritmus stále určuje najkratšiu cestu.

2

4

1

4 3

3

ryža. 17

Existuje aj iná metóda na riešenie podobných problémov - metóda vyčerpávajúceho vyhľadávania (niekedy sa hovorí metóda Brute force, čo znamená vyčerpávajúce vyhľadávanie - to nie je úplne správne, pretože vyhľadávanie nemusí byť úplné), ktorá pozostáva z prehľadávania všetkých možných kombinácií bodov. (cieľové body). Ako je známe z matematiky, počet takýchto permutácií sa rovná n!, kde n je počet bodov. Keďže v probléme obchodného cestujúceho sa východiskový bod väčšinou berie ako rovnaký (prvý bod), stačí nám prejsť cez zvyšné, t.j. počet permutácií bude rovný (n–1)!. Tento algoritmus takmer vždy poskytuje presné riešenie problému obchodného cestujúceho, ale čas výpočtu môže byť príliš vysoký. Je známe, že s hodnotami n > 12 by moderný počítač nedokázal vyriešiť problém obchodného cestujúceho ani počas celej existencie vesmíru. Existujú aj iné algoritmy na riešenie problému obchodného cestujúceho, ktoré sú oveľa presnejšie ako „chamtivý“ algoritmus a oveľa rýchlejšie ako metóda hrubej sily. My sa však pozeráme na grafy a tieto metódy nesúvisia s teóriou grafov.

Chromatické číslo grafu.

Problém s vyfarbením geografickej mapy

Je uvedená geografická mapa, ktorá zobrazuje krajiny oddelené hranicami. Je potrebné vyfarbiť mapu tak, aby krajiny, ktoré majú spoločné časti hranice, boli vymaľované rôznymi farbami a aby sa použil minimálny počet farieb.

Pomocou tejto mapy zostavíme graf nasledovne. Priraďme vrcholy grafu ku krajinám mapy. Ak majú niektoré dve krajiny spoločný úsek hranice, potom budú príslušné vrcholy spojené hranou, v opačnom prípade je ľahké vidieť, že vyfarbenie mapy zodpovedá správnemu vyfarbeniu vrcholov výsledného grafu. a minimálny počet potrebných farieb sa rovná chromatickému číslu tohto grafu.

Chromatický číselný graf je najmenší počet farieb, pomocou ktorých je možné vyfarbiť vrcholy grafu takým spôsobom, že ľubovoľné dva vrcholy spojené hranou sú vymaľované rôznymi farbami. Matematici dlho nevedeli vyriešiť tento problém: stačia štyri farby na zafarbenie ľubovoľnej zemepisnej mapy tak, aby boli akékoľvek dve krajiny, ktoré majú spoločnú hranicu, zafarbené rôznymi farbami? Ak krajiny znázorníme ako body - vrcholy grafu, spájajúce hranami tie vrcholy, pre ktoré ich ohraničujú príslušné krajiny (obr. 18), potom sa problém zredukuje na nasledovné: je pravda, že chromatické číslo ľubovoľného graf umiestnený na rovine nie je väčší ako štyri? Kladnú odpoveď na túto otázku sme získali len nedávno pomocou počítača.

ryža. 18

Hra "štyri farby"

Stephen Barr navrhol papierovú logickú hru pre dvoch hráčov s názvom „Four Colors“. Slovami Martina Gardnera: „Nepoznám lepší spôsob, ako pochopiť ťažkosti, s ktorými sa stretávame pri riešení problému štyroch farieb, ako jednoducho hrať túto kurióznu hru.

Táto hra vyžaduje štyri farebné ceruzky. Prvý hráč začína hru vykreslením náhodného prázdneho poľa. Druhý hráč ho vyfarbí ktoroukoľvek zo štyroch farieb a následne si nakreslí svoju prázdnu plochu. Prvý hráč vyfarbí oblasť druhého hráča a pridá novú oblasť a tak ďalej – každý hráč vyfarbí oblasť súpera a pridá svoju. V tomto prípade by mali byť oblasti, ktoré majú spoločnú hranicu, natreté rôznymi farbami. Ten, kto je nútený vziať si piaty náter, prehráva.

Kombinatorické a logické problémy.

V roku 1936 nemecký matematik D. Koenig prvýkrát vykonal štúdiu takýchto schém a navrhol nazvať takéto schémy „grafmi“ a systematicky študovať ich vlastnosti. Takže ako samostatná matematická disciplína bola teória grafov zavedená až v 30-tych rokoch dvadsiateho storočia kvôli tomu, že sa začali používať takzvané „veľké systémy“, t.j. systémy s veľkým počtom objektov navzájom prepojených rôznymi vzťahmi: siete železníc a leteckých spoločností, telefónne ústredne pre mnoho tisíc účastníkov, systémy tovární - spotrebitelia a podniky - dodávatelia, rádiové obvody, veľké molekuly atď. atď. Ukázalo sa, že je nemožné pochopiť fungovanie takýchto systémov bez preštudovania ich dizajnu, ich štruktúry. Tu prichádza vhod teória grafov. V polovici 20. storočia sa problémy teórie grafov začali objavovať aj v čistej matematike (algebra, topológia, teória množín). Aby bolo možné aplikovať teóriu grafov na takú širokú škálu oblastí, musí byť vysoko abstraktná a formalizovaná. V súčasnosti zažíva éru rýchleho oživenia Grafy sa využívajú: 1) v teórii plánovania a riadenia, 2) v teórii plánovania, 3) v sociológii, 4) v matematickej lingvistike, 5) v ekonómii, 6) v biológii. , 7) chémia, 8) medicína , 9) v oblastiach aplikovanej matematiky ako teória automatov, elektronika, 10) pri riešení pravdepodobnostných a kombinatorických úloh a pod. Najbližšie ku grafom má topológia a kombinatorika.

Kombinatorika (kombinatorická analýza) je odvetvie matematiky, ktoré študuje diskrétne objekty, množiny (kombinácie, permutácie, umiestnenie a počítanie prvkov) a vzťahy na nich (napríklad čiastočné usporiadanie). Kombinatorika súvisí s mnohými ďalšími oblasťami matematiky – algebrou, geometriou, teóriou pravdepodobnosti a má široké uplatnenie v rôznych oblastiach poznania (napríklad genetika, informatika, štatistická fyzika). Termín „kombinatorika“ zaviedol do matematického používania Leibniz, ktorý v roku 1666 publikoval prácu „Discourses on the Combinatorial Art“. Niekedy sa kombinatorika chápe ako rozsiahlejší odbor diskrétnej matematiky, ktorý zahŕňa najmä teóriu grafov.

Teória grafov bola široko rozvinutá od 50. rokov. 20. storočia v súvislosti s formovaním kybernetiky a rozvojom výpočtovej techniky. ANa grafoch pracovali traja moderní matematici: C. Berge, O. Ore, A. Zykov.

Grafy sa často používajú na riešenie logických problémov zahŕňajúcich vymenovanie možností. Zvážte napríklad nasledujúci problém. 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. Situáciu v každom okamihu možno opísať tromi číslami, kde A je počet litrov vody vo vedre, B je vo veľkej panvici, C je v menšej. V počiatočnom momente bola situácia opísaná trojicou čísel (8, 0, 0), z ktorých môžeme prejsť na jednu z dvoch situácií: (3, 5, 0), ak naplníme veľkú panvicu vodou, alebo (5,0, 3), ak naplníte menšiu panvicu. Výsledkom sú dve riešenia: jedno na 7 ťahov, druhé na 8 ťahov.

Pozrime sa na problémy, ktoré sa dajú jednoducho vyriešiť nakreslením grafu.

Úloha č.1. Andrey, Boris, Victor a Grigory hrali šach. Každý s každým hral jednu hru. Koľko hier sa hralo?

Úloha sa rieši pomocou úplného grafu so štyrmi vrcholmi A, B, C, D, označenými prvými písmenami mien každého z chlapcov. Kompletný graf obsahuje všetky možné hrany. V tomto prípade okrajové segmenty označujú hrané šachové hry. Z obrázku je vidieť, že graf má 6 hrán, čo znamená, že bolo odohraných 6 hier.

Odpoveď: 6 hier.

Úloha č.2. Andrey, Boris, Victor a Grigory si navzájom darovali svoje fotografie ako suveníry. Navyše každý chlapec dal každému zo svojich priateľov jednu fotografiu. Koľko fotografií bolo darovaných?

Riešenie sa dá ľahko nájsť, ak nakreslíte graf:

1 spôsob. Pomocou šípok na okrajoch celého grafu je znázornený proces výmeny fotografií. Je zrejmé, že šípok je 2x viac ako hrán, t.j. 12.

Metóda 2. Každý zo 4 chlapcov dal svojim kamarátom 3 fotografie, celkovo teda dostali 34 = 12 fotografií.

Odpoveď: 12 fotografií.

Úloha č. 3. Je známe, že priezviská každého z troch dievčat začínajú rovnakým písmenom ako ich krstné mená. Anyino priezvisko je Anisimova. Priezvisko Katya nie je Kareva a priezvisko Kira nie je Krasnova. Aké je priezvisko každého dievčaťa?

Riešenie: Podľa podmienok úlohy vytvorme graf, ktorého vrcholy sú mená a priezviská dievčat. Plná čiara znamená, že dievča má dané priezvisko, a bodkovaná čiara znamená, že nie. Z podmienok problému je zrejmé, že Anya je priezvisko Anisimova (spájame dva zodpovedajúce body plnou čiarou). Z toho vyplýva, že priezvisko Katya a Kira nie je Anisimova. Keďže Katya nie je Anisimova alebo Kareva, znamená to, že je Krasnova. Zostáva, že Kira sa volá Kareva. Odpoveď: Anya Anisimova, Katya Krasnova, Kira Kareva.

Graf je súbor objektov so súvislosťami medzi nimi. Objekty sú reprezentované ako vrcholy alebo uzly grafu (sú označené bodkami) a spojenia sú reprezentované ako oblúky alebo hrany. Ak je na diagrame jednosmerné spojenie vyznačené čiarami so šípkami, ak je obojsmerné spojenie medzi objektmi na diagrame označené čiarami bez šípok. Hlavným smerom práce s kombinatorickými problémami je prechod od náhodného počítania možností k systematickému vyčísleniu. Problémy tohto typu je možné riešiť prehľadnejšie pomocou grafu.

Mnoho logických problémov je jednoduchšie vyriešiť pomocou grafov. Grafy umožňujú vizuálne znázorniť podmienky problému, a tým výrazne zjednodušiť jeho riešenie.

Úloha č. 4. Uchádzač z fyziky a matematiky musí absolvovať tri prijímacie skúšky desaťbodovým systémom. Koľkými spôsobmi môže zložiť skúšky, aby bol prijatý na univerzitu, ak v tom roku dosiahol 28 bodov?

Riešenie. Na vyriešenie tohto problému, podobne ako v mnohých iných kombinatorických a pravdepodobnostných problémoch, je efektívne usporiadať prvky analyzovanej množiny vo forme stromu. Z jedného vybraného vrcholu sa nakreslia hrany zodpovedajúce známke v prvej skúške a potom sa na ich konce pridajú nové hrany zodpovedajúce možným výsledkom druhej skúšky a následne tretej.

Ak sa chcete zapísať na fyziku a matematiku, môžete absolvovať prijímacie skúšky 10 rôznymi spôsobmi.

Stromový graf je tak pomenovaný pre svoju vonkajšiu podobnosť so stromom. Pomocou stromového grafu je počítanie možností oveľa jednoduchšie. Kreslenie stromu variant je užitočné aj vtedy, keď chcete zaznamenať všetky existujúce kombinácie prvkov.

Úloha č. 5. Na jednom vzdialenom ostrove žijú dva kmene: rytieri (ktorí vždy hovoria pravdu) a darebáci (ktorí vždy klamú). Jeden múdry cestovateľ rozprával tento príbeh. „Keď som prišiel na ostrov, stretol som dvoch miestnych obyvateľov a chcel som vedieť, z akého kmeňa sú. Spýtal som sa prvého: "Ste obaja rytieri?" Nepamätám si, či odpovedal „áno“ alebo „nie“, ale z jeho odpovede som nevedel jednoznačne určiť, ktorý z nich je ktorý. Potom som sa spýtal toho istého obyvateľa: "Ste z rovnakého kmeňa?" Opäť si nepamätám, či odpovedal „áno“ alebo „nie“, ale po tejto odpovedi som okamžite uhádol, ktorý je ktorý. S kým sa mudrc stretol?

P

Riešenie:

R

R

Nie

áno

áno

áno

áno

áno

Nie

Nie

áno

áno

áno

2

Odpoveď: prvá odpoveď je „áno“, druhá odpoveď je „nie“ - mudrc stretol dvoch darebákov.

Záver. Aplikácia teórie grafov v rôznych oblastiach vedy a techniky.

Inžinier kreslí schémy elektrických obvodov.

Chemik kreslí štruktúrne vzorce, aby ukázal, ako sú atómy v komplexnej molekule navzájom spojené pomocou valenčných väzieb. Historik sleduje rodokmeň podľa rodokmeňa. Vojenský vodca zmapuje sieť komunikácií, cez ktorú sú posily dodávané zozadu do predných jednotiek.

Sociológ pomocou veľmi zložitého diagramu ukazuje, ako sú si rôzne oddelenia jednej obrovskej korporácie navzájom podriadené.

Čo majú všetky tieto príklady spoločné? Každá z nich obsahuje graf.

V jazyku teórie grafov sa formuje a rieši veľa technických problémov, problémov z oblasti ekonómie, sociológie, manažmentu atď. Grafy sa používajú na vizuálne znázornenie objektov a vzťahov medzi nimi

Teória grafov zahŕňa aj množstvo matematických problémov, ktoré dodnes neboli vyriešené.

Literatúra.

„Encyklopédia pre deti. T.11. Matematika“ /hlavný redaktor. M.D. Aksenova / Vydavateľské centrum Avanta+, 1998.

„Za stránkami učebnice matematiky“ Comp. S. A. Litvinová. -2. vyd., rozšírené. – M.: Globus, Volgograd: Panoráma, 2008.

Grafy // Kvantové. -1994.- č.6.

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

Zykov A.A. Základy teórie grafov M.: Univerzitná kniha, 2004.

Melnikov O.I. Zábavné problémy v teórii grafov Vydavateľ: TetraSystems, 2001.

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

Materiály z Wikipédie – voľnej encyklopédie.

Vyplnila: Mukhina Anna, študentka 9. ročníka
Vedúci: Kolchanová G.R.
učiteľ matematiky

Grafová metóda je veľmi dôležitá a široká
 Grafová metóda je veľmi dôležitá a široká
používané v rôznych oblastiach vedy a
životná činnosť človeka.
životná činnosť človeka.
 Riešenie mnohých matematických úloh
zjednoduší, ak môžete použiť
grafov. Reprezentácia údajov ako graf
dáva im prehľadnosť a jednoduchosť.
sú také zjednodušené, získané
presvedčivosť, ak používate grafy.
 Veľa matematických dôkazov

Cieľ: zvážiť riešenie problémov s
pomocou "Graf", zvážte
„Grafy“ s použitím príkladov algoritmov a
rodokmene
Úlohy:
 Preštudujte si populárno-náučnú literatúru o
 Analyzujte výsledky vykonaného testu
tento problém.
experimenty

 Graf je systém, ktorý je možné prezerať intuitívne
ako mnohé kruhy a mnohé ich spájajú. Hrnčeky
sa nazývajú vrcholy grafu, čiary so šípkami - oblúky,
bez šípok - hrán.
 Začiatok teórie grafov sa datuje do roku 1736, kedy sa rozhodol L. Euler
v tom čase populárny „problém Konigsbergského mosta“.
 Termín „graf“ prvýkrát zaviedol o 200 rokov neskôr (v roku 1936) D. Koenig.
 Matematické grafy so šľachtickým titulom „gróf“ sú spojené spoločným
 Grafy sú algoritmy počítačových programov, sieťové diagramy
konštrukcia, kde vrcholy sú udalosti označujúce ukončenie prác na
nejaká oblasť a hrany spájajúce tieto vrcholy sú diela, ktoré
možné začať po dokončení jednej udalosti a musí sa dokončiť
robiť nasledovné.
pôvod z latinského slova „graphio“ - píšem. Typické grafy
sú schémy leteckých spoločností, ktoré sú často vyvesené na letiskách, schémy
metro, a na zemepisných mapách - obrázky železníc.
Vybrané body grafu sa nazývajú jeho vrcholy a čiary, ktoré ich spájajú
- rebrá.
 Slovo „strom“ v teórii grafov znamená graf, v ktorom nie sú žiadne cykly, tj.
v ktorých nie je možné prejsť z určitého vrcholu do niekoľkých rôznych
rebrá a vráťte sa do rovnakého vrcholu.

 Mesto Königsberg sa nachádza na
brehy rieky Pregel a dva
ostrovy. Rôzne časti mesta
spájalo ich sedem mostov. Autor:
v nedeľu vystupovali mešťania
prechádzky po meste. Otázka: je to možné
mám sa takto prejsť?
takže keď odídeš z domu,
vrátiť sa tým, že pôjdete do
presne raz na každom moste.
Mosty cez rieku Pregel
umiestnené ako na obrázku.
 Uvažujme zodpovedajúci graf
diagram mosta
 Ak chcete odpovedať na problémovú otázku,
staci to zistit aspon od
jeden vrchol vyjde dokonca
počet mostov.
 Pri prechádzke mestom nemôžete
prejsť všetky mosty raz a
vrátiť sa.

 Zvážte problém hľadania východu
z labyrintu, ktorého chodby nie sú
vyskytuje sa napríklad pri potulkách
musí byť na jednom
úrovni. Podobná situácia
v jaskyniach alebo katakombách.
súd
 Obrázok ukazuje zaujímavosť
príklad bludiska v Hampton Gardens
 Zostrojme zodpovedajúci
graf. Chodby labyrintu sú
okraje grafu a priesečníky, slepé uličky,
vstupy a výstupy sú vrcholy.
 Teraz to jasne vidíte v strede
do labyrintu sa dá dostať nasledovaním
 A podľa toho opustite stred
tieto vrcholy:
1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.
bludisko na trase:
13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

Na dva sa pozrieme na grafy podrobnejšie
príklady:
 Algoritmy
 Rodokmene

Nominácia „Slávni synovia vlasti“

Téma: „Alexej Petrovič Chulkov - hrdina Sovietskeho zväzu“

Galiullin Ravil

MBOU "Yukhmachinskaya stredná škola pomenovaná po Hrdinovi Sovietskeho zväzu Alexejovi Petrovičovi Chulkovovi"

žiak 7. ročníka

Moskvina G.A.

1.Úvod.

2. Hlavná časť

2.1. Život a výkon A.P. Chulkova

2.2. Spomienka - zvečnenie mena Hrdina Sovietskeho zväzu v pamätných predmetoch

3.Záver

4. Zoznam použitých referencií

1. Úvod

Veľká vlastenecká vojna je jednou z najstrašnejších skúšok, ktoré postihli našich ľudí. Závažnosť a krviprelievanie vojny zanechali v mysliach ľudí veľkú stopu. Vlastenectvo bolo v ruskom štáte vždy národnou povahovou črtou.

Každé mesto a dedina má svojich hrdinov, ktorí preslávili našu krajinu. Bohužiaľ, v poslednej dobe sa hovorí, že mladá generácia začala zabúdať na činy našich starých otcov a pradedov. A všade naokolo sú informačné vlny, ktoré sa opäť snažia očierniť výkon sovietskeho ľudu. Preto je táto téma výskumnej práce aktuálna pre riešenie takého problému, akým je výchova mravnej a vlasteneckej osobnosti. Našou úlohou je spomínať na hrdinov, vážiť si túto spomienku a odovzdávať ju ďalším generáciám.

Pamäť minulosti... Nie, to nie je len vlastnosť ľudského vedomia, jeho schopnosť uchovávať stopy minulosti.

Pamäť je spojenie medzi minulosťou a budúcnosťou. Bez ohľadu na to, koľko rokov uplynulo, bez ohľadu na to, koľko storočí uplynulo, musíme s vďačnosťou spomínať na tých, ktorí zachránili svet pred hnedým morom a našich ľudí pred zničením. A nenechať prepisovať históriu.

Teraz, keď sa na Západe, v bývalých zväzových republikách pobaltských štátov a na Ukrajine výkony vojakov Červenej armády stavajú na rovnakú úroveň so službou na strane nacistov a esesmanom stavajú pomníky, musíme pamätajte znova a znova na tých, ktorí položili svoje životy na oltár vlasti.

Cieľ projektu:študovať vojenskú cestu a výkon Hrdinu Sovietskeho zväzu, ktorého meno nesie naša škola.

Úlohy:- zoznámiť sa s algoritmom pre prácu na projekte;

Preštudujte si všetku dostupnú literatúru a mediálne publikácie o výskumnej téme;

Analyzujte získané informácie a vyvodzujte závery

Práca je venovaná štúdiu biografie Alexeja Petroviča Čulkova, hrdinu Sovietskeho zväzu, narodeného v obci Juchmači, Tatárska autonómna sovietska socialistická republika.

Hrdina Sovietskeho zväzu Alexej Petrovič Čulkov je náš krajan, jeho meno nesie naša škola v dedine Juchmači. Kto to je, ako žil, o čom sníval, prečo mu bol udelený titul Hrdina Sovietskeho zväzu?

Od skončenia Veľkej vlasteneckej vojny uplynulo viac ako 70 rokov. V rozľahlosti našej vlasti sú obelisky padlým, tým, ktorí sa nevrátili z bojov. Boli mladí. Kedy toho stihli toľko, že boli nominovaní na najvyššie ocenenie Vlasti? Prečo sa obetovali? Naozaj nechceli prežiť?

Téma mojej výskumnej práce: Osud môjho krajana.

Rozhodol som sa venovať tejto otázke podrobnejšie. Za týmto účelom som navštívil školské múzeum, kde je časť venovaná Alexejovi Petrovičovi. Aj vo svojej práci som sa opieral o spomienky hrdinu Sovietskeho zväzu, generála - plukovníka Vasilija Vasiljeviča Rešetnikova, Wikipedia, ako aj o knihu Yu.N. Khudov "Okrídlený komisár".

Metódy: Počas realizácie projektu som sa zoznámil s algoritmom na vykonávanie výskumných prác, preštudoval som si vlastivednú literatúru, prezrel si dostupnú literatúru, internetové materiály, spomienky kolegu.

Význam štúdie: tento materiál možno použiť na hodinách dejepisu, počas mimoškolských aktivít venovaných pamätným dátumom a výročiam a na hodinách v múzeu.

2. Hlavná časť

2.1. Život a výkon A.P. Chulkova

Čulkov Alexej Petrovič sa narodil 30. apríla 1908 v dedine Juchmači v Ruskej ríši, dnes okres Alkeevsky v Tatarstane, v robotníckej rodine. Rus podľa národnosti. V roku 1920 po zranení na fronte zomiera jeho otec. Štyri deti zostali sirotami. Najstarší Sergej ešte skôr odišiel do Karabanova, aby navštívil svojich príbuzných, kde dostal prácu v továrni. Spolu s desaťročným Alexejom jeho matka opustila dve mladšie sestry - Olyu a Polinu. Tento rok vypuklo v Povolží strašné sucho. Začal sa veľký hladomor. Lyosha dostane prácu ako poľnohospodársky robotník pre kulaka, ktorý sa stará o svoje stádo o chudobné jedlo. Jedného dňa majiteľ porazil Leshu. A chlapec, ktorý sa rozlúčil so svojou matkou a sestrami, sa rozhodol ísť k svojmu bratovi do Karabanova. Peniaze na cestovanie a jedlo – ani cent. S gangom tých istých detí ulice sa Lyosha vydáva smerom k Moskve. Na stanici v Kostrome nás zastihla ďalšia razia. Alexey teda skončil v sirotinci Kostroma, kde absolvoval zvyšné dve triedy a s vysvedčením o ukončení základnej školy prišiel ako 14-ročný a prišiel do Karabanova.

Od roku 1925 - obyvateľ obce Karabanovo (teraz mesto) v regióne Vladimir. Tu Alexey pracoval v tkáčskej továrni 3. internacionály v rokoch 1927 až 1933. Tu v továrni stretol svoju budúcu manželku Veru. S ktorým mal Alexej Petrovič štyroch synov.

Člen CPSU(b)/CPSU od roku 1931. Absolvoval robotnícku fakultu a 1. ročník Moskovského pedagogického inštitútu. Pracoval v Moskve.

V roku 1933 bol povolaný do Červenej armády, v roku 1934 absolvoval Luganskú vojenskú leteckú školu. Svoje prvé bojové misie absolvoval počas sovietsko-fínskej vojny v rokoch 1939-1940 a úspešne sa zúčastnil bombardovania a leteckého útoku na opevnenia Mannerheimovej línie. Velenie vysoko ocenilo bojové schopnosti a zručnú plodnú politickú prácu pilota, staršieho politického inštruktora Alexeja Chulkova. Bol vyznamenaný Rádom Červeného praporu a dostal vojenskú hodnosť komisára práporu.

V bitkách Veľkej vlasteneckej vojny od prvých dní. Do novembra 1942 vykonal zástupca veliteľa letky pre politické záležitosti 751. leteckého pluku major Alexej Čulkov 114 bojových misií s cieľom bombardovať vojensko-priemyselné objekty hlboko za nepriateľskými líniami a jeho jednotky na frontovej línii.

7. novembra 1942 pri návrate z bojovej misie pri meste Orsha zasiahla jeho lietadlo protilietadlová paľba a zrútilo sa v oblasti Kaluga.

V roku 2004 vyšla kniha Vasilija Vasilieviča Rešetnikova, Hrdina Sovietskeho zväzu, generálplukovník.

Počas vojny bol pilotom 751. pluku 17. leteckej divízie diaľkových bombardérov. V roku 1942 bojoval v letke, ktorej bol Chulkov komisárom. Opakovane lietal pod jeho vedením na bojové misie. Vasilij Vasilievič si na svojho komisára spomína takto: V tú noc, zo siedmeho na ôsmeho novembra 1942, sa posádka komisára Alexeja Petroviča Čulkova nevrátila z bojovej misie. Aj keď bol komisárom eskadry Uruta, celý pluk ho uctieval ako svojho komisára, čo spôsobilo nedobrovoľnú žiarlivosť medzi ostatnými, vrátane plukovných, ale nelietajúcich politických pracovníkov.

Toto je jemná vec - autorita, najmä autorita komisára. Kritériá pre oficiálne postavenie tu vôbec nefungujú, aj keď úspešne poskytujú celý komplex vonkajších znakov úcty. V pevnej cene rešpektu sa uvádza iba morálna a intelektuálna miera jednotlivca. Akurát jednotlivci, nie pozície. Vo vojne sa cenili činy, a aj keď to slovo bolo živé, nie mŕtve, oficiálne.

Alexej Petrovič mal ďaleko od učebnicového komisára – navonok bol úplne nenáročný a rozhodne nie tribúnsky. Preslávil sa skôr ako vynikajúci bojový pilot a pamätajte, že nikoho neoklamal správami ani poučkami. Dostal silnú prirodzenú myseľ, láskavú dušu a silného bojového ducha. Prešiel sovietsko-fínskou vojnou ako verný vojak svojej vlasti a nezaváhal ani v prvý deň Veľkej vlasteneckej vojny. Teraz bol počet jeho bojových misií v jeho druhej stovke. Letel s nami ako obyčajný veliteľ lode, no rád vzlietol ako prvý, možno sa mu to nepáčilo, nevidel v tom žiadne taktické výhody, no miesto pred letkou zrejme považoval za svoje. .

Chulkov po bombardovaní letiska Orsha už kráčal domov a bol pol hodiny vzdialený od vlastných ľudí, keď sa zrazu dostali pod paľbu, strela zasiahla pravý motor. Začalo sa z neho dymiť, hrkotať, kašľať a bolo ho treba vypnúť. Vrtuľa sa, žiaľ, ďalej otáčala, šmýkanie sa stalo nevyhnutným a auto začalo mierne klesať. Pred líniou zostávalo veľmi málo nadmorskej výšky, ale Alexey Petrovič a jeho stály navigátor Grigory Chumash na ceste našli základňu pre našich bojovníkov v regióne Kaluga a rozhodli sa pristáť.

V noci takéto letiská nefungujú a nemajú ani nočné pristávacie zariadenia, ale svietili služobné svetlá „T“ a Alexey Petrovič úspešne pristál pozdĺž pristávacej dráhy, možno s určitým preletom. Letisko bolo maličké, na maskovanie bolo vybavené kopami sena a maketami zvierat, a keď bolo lietadlo na jeho okraji, radisti, vidiac túto „vidiecku krajinu“, jedným hlasom kričali: „Falošné letisko! Alexey Petrovič podľahol kriku, a hoci v nasledujúcom okamihu Chumash zakričal: „Posaďte sa! - už bolo neskoro. Ľavý motor ťahal auto ďalej na plný plyn, no stratenú rýchlosť a nadmorskú výšku nedokázalo nabrať späť a ani s jedným nezasunutým podvozkom. Pri otáčaní mimo letiska lietadlo krídlom narazilo do borovíc, spadlo na zem a začalo horieť. Plamene z nádrží sa plazili smerom k pilotnej kabíne. Chulkov bol ranený a nemohol sám vstať. Tam horelo. Pri požiari zahynul aj radista Dyakov. Strelec Glazunov, ktorý prekonal bolesť z modrín a odrenín, vyliezol cez kruh veže, ale nedokázal sa dostať cez oheň k veliteľovi. Grisha Chumash bol vymrštený zo svojej rozbitej navigátorskej ulity a pri páde si zlomil nohu na dvoch miestach. Odplazil sa od ohňa, obviazal si krvácajúce rany útržkami bielizne a začal čakať na pomoc. Prišla z letiska. Po početných operáciách sa noha citeľne skrátila a s lietaním som sa musel rozlúčiť.

Takto zomrel náš legendárny komisár.

Za niečo vyše roka vojny vykonal 119 bojových misií, z toho 111 v noci.

Bombardovaný Berlín a ďalšie mestá a vojenské zariadenia v Nemecku. Pri bombardovaní podporoval naše pozemné jednotky v prvej línii. Za cenu svojho života priblíženie hodiny víťazstva.

V decembri počas formovania pluku bol rozkaz prečítaný. Sú tam tieto slová:

Za bezhraničnú oddanosť vlasti, za dobrú organizáciu bojovej práce eskadry, za osobnú odvahu a hrdinstvo v boji, pohŕdajúc smrťou, je práporový komisár Čulkov hodný najvyššieho vládneho vyznamenania „Hrdina Sovietskeho zväzu“ s. odovzdanie Leninovho rádu a medaily Zlatá hviezda - posmrtne

Pochovali ho v meste Kaluga.

ocenenia

Dekrétom Prezídia Najvyššieho sovietu ZSSR z 31.12.1942 Za výkon a vynikajúce plnenie bojových úloh velenia bol major Alexej Petrovič Chulkov posmrtne ocenený titulom Hrdina Sovietskeho zväzu.

Vyznamenaný dvoma Leninovými rádmi a dvomi rádmi Červenej zástavy.

Zo zoznamu ocenení:

Major Chulkov pracuje ako zástupca veliteľa leteckej letky pre politické záležitosti. Lietanie na lietadle Il-4 ako súčasť nočnej posádky, kde je navigátorom kapitán Chumash, strelec-radista predák Kozlovský a letecký strelec starší seržant Dyakov.

V aktívnej armáde bol od prvých dní 2. svetovej vojny. Za toto obdobie vykonal 114 bojových vzletov, z toho 111 v noci a všetky pri vynikajúcom plnení bojovej úlohy. Letel bombardovať vojensko-priemyselné zariadenia a politické centrá nepriateľa v hlbokom tyle: Berlín - 2-krát, Budapešť - 1-krát, Danzig - 1-krát, Koenigsberg - 1-krát, Varšava - 2-krát.

Za vynikajúce plnenie bojových úloh velenia poraziť nemecký fašizmus mu bol udelený Leninov rád a Rád červenej zástavy. Po ocenení vykonal 55 bojových misií. Počas pôsobenia ako vojenský komisár leteckej eskadry sa presadil ako vychovávateľ personálu v duchu oddanosti vlasti a nenávisti k nepriateľovi. Jeho letka absolvovala 951 bojových letov proti nepriateľovi počas bojových operácií. Súdruh Chulkov svojím osobným príkladom inšpiruje podriadený personál k hrdinským činom. Disciplinovaný, náročný na seba a svojich podriadených. Medzi personálom má zaslúženú autoritu. Venuje sa veci Leninovej strany a socialistickej vlasti.

Za vynikajúce plnenie bojových úloh velenia s cieľom poraziť nemecký fašizmus a prejavenú odvahu a hrdinstvo si major Čulkov zaslúži vládne ocenenie Leninovho rádu.

Veliteľ 751 AP DD Hrdina Sovietskeho zväzu
Podplukovník TIKHONOV 4. novembra 1942.

Záver Vojenskej rady.

Hodný vládneho ocenenia titulu Hrdina Sovietskeho zväzu.

Letecký veliteľ Člen vojenskej rady
diaľkové letectvo
Generál letectva GOLOVANOV
Divízny komisár GURYANOV
30. novembra 1942

2.2. Spomienka - zvečnenie mena Hrdina Sovietskeho zväzu v pamätných predmetoch

Pamätník slávy na kopci Poklonnaya v Moskve

Pamätný komplex Kaluga

Ulica v meste Karabanovo v regióne Vladimir nesie meno hrdinu.

V roku 2004 vyšla kniha V. V. Reshetnikova „Čo bolo, bolo“, ktorá hovorí o Chulkovovi.

Dokumentárny príbeh „Okrídlený komisár“ od Yu.N. Khudova

V roku 2000 bola naša škola pomenovaná po Countryman Hero.

Riaditeľom našej školy je príbuzný Chulkova Alexej Petrovič Chulkov Petr Alexandrovič. Práve vďaka jeho aktivitám nesie naša škola meno Hrdina. Samotný Pyotr Alexandrovič je dôstojným synom vlasti. V roku 1983 bol povolaný do ozbrojených síl ZSSR. Slúžil v Afganskej republike, veliteľ bezpečnostnej čaty samostatného sprievodu motorizovaných pušiek. Spolu so svojimi kamarátmi sprevádzal kolóny nákladných áut KAMAZ s nákladom. Jedného dňa sa kolóna dostala pod paľbu a Pyotr Alexandrovič bol zranený.

Chulkov Pyotr Aleksandrovich získal: hviezdu „Účastník afganskej vojny“, rádový odznak „Bojovník – internacionalista“, medailu „Od vďačného afganského ľudu“, Certifikát prezídia Najvyššieho sovietu ZSSR „Za odvahu a vojenská odvaha“.

Vyznačuje sa skromnosťou, zodpovednosťou, prísnosťou a eleganciou. Je talentovaným vodcom a organizátorom učiteľských a študentských tímov. Pod jeho vedením patrí škola medzi najlepšie školy v okolí.

Výstava v školskom múzeu dediny Yukhmachi

Park víťazstva v Kazani

Pamätník venovaný Chulkovovi A.P. v dedine Yukhmachi, v domovine hrdinu.

V.V. Reshetnikov s vnučkou A.P. Chulkovou Elena Shusharina. Moskva 2007.

3.Záver

Život a výkon, tieto slová často počujeme. Jednoduchý muž z vnútrozemia, ktorý mal 34 rokov, sa ukázal ako skutočný hrdina vojny a krvavých bitiek. A.P. Chulkov sa stal hrdinom z nejakého dôvodu, bol skutočným človekom, ktorého vychovávala jeho rodina, jeho vlasť.

Práca na materiáloch o hrdinovi prispela k určeniu duchovných smerníc, morálnych hodnôt, univerzálnych ľudských priorít a formovaniu vlasteneckého vedomia ako jednej z najdôležitejších hodnôt a základov duchovnej a morálnej jednoty.

A potreba podieľať sa na záležitostiach Ruského hnutia školákov, ktorého som členom, sa stáva zrejmou. Ide o verejno-štátnu detskú a mládežnícku organizáciu, ktorá vznikla rozhodnutím ustanovujúcej schôdze z 28. marca 2016 na Moskovskej univerzite pomenovanej po M. V. Lomonosov. V súlade s dekrétom prezidenta Ruskej federácie z 29. októbra 2015. RDS pôsobí v týchto oblastiach: - vojensko-vlastenecká - „Armáda mládeže“

Osobný rozvoj

Občiansky aktivizmus (dobrovoľníctvo, pátracia práca, štúdium histórie, miestnej histórie)

Informácie a médiá.

4. Referencie:

1.V.V. Reshetnikov „Čo sa stalo, čo sa stalo“, M., 2004.

2. Yu.N. Khudov "Okrídlený komisár"

3. Materiály zo školského múzea dediny Yukhmachi

4. Foto z osobného archívu Chulkov P.A.

5.http://ru.wikipedia.org

Formulár žiadosti účastníka

Republikánska súťaž projektov „Slávne stránky histórie.

School of Heroes“ pre študentov 5. – 7. ročníka všeobecného vzdelávania

Organizácie Tatarskej republiky nesúce meno Hrdina

Územie RT, okres Alkeevsky, dedina Yukhmachi

Nominácia "Slávni synovia vlasti"

Meno, priezvisko účastníka Ravil Galiullin

Dátum narodenia 05. 01.2005

Veková skupina 7. trieda

Celý názov vzdelávacej organizácie MBOU "Yukhmachinskaya stredná škola pomenovaná po Hrdinovi Sovietskeho zväzu Alexejovi Petrovičovi Chulkovovi"dedina Yukhmachi, sv. Shkolnaya, dom 10 a

Telefónne číslo 89276781352

E-mail [chránený e-mailom]

Celé meno učiteľa (celé) Moskvina Galina Alexandrovna

Kontaktné telefónne číslo učiteľa 89270389187

Súhlas so spracovaním osobných údajov

ja, Shubina Tatyana Nikolaevna, pas 9200097914 , vydané ATC leteckého stavebného obvodu Kazaň, 01.11.2002___________________________________________________________
(kedy, kým)

RT, okres Alkeevsky, dedina Yukhmachi, ul. Škola 4.

____________________________________________________________________________________________________________________

Súhlasím so spracovaním osobných údajov môjho dieťaťa Galiullin Ravil Rashitovič

RT, okres Alkeevsky, dedina Yukhmachi, ul. Škola 4.

prevádzkovateľa Ministerstva školstva a vedy Tatarskej republiky zúčastniť sa súťaže.

Zoznam osobných údajov, na spracovanie ktorých sa udeľuje súhlas: priezvisko, meno, priezvisko, škola, trieda, adresa bydliska, dátum narodenia, telefónne číslo, emailová adresa, výsledky účasti v záverečnej fáze súťaže.

Prevádzkovateľ má právo zhromažďovať, systematizovať, zhromažďovať, uchovávať, objasňovať, používať, prenášať osobné údaje tretím stranám – vzdelávacím organizáciám, školským úradom okresov (miest), Ministerstvu školstva a vedy Republiky Tatarstan, Ministerstvu Vzdelávanie Ruskej federácie, iné právnické osoby a fyzické osoby zodpovedné za organizáciu a vedenie rôznych fáz súťaže, depersonalizáciu, blokovanie a likvidáciu osobných údajov.

Týmto vyhlásením oprávňujem, aby boli nasledovné osobné údaje môjho dieťaťa považované za verejne dostupné, a to aj na internete: priezvisko, meno, trieda, škola, materská škola, výsledok záverečnej fázy súťaže, ako aj zverejnenie naskenovanej kópie diela vo verejnej doméne.

Spracúvanie osobných údajov sa vykonáva v súlade s normami federálneho zákona Ruskej federácie zo dňa 27. júla 2006 č. 152-FZ „O osobných údajoch“.

Táto zmluva nadobúda platnosť dňom jej podpisu a jej platnosť je 3 roky.

______________________ ______________________________ (osobný podpis, dátum)

Tretie mesto vedecké

študentská konferencia

Informatika a matematika

Výskumná práca

Eulerove kruhy a teória grafov pri riešení problémov

školská matematika a informatika

Valijev Airat

Mestská vzdelávacia inštitúcia

„Stredná škola číslo 10 s prehĺbeným štúdiom

jednotlivé predmety“, 10 B trieda, Nižnekamsk

Vedeckí vedúci:

Khalilova Nafise Zinnyatullovna, učiteľka matematiky

Učiteľ informatiky

Naberezhnye Chelny

Úvod. 3

Kapitola 1. Eulerove kruhy. 4

1.1. Teoretické základy o Eulerových kruhoch. 4

1.2. Riešenie problémov pomocou Eulerových kruhov. 9

Kapitola 2. O stĺpcoch 13

2.1.Teória grafov. 13

2.2. Riešenie problémov pomocou grafov. 19

Záver. 22

Referencie. 22

Úvod

„Všetka naša dôstojnosť spočíva v myslení.

Nie je to priestor, nie je to čas, ktorý nemôžeme naplniť,

povznáša nás, totiž to, našu myšlienku.

Naučme sa dobre myslieť."

B. Pascal,

Relevantnosť. Hlavnou úlohou školy nie je poskytnúť deťom veľké množstvo vedomostí, ale naučiť žiakov získavať poznatky sami, schopnosť tieto poznatky spracovať a aplikovať v bežnom živote. Dané úlohy môže riešiť žiak, ktorý má nielen schopnosť dobre a usilovne pracovať, ale aj žiak s rozvinutým logickým myslením. V tomto smere mnohé školské predmety obsahujú rôzne typy úloh, ktoré rozvíjajú u detí logické myslenie. Pri riešení týchto problémov využívame rôzne techniky riešenia. Jednou z metód riešenia je použitie Eulerových kružníc a grafov.

Účel štúdie: štúdium materiálu používaného na hodinách matematiky a informatiky, kde sa ako jedna z metód riešenia problémov využívajú Eulerove kružnice a teória grafov.

Ciele výskumu:

1. Preštudujte si teoretické základy pojmov: „Eulerovské kruhy“, „Grafy“.

2. Vyriešte úlohy školského kurzu vyššie uvedenými metódami.

3. Zostavte výber materiálu pre žiakov a učiteľov na hodinách matematiky a informatiky.

Výskumná hypotéza: používanie Eulerových kruhov a grafov zvyšuje prehľadnosť pri riešení problémov.

Predmet výskumu: pojmy: „Eulerove kruhy“, „Grafy“, problémy školského kurzu matematiky a informatiky.

Kapitola 1. Eulerove kruhy.

1.1. Teoretické základy o Eulerových kruhoch.

Eulerove kruhy (Eulerove kruhy) sú metóda modelovania akceptovaná v logike, vizuálna reprezentácia vzťahov medzi objemami pojmov pomocou kruhov, ktorú navrhol slávny matematik L. Euler (1707–1783).

Označenie vzťahov medzi objemami pojmov pomocou kruhov použil predstaviteľ aténskej novoplatónskej školy - Filoponus (VI. storočie), ktorý napísal komentáre k Aristotelovej Prvej analýze.

Konvenčne sa uznáva, že kruh vizuálne zobrazuje objem jedného konceptu. Rozsah konceptu odráža súhrn objektov jednej alebo druhej triedy objektov. Preto každý objekt triedy objektov môže byť reprezentovaný bodom umiestneným vo vnútri kruhu, ako je znázornené na obrázku:

Skupina objektov, ktoré tvoria vzhľad danej triedy objektov, je znázornená ako menší kruh nakreslený vo vnútri väčšieho kruhu, ako je to znázornené na obrázku.

https://pandia.ru/text/78/128/images/image003_74.gif" alt="prekrývajúce sa triedy" width="200" height="100 id=">!}

Toto je presne vzťah, ktorý existuje medzi rozsahom pojmov „študent“ a „člen Komsomolu“. Niektorí (ale nie všetci) študenti sú členmi Komsomolu; niektorí (ale nie všetci) členovia Komsomolu sú študenti. Nevytieňovaná časť kruhu A odráža tú časť rozsahu pojmu „študent“, ktorá sa nezhoduje s rozsahom pojmu „člen Komsomolu“; Netieňovaná časť kruhu B odráža tú časť rozsahu pojmu „člen Komsomolu“, ktorá sa nezhoduje s rozsahom pojmu „študent“. Vytieňovaná časť, ktorá je spoločná pre oba kruhy, označuje študentov, ktorí sú členmi Komsomolu, a členov Komsomolu, ktorí sú študentmi.

Keď ani jeden objekt zobrazený v objeme konceptu A nemôže byť súčasne zobrazený v objeme konceptu B, potom je v tomto prípade vzťah medzi objemami konceptov znázornený pomocou dvoch kruhov nakreslených jeden mimo druhého. Ani jeden bod ležiaci na povrchu jednej kružnice nemôže byť na povrchu inej kružnice.

https://pandia.ru/text/78/128/images/image005_53.gif" alt=" koncepty s rovnakými objemami - zhodné kruhy" width="200" height="100 id=">!}

Takýto vzťah existuje napríklad medzi pojmami „zakladateľ anglického materializmu“ a „autor Nového organonu“. Rozsah týchto pojmov je rovnaký, odrážajú tú istú historickú postavu – anglického filozofa F. Bacona.

Často sa to deje takto: jeden pojem (generický) je podradený viacerým špecifickým pojmom naraz, ktoré sa v tomto prípade nazývajú podriadené. Vzťah medzi týmito pojmami je znázornený vizuálne jedným veľkým kruhom a niekoľkými menšími kruhmi, ktoré sú nakreslené na povrchu väčšieho kruhu:

https://pandia.ru/text/78/128/images/image007_46.gif" alt="opačné pojmy" width="200" height="100 id=">!}

Zároveň je jasné, že medzi protikladnými pojmami je možný aj tretí, priemer, pretože nevyčerpávajú úplne rozsah generického pojmu. Toto je presne vzťah, ktorý existuje medzi pojmami „ľahký“ a „ťažký“. Vzájomne sa vylučujú. O tom istom predmete, branom v rovnakom čase a v rovnakom vzťahu, nemožno povedať, že je zároveň ľahký aj ťažký. Ale medzi týmito pojmami existuje stredná cesta, tretia: predmety sú nielen ľahké a ťažké, ale aj stredne ťažké.

Keď existuje protichodný vzťah medzi pojmami, potom sa vzťah medzi objemami pojmov zobrazuje inak: kruh je rozdelený na dve časti takto: A je všeobecný pojem, B a ne-B (označené ako B) sú protichodné pojmy. . Konfliktné pojmy sa navzájom vylučujú a patria do rovnakého rodu, čo možno vyjadriť nasledujúcim diagramom:

https://pandia.ru/text/78/128/images/image009_38.gif" alt="predmet a predikát definície" width="200" height="100 id=">!}

Inak vyzerá diagram vzťahu medzi objemami podmetu a predikátu vo všeobecnom kladnom súde, ktorý nie je definíciou pojmu. V takomto úsudku je rozsah predikátu väčší ako rozsah podmetu je celý zahrnutý do rozsahu predikátu. Preto je vzťah medzi nimi znázornený pomocou veľkých a malých kruhov, ako je znázornené na obrázku:

Školské knižnice" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">školská knižnica, 20 - v okrese. Koľko žiakov piateho ročníka:

a) nie sú čitateľmi školskej knižnice;

b) nie sú čitateľmi okresnej knižnice;

c) sú len čitateľmi školskej knižnice;

d) sú len čitateľmi krajskej knižnice;

e) sú čitateľmi oboch knižníc?

3. Každý študent v triede sa učí buď angličtinu alebo francúzštinu, prípadne oboje. 25 ľudí študuje angličtinu, 27 ľudí študuje francúzštinu a 18 ľudí študuje oboje. Koľko žiakov je v triede?

4. Na list papiera nakreslite kruh s plochou 78 cm2 a štvorec s plochou 55 cm2. Plocha priesečníka kruhu a štvorca je 30 cm2. Časť listu, ktorú nezaberá kruh a štvorec, má plochu 150 cm2. Nájdite oblasť listu.

5. V MŠ je 52 detí. Každý z nich miluje buď tortu alebo zmrzlinu, alebo oboje. Polovica detí má rada torty a 20 ľudí má rado tortu a zmrzlinu. Koľko detí miluje zmrzlinu?

6. V študentskom produkčnom tíme je 86 stredoškolákov. 8 z nich nevie ovládať ani traktor, ani kombajn. 54 žiakov dobre ovládalo traktor, 62 - kombajn. Koľko ľudí z tohto tímu môže pracovať na traktore aj na kombajne?

7. V triede je 36 žiakov. Mnohí z nich navštevujú krúžky: fyzika (14 ľudí), matematika (18 ľudí), chémia (10 ľudí). Okrem toho je známe, že všetky tri krúžky navštevujú 2 ľudia; Z tých, ktorí navštevujú dva krúžky, sa 8 ľudí venuje matematickým a fyzikálnym krúžkom, 5 je matematickým a chemickým krúžkom, 3 sú fyzikálne a chemické. Koľko ľudí nenavštevuje žiadny klub?

8. 100 žiakov šiesteho ročníka našej školy sa zapojilo do prieskumu, ktoré počítačové hry sa im páčili najviac: simulátory, úlohy alebo stratégie. Výsledkom bolo, že 20 respondentov menovalo simulátory, 28 - úlohy, 12 - stratégie. Ukázalo sa, že 13 školákov rovnako preferuje simulátory a úlohy, 6 študentov – simulátory a stratégie, 4 študenti – úlohy a stratégie a 9 študentom sú tieto počítačové hry úplne ľahostajné. Niektorí zo školákov odpovedali, že ich rovnako zaujímajú simulátory, úlohy a stratégie. Koľko je tých chlapov?

Odpovede

https://pandia.ru/text/78/128/images/image012_31.gif" alt="Oval: A" width="105" height="105">1.!}

A – šach 25-5=20 – ľudí. vedieť hrať

B – dáma 20+18-20=18 – ľudia hrajú dámu aj šach

2. Ш – veľa návštevníkov školskej knižnice

P – veľa návštevníkov okresnej knižnice

https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">

5. 46. P – torta, M – zmrzlina

6 – deti milujú koláče

6. 38. T – traktor, K – kombajn

54+62-(86-8)=38 – schopný pracovať na traktore aj na kombajne

grafy“ a systematicky študovať ich vlastnosti.

Základné pojmy.

Prvým zo základných pojmov teórie grafov je pojem vrchol. V teórii grafov sa berie ako primárny a nie je definovaný. Nie je ťažké si to predstaviť na vlastnej intuitívnej úrovni. Zvyčajne sú vrcholy grafu vizuálne znázornené vo forme kruhov, obdĺžnikov a iných obrázkov (obr. 1). V každom grafe musí byť prítomný aspoň jeden vrchol.

Ďalším základným pojmom v teórii grafov sú oblúky. Oblúky sú zvyčajne rovné alebo zakrivené segmenty spájajúce vrcholy. Každý z dvoch koncov oblúka sa musí zhodovať s nejakým vrcholom. Prípad, keď sa oba konce oblúka zhodujú s rovnakým vrcholom, nie je vylúčený. Napríklad na obr. 2 sú prijateľné obrázky oblúkov a na obr. 3 sú neprijateľné:

V teórii grafov sa používajú dva typy oblúkov – neusmernené alebo usmernené (orientované). Graf obsahujúci iba orientované oblúky sa nazýva orientovaný graf alebo digraf.

Oblúky môžu byť jednosmerné, pričom každý oblúk má iba jeden smer, alebo obojsmerné.

Vo väčšine aplikácií je možné bez straty významu nahradiť všesmerový oblúk obojsmerným oblúkom a obojsmerný oblúk dvoma jednosmernými oblúkmi. Napríklad, ako je znázornené na obr. 4.

Spravidla sa graf buď okamžite zostrojí tak, že všetky oblúky majú rovnakú smerovú charakteristiku (napríklad všetky sú jednosmerné), alebo sa do tejto podoby privedie transformáciami. Ak je oblúk AB nasmerovaný, znamená to, že z jeho dvoch koncov sa jeden (A) považuje za začiatok a druhý (B) za koniec. V tomto prípade hovoria, že začiatok oblúka AB je vrchol A a koniec je vrchol B, ak oblúk smeruje z A do B, alebo že oblúk AB vychádza z vrcholu A a vstupuje do B (obr. 5 ).

Dva vrcholy grafu spojené nejakým oblúkom (niekedy bez ohľadu na orientáciu oblúka) sa nazývajú susedné vrcholy.

Dôležitým pojmom pri štúdiu grafov je pojem cesta. Dráha A1,A2,...An je definovaná ako konečná postupnosť (dvojica) vrcholov A1,A2,...An a oblúkov A1, 2,A2,3,...,An-1, n, ktoré sa postupne spájajú tieto vrcholy.

Dôležitým pojmom v teórii grafov je koncept konektivity. Ak pre akékoľvek dva vrcholy grafu existuje aspoň jedna cesta, ktorá ich spája, graf sa nazýva spojený.

Ak napríklad zobrazíte ľudský obehový systém ako graf, kde vrcholy zodpovedajú vnútorným orgánom a oblúky krvným kapiláram, potom je takýto graf zjavne spojený. Dá sa povedať, že obehový systém dvoch ľubovoľných ľudí je nesúvislý graf? Očividne nie, keďže v prírode sa pozorujú tzv. "Siamské dvojčatá".

Konektivita môže byť nielen kvalitatívna charakteristika grafu (spojená/neprepojená), ale aj kvantitatívna.

Graf sa nazýva K-spojený, ak každý z jeho vrcholov je spojený s K inými vrcholmi. Niekedy sa hovorí o slabo a silne prepojených grafoch. Tieto pojmy sú subjektívne. Výskumník nazýva graf silne spojený, ak pre každý z jeho vrcholov je počet susedných vrcholov podľa názoru výskumníka veľký.

Niekedy je konektivita definovaná ako charakteristika nie každého, ale jedného (ľubovoľného) vrcholu. Potom sa objavia definície typov: graf sa nazýva K-spojený, ak je aspoň jeden z jeho vrcholov spojený s K ďalšími vrcholmi.

Niektorí autori definujú konektivitu ako extrémnu hodnotu kvantitatívnej charakteristiky. Napríklad graf je K-spojený, ak je v grafe aspoň jeden vrchol, ktorý je spojený s K susednými vrcholmi, a žiadny vrchol, ktorý je spojený s viac ako K susednými vrcholmi.

Napríklad detská kresba osoby (obr. 6) je graf s maximálnou konektivitou 4.

Ďalšia charakteristika grafu, skúmaná v mnohých problémoch, sa často nazýva mohutnosť grafu. Táto charakteristika je definovaná ako počet oblúkov spájajúcich dva vrcholy. V tomto prípade sa oblúky s opačným smerom často posudzujú oddelene.

Napríklad, ak vrcholy grafu predstavujú uzly spracovania informácií a oblúky sú jednosmerné kanály na prenos informácií medzi nimi, potom spoľahlivosť systému nie je určená celkovým počtom kanálov, ale najmenším počtom kanálov v akýkoľvek smer.

Mohutnosť, podobne ako konektivitu, možno určiť tak pre každú dvojicu vrcholov grafu, ako aj pre nejaký (ľubovoľný) pár.

Základnou charakteristikou grafu je jeho rozmer. Tento pojem sa zvyčajne chápe ako počet vrcholov a oblúkov existujúcich v grafe. Niekedy je táto hodnota definovaná ako súčet množstiev prvkov oboch typov, niekedy ako súčin, niekedy ako počet prvkov len jedného (jednoho alebo druhého) typu.

Typy grafov.

Objekty modelované grafmi sú veľmi rôznorodého charakteru. Túžba odrážať túto špecifickosť viedla k opisu veľkého počtu odrôd grafov. Tento proces pokračuje dodnes. Mnohí výskumníci pre svoje špecifické účely zavádzajú nové odrody a vykonávajú svoje matematické štúdie s väčším alebo menším úspechom.

V srdci celej tejto rozmanitosti je niekoľko pomerne jednoduchých myšlienok, o ktorých tu budeme hovoriť.

Farbenie

Farbenie grafov je veľmi populárny spôsob úpravy grafov.

Táto technika umožňuje zvýšiť prehľadnosť modelu a zvýšiť matematickú záťaž. Spôsoby zavádzania farby môžu byť rôzne. Oblúky aj vrcholy sú zafarbené podľa určitých pravidiel. Sfarbenie je možné určiť jednorazovo alebo sa časom meniť (to znamená, keď graf nadobudne nejaké vlastnosti); farby je možné previesť podľa určitých pravidiel atď.

Napríklad nech graf predstavuje model ľudského krvného obehu, kde vrcholy zodpovedajú vnútorným orgánom a oblúky krvným kapiláram. Zafarbíme tepny na červeno a žily na modro. Potom je zrejmé, že nasledujúce tvrdenie je pravdivé - v uvažovanom grafe (obr. 8) sú, a to iba dva, vrcholy s vychádzajúcimi červenými oblúkmi (červená farba je na obrázku znázornená tučným písmom).

Dĺžka

Niekedy majú prvky objektu modelované vrcholmi výrazne odlišné znaky. Alebo sa počas procesu formalizácie ukáže ako užitočné pridať nejaké fiktívne prvky k prvkom, ktoré v objekte skutočne existujú. V tomto a niektorých ďalších prípadoch je prirodzené rozdeliť vrcholy grafu do tried (podielov). Graf obsahujúci vrcholy dvoch typov sa nazýva bipartitný atď. V tomto prípade obmedzenia grafu zahŕňajú pravidlá týkajúce sa vzťahov medzi vrcholmi rôznych typov. Napríklad: „neexistuje žiadny oblúk, ktorý by spájal vrcholy rovnakého typu.“ Jeden z druhov grafov tohto druhu sa nazýva „Petriho sieť“ (obr. 9) a je pomerne rozšírený. Petriho sieťam sa budeme podrobnejšie venovať v ďalšom článku tejto série.

Pojem údolia možno aplikovať nielen na vrcholy, ale aj na oblúky.

2.2. Riešenie problémov pomocou grafov.

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

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

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

4.

Dudeneyho úlohy.

1. Smith, Jones a Robinson pracujú v tej istej vlakovej posádke ako rušňovodič, sprievodca a kurič. Ich povolania nemusia byť nevyhnutne pomenované v rovnakom poradí ako ich priezviská. Vo vlaku, ktorý obsluhuje brigáda, sedia traja cestujúci s rovnakým priezviskom. V budúcnosti budeme každého cestujúceho s úctou nazývať „Pán“.

2. Pán Robinson žije v Los Angeles.

3. Dirigent býva v Omahe.

4. Pán Jones už dávno zabudol na všetku algebru, ktorú ho učili na vysokej škole.

5. Cestujúci, menovec vodiča, žije v Chicagu.

6. Dirigent a jeden z cestujúcich, slávny odborník na matematickú fyziku, hoci chodia do rovnakého kostola.

7. Smith vždy vyhrá nad hasičom, keď sa náhodou stretnú pri hre biliardu.

Aké je priezvisko vodiča? (Obr. 13)

Tu 1-5 sú počty ťahov, v zátvorkách sú počty bodov úlohy, na základe ktorých boli ťahy (závery) urobené. Z odseku 7 ďalej vyplýva, že požiarnik nie je Smith, teda Smith je strojník.

Záver

Analýza teoretického a praktického materiálu na študovanú tému nám umožňuje vyvodiť závery o úspešnosti používania Eulerových kruhov a grafov na rozvoj logického myslenia u detí, vzbudzovanie záujmu o študovaný materiál, používanie vizualizácie na hodinách, ako napr. ako aj redukciu zložitých problémov na jednoduché na pochopenie a riešenie.

Referencie

1. „Zábavné úlohy v informatike“, Moskva, 2005

2. „Scenáre pre školské prázdniny“ od E. Vladimirovej, Rostov na Done, 2001

3. Úlohy pre zvedavcov. , M., Vzdelávanie, 1992,

4. Mimoškolská práca z matematiky, Saratov, Lyceum, 2002.

5. Nádherný svet čísel. , ., M., Vzdelávanie, 1986,

6. Algebra: učebnica pre 9. ročník. a ďalší, vyd. , - M.: Osveta, 2008