Navyše, posledných 12 rokov svojho života bol Euler vážne chorý, oslepol a napriek ťažkej chorobe pokračoval v práci a tvorení.

Štatistické výpočty ukazujú, že Euler urobil v priemere jeden objav za týždeň.

Je ťažké nájsť matematický problém, ktorý sa v Eulerových dielach nedotkol.

Všetci matematici nasledujúcich generácií študovali s Eulerom tak či onak a nie nadarmo známy francúzsky vedec P.S. Laplace povedal: "Prečítaj si Eulera, je učiteľom nás všetkých."

Lagrange hovorí: "Ak naozaj milujete matematiku, prečítajte si Eulera; expozícia jeho diel sa vyznačuje úžasnou jasnosťou a presnosťou." Elegancia výpočtov je ním skutočne dovedená na najvyšší stupeň. Condorcet zakončil svoj prejav na akadémii na pamiatku Eulera nasledujúcimi slovami: "Tak, Euler prestal žiť a počítať!" Žiť s cieľom počítať - aké nudné sa to zdá zvonku! Je zvykom predstaviť si matematiku suchú a hluchú ku všetkému svetskému, k tomu, čo zaujíma obyčajných ľudí.

S menom Euler je problém troch domov a troch studní.

TEÓRIA GRAFOV

Jedna z vetiev topológie. Graf je geometrický diagram, ktorý predstavuje sústavu čiar spájajúcich niektoré dané body. Body sa nazývajú vrcholy a čiary, ktoré ich spájajú, sa nazývajú hrany (alebo oblúky). Všetky problémy teórie grafov je možné riešiť v grafickej aj maticovej forme. V prípade zápisu v maticovej forme sa možnosť prenosu správy z daného vrcholu do iného označí jednotkou a jej absencia sa označí nulou.

Vznik teórie grafov v 18. storočí. spojené s matematickými hlavolamami, no obzvlášť silný impulz k jeho rozvoju dalo 19. storočie. a hlavne v 20. storočí, kedy boli objavené možnosti jeho praktických aplikácií: na výpočty rádioelektronických obvodov, riešenie tzv. dopravné úlohy a pod. Od 50. rokov. Teória grafov sa čoraz viac využíva v sociálnej psychológii a sociológii.

Z oblasti teórie grafov treba spomenúť diela F. Harryho, J. Kemenyho, K. Flamenta, J. Snella, J. Frencha, R. Normana, O. Oizera, A. Beivelasa, R. Weissa a i. V ZSSR podľa T. g. práce Φ. M. Borodkin a ďalší.

Jazyk teórie grafov je vhodný na analýzu rôznych druhov štruktúr a prenosu stavov. V súlade s tým môžeme rozlíšiť nasledovné typy sociologických a sociálno-psychologických problémov riešených pomocou teórie grafov.

Formalizácia a konštrukcia všeobecného štruktúrneho modelu sociálneho objektu na rôzne úrovne jeho komplexnosť. Napríklad organizačné schémy, sociogramy, porovnanie systémov príbuzenstva v rôznych spoločnostiach, analýza štruktúry rolí skupín atď. Môžeme predpokladať, že štruktúra rolí zahŕňa tri zložky: osoby, pozície (v zjednodušenej verzii - pozície) a úlohy vykonávané na tejto pozícii. Každý komponent môže byť reprezentovaný ako graf:

Je možné skombinovať všetky tri grafy pre všetky pozície, alebo len pre jeden, a vo výsledku tak získame jasnú predstavu o špecifickej štruktúre c.l. túto rolu. Takže pre rolu pozície P5 máme graf (obr.). Votkanie neformálnych vzťahov do naznačenej formálnej štruktúry výrazne skomplikuje graf, ale bude to viac presnú kópiu realita.

2) Analýza získaného modelu, výber štruktúrnych jednotiek (subsystémov) v ňom a štúdium ich vzťahov. Týmto spôsobom možno oddeliť napríklad podsystémy vo veľkých organizáciách.

3) Štúdium úrovní štruktúry hierarchických organizácií: počet úrovní, počet spojení prechádzajúcich z jednej úrovne do druhej a od jednej osoby k druhej. Na základe toho sa riešia tieto úlohy:

a) množstvá. posúdenie váhy (stavu) jednotlivca v hierarchickej organizácii. Jednou z možných možností na určenie stavu je vzorec:

kde r (p) je postavenie určitej osoby p, k je hodnota úrovne podriadenosti definovaná ako najmenší počet krokov od danej osoby k jej podriadenému, nk je počet osôb na danej úrovni k . Napríklad v organizácii zastúpenej nasledovným. počítať:

hmotnosť a=1 2+2 7+3 4=28; 6=1 3+2 3=9 atď.

b) určenie vedúceho skupiny. Vodca sa zvyčajne vyznačuje väčším spojením s ostatnými členmi skupiny ako s ostatnými. Rovnako ako v predchádzajúcom probléme, aj tu je možné použiť rôzne metódy na výber vodcu.

Najjednoduchší spôsob je daný vzorcom: r=Σdxy/Σdqx, t.j. podiel delenia súčtu všetkých vzdialeností každého ku všetkým ostatným súčtom vzdialeností jednotlivca ku všetkým ostatným.

4) Analýza efektívnosti tohto systému, ktorá zahŕňa aj také úlohy ako hľadanie optimálnej štruktúry organizácie, zvyšovanie skupinovej súdržnosti, analýza sociálneho systému z hľadiska jeho stability; štúdium informačných tokov (prenos správ pri riešení problémov, vplyv členov skupiny na seba v procese zoskupovania); s pomocou TG riešia problém hľadania optimálnej komunikačnej siete.

Ako pre teóriu grafov, tak aj pre akýkoľvek matematický aparát, platí tvrdenie, že základné princípy riešenia problému stanovuje obsahová teória (v tomto prípade sociológia).

Úloha : Traja susedia sa delia o tri studne. Je možné nakresliť nepretínajúce sa cesty od každého domu ku každej studni. Cestičky nemôžu prechádzať cez studne a domy (obr. 1).

Ryža. 1. K problematike domov a studní.

Na vyriešenie tohto problému používame vetu dokázanú Eulerom v roku 1752, ktorá je jednou z hlavných v teórii grafov. Prvá práca o teórii grafov patrí Leonhardovi Eulerovi (1736), hoci pojem „graf“ prvýkrát zaviedol v roku 1936 maďarský matematik Denes Koenig. Grafy sa nazývali schémy pozostávajúce z bodov a spájajúce tieto body s úsečkami alebo krivkami.

Veta. Ak je mnohouholník rozdelený na konečný počet mnohouholníkov takým spôsobom, že žiadne dva mnohouholníky oddielu buď nemajú spoločné body, alebo majú spoločné vrcholy, alebo majú spoločné hrany, potom rovnosť

V – P + G = 1, (*)

kde B je celkový počet vrcholov, P je celkový počet hrán, G je počet polygónov (ploch).

Dôkaz. Dokážme, že rovnosť sa nemení, ak nakreslíme uhlopriečku v niektorom mnohouholníku daného oddielu (obr. 2, a).

a) b)

Po nakreslení takejto uhlopriečky bude mať nový oddiel B vrcholov, hrán P + 1 a počet polygónov sa zvýši o jeden. Preto máme

B - (P + 1) + (G + 1) \u003d B - P + G.

Pomocou tejto vlastnosti nakreslíme uhlopriečky rozdeľujúce prichádzajúce mnohouholníky na trojuholníky a pre výsledné rozdelenie ukážeme, že vzťah je splniteľný.

Aby sme to dosiahli, dôsledne odstránime vonkajšie okraje, čím znížime počet trojuholníkov. V tomto prípade sú možné dva prípady:

na odstránenie trojuholníka ABC je potrebné odstrániť dve hrany, v našom prípade AB a BC;

na odstránenie trojuholníka MKN je potrebné odstrániť jeden okraj, v našom prípade MN.

V oboch prípadoch sa rovnosť nezmení. Napríklad v prvom prípade po odstránení trojuholníka bude graf pozostávať z vrcholov B-1, hrán P-2 a polygónu G-1:

(B - 1) - (P + 2) + (G -1) \u003d B - P + G.

Odstránenie jedného trojuholníka teda nezmení rovnosť.

Pokračujúc v tomto procese odstraňovania trojuholníkov, nakoniec dospejeme k oddielu pozostávajúcom z jedného trojuholníka. Pre takéto rozdelenie B = 3, P = 3, Γ = 1, a preto

To znamená, že rovnosť platí aj pre pôvodné rozdelenie, čím nakoniec dostaneme, že vzťah platí pre dané rozdelenie mnohouholníka.

Všimnite si, že Eulerov vzťah nezávisí od tvaru polygónov. Polygóny možno deformovať, zväčšovať, zmenšovať alebo dokonca ohýbať ich strany, pokiaľ sa strany nezlomia. Eulerov vzťah sa nemení.

Teraz pristúpime k riešeniu problému troch domov a troch studní.

rozhodnutie. Predpokladajme, že sa to dá. Domy označíme bodmi D1, D2, D3, studne bodmi K1, K2, K3 (obr. 1). Spájame každý bodový dom s každou bodovou studňou. Dostaneme deväť hrán, ktoré sa v pároch nepretínajú.

Tieto hrany tvoria v rovine mnohouholník rozdelený na menšie mnohouholníky. Preto pre toto rozdelenie musí byť splnený Eulerov vzťah B - P + G = 1.

K uvažovaným plochám pridajme ešte jednu plochu - vonkajšiu časť roviny vzhľadom na mnohouholník. Potom Eulerov vzťah bude mať tvar B - P + G = 2, pričom B = 6 a P = 9.

Preto Г = 5. Každá z piatich stien má aspoň štyri hrany, pretože podľa stavu problému by žiadna z ciest nemala priamo spájať dva domy alebo dve studne. Keďže každá hrana leží presne na dvoch plochách, počet hrán musí byť aspoň (5 4)/2 = 10, čo je v rozpore s podmienkou, že ich počet je 9.

Výsledný rozpor ukazuje, že odpoveď v úlohe je záporná. - nie je možné nakresliť nepretínajúce sa cesty z každého domu do každého stĺpca

Teória grafov v chémii

Aplikácia teórie grafov na konštrukciu a rozbor rôznych tried chemických a chemicko-technologických grafov, ktoré sa nazývajú aj topológia, modely, t.j. modely, ktoré berú do úvahy len charakter spojenia vrcholov. Oblúky (hrany) a vrcholy týchto grafov odrážajú chemické a chemicko-technologické pojmy, javy, procesy alebo objekty a teda kvalitatívny a kvantitatívny vzťah alebo určitý vzťah medzi nimi.

Teoretické úlohy. Chemické grafy umožňujú predpovedať chemické premeny, vysvetliť podstatu a systematizovať niektoré základné pojmy chémie: štruktúra, konfigurácia, konfirmácie, kvantovo-mechanické a štatisticko-mechanické interakcie molekúl, izoméria atď. Chemické grafy zahŕňajú molekulárne, bipartitné a signálne grafy. kinetických rovníc reakcií. Molekulové grafy používané v stereochémii a štruktúrnej topológii, chémii klastrov, polymérov atď. sú neorientované grafy, ktoré zobrazujú štruktúru molekúl. Vrcholy a hrany týchto grafov zodpovedajú zodpovedajúcim atómom a chemickým väzbám medzi nimi.

V stereochémii org. c-c najčastejšie používajú molekulárne stromy - kostry molekulárnych grafov, ktoré obsahujú iba všetky vrcholy zodpovedajúce atómom. Zostavovanie množín molekulárnych stromov a stanovenie ich izomorfizmu umožňuje určiť molekulárne štruktúry a nájsť celkový počet izomérov alkánov, alkénov a alkínov . Molekulové grafy umožňujú zredukovať problémy súvisiace s kódovaním, nomenklatúrou a štruktúrnymi znakmi (vetvenie, cyklickosť atď.) molekúl rôznych zlúčenín na analýzu a porovnávanie čisto matematických znakov a vlastností molekulových grafov a ich stromov, ako aj ako ich zodpovedajúce matice. Na identifikáciu počtu korelácií medzi štruktúrou molekúl a fyzikálno-chemickými (vrátane farmakologickými) vlastnosťami zlúčenín sa používa viac ako 20 tzv. Topologické indexy molekúl (Wiener, Balaban, Hosoyya, Plat, Randich a pod.), ktoré sa určujú pomocou matíc a číselných charakteristík molekulárnych stromov. Napríklad Wienerov index W \u003d (m3 + m) / 6, kde m je počet vrcholov zodpovedajúcich atómom C, koreluje s molekulovými objemami a lommi, entalpiami tvorby, viskozitou, povrchovým napätím, chromatografickými konštantami zlúčenín, oktánové čísla uhľovodíkov a dokonca aj fyziol . drogová aktivita. Dôležitými parametrami molekulárnych grafov používaných na určenie tautomérnych foriem danej látky a ich reaktivity, ako aj pri klasifikácii aminokyselín, nukleových kyselín, uhľohydrátov a iných komplexných prírodných zlúčenín je priemerná a plná (H) informačná kapacita. . Analýza molekulárnych grafov polymérov, ktorých vrcholy zodpovedajú monomérnym jednotkám a hrany chemickým väzbám medzi nimi, umožňuje vysvetliť napríklad: účinky vylúčeného objemu, vedúce ku kvalitám. zmeny v predpokladaných vlastnostiach polymérov. Pomocou teórie grafov a princípov umelej inteligencie bol vyvinutý softvér pre systémy vyhľadávania informácií v chémii, ako aj automatizované systémy na identifikáciu molekulárnych štruktúr a racionálne plánovanie organickej syntézy. Pre praktickú realizáciu na počítači operácií výberu racionálnych spôsobov chemických látok. transformácie založené na retrosyntetickom a syntonickom princípe využívajú na hľadanie riešení viacúrovňové rozvetvené grafy, ktorých vrcholy zodpovedajú molekulovým grafom reaktantov a produktov a oblúky predstavujú transformácie.

Na riešenie viacrozmerných problémov analýzy a optimalizácie chemicko-technologických systémov (CTS) sa používajú nasledujúce chemicko-technologické grafy: tok, informačný tok, signál a graf spoľahlivosti. Na štúdium chem. fyzika porúch v systémoch pozostávajúcich z veľkého počtu častíc, využívajú tzv. Feynmanove diagramy sú grafy, ktorých vrcholy zodpovedajú elementárnym interakciám fyzikálnych častíc, hrán ich dráh po zrážkach. Tieto grafy umožňujú najmä skúmať mechanizmy oscilačných reakcií a určiť stabilitu reakčných systémov. vrcholy grafov zodpovedajú zariadeniam, v ktorých sa menia tepelné náklady fyzických tokov, a navyše zdrojom a záchytom tepelnej energie systému; oblúky zodpovedajú fyzikálnym a fiktívnym (fyz.-chemická premena energie v prístrojoch) tepelným tokom a hmotnosti oblúkov sa rovnajú entalpiám tokov. Materiálové a tepelné grafy slúžia na zostavovanie programov pre automatizovaný vývoj algoritmov na riešenie sústav rovníc materiálových a tepelných bilancií komplexných CTS. Grafy toku informácií zobrazujú logicko-informačnú štruktúru sústav rovníc mat. modely XTS; sa používajú na vývoj optimálnych algoritmov na výpočet týchto systémov. Bipartitný informačný graf je neorientovaný alebo orientovaný graf, ktorého vrcholy zodpovedajú resp. rovnice fl -f6 a premenné q1 - V a vetvy odrážajú ich vzťah. Informačný graf - digraf zobrazujúci poradie riešenia rovníc; vrcholy grafu zodpovedajú týmto rovniciam, zdrojom a prijímačom informácie XTS a vetvám informácií. premenné. Signálové grafy zodpovedajú lineárnym sústavám rovníc matematických modelov chemicko-technologických procesov a systémov. Grafy spoľahlivosti sa používajú na výpočet rôznych ukazovateľov spoľahlivosti X.

Referencie:

1. Berzh K., T. g. a jeho aplikácia, preložené z francúzštiny, M., 1962;

2. Kemeny J., Snell J., Thompson J., Úvod do konečnej matematiky, prel. z angličtiny, 2. vydanie, M., 1963;

3.Ope O., Grafy a ich aplikácia, prel. z angličtiny, M., 1965;

4. O. V. Belykh, E. V. Belyaev, Možnosti využitia T. g. v sociológii, in: Človek a spoločnosť, roč. 1, [L.], 1966;

5. Kvantitatívne metódy v sociologickom výskume, M., 1966; Beljajev E. V., Problémy sociologického merania, "VF", 1967, č. 7; Bavelas. Komunikačné vzorce v skupinách zameraných na úlohy, v knihe. Lerner, D., Lasswell H., Politické vedy, Stanford, 1951;

6. Kemeny J. G., Snell J., Matematické modely v sociálnych vedách, N. Y., 1962; Filament C., Applications of graph theory to group structure, N. Y., 1963; Oeser Ο. A., Hararu F., Štruktúry rolí a opis z hľadiska teórie grafov, v Viddle B., Thomas E. J., Teória rolí: koncepty a výskum, N. Y., 1966. E. Belyaev. Leningrad.

Stránka 8, ako anorganická, ... vydatá za dobrodruha Právo >> Historické postavy

Z hlavného úlohy teórie opatrenia a ergodic teórie(v teórie klesajúci ... v oblasti fyziky, chémia, fyziológia alebo medicína, ... Maximálny prietok Nech je graf(s orientovanými okrajmi), ... na dlhú dobu nevyriešené. Elipsoidná metóda má...

OBECNÝ SAMOSTATNÝ VŠEOBECNÝ ŠKOLSKÝ ÚSTAV STREDNÁ ŠKOLA № 2

Pripravené

Legkokonets Vladislav, 10A študent

Praktické využitie Teórie grafov

Dozorca

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

st.Bryukhovetskaya

2011

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

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

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

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

4.1 Známe úlohy………………………………………………………………...8

4.2 Niektoré zaujímavé úlohy……………………………………….………..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í………….……………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………….

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

Úvod

Teória grafov, ktorá sa zrodila pri riešení hádaniek a zábavných hier, sa teraz stala jednoduchou, prístupnou a mocný nástroj riešenie problémov týkajúcich sa širokého spektra problémov. Grafy sú doslova všadeprítomné. Vo forme grafov sa dajú napríklad interpretovať cestné diagramy a elektrické obvody, geografické mapy a molekuly chemických zlúčenín, spojenia 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. Je to spôsobené 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, blokové schémy programy, v ekonómii a štatistike, chémii a biológii, v teórii plánovania. Takže relevantnosť Téma je spôsobená na jednej strane popularitou grafov a súvisiacich výskumných metód a na druhej strane nevyvinutým uceleným systémom ich implementácie.

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

cieľ výskum bol pomocou grafov naučiť sa 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 ľudského života.

Ciele výskumu:

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

2. Preverte efektivitu grafovej metódy 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ť rodokmeň svojej rodiny? A 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 destinácie do viacerých sídiel. Každý študent čelil logickým transfúznym úlohám. 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 vzniku teórie grafov

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

„Raz som dostal problém s ostrovom, ktorý sa nachádza v meste Koenigsberg a je obklopený riekou, cez ktorú je prehodených sedem mostov.

[Príloha Obr. 1] Otázkou je, či ich niekto môže obchádzať nepretržite, pričom cez 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, hoci banálna, sa mi však zdala hodná pozornosti, pretože na jej riešenie nestačí ani geometria, ani algebra, ani kombinatorické umenie. Po dlhom premýšľaní som našiel ľahké pravidlo, založené na úplne presvedčivom dôkaze, pomocou ktorého sa vo všetkých problémoch tohto druhu dá okamžite určiť, či sa takéto kolo dá urobiť cez ľubovoľný počet a ľubovoľne umiestnených mostov alebo nie. Mosty Königsberg sú umiestnené tak, aby ich bolo možné znázorniť na nasledujúcom obrázku [Príloha Obr. 2], kde A označuje ostrov a B , C a D sú č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:

„Zdá sa, že toto riešenie svojou povahou nemá veľa spoločného s matematikou a nie je mi jasné, prečo by sa toto riešenie malo očakávať skôr od matematika než od akejkoľvek inej osoby, pretože toto riešenie je podporované iba rozumom a Na nájdenie tohto riešenia nie je potrebné zapájať žiadne zákony matematiky. Neviem teda, ako sa ukázalo, že otázky, ktoré majú s matematikou veľmi málo spoločného, budú s väčšou pravdepodobnosťou riešené matematikmi ako inými."

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

"Otázkou je určiť, či je možné obísť všetkých týchto sedem mostov, pričom 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 úsekov sú oddelené vodou - také , ktoré nemajú žiadny iný prechod z jedného do druhého, s výnimkou mosta. V tomto príklade sú štyri takéto úseky - A, B, C, D. Ďalej je potrebné rozlíšiť, či počet mostov vedúcich do týchto jednotlivých úsekov je párne alebo nepárne. Takže v našom prípade vedie do úseku A päť mostov a na zvyšok tri mosty, t.j. počet mostov vedúcich k jednotlivým úsekom je nepárny a tento už stačí na to, aby Vyriešte problém. Keď sa to zistí, použijeme nasledujúce pravidlo: ak by bol počet mostov vedúcich ku každému jednotlivému úseku párny, potom by bola možná obchádzka a zároveň by bolo možné začať túto obchádzku z ktorejkoľvek sekcie by bolo nepárne, pretože iba jeden by bol n ak to nemôže byť párne, tak aj vtedy by sa prechod mohol uskutočniť, ako je predpísané, ale určite treba brať len začiatok obchádzky z jedného z tých dvoch úsekov, do ktorých vedie nepárny počet mostov. Ak by napokon existovalo viac ako dva úseky, ku ktorým vedie nepárny počet mostov, potom je takýto pohyb vo všeobecnosti nemožný ... ak by sa tu dali uviesť iné, závažnejšie problémy, táto metóda by mohla byť ešte užitočnejšia a nemala by byť zanedbaný“.

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é rigorózne 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 nazývaných vrcholy grafu a párovo spájajúcich niektoré z týchto vrcholov čiar, nazývaných 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 budúcnosti budeme vrcholy grafu označovať 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 nula - počítať .

Zápis: O "– graf s vrcholmi a bez hrán

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 možno znázorniť ako n-uholník, v ktorom sú nakreslené všetky uhlopriečky

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

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

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

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

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

Pojmy rovinný graf a plochy grafu sa používajú pri riešení úloh na „správne“ vyfarbenie rôznych máp.

Definícia 10. Cesta z 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, ktorej začiatočný a koncový bod sú rovnaké.

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

Definícia 13. dlhá cesta , položené na slučke , je počet hrán tejto cesty.

Definícia 14. Dva vrcholy A a B v grafe sa nazývajú spojené (nespojené), ak v nich 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 stromu 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. Neprepojený graf pozostávajúci výlučne zo stromov sa nazýva les.

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

Zvážili sme teda hlavné 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 výzvy

Problém obchodného cestujúceho

Problém obchodného cestujúceho je jedným zo známych problémov v teórii kombinatoriky. Bol postavený v roku 1934 a najlepší matematici si na ňom vylámali zuby.

Vyhlásenie o probléme je nasledovné.
Cestujúci obchodník (cestujú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 prejsť mestami, aby uzavretá cesta (prehliadka) cestujúceho obchodníka bola č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ť draho zaplatiť.
Zoberme si napríklad sieť na obrázku [aplikácia obr. 3] predstavujúci úzky kosoštvorec. Nechajte obchodníka začať od mesta 1. „Prejsť do najbližšie mesto“ odvezie ho do mesta 2, potom 3, potom 4; na poslednom kroku budete musieť zaplatiť za chamtivosť a vrátiť sa pozdĺž dlhej uhlopriečky kosoštvorca. Výsledkom nie je najkratšia, ale najdlhšia túra.

Problém Königsbergských mostov.

Úloha je formulovaná nasledovne.
Mesto Königsberg sa nachádza na brehoch rieky Pregel a dvoch ostrovov. Rôzne časti mesta spájalo sedem mostov. V nedeľu mešťania podnikali prechádzky po meste. Otázka: Je možné urobiť prechádzku tak, že keď odídete z domu, vrátite sa a 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 schéme mostíka [príloha obr.2].

Na zodpovedanie otázky problému stačí zistiť, či je graf Euler. (Aspoň jeden vrchol musí mať párny počet mostíkov). Prechádzať sa po meste je nemožné raz prejsť všetky mosty a vrátiť sa späť.

Niekoľko zaujímavých výziev

1. "Trasy".

Úloha 1

Ako si pamätáte, lovec mŕtve dušeČičikov raz navštívil slávnych vlastníkov pôdy. Navštívil ich v tomto poradí: Manilov, Korobochka, Nozdrev, Sobakevič, Pljuškin, Tentetnikov, generál Betriščev, Petuch, Konstanzholgo, plukovník Koshkarev. Bol nájdený diagram, na ktorom Chichikov načrtol relatívnu polohu panstiev a vidiecke cesty ich spájaním. Určte, ktorá usadlosť patrí komu, ak Čičikov neprešiel niektorou z ciest viackrát [príloha obr.4].

rozhodnutie:

Podľa automapy je vidieť, že Čičikov začal svoju púť s usadlosťou E a skončil s usadlosťou O. Všimli sme si, že k statkom B a C vedú len dve cesty, takže Čičikov musel jazdiť po týchto cestách. Označme ich tučnými čiarami. Úseky trasy prechádzajúcej cez A sú určené: AC a AB. Čičikov necestoval po cestách AE, AK a AM. Preškrtnime ich. Označme hrubou čiarou ED ; prečiarknite DK . Prečiarknite MO a MN; označte hrubou čiarou MF ; prečiarknuť FO ; hrubou čiarou označíme FH , NK a KO. Nájdime jedinú možnú cestu za daných podmienok. A dostaneme: panstvo E - patrí Manilovovi, D - Korobochka, C - Nozdrev, A - Sobakevič, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [aplikácia obr. 5].

Úloha 2

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

Môžete sa pohybovať iba v smere šípok. Každý bod nie je možné navštíviť viac ako 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.

rozhodnutie:

Postupne „stratifikujte“ schému do stromu, začínajúc od vrcholu 1 [aplikácia obr. 7]. Zoberme si strom. číslo možné spôsoby zásahov 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"

Úloha 1

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

a) celkovo bol odoslaný 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: Účastníci festivalu nech sú A 1 , A 2 , A 3 . . . , A n sú vrcholy grafu a hrany spájajú dvojice vrcholov reprezentujúcich chlapcov, ktorí si vymenili obálky [Príloha Obr. 8]

rozhodnutie:

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 = krok. Krok 1 +. A 2 + + . . . + krok. A n -1 + krok. A n , N =2p , kde p je počet hrán grafu, t.j. N je párne. Preto bol odoslaný párny počet obálok;

b) v rovnosti N = krok. Krok 1 +. A 2 + + . . . + krok. A n -1 + krok. 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. A to znamená, že počet účastníkov, ktorí si vymenili obálky nepárny počet krát, je párny.

Úloha 2

Raz sa Andrei, Boris, Volodya, Dasha a Galya dohodli, že pôjdu večer do kina. Na výbere kina a sedenia sa rozhodli dohodnúť telefonicky. Rozhodlo sa tiež, že ak nebude možné niekomu zatelefonovať, výlet do kina sa ruší. Večer sa v kine nezišli všetci, a preto návšteva kina padla. Na druhý deň začali zisťovať, kto komu volal. Ukázalo sa, že Andrey volal Boris a Voloďa, Voloďa volala Boris a Dáša, Boris volal Andrey a Dáša, Dáša volala Andrey a Voloďa a Galya volala Andrej, Voloďa a Boris. Kto sa nemohol dovolať a preto neprišiel na stretnutie?

rozhodnutie:

Nakreslime päť bodov a označme ich písmenami A, B, C, D, E. Toto sú prvé písmená mien. Spojme tie bodky, ktoré zodpovedajú menám chlapcov, ktorí si navzájom volali.

[aplikácia obr. 9]

Z obrázku je vidieť, ž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 dovolať (body D a D nie sú spojené segmentom) a preto v súlade s dohodou neprišli do kina.

Využitie 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 odvetví, 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 táto štúdia.

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, automatizácii. Mnohé matematické fakty je vhodné 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í. AT nedávne časy Teória grafov nachádza stále viac aplikácií v aplikovanej problematike. Objavila sa dokonca aj počítačová chémia – pomerne 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, ktoré zobrazujú štruktúru molekúl [aplikácia obr. 10]. Vrcholy a hrany týchto grafov zodpovedajú zodpovedajúcim atómom a chemické väzby medzi nimi.

Molekulové grafy a stromy: [aplikácia obr. 10] a, b - multigrafy resp. etylén a formaldehyd; in-mol. izoméry pentánu (stromy 4, 5 sú izomorfné so stromom 2).

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

Proteínové siete

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

Hierarchický systémový graf nazývaný strom. Výrazná vlastnosť stromu je, že medzi ľubovoľnými dvoma jeho vrcholmi je len jedna cesta. Strom neobsahuje cykly a 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 patrí do jednej triedy 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 prezentovaný vo forme rodokmeňa, ktorý je tiež „stromom“ v zmysle teórie grafov.

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

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

Riešenie problémov

1. Transportná úloha. Nech je v meste Krasnodar základňa so surovinami, ktoré je potrebné vysadiť v mestách Krymsk, Temryuk, Slavyansk-on-Kuban a Timashevsk v jednom chode, pričom minúť čo najmenej času a paliva a vrátiť sa späť do Krasnodaru.

rozhodnutie:

Najprv si vytvoríme graf všetkých možných trás. [aplikácia 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, strom [aplikácia 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í, ale potrebujeme len najkratšie cesty. Zo všetkých riešení sú spokojné len dve, ide o 350 km.

Podobne je to možné a myslím si, že je potrebné počítať skutočnú prepravu z jednej lokalite ostatným.

Logická úloha pre transfúziu. Vo vedre je 8 litrov vody a dva hrnce s objemom 5 a 3 litre. je potrebné naliať 4 litre vody do päťlitrového hrnca a nechať 4 litre vo vedre, t. j. naliať vodu rovnomerne do vedra a veľkého hrnca.

rozhodnutie:

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

Takže, aby ste sa naučili riešiť problémy, musíte pochopiť, čo sú, ako sú usporiadané, z ktorých základné časti pozostávajú z toho, aké nástroje sa používajú na riešenie problémov.

Pri riešení praktických úloh pomocou teórie grafov sa ukázalo, že na 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ý spočíva v geometrickom znázornení grafov a 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 grafu. .

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

Bol som presvedčený, že grafy sú široko používané v ekonomike, manažmente a technike. V programovaní sa používa aj teória grafov, o ktorej sa v tomto článku nehovorí, ale myslím si, že je to len otázka času.

V tejto vedeckej práci sa uvažuje o matematických grafoch, ich oblastiach použitia, pomocou grafov sa riešia viaceré problémy. Znalosť základov teórie grafov je potrebná v rôznych oblastiach súvisiacich s riadením výroby, podnikaním (napríklad diagram stavebnej siete, harmonogramy doručovania pošty). Okrem toho som si pri práci na vedeckej práci osvojil prácu na počítači v textovom editore WORD. Teda úlohy vedecká práca dokončené.

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.

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

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

Zykov A.A. Teória konečných grafov. -Novosibirsk: Nauka, 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. "Mir", 1972 (kapitola 35);

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

Dodatok

Ryža. 6

Ryža. 7

Ryža. osem

aplikácie

Dodatok

Ryža. štrnásť

aplikácie

Dodatok

Navyše, posledných 12 rokov svojho života bol Euler vážne chorý, slepý a napriek tomu ťažké ochorenie pokračovali v práci a tvorení. Štatistické výpočty ukazujú, že Euler urobil v priemere jeden objav za týždeň. Je ťažké nájsť matematický problém, ktorý sa v Eulerových dielach nedotkol. Všetci matematici nasledujúcich generácií študovali s Eulerom tak či onak a nie nadarmo známy francúzsky vedec P.S. Laplace povedal: "Prečítaj si Eulera, je učiteľom nás všetkých." Lagrange hovorí: "Ak naozaj milujete matematiku, prečítajte si Eulera; expozícia jeho diel sa vyznačuje úžasnou jasnosťou a presnosťou." Elegancia výpočtov je ním skutočne dovedená na najvyšší stupeň. Condorcet zakončil svoj prejav na akadémii na pamiatku Eulera nasledujúcimi slovami: "Tak, Euler prestal žiť a počítať!" Žiť s cieľom počítať - aké nudné sa to zdá zvonku! Je zvykom predstaviť si matematiku suchú a hluchú ku všetkému svetskému, k tomu, čo zaujíma obyčajných ľudí. S menom Euler je problém troch domov a troch studní.

TEÓRIA GRAFOV

1) Formalizácia a konštrukcia všeobecného štrukturálneho modelu sociálneho objektu na rôznych úrovniach jeho zložitosti. Napríklad organizačné schémy, sociogramy, porovnanie systémov príbuzenstva v rôznych spoločnostiach, analýza štruktúry rolí skupín atď. Môžeme predpokladať, že štruktúra rolí zahŕňa tri zložky: osoby, pozície (v zjednodušenej verzii - pozície) a úlohy vykonávané na tejto pozícii. Každý komponent môže byť reprezentovaný ako graf:

Je možné skombinovať všetky tri grafy pre všetky pozície, alebo len pre jeden, a vo výsledku tak získame jasnú predstavu o špecifickej štruktúre c.l. túto rolu. Takže pre rolu pozície P5 máme graf (obr.). Votkanie neformálnych vzťahov do zadanej formálnej štruktúry výrazne skomplikuje graf, ale bude presnejšou kópiou reality.

2) Analýza získaného modelu, výber štruktúrnych jednotiek (subsystémov) v ňom a štúdium ich vzťahov. Týmto spôsobom možno oddeliť napríklad podsystémy vo veľkých organizáciách.

a) množstvá. posúdenie váhy (stavu) jednotlivca v hierarchickej organizácii. Jednou z možných možností na určenie stavu je vzorec:

hmotnosť a=1 2+2 7+3 4=28; 6=1 3+2 3=9 atď.

Ako pre teóriu grafov, tak aj pre akýkoľvek matematický aparát, platí tvrdenie, že základné princípy riešenia problému stanovuje obsahová teória (v tomto prípade sociológia).

Úloha : Traja susedia sa delia o tri studne. Je možné nakresliť nepretínajúce sa cesty od každého domu ku každej studni. Cestičky nemôžu prechádzať cez studne a domy (obr. 1).

Ryža. 1. K problematike domov a studní.

V – P + G = 1, (*)

kde B je celkový počet vrcholov, P je celkový počet hrán, G je počet polygónov (ploch).

Dôkaz. Dokážme, že rovnosť sa nemení, ak nakreslíme uhlopriečku v niektorom mnohouholníku daného oddielu (obr. 2, a).

Po nakreslení takejto uhlopriečky bude mať nový oddiel B vrcholov, hrán P + 1 a počet polygónov sa zvýši o jeden. Preto máme

B - (P + 1) + (G + 1) \u003d B - P + G.

Pomocou tejto vlastnosti nakreslíme uhlopriečky rozdeľujúce prichádzajúce mnohouholníky na trojuholníky a pre výsledné rozdelenie ukážeme, že vzťah je splniteľný.

Aby sme to dosiahli, dôsledne odstránime vonkajšie okraje, čím znížime počet trojuholníkov. V tomto prípade sú možné dva prípady:

na odstránenie trojuholníka ABC je potrebné odstrániť dve hrany, v našom prípade AB a BC;

na odstránenie trojuholníka MKN je potrebné odstrániť jeden okraj, v našom prípade MN.

V oboch prípadoch sa rovnosť nezmení. Napríklad v prvom prípade po odstránení trojuholníka bude graf pozostávať z vrcholov B-1, hrán P-2 a polygónu G-1:

(B - 1) - (P + 2) + (G -1) \u003d B - P + G.

Odstránenie jedného trojuholníka teda nezmení rovnosť.

Pokračujúc v tomto procese odstraňovania trojuholníkov, nakoniec dospejeme k oddielu pozostávajúcom z jedného trojuholníka. Pre takéto rozdelenie B = 3, P = 3, Γ = 1, a preto

To znamená, že rovnosť platí aj pre pôvodné rozdelenie, čím nakoniec dostaneme, že vzťah platí pre dané rozdelenie mnohouholníka.

Teraz pristúpime k riešeniu problému troch domov a troch studní.

Tieto hrany tvoria v rovine mnohouholník rozdelený na menšie mnohouholníky. Preto pre toto rozdelenie musí byť splnený Eulerov vzťah B - P + G = 1.

K uvažovaným plochám pridajme ešte jednu plochu - vonkajšiu časť roviny vzhľadom na mnohouholník. Potom Eulerov vzťah bude mať tvar B - P + G = 2, pričom B = 6 a P = 9.

Štúdium vzťahu medzi vlastnosťami látok a ich štruktúrou je jednou z hlavných úloh chémie. Veľký prínos k jeho riešeniu priniesla štruktúrna teória organických zlúčenín, medzi zakladateľov ktorej patrí veľký ruský chemik Alexander Michajlovič Butlerov (1828-1886). Bol to on, kto prvý zistil, že vlastnosti látky závisia nielen od jej zloženia (molekulárneho vzorca), ale aj od poradia, v ktorom sú atómy v molekule prepojené. Tento poriadok sa nazýval „chemická štruktúra“. Butlerov predpovedal, že kompozícia C 4 H 10 môže zodpovedať dvom látkam, ktoré majú odlišnú štruktúru - butánu a izobutánu, a potvrdili to syntézou poslednej menovanej látky.

Myšlienka, že poradie, v ktorom sú atómy spojené, má kľúčový význam pre vlastnosti hmoty, sa ukázala ako veľmi plodná. Je založená na znázornení molekúl pomocou grafov, v ktorých atómy zohrávajú úlohu vrcholov a chemické väzby medzi nimi sú hrany spájajúce vrcholy. V grafickom znázornení sa dĺžky väzieb a uhly medzi nimi ignorujú. Molekuly C opísané vyššie 4 H 10 sú zobrazené v nasledujúcich stĺpcoch:

Atómy vodíka nie sú v takýchto grafoch uvedené, pretože ich umiestnenie možno jednoznačne určiť zo štruktúry uhlíkovej kostry. Pripomeňme, že uhlík v organických zlúčeninách je štvormocný, a preto v príslušných grafoch nemôžu od každého vrcholu odchádzať viac ako štyri hrany.

Grafy sú matematické objekty, preto ich možno charakterizovať pomocou čísel. Z toho vzišiel nápad vyjadriť štruktúru molekúl číslami, ktoré sú spojené so štruktúrou molekulových grafov. Tieto čísla sa v chémii nazývajú „topologické indexy“. Výpočtom nejakého topologického indexu pre veľký počet molekúl je možné vytvoriť vzťah medzi jeho hodnotami a vlastnosťami látok a potom použiť tento vzťah na predpovedanie vlastností nových, ešte nesyntetizovaných látok. K dnešnému dňu chemici a matematici navrhli stovky rôznych indexov charakterizujúcich určité vlastnosti molekúl.

Metódy výpočtu topologických indexov

Metódy na výpočet topologických indexov môžu byť veľmi rôznorodé, ale všetky musia spĺňať celkom prirodzené požiadavky:

1) každá molekula má svoj vlastný individuálny index;

2) Molekuly s podobnými vlastnosťami majú podobné indexy.

Pozrime sa, ako sa táto myšlienka realizuje na príklade nasýtených uhľovodíkov - alkánov. Kľúčom ku konštrukcii mnohých indexov je koncept „matice vzdialenosti“ D. Toto je názov matice, ktorej prvky znázorňujú počet hrán oddeľujúcich zodpovedajúce vrcholy molekulového grafu. Zostrojme túto matricu pre tri izomérne uhľovodíky zloženia C 5 H 12 . Aby sme to dosiahli, nakreslíme ich molekulárne grafy a prečíslujeme vrcholy (v ľubovoľnom poradí):

Diagonálne prvky matice vzdialenosti pre uhľovodíky sú rovné 0. V prvom stĺpci je vrchol 1 spojený s vrcholom 2 jednou hranou, takže prvok matice d 12 = 1. Podobne d 13 = 2, d 14 = 3, d 15 = 4. Prvý riadok v matici vzdialenosti normálneho pentánu je: (0 1 2 3 4). Kompletné matice vzdialeností pre tri grafy:

molekulová chémia topologický index

Vzdialenosť medzi vrcholmi nezávisí od poradia ich enumerácie, takže matice vzdialenosti sú symetrické vzhľadom na uhlopriečku.

Prvý topologický index odrážajúci štruktúru molekulárneho grafu (G) navrhol v roku 1947 Wiener. Je definovaný ako súčet diagonálne prvky matica vzdialenosti plus polovičný súčet jej mimodiagonálnych prvkov:

(1)

Pre vyššie uvedené grafy zodpovedajúce pentánom C 5 H 12 Wienerov index nadobúda hodnoty 20, 18 a 16. Dá sa predpokladať, že popisuje stupeň rozvetvenia uhľovodíkov: najväčšie hodnoty zodpovedajú najmenej rozvetveným uhľovodíkom. S nárastom dĺžky uhlíkového skeletu sa Wienerov index zvyšuje, keďže v matici vzdialenosti je viac prvkov. Štatistická analýza na príklade niekoľkých stoviek uhľovodíkov ukázala, že Wienerov index koreluje s niektorými fyzikálnymi vlastnosťami alkánov: body varu, výparné teplo, molárny objem.

Iný typ indexu nie je založený na vzdialenostiach medzi vrcholmi, ale na počte najbližších susedov pre každý vrchol. Ako príklad si vypočítajme Randic index, ktorý je definovaný takto:

(2)

kde vi- stupeň i-tého vrcholu, teda počet hrán z neho vyčnievajúcich. Pre vyššie uvedené grafy je Randic index:

(3)

(4)

(5)

Tento index tiež klesá s rastúcim stupňom rozvetvenia uhlíkovej kostry a možno ho použiť na popis fyzikálne vlastnosti alkány.

Alkány sú chemicky najnudnejším typom organickej molekuly, pretože neobsahujú žiadne „vlastnosti“ – dvojité a trojité väzby alebo atómy prvkov iných ako vodík a uhlík (takéto prvky sa nazývajú heteroatómy). Zavedenie heteroatómov do zloženia molekuly môže radikálne zmeniť vlastnosti látky. Pridaním iba jedného atómu kyslíka sa teda premení skôr inertný plynný etán C 2 H 6 na tekutý etanol C 2 H 5 OH, ktorý vykazuje pomerne vysokú chemickú a biologickú aktivitu.

V dôsledku toho sa v topologických indexoch molekúl, ktoré sú zložitejšie ako alkány, musí brať do úvahy prítomnosť viacnásobných väzieb a heteroatómov. Robí sa to tak, že vrcholom a hranám grafov sa priraďujú určité číselné koeficienty – „váhy“. Napríklad v matici vzdialenosti môžu byť diagonálne prvky definované z hľadiska jadrového náboja Zi(pripomeňme si, že pre uhlík Z = 6):

(6)

Mimodiagonálne prvky sú určené súčtom cez hrany a každá hrana spája atómy s nábojmi Zia Zj, je priradená váha

(7)

kde b sa rovná poradiu väzieb medzi atómami (1 pre jednoduchú väzbu, 2 pre dvojitú väzbu, 3 pre trojitú väzbu). Pre obyčajné jednoduché väzby uhlík-uhlík je k = 1. Porovnajte Wienerove indexy C propánu 3 H 8 a tri látky obsahujúce kyslík podobného zloženia: propylalkohol C 3 H 8 O, jeho izomérny izopropylalkohol C 3 H 8 O a acetón C 3 H 6 Oh

Na tento účel vypočítame matice vzdialenosti podľa uvedených pravidiel. V molekulových grafoch uvádzame všetky atómy okrem atómov vodíka 1) Propán

2) V molekule propylalkoholu je kyslík naviazaný na extrémny atóm uhlíka:

Pre jednoduchú väzbu C–O je váhový faktor 36/(68) = 0,75. Diagonálny prvok matrice zodpovedajúci kyslíku:

d 44 = 1 – 6/8 = 0.25.

Pre molekuly obsahujúce heteroatómy prestáva byť Wienerov index celým číslom. 3) V molekule izopropylalkoholu je kyslík viazaný na stredný atóm uhlíka:

4) V acetóne je poradie spojenia atómov rovnaké ako v izopropylalkohole, ale väzba medzi uhlíkom a kyslíkom je dvojitá:

Pre dvojitú väzbu C=O je váhový faktor 36/(268) = 0,375

Ako je možné vidieť, pridanie heteroatómu do štruktúry alkánov vedie k zvýšeniu Wienerovho indexu v dôsledku zväčšenia veľkosti matice vzdialenosti. Pridanie viacnásobných väzieb a zvýšenie stupňa rozvetvenia molekuly tento index znižuje. Tieto pravidlá platia aj pre zložitejšie molekuly. Spočiatku boli topologické indexy vyvinuté len na účely predpovedania fyzikálno-chemických vlastností látok. Neskôr sa však začali využívať na riešenie iných problémov. Uvažujme o niektorých z nich. Jedna z aplikácií topologických indexov súvisí s klasifikáciou organických zlúčenín a vytváraním organických databáz. Problémom je nájsť taký index, ktorý by charakterizoval chemickú štruktúru jedna k jednej a z ktorého by sa táto štruktúra dala obnoviť. Požadovaný index musí mať dobrú rozlišovaciu schopnosť, to znamená rozlišovať medzi sebou aj molekuly, ktoré sú si svojou štruktúrou blízke. Táto úloha je náročná, keďže už je známych viac ako 20 miliónov organických štruktúr. Jeho riešenie sa zrejme nájde ako výsledok použitia kompozitných topologických indexov.

1 V priebehu posledných desaťročí sa v teoretickej chémii rozšírili koncepty topológie a teórie grafov. Sú užitočné pri hľadaní kvantitatívnych vzťahov "štruktúra-vlastnosť" a "štruktúra-aktivita", ako aj pri riešení grafo-teoretických a kombinatoricko-algebraických problémov, ktoré vznikajú pri zbere, ukladaní a spracovávaní informácií o štruktúre a vlastnostiach. látok.

Grafy slúžia predovšetkým ako prostriedok na znázornenie molekúl. V topologickom popise molekuly je znázornená ako molekulový graf (MG), kde vrcholy zodpovedajú atómom a okraje zodpovedajú chemickým väzbám (graf-teoretický model molekuly). Zvyčajne sú v tomto znázornení uvažované iba skeletové atómy, napríklad uhľovodíky s "vymazanými" atómami vodíka.

Valence chemické prvky ukladá určité obmedzenia na stupne vrcholov. Alkánové stromy (spojené grafy, ktoré nemajú cykly) majú vrcholové stupne (r), ktoré nemôžu presiahnuť štyri (r = 1, 2, 3, 4).

Grafy je možné špecifikovať v maticovej forme, čo je výhodné pri práci s nimi na počítači.

Matica susednosti vrcholov jednoduchého grafu je štvorcová matica A = [aσχ] s prvkami aσχ = 1, ak sú vrcholy σ a χ spojené hranou a σχ = 0 v opačnom prípade. Matica vzdialenosti je štvorcová matica D = s prvkami dσχ definovaným ako minimálny počet hrán (najkratšia vzdialenosť) medzi vrcholmi σ a χ. Niekedy sa používajú aj matice susednosti a okrajovej vzdialenosti (A e a D e).

Typ matíc A a D (A e a D e) závisí od spôsobu číslovania vrcholov (alebo hrán), čo spôsobuje nepríjemnosti pri manipulácii s nimi. Na charakterizáciu grafu sa používajú grafové invarianty – topologické indexy (TI).

Počet ciest dĺžky jedna

pi = xcc 0 = m = n-1

Počet ciest dĺžky dva

Počet trojíc susedných hrán (so spoločným vrcholom)

Wienerovo číslo (W), definované ako polovičný súčet prvkov matice vzdialeností uvažovaného grafu:

atď.

Metodológia na štúdium vzťahu „štruktúra-vlastnosť“ prostredníctvom topologických indexov v grafovo-teoretickom prístupe zahŕňa nasledujúce kroky.

Výber predmetov štúdia (tréningová vzorka) a analýza stavu číselných údajov o vlastnosti P pre daný rozsah zlúčenín.

Výber TI s prihliadnutím na ich rozlišovaciu schopnosť, korelačnú schopnosť s vlastnosťami atď.

Štúdium grafických závislostí "Vlastnosť P - TI grafu molekuly", napríklad P na n - počet atómov skeletu, P na W - Wienerovo číslo atď.

Stanovenie funkčnej (analytickej) závislosti P = _DTI), napr.

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

P \u003d a (TI) 1 + b (TI) 2 + ... + n (TI) n + c

atď. Tu sú a, b, c niektoré parametre (nezamieňať s parametrami aditívnych obvodov), ktoré sa majú určiť.

Numerické výpočty Р, porovnanie vypočítaných hodnôt s experimentálnymi.

Predikcia vlastností zlúčenín, ktoré ešte neboli študované alebo dokonca získané (mimo tejto vzorky).

Topologické indexy sa používajú aj pri konštrukcii aditívnych výpočtov a prognostických schém. Môžu byť použité pri vývoji nových lieky, pri hodnotení karcinogénnej aktivity niektorých chemických látok, predpovedať relatívnu stabilitu nových (zatiaľ nesyntetizovaných) zlúčenín atď.

Malo by sa však pamätať na to, že výber TI je často náhodný; nemusia odrážať dôležité štrukturálne vlastnosti molekúl alebo duplicitné informácie (získané pomocou iných indexov) a výpočtové schémy nemusia mať pevný teoretický základ a je ťažké ich fyzikálno-chemicky interpretovať.

Personál oddelenia fyzikálna chémia TVGU už mnoho rokov vykonáva výpočtovú a teoretickú štúdiu o probléme „Vzťah medzi vlastnosťami látok a štruktúrou molekúl: matematické (počítačové) modelovanie“. Dôraz je kladený na cielené hľadanie nových štruktúr, algoritmov na riešenie množstva grafo-teoretických a kombinatorických problémov, ktoré vznikajú pri zbere a spracovaní informácií o štruktúre a vlastnostiach látok, vytváranie expertných informačných systémov a databáz. rozvoj kvantitatívnych metód výpočtu a prognózovania.

Vytvorili sme aditívne schémy a našli analytické závislosti formy P = Y(TI) pre množstvo organických a iných molekúl. Podľa získaných vzorcov boli vykonané numerické výpočty fyzikálno-chemických vlastností uvažovaných zlúčenín, s .

Bibliografia

Vinogradova M.G., Papulov Yu.G., Smoljakov V.M. Kvantitatívne korelácie „vlastnosti štruktúry“ alkánov. Schémy aditívneho výpočtu. Tver, 1999. 96 s.
Chemické aplikácie topológia a teória grafov / Ed. R. Kráľ. M.: Mir, 1987. 560 s.
Aplikácia teórie grafov v chémii / Ed. N.S. Zefirova a S.I. Kuchanovej. Novosibirsk: Nauka, 1988. 306 s.
Stankevich M.I., Stankevich I.V., Zefirov N.S. Topologické indexy v organickej chémii // Uspekhi khimii. 1988. V.57, č. 3, S.337-366.
Vinogradová M.G., Saltyková M.N. Graf-teoretický prístup pri štúdiu vzťahu medzi štruktúrou a vlastnosťami alkylsilánov.// Fundamental Research, 2009. č.1. s. 17-19.
Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Vzťah medzi štruktúrou a vlastnosťami alkylsilánov // Úspechy moderných prírodných vied, č. 1, 2010. S. 136-137.
Vinogradová M.G., Saltyková M.N., Efremová A.O. Korelácie "Štruktúra - vlastnosť" alkylsilánov: graf-teoretický prístup // Úspechy moderných prírodných vied, č. 3, 2010. S.141-142.

Bibliografický odkaz

Vinogradová M.G. TEÓRIA GRAFOV V CHÉMII // International Journal of Applied and Fundamental Research. - 2010. - č. 12. - S. 140-142;
URL: http://dev.applied-research.ru/ru/article/view?id=1031 (dátum prístupu: 17.12.2019). Dávame do pozornosti časopisy vydávané vydavateľstvom "Academy of Natural History"

Proteínové siete

Metódy výpočtu topologických indexov

Bibliografický odkaz