B - P + G = 1, (*)

kjer je B skupno število oglišč, P skupno število robov, G število poligonov (ploskev).

Dokaz. Dokažimo, da se enakost ne spremeni, če v nekem mnogokotniku dane particije narišemo diagonalo (slika 2, a).

a) b)

Slika 2

Po risanju takšne diagonale bo imela nova particija B oglišč, P+1 robov, število poligonov pa se bo povečalo za enega. Zato imamo

B - (P + 1) + (G + 1) = B - P + G.

Z uporabo te lastnosti narišemo diagonale, ki razdelijo prihajajoče mnogokotnike na trikotnike, in za nastalo particijo pokažemo izvedljivost relacije.

Da bi to naredili, bomo zaporedno odstranili zunanje robove in zmanjšali število trikotnikov. V tem primeru sta možna dva primera:

če želite odstraniti trikotnik ABC, morate odstraniti dva robova, v našem primeru AB in BC;

Če želite odstraniti trikotnik MKN, morate odstraniti en rob, v našem primeru MN.

V obeh primerih se enakost ne bo spremenila. Na primer, v prvem primeru bo po odstranitvi trikotnika graf sestavljen iz oglišč B-1, robov P-2 in poligona G-1:

(B - 1) - (P + 2) + (G -1) = B - P + G.

Tako odstranitev enega trikotnika ne spremeni enakosti.

Če nadaljujemo s tem postopkom odstranjevanja trikotnikov, bomo na koncu prišli do particije, sestavljene iz enega samega trikotnika. Za takšno particijo je B = 3, P = 3, G = 1 in zato

B - P + G = 1.

To pomeni, da enakost velja tudi za prvotno razbitje, iz česar končno dobimo, da relacija velja za to razbitje mnogokotnika.

Upoštevajte, da Eulerjeva relacija ni odvisna od oblike mnogokotnikov. Poligone lahko deformiramo, povečamo, pomanjšamo ali celo ukrivimo stranice, če med stranicami ni vrzeli. Eulerjeva relacija se ne bo spremenila.

Nadaljujmo z reševanjem problema treh hiš in treh vodnjakov.

rešitev . Predpostavimo, da je to mogoče storiti. Hiše označimo s točkami D1, D2, D3, vodnjake pa s točkami K1, K2, K3 (slika 1). Vsako hišno točko povežemo z vsako vodnjaško točko. Dobimo devet robov, ki se ne sekajo v parih.

Ti robovi tvorijo mnogokotnik na ravnini, razdeljen na manjše mnogokotnike. Zato mora biti za to particijo izpolnjena Eulerjeva relacija B - P + G = 1.

Obravnavanim obrazom dodajmo še eno ploskev - zunanji del ravnine glede na poligon. Potem bo Eulerjeva relacija prevzela obliko B - P + G = 2, z B = 6 in P = 9.

Zato je G = 5. Vsaka od petih ploskev ima vsaj štiri robove, saj po pogojih problema nobena od poti ne sme neposredno povezovati dveh hiš ali dveh vodnjakov. Ker vsak rob leži na točno dveh ploskvah, mora biti število robov najmanj (5 4)/2 = 10, kar je v nasprotju s pogojem, da je njihovo število 9.

Nastalo protislovje kaže, da je odgovor na problem negativen - nemogoče je narisati poti, ki se ne križajo, od vsake hiše do vsake vasi

Teorija grafov v kemiji

Uporaba teorije grafov pri konstrukciji in analizi različnih razredov kemijskih in kemijsko-tehnoloških grafov, ki jih imenujemo tudi topologija, modeli, t.j. modeli, ki upoštevajo samo naravo povezav med vozlišči. Loki (robovi) in oglišča teh grafov odražajo kemijske in kemijsko-tehnološke pojme, pojave, procese ali objekte in s tem kvalitativne in kvantitativne odnose ali določene odnose med njimi.

Teoretični problemi. Kemijski grafi omogočajo napovedovanje kemijskih pretvorb, pojasnjujejo bistvo in sistematizirajo nekatere osnovne pojme kemije: zgradbo, konfiguracijo, potrditve, kvantno mehanske in statistično-mehanske interakcije molekul, izomerije itd. Kemijski grafi vključujejo molekularne, bipartitne in signalne grafe. enačb kinetične reakcije. Molekularni grafi, ki se uporabljajo v stereokemiji in strukturni topologiji, kemiji grozdov, polimerov itd., so neusmerjeni grafi, ki prikazujejo strukturo molekul. Oglišča in robovi teh grafov ustrezajo ustreznim atomom in kemičnim vezem med njimi.

V stereokemiji org. c-c najpogosteje uporabljena so molekularna drevesa - vpeta drevesa molekularnih grafov, ki vsebujejo samo vsa vozlišča, ki ustrezajo atomom, in ugotavljanje njihove izomorfnosti omogoča določanje molekulskih struktur in iskanje skupnega števila izomerov alkanov, alkeni in alkini. Molekularni grafi omogočajo zmanjšanje težav, povezanih s kodiranjem, nomenklaturo in strukturnimi značilnostmi (razvejanostjo, cikličnostjo itd.) molekul različnih spojin na analizo in primerjavo čisto matematičnih značilnosti in lastnosti molekularnih grafov in njihovih dreves ter njihove ustrezne matrike. Za ugotavljanje števila korelacij med strukturo molekul in fizikalno-kemijskimi (vključno s farmakološkimi) lastnostmi spojin je bilo razvitih več kot 20 tako imenovanih. Topološki indeksi molekul (Wiener, Balaban, Hosoya, Plata, Randic itd.), ki so določeni z uporabo matrik in numeričnih karakteristik molekularnih dreves. Na primer, Wienerjev indeks W = (m3 + m)/6, kjer je m število oglišč, ki ustrezajo atomom C, je v korelaciji z molekulskimi volumni in lomom, tvorbenimi entalpijami, viskoznostjo, površinsko napetostjo, kromatografskimi konstantami spojin, oktanom število ogljikovodikov in celo fiziol. aktivnost zdravil. Pomembna parametra molekularnih grafov, ki se uporabljajo za določanje tavtomernih oblik dane snovi in ​​njihove reaktivnosti ter pri razvrščanju aminokislin, nukleinskih kislin, ogljikovih hidratov in drugih kompleksnih naravnih spojin, sta povprečna in skupna (H) informacijska kapaciteta. Analiza molekularnih grafov polimerov, katerih oglišča ustrezajo monomernim enotam, robovi pa kemičnim vezem med njimi, omogoča razlago na primer učinkov izključenega volumna, ki vodijo do kvalitet. spremembe predvidenih lastnosti polimerov. Z uporabo teorije grafov in načel umetne inteligence je bila razvita programska oprema za sisteme za iskanje informacij v kemiji ter avtomatizirani sistemi za identifikacijo molekulskih struktur in racionalno načrtovanje organske sinteze. Za praktično izvedbo na računalniku operacij za izbiro racionalnih kemijskih poti. transformacije, ki temeljijo na retrosintetičnih in sintonskih principih, uporabljajo večnivojske razvejane iskalne grafe za možnosti rešitve, katerih oglišča ustrezajo molekularnim grafom reagentov in produktov, loki pa prikazujejo transformacije.

Za reševanje večdimenzionalnih problemov analize in optimizacije kemijsko tehnoloških sistemov (CTS) se uporabljajo naslednji kemijsko tehnološki grafi: tokovni, informacijski, signalni in zanesljivi grafi. Za študij kemije. Fizika motenj v sistemih, sestavljenih iz velikega števila delcev, uporablja t.i. Feynmanovi diagrami so grafi, katerih oglišča ustrezajo elementarnim interakcijam fizičnih delcev, robovi njihovih poti po trkih. Zlasti ti grafi omogočajo proučevanje mehanizmov oscilatornih reakcij in določanje stabilnosti reakcijskih sistemov. Grafi materialnega toka prikazujejo spremembe v porabi snovi v CTS. Grafi toplotnega toka prikazujejo toplotne bilance v CTS; oglišča grafov ustrezajo napravam, v katerih se spreminja poraba toplote fizičnih tokov, poleg tega pa virom in ponorom toplotne energije sistema; loki ustrezajo fizičnim in fiktivnim (fizikalno-kemijska pretvorba energije v napravah) toplotnim tokovom, uteži lokov pa so enake entalpijam tokov. Materialni in toplotni grafi se uporabljajo za sestavljanje programov za avtomatiziran razvoj algoritmov za reševanje sistemov enačb za materialne in toplotne bilance kompleksnih kemijskih sistemov. Grafi informacijskega toka prikazujejo logično informacijsko strukturo sistemov matematičnih enačb. modeli XTS; se uporabljajo za razvoj optimalnih algoritmov za izračun teh sistemov. Bipartitni informacijski graf je neusmerjen ali usmerjen graf, katerega vozlišča si ustrezajo. enačbe fl -f6 in spremenljivke q1 – V, veje pa odražajo njihov odnos. Informacijski graf – digraf, ki prikazuje vrstni red reševanja enačb; oglišča grafa ustrezajo tem enačbam, virom in sprejemnikom informacij XTS, veje pa informacijam. spremenljivke. Signalni grafi ustrezajo linearnim sistemom enačb matematičnih modelov kemijsko tehnoloških procesov in sistemov. Za izračun različnih kazalnikov zanesljivosti X se uporabljajo grafi zanesljivosti.

Uporabljena literatura:

1.Berge K., T. g. in njegova uporaba, prevod iz francoščine, M., 1962;

2. Kemeny J., Snell J., Thompson J., Uvod v končno matematiko, prev. iz angleščine, 2. izd., M., 1963;

3.Ope O., Grafi in njihova uporaba, trans. iz angleščine, M., 1965;

4. Belykh O.V., Belyaev E.V., Možnosti uporabe tehnologije v sociologiji, v: Človek in družba, vol. 1, [L.], 1966;

5. Kvantitativne metode v sociološkem raziskovanju, M., 1966; Belyaev E.V., Problemi socioloških meritev, "VF", 1967, št. 7; Bavelas. Komunikacijski vzorci v nalogah usmerjenih skupinah, v knjigi. Lerner D., Lass well H., Politične vede, Stanford, 1951;

OBČINSKI SAMOSTOJNI IZOBRAŽEVALNI ZAVOD SREDNJA ŠOLA ŠT. 2

Pripravljeno

Legkokonets Vladislav, učenec 10.A razreda

Praktična uporaba teorije grafov

Nadzornik

L.I. Noskova, učiteljica matematike

Art Bryukhovetskaya

2011

1. Uvod…………………………………………………………………………………….………….3

2. Zgodovina nastanka teorije grafov………………………………………….………..4

3. Osnovne definicije in izreki teorije grafov…………………………….………6

4. Težave, rešene z uporabo grafov……………………………..………………………..8

4.1 Znani problemi………………………………….………………………...8

4.2 Več zanimivih problemov…………………………………………………..9

5. Uporaba grafov na različnih področjih življenja ljudi………………………………...11

6. Reševanje težav………………………………………………………………………………………...12

7. Zaključek………………….…………………………………………………………….13

8. Seznam referenc………….………………………………………………………………14

9.Dodatek……………………………………………………………………………………………15

Uvod

Teorija grafov, rojena iz reševanja ugank in zabavnih iger, je zdaj postala preprosto, dostopno in zmogljivo orodje za reševanje vprašanj, povezanih s številnimi problemi. Grafi so dobesedno vseprisotni. V obliki grafov si lahko na primer razlagate cestne zemljevide in električne tokokroge, geografske karte in molekule kemičnih spojin, povezave med ljudmi in skupinami ljudi. V zadnjih štirih desetletjih je teorija grafov postala ena najhitreje razvijajočih se vej matematike. To poganjajo zahteve hitro rastočega področja uporabe. Uporablja se pri načrtovanju integriranih vezij in krmilnih vezij, pri preučevanju avtomatov, logičnih vezij, blokovnih diagramov programov, v ekonomiji in statistiki, kemiji in biologiji, v teoriji razporejanja. zato ustreznost Temo na eni strani določa priljubljenost grafov in z njimi povezanih raziskovalnih metod, na drugi strani pa nerazvit, celosten sistem za njeno izvajanje.

Reševanje mnogih življenjskih problemov zahteva dolga računanja, včasih pa tudi ta računanja ne prinesejo uspeha. To je tisto raziskovalni problem. Postavlja se vprašanje, ali je za njihovo rešitev mogoče najti preprosto, racionalno, kratko in elegantno rešitev. Ali je reševanje problemov lažje, če uporabljate grafe? To je določilo tema moje raziskave: “Praktična uporaba teorije grafov”

Namen Raziskava je bila namenjena uporabi grafov za učenje, kako hitro rešiti praktične probleme.

Raziskovalna hipoteza. Metoda grafov je zelo pomembna in se pogosto uporablja na različnih področjih znanosti in človekove dejavnosti.

Raziskovalni cilji:

1. Preučite literaturo in internetne vire o tej temi.

2. Preveri učinkovitost metode grafov pri reševanju praktičnih nalog.

3. Potegnite zaključek.

Praktični pomen študije je, da bodo rezultati nedvomno vzbudili zanimanje marsikoga. Ali še nihče od vas ni poskusil zgraditi svojega družinskega drevesa? Kako to narediti pravilno? Vodja transportnega podjetja mora verjetno rešiti problem donosnejše uporabe transporta pri prevozu blaga iz cilja v več naselij. Vsak šolar se je srečal z logičnimi težavami s transfuzijo. Izkazalo se je, da jih je mogoče enostavno rešiti z uporabo grafov.

Pri delu se uporabljajo naslednje metode: opazovanje, iskanje, selekcija, analiza.

Zgodovina teorije grafov

Za utemeljitelja teorije grafov velja matematik Leonhard Euler (1707-1783). Zgodovino te teorije je mogoče izslediti skozi korespondenco velikega znanstvenika. Tukaj je prevod latinskega besedila, ki je vzet iz Eulerjevega pisma italijanskemu matematiku in inženirju Marinoniju, poslanega iz Sankt Peterburga 13. marca 1736.

»Nekoč so mi zastavili problem o otoku v mestu Königsberg, ki ga obdaja reka s sedmimi mostovi čez njo.

[Dodatek Slika 1] Vprašanje je, ali jih lahko nekdo neprekinjeno obide in gre le enkrat čez vsak most. In potem sem bil obveščen, da tega še nikomur ni uspelo, a nihče ni dokazal, da je to nemogoče. To vprašanje, čeprav trivialno, se mi je vendarle zdelo vredno pozornosti, saj niti geometrija, niti algebra, niti kombinatorika ne zadostujejo za njegovo rešitev. Po dolgem premisleku sem našel enostavno pravilo, ki temelji na povsem prepričljivem dokazu, s pomočjo katerega je mogoče v vseh tovrstnih problemih takoj ugotoviti, ali je tak ovinek mogoče narediti skozi poljubno število in poljubno število mostov, ki se nahajajo ali ne. Koenigsberški mostovi so nameščeni tako, da jih je mogoče prikazati na naslednji sliki [Dodatek Slika 2], kjer A označuje otok, B, C in D pa dele celine, ločene drug od drugega z rečnimi rokavi

O metodi, ki jo je odkril za reševanje tovrstnih problemov, je Euler zapisal:

»Ta rešitev po svoji naravi očitno nima veliko skupnega z matematiko in ne razumem, zakaj bi to rešitev pričakovali od matematika in ne od katere koli druge osebe, saj je ta odločitev podprta samo z razmišljanjem in ni da bi našli to rešitev, obstajajo kakršni koli zakoni, ki so neločljivo povezani z matematiko. Torej, ne vem, kako se izkaže, da bodo vprašanja, ki imajo zelo malo opraviti z matematiko, bolj verjetno rešili matematiki kot drugi.«

Ali je torej mogoče königsberške mostove obiti tako, da se peljete le enkrat čez vsakega od teh mostov? Da bi našli odgovor, nadaljujmo Eulerjevo pismo Marinoniju:

"Vprašanje je ugotoviti, ali je mogoče obiti vseh teh sedem mostov in skozi vsakega le enkrat ali ne. Moje pravilo vodi do naslednje rešitve tega vprašanja. Najprej morate pogledati, koliko odsekov so ločeni z vodo - taki , ki nimajo drugega prehoda iz enega v drugega, razen skozi most. V tem primeru so štirje taki odseki - A, B, C, D. Nato morate razlikovati, ali je št število mostov, ki vodijo do teh posameznih odsekov, je sodo ali liho. Torej v našem primeru pet mostov vodi do odseka A, po trije mostovi pa vodijo do preostalih, tj. število mostov, ki vodijo do posameznih odsekov, je liho in samo to je. dovolj za rešitev problema. Ko je to ugotovljeno, uporabimo naslednje pravilo: če bi bilo število mostov, ki vodijo do vsakega posameznega odseka, bi bil omenjeni obvoz možen, hkrati pa bi bil mogoč. Če bi bili dve od teh številk lihi, potem bi tudi takrat prehod lahko končali, kot je predpisano, vendar je treba zagotovo vzeti samo začetek obvoza. enega od tistih dveh odsekov, do katerih vodi liho število mostov. Če bi končno obstajalo več kot dva odseka, do katerih vodi liho število mostov, potem je takšen premik na splošno nemogoč ... če bi lahko sem prinesli druge, resnejše težave, bi ta metoda lahko bila še bolj koristna in bi morala ne smemo zanemariti."

Osnovne definicije in izreki teorije grafov

Teorija grafov je matematična disciplina, ki je nastala s prizadevanji matematikov, zato njena predstavitev vključuje potrebne stroge definicije. Torej, nadaljujmo z organiziranim uvodom v osnovne koncepte te teorije.

Definicija 1. Graf je zbirka končnega števila točk, ki jih imenujemo oglišča grafa, in črt v paru, ki povezujejo nekatera od teh oglišč, imenovanih robovi ali loki grafa.

To definicijo lahko formuliramo drugače: graf je neprazna množica točk (vozlišč) in segmentov (robov), katerih oba konca pripadata dani množici točk.

V nadaljevanju bomo oglišča grafa označevali z latiničnimi črkami A, B, C, D. Včasih bo graf kot celota označen z eno veliko začetnico.

Definicija 2. Točke grafa, ki ne pripadajo nobenemu robu, imenujemo izolirane.

Definicija 3. Graf, ki je sestavljen samo iz izoliranih vozlišč, se imenuje ničelni - štetje .

Zapis: O "– graf z vozlišči, ki nima robov

Definicija 4. Graf, v katerem je vsak par vozlišč povezan z robom, se imenuje popoln.

Oznaka: U" – graf, sestavljen iz n oglišč in robov, ki povezujejo vse možne pare teh oglišč. Tak graf lahko predstavimo kot n-kotnik, v katerem so narisane vse diagonale

Definicija 5. Stopnja oglišča je število robov, ki jim oglišče pripada.

Opredelitev 6. Graf, katerega stopnje vseh k oglišč so enake, se imenuje homogeni stopenjski graf .

Opredelitev 7. Komplement danega grafa je graf, sestavljen iz vseh robov in njihovih koncev, ki jih je treba dodati izvirnemu grafu, da dobimo popoln graf.

Opredelitev 8. Graf, ki ga lahko na ravnini predstavimo tako, da se njegovi robovi sekajo le v ogliščih, imenujemo ravninski.

Opredelitev 9. Mnogokotnik ravninskega grafa, ki ne vsebuje nobenih oglišč ali robov grafa, se imenuje njegova ploskev.

Koncepti ravninskega grafa in obraza grafa se uporabljajo pri reševanju problemov o "pravilnem" barvanju različnih zemljevidov.

Opredelitev 10. Pot od A do X je zaporedje robov, ki vodijo od A do X, tako da imata vsaka dva sosednja roba skupno oglišče in noben rob se ne pojavi več kot enkrat.

Opredelitev 11. Cikel je pot, na kateri se začetna in končna točka ujemata.

Opredelitev 12. Preprost cikel je cikel, ki ne gre več kot enkrat skozi nobeno točko grafa.

Opredelitev 13. Dolžina poti , položen na zanko , imenujemo število robov te poti.

Opredelitev 14. Dve točki A in B v grafu se imenujeta povezani (nepovezani), če obstaja (ne obstaja) pot, ki vodi od A do B.

Opredelitev 15. Graf imenujemo povezan, če sta vsaki dve njegovi točki povezani; če graf vsebuje vsaj en par nepovezanih vozlišč, se graf imenuje nepovezan.

Opredelitev 16. Drevo je povezan graf, ki ne vsebuje ciklov.

Tridimenzionalni model drevesnega grafa je na primer pravo drevo s svojo zapleteno razvejano krošnjo; reka in njeni pritoki prav tako tvorijo drevo, vendar že ravno - na površini zemlje.

Opredelitev 17. Nepovezan graf, ki je v celoti sestavljen iz dreves, se imenuje gozd.

Opredelitev 18. Drevo, v katerem je vseh n oglišč oštevilčenih od 1 do n, imenujemo drevo s preštevilčenimi oglišči.

Tako smo preučili osnovne definicije teorije grafov, brez katerih ne bi bilo mogoče dokazovati izrekov in posledično reševati problemov.

Težave rešene z uporabo grafov

Znani problemi

Problem trgovskega potnika

Problem trgovskega potnika je eden od znanih problemov v teoriji kombinatorike. Predstavljen je bil leta 1934 in najboljši matematiki so si ob njem zlomili zobe.

Izjava problema je naslednja.
Potujoči trgovec (potujoči trgovec) mora zapustiti prvo mesto, obiskati mesta 2,1,3..n enkrat v neznanem vrstnem redu in se vrniti v prvo mesto. Razdalje med mesti so znane. V kakšnem vrstnem redu je treba iti po mestih, da bo zaprta pot (ogled) trgovskega potnika najkrajša?

Metoda reševanja problema trgovskega potnika

Požrešen algoritem "pojdite v najbližje (ki ga še niste vnesli) mesto."
Ta algoritem se imenuje "požrešen", ker morate v zadnjih korakih močno plačati za pohlep.
Upoštevajte na primer omrežje na sliki [Dodatek Slika 3], ki predstavlja ozek romb. Naj trgovski popotnik začne iz mesta 1. Algoritem »pojdi do najbližjega mesta« ga bo pripeljal do mesta 2, nato 3, nato 4; na zadnjem koraku boste morali plačati za svoj pohlep in se vrniti po dolgi diagonali diamanta. Rezultat ne bo najkrajša, ampak najdaljša tura.

Problem königsberških mostov.

Problem je formuliran na naslednji način.
Mesto Koenigsberg leži na bregovih reke Pregel in dveh otokov. Različne dele mesta je povezovalo sedem mostov. Ob nedeljah so se meščani sprehajali po mestu. Vprašanje: ali se je mogoče sprehoditi tako, da se po odhodu od hiše vrnete nazaj in hodite po vsakem mostu točno enkrat.
Mostovi čez reko Pregel se nahajajo kot na sliki[Dodatek Slika 1].

Razmislite o grafu, ki ustreza diagramu mostu [Dodatek, slika 2].

Za odgovor na vprašanje problema je dovolj ugotoviti, ali je graf Eulerjev. (Sodo število mostov mora segati iz vsaj enega oglišča). Ne moreš hoditi po mestu in enkrat prečkati vse mostove ter se vrniti.

Več zanimivih nalog

1. "Poti".

Problem 1

Kot se spomnite, je lovec na mrtve duše Čičikov enkrat obiskal slavne posestnike. Obiskal jih je v naslednjem vrstnem redu: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, general Betrishchev, Petukh, Konstanzholgo, polkovnik Koshkarev. Najden je bil diagram, na katerem je Čičikov skiciral relativne položaje posesti in podeželskih cest, ki jih povezujejo. Ugotovite, katera posest komu pripada, če Čičikov ni vozil po nobeni cesti večkrat [Dodatek, slika 4].

rešitev:

Cestni zemljevid kaže, da je Čičikov svojo pot začel s posesti E in končal s posestvom O. Upoštevajte, da le dve cesti vodita do posesti B in C, zato je moral Čičikov potovati po teh cestah. Označimo jih s krepko črto. Identificirani so odseki poti, ki potekajo skozi A: AC in AB. Čičikov ni potoval po cestah AE, AK in AM. Prečrtajmo jih. Označimo s krepko črto ED; Prečrtajmo DK. Prečrtajmo MO in MN; Označimo MF s krepko črto; prečrtaj FO; S krepko črto označimo FH, NK in KO. Poiščimo edino možno pot pod tem pogojem. In dobimo: posestvo E - pripada Manilovu, D - Korobochki, C - Nozdrevu, A - Sobakeviču, B - Pljuškinu, M - Tentetnikovu, F - Betriščevu, N - Petuhu, K - Konstanzholgu, O - Koškarevu [Dodatek Slika 5].

Problem 2

Slika prikazuje zemljevid območja [Dodatek, slika 6].

Lahko se premikate le v smeri puščic. Vsako točko lahko obiščete največ enkrat. Na koliko načinov lahko prideš od točke 1 do točke 9? Katera pot je najkrajša in katera najdaljša.

rešitev:

Vezje zaporedno "razslojimo" v drevo, začenši od točke 1 [Dodatek Slika 7]. Vzemimo drevo. Število možnih poti od 1 do 9 je enako številu "visečih" oglišč drevesa (14 jih je). Očitno je najkrajša pot 1-5-9; najdaljša je 1-2-3-6-5-7-8-9.

2 "Skupine, zmenki"

Problem 1

Udeleženci glasbenega festivala so si po srečanju izmenjali kuverte z naslovi. Dokaži, da:

a) je bilo izročenih sodo število ovojnic;

b) število udeležencev, ki so si kuverte izmenjali liho število, je sodo.

Rešitev: Naj bodo udeleženci festivala A 1, A 2, A 3. . . , In n so oglišča grafa, robovi pa povezujejo pare oglišč, ki predstavljajo fanta, ki si izmenjujeta ovojnice [Dodatek Slika 8]

rešitev:

a) stopnja vsakega vozlišča A i kaže število kuvert, ki jih je udeleženec A i dal svojim prijateljem. Skupno število oddanih ovojnic N je enako vsoti stopenj vseh oglišč grafa N = stopnja. Korak 1 +. A 2 + + . . . + korak. A n -1 + stopnja. In n, N =2p, kjer je p število robov grafa, tj. N – sodo. Posledično je bilo oddanih sodo število kuvert;

b) v enakosti N = stopnja. Korak 1 +. A 2 + + . . . + korak. A n -1 + stopnja. In n mora biti vsota lihih členov soda, to pa je lahko le, če je število lihih členov sodo. To pomeni, da je število sodelujočih, ki so si kuverte izmenjali liho število, sodo.

Problem 2

Nekega dne so se Andrej, Boris, Volodja, Daša in Galja dogovorili, da gredo zvečer v kino. Odločili so se, da bodo izbiro kina in predstave uskladili po telefonu. Odločeno je bilo tudi, da če z nekom ne bo mogoče vzpostaviti stika po telefonu, bo izlet v kino odpovedan. Zvečer se v kinu niso zbrali vsi, zato je bil obisk filma odpovedan. Naslednji dan so začeli ugotavljati, kdo je koga klical. Izkazalo se je, da je Andrej poklical Borisa in Volodjo, Volodja Borisa in Dašo, Boris Andreja in Dašo, Daša Andreja in Volodjo, Galja pa Andreja, Volodjo in Borisa. Komu ni uspelo priti do telefona in zato ni prišel na sestanek?

rešitev:

Narišimo pet pik in jih označimo s črkami A, B, C, D, D. To so prve črke imen. Povežimo pike, ki ustrezajo imenom fantov, ki so klicali.

[Dodatek Slika 9]

Iz slike je jasno, da je vsak od fantov - Andrej, Boris in Volodja - poklical vse ostale. Zato so ti fantje prišli v kino. Toda Galya in Dasha se nista mogli pogovarjati po telefonu (točki G in E nista povezani s črto) in zato v skladu z dogovorom nista prišli v kino.

Uporaba grafov na različnih področjih življenja ljudi

Poleg navedenih primerov se grafi pogosto uporabljajo v gradbeništvu, elektrotehniki, managementu, logistiki, geografiji, strojništvu, sociologiji, programiranju, avtomatizaciji tehnoloških procesov in proizvodnje, psihologiji in oglaševanju.

Na katerem koli področju znanosti in tehnologije srečate grafe. Grafi so čudoviti matematični objekti, s katerimi lahko rešujete matematične, ekonomske in logične probleme, različne uganke in poenostavljate pogoje problemov v fiziki, kemiji, elektroniki in avtomatizaciji. Mnoga matematična dejstva je mogoče priročno formulirati v jeziku grafov. Teorija grafov je del mnogih znanosti. Teorija grafov je ena najlepših in najbolj nazornih matematičnih teorij. V zadnjem času teorija grafov najde vse več aplikacij v uporabnih vprašanjih. Pojavila se je celo računalniška kemija - razmeroma mlado področje kemije, ki temelji na uporabi teorije grafov.

Molekularni grafi, ki se uporabljajo v stereokemiji in strukturni topologiji, kemiji grozdov, polimerov itd., so neusmerjeni grafi, ki prikazujejo strukturo molekul [Dodatek, slika 10]. Oglišča in robovi teh grafov ustrezajo ustreznim atomom in kemičnim vezem med njimi.

Molekularni grafi in drevesa: [Dodatek, slika 10] a, b - multigrafi oz. etilen in formaldehid; pravijo izomeri pentana (drevesa 4, 5 so izomorfna drevesu 2).

V stereokemiji organizmov najbolj. Pogosto se uporabljajo molekularna drevesa - glavna drevesa molekularnih grafov, ki vsebujejo samo vsa oglišča, ki ustrezajo atomom C. Kompilacija nizov mol. drevesa in ugotavljanje njihovega izomorfizma omogoča ugotavljanje, da pravijo. strukture in ugotovi skupno število izomerov alkanov, alkenov in alkinov

Proteinska omrežja

Proteinska omrežja so skupine fizično medsebojno delujočih proteinov, ki delujejo v celici skupaj in usklajeno ter nadzorujejo medsebojno povezane procese, ki potekajo v telesu. [priloga sl. 11].

Hierarhični sistemski graf imenovano drevo. Posebnost drevesa je, da obstaja samo ena pot med katerima koli dvema njegovima ogliščema. Drevo ne vsebuje ciklov ali zank.

Običajno ima drevo, ki predstavlja hierarhični sistem, eno glavno vozlišče, ki se imenuje koren drevesa. Vsako oglišče drevesa (razen korena) ima samo enega prednika - objekt, ki ga določa, je vključen v en razred najvišje ravni. Vsako oglišče drevesa lahko ustvari več potomcev - oglišč, ki ustrezajo razredom nižje ravni.

Za vsak par oglišč drevesa obstaja edinstvena pot, ki ju povezuje. Ta lastnost se uporablja pri iskanju vseh prednikov, na primer po moški liniji, katere koli osebe, katere rodovnik je predstavljen v obliki družinskega drevesa, ki je "drevo" v smislu teorije grafov.

Primer mojega družinskega drevesa [Dodatek, slika 12].

Še en primer. Slika prikazuje svetopisemsko družinsko drevo [Dodatek, slika 13].

Reševanje problemov

1.Transportna naloga. Naj bo v mestu Krasnodar baza s surovinami, ki jih je treba razdeliti v mesta Krymsk, Temryuk, Slavyansk-on-Kuban in Timashevsk na enem potovanju, pri tem pa porabiti čim manj časa in goriva ter se vrniti nazaj v Krasnodar .

rešitev:

Najprej naredimo graf vseh možnih potovalnih poti [Dodatek Slika 14], upoštevajoč realne ceste med temi naselji in razdaljo med njimi. Da bi rešili ta problem, moramo ustvariti še en graf, podoben drevesu [Dodatek Slika 15].

Za udobje rešitve mesta označujemo s številkami: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Rezultat je 24 rešitev, a potrebujemo le najkrajše poti. Od vseh rešitev sta le dve zadovoljivi; to je 350 km.

Podobno je mogoče in mislim, da je potrebno izračunati dejanski prevoz iz enega kraja v drugega.

Logični problem, ki vključuje transfuzijo. Vedro vsebuje 8 litrov vode, zraven sta dve posodi s prostornino 5 in 3 litre. v petlitrsko ponev morate naliti 4 litre vode in pustiti 4 litre v vedru, tj. enakomerno naliti vodo v vedro in veliko ponev.

rešitev:

Stanje v vsakem trenutku lahko opišemo s tremi številkami [Dodatek, slika 16].

Kot rezultat dobimo dve rešitvi: eno v 7 potezah, drugo v 8 potezah.

Zaključek

Torej, da bi se naučili reševati probleme, morate razumeti, kaj so, kako so strukturirani, iz katerih komponent so sestavljeni, katera so orodja, s katerimi se težave rešujejo.

Pri reševanju praktičnih problemov s teorijo grafov je postalo jasno, da je treba na vsakem koraku, v vsaki fazi njihovega reševanja uporabiti ustvarjalnost.

Že od samega začetka, na prvi stopnji, je v tem, da morate biti sposobni analizirati in kodirati stanje problema. Druga stopnja je shematski zapis, ki je sestavljen iz geometrijske predstavitve grafov, pri tej stopnji pa je element kreativnosti zelo pomemben, saj še zdaleč ni enostavno najti ujemanja med elementi pogoja in ustreznimi elementi pogoja. graf.

Pri reševanju transportnega problema ali naloge sestavljanja družinskega drevesa sem prišel do zaključka, da je metoda grafov vsekakor zanimiva, lepa in nazorna.

Prepričal sem se, da se grafi pogosto uporabljajo v ekonomiji, managementu in tehnologiji. Teorija grafov se uporablja tudi v programiranju. O tem v tem delu nismo razpravljali, vendar mislim, da je to le vprašanje časa.

To znanstveno delo preučuje matematične grafe, področja njihove uporabe in rešuje več problemov z uporabo grafov. Poznavanje osnov teorije grafov je potrebno na različnih področjih, povezanih s proizvodnjo in vodenjem poslovanja (na primer urnik izgradnje omrežja, urnik dostave pošte). Poleg tega sem ob delu na znanstveni nalogi osvojil delo na računalniku z urejevalnikom besedil WORD. S tem so cilji znanstvenega dela izpolnjeni.

Iz vsega navedenega torej neizpodbitno izhaja praktična vrednost teorije grafov, katere dokaz je bil cilj tega dela.

Literatura

Berge K. Teorija grafov in njene aplikacije. -M .: IIL, 1962.

Kemeny J., Snell J., Thompson J. Uvod v končno matematiko. -M .: IIL, 1963.

Ore O. Grafi in njihova uporaba. -M .: Mir, 1965.

Harari F. Teorija grafov. -M .: Mir, 1973.

Zykov A.A. Teorija končnih grafov. -Novosibirsk: Znanost, 1969.

Berezina L.Yu. Grafi in njihova uporaba. -M .: Izobraževanje, 1979. -144 str.

"Soros Educational Journal" št. 11 1996 (članek "Flat graphs");

Gardner M. "Matematični prosti čas", M. "Svet", 1972 (poglavje 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "Stari zabavni problemi", M. "Znanost", 1988 (del 2, oddelek 8; dodatek 4);

Aplikacija

Aplikacija

p

riž. 6

riž. 7

riž. 8

Aplikacija

Aplikacija

Aplikacija

p

riž. 14

Aplikacija

Povzetek na temo višja matematika na temo:

Uporaba teorije grafov v kemiji

Izvaja dijak skupine NH-202

Moskva 2011
Grafi so področje končne matematike, ki proučuje diskretne strukture; uporablja za reševanje različnih teoretičnih in uporabnih problemov.
nekaj osnovni pojmi. Graf je zbirka točk (vozlišč) in zbirka parov teh točk (ne nujno vseh), povezanih s premicami (slika 1,a). Če so črte v grafu usmerjene (tj. puščice kažejo smer povezave vozlišč), se imenujejo loki ali veje; če je neorientiran, - robovi. V skladu s tem se graf, ki vsebuje samo loke, imenuje usmerjen graf ali digraf; le robno neorientiran; loki in rebra - mešani. Graf z več robovi se imenuje multigraf; graf, ki vsebuje samo robove, ki pripadajo dvema njegovima disjunktnim podmnožicam (delom), je bipartiten; loki (robovi) in (ali) vozlišča, ki ustrezajo določenim utežem ali številčnim vrednostim katerega koli parametra, so uteženi. Pot v grafu je izmenično zaporedje tock in lokov, v katerih se nobena od tock ne ponovi (na primer a, b na sliki 1,a); kontura - zaprta pot, v kateri prva in zadnja točka sovpadata (na primer f, h); zanka - lok (rob), ki se začne in konča na isti točki. Veriga grafa je zaporedje robov, v katerem se nobena od oglišč ne ponovi (na primer c, d, e); cikel - zaprta veriga, v kateri njena začetna in končna točka sovpadata. Graf se imenuje povezan, če je katerikoli par njegovih vozlišč povezan z verigo ali potjo; sicer se graf imenuje nepovezan.
Drevo je povezan neusmerjen graf, ki ne vsebuje ciklov ali kontur (slika 1, b). Vpeti podgraf grafa je njegova podmnožica, ki vsebuje vsa oglišča in samo določene robove. Vpeto drevo grafa je njegov vpeti podgraf, ki je drevo. Grafi se imenujejo izomorfni, če obstaja ujemanje ena proti ena med množicami njihovih oglišč in robov (lokov).
Za reševanje problemov teorije grafov in njenih aplikacij so grafi predstavljeni z matrikami (sosednje, incidenčne, dvovrstične itd.), pa tudi s posebnimi. numerične značilnosti. Na primer, v matriki sosednosti (slika 1c) vrstice in stolpci ustrezajo številu točk grafa, njeni elementi pa imajo vrednosti 0 in 1 (oziroma odsotnost in prisotnost loka med dani par vozlišč); v incidenčni matriki (sl. 1d) vrstice ustrezajo številu vozlišč, stolpci ustrezajo številu lokov, elementi pa imajo vrednosti 0, + 1 in - 1 (oziroma odsotnost , prisotnost loka, ki vstopa in zapušča točko). Najpogostejše numerične značilnosti: število vozlišč (m), število lokov ali robov (n), ciklomatsko število ali rang grafa (n - m + k, kjer je k število povezanih podgrafov v nepovezan graf; na primer, za graf na sliki 1,b bo rang: 10-6+ 1 =5).
Uporaba teorije grafov temelji na konstrukciji in analizi različnih razredov kemijskih in kemijsko-tehnoloških grafov, ki jih imenujemo tudi topološki modeli, t.j. modeli, ki upoštevajo samo naravo povezav med vozlišči. V lokih (robovih) in ogliščih teh grafov so prikazani kemijski in kemijsko-tehnološki pojmi, pojavi, procesi ali objekti in s tem kvalitativna in kvantitativna razmerja oziroma določena razmerja med njimi.

riž. 1. Ponazoritev nekaterih osnovnih pojmov: a-mešani graf; b-razpeto drevo (polni loki a, h, d, f, h) in določen podgraf (črtkani loki c, e, g, k, l) digrafa; c, r-matrike oz. sosednost in incidenca digrafa.
Teoretični problemi. Kemijski grafi omogočajo napovedovanje kemijskih transformacij, pojasnjujejo bistvo in sistematizirajo nekatere temeljne pojme kemije: zgradbo, konfiguracijo, konformacije, kvantomehanske in statistično-mehanske interakcije molekul, izomerije itd. Kemijski grafi vključujejo molekularne, bipartitne in signalne grafe. enačb kinetične reakcije.
Molekularni grafi, ki se uporabljajo v stereokemiji in strukturni topologiji, kemiji grozdov, polimerov itd., so neusmerjeni grafi, ki prikazujejo strukturo molekul (slika 2). Oglišča in robovi teh grafov ustrezajo atomom oziroma kemičnim vezem med njimi.

riž. 2. Molekularni grafi in drevesa: a, b - multigrafi oz. etilen in formaldehid; pravijo izomeri pentana (drevesa 4, 5 so izomorfna drevesu 2).
V stereokemiji organskih snovi se najpogosteje uporabljajo molekularna drevesa - vpeta drevesa molekularnih grafov, ki vsebujejo samo vsa oglišča, ki ustrezajo atomom C (sl. 2, a in b). Sestavljanje nizov molekularnih dreves in ugotavljanje njihovega izomorfizma omogoča določanje molekulskih struktur in iskanje skupnega števila izomerov alkanov, alkenov in alkinov (slika 2, c).
Molekularni grafi omogočajo zmanjšanje težav, povezanih s kodiranjem, nomenklaturo in strukturnimi značilnostmi (razvejanostjo, cikličnostjo itd.) molekul različnih spojin na analizo in primerjavo čisto matematičnih značilnosti in lastnosti molekularnih grafov in njihovih dreves ter njihove ustrezne matrike. Za identifikacijo kvantitativnih povezav med strukturo molekul in fizikalno-kemijskimi (vključno s farmakološkimi) lastnostmi spojin je bilo razvitih več kot 20 tisoč imen topoloških indeksov molekul (Wiener, Balaban, Hosoya, Plat, Randich itd.), ki so določeno z uporabo matrik in numeričnih karakteristik molekularnih dreves. Na primer, Wienerjev indeks W = (m 3 + m)/6, kjer je m število oglišč, ki ustrezajo atomom C, korelira z molekulskimi volumni in refrakcijo, tvorbenimi entalpijami, viskoznostjo, površinsko napetostjo, kromatografskimi konstantami spojin, oktansko število ogljikovodikov in celo fiziološko aktivnost zdravil.
Pomembna parametra molekularnih grafov, ki se uporabljajo za določanje tavtomernih oblik dane snovi in ​​njihove reaktivnosti ter pri klasifikaciji aminokislin, nukleinskih kislin, ogljikovih hidratov in drugih kompleksnih naravnih spojin, sta povprečna in skupna (H) informacijska kapaciteta. Parameter se izračuna s Shannonovo informacijsko entropijsko formulo: , kjer je p t verjetnost, da vozlišča m grafa pripadajo i-ti vrsti ali ekvivalenčnemu razredu, k; i = , parameter. Preučevanje molekularnih struktur, kot so anorganski grozdi ali Möbiusovi trakovi, se zmanjša na ugotavljanje izomorfizma ustreznih molekularnih grafov z njihovo umestitvijo (vdelavo) v kompleksne poliedre (na primer poliedre v primeru grozdov) ali posebne. večdimenzionalne površine (na primer Riemannove površine). Analiza molekularnih grafov polimerov, katerih oglišča ustrezajo monomernim enotam, robovi pa kemijskim vezem med njimi, omogoča razlago na primer učinkov izločenega volumna, ki vodi do kvalitativnih sprememb napovedanih lastnosti polimerov. .

riž. 3. Reakcijski grafi: a-bipartitni; b-signalna raven kinetike; r 1, g 2 -r-cija; a1-a6-reagenti; k-stopnje konstante p-tsny; s-kompleksna spremenljivka Laplaceove transformacije.
S pomočjo teorije grafov in principov umetne inteligence je bila razvita programska oprema za sisteme za iskanje informacij v kemiji ter avtomatizirane sisteme za identifikacijo molekulskih struktur in racionalno načrtovanje organske sinteze. Za praktično izvajanje operacij na računalniku za izbiro racionalnih poti kemijskih transformacij, ki temeljijo na retrosintetičnih in sintonskih principih, se uporabljajo večnivojski razvejani iskalni grafi za možnosti rešitve, katerih oglišča ustrezajo molekularnim grafom reagentov in produktov, loki pa prikazujejo pretvorbe snovi.

riž. 4. Enokrožni kemijsko-tehnološki sistem in pripadajoči grafi: a-strukturni diagram; b, c-grafi pretoka materiala. s skupnimi masnimi pretoki in pretokom komponente A; r - graf toplotnega toka; d-fragment sistema enačb (f 1 - f 6) materialne bilance, pridobljen z analizo grafov na sl. 4, b in c; e-bipartitni informacijski digraf; g-informacijski graf, I-mešalnik; II-reaktor; III-destilacijska kolona; IV-hladilnik; I 1 -I 8 -tehnol. potoki; q-masni pretok; H je entalpija pretoka; i. s in i*, s* - oz. resnični in fiktivni viri in ponori materialnih in toplotnih tokov; c-koncentracija reagenta; V je prostornina reaktorja.
Matrične predstavitve molekulskih grafov različnih spojin so enakovredne (po transformaciji ustreznih matričnih elementov) matričnim metodam kvantne kemije. Zato se teorija grafov uporablja pri izvajanju kompleksnih kvantno kemijskih izračunov: za določanje števila, lastnosti in energije molekularnih orbital, napovedovanje reaktivnosti konjugiranih alternativnih in nealternantnih polienov, prepoznavanje aromatskih in antiaromatskih lastnosti snovi itd.
Za preučevanje motenj v sistemih, sestavljenih iz velikega števila delcev, se v kemijski fiziki uporabljajo tako imenovani Feynmanovi diagrami - grafi, katerih oglišča ustrezajo elementarnim interakcijam fizičnih delcev, robovi pa njihovim potem po trkih. Zlasti ti grafi omogočajo preučevanje mehanizmov nihajnih reakcij in določanje stabilnosti reakcijskih sistemov.
Za izbiro racionalnih poti za transformacijo molekul reagenta za dani nabor znanih interakcij se uporabljajo bipartitni reakcijski grafi (točke ustrezajo molekulam in tem reakcijam, loki ustrezajo interakcijam molekul v reakciji; sl. 3,a ). Takšni grafi omogočajo razvoj interaktivnih algoritmov za izbiro optimalnih poti kemijskih transformacij, ki zahtevajo najmanjše število vmesnih reakcij, minimalno število reagentov s seznama sprejemljivih ali dosežejo največji izkoristek produktov.
Signalni grafi enačb kinetične reakcije prikazujejo sisteme kinetičnih enačb, predstavljenih v algebrsko-operatorski obliki (slika 3b). Točke grafov ustrezajo tako imenovanim informacijskim spremenljivkam ali signalom v obliki koncentracij reagentov, loki - odnosom signalov, uteži lokov pa so določene s kinetičnimi konstantami. Takšni grafi se uporabljajo pri preučevanju mehanizmov in kinetike kompleksnih katalitskih reakcij, kompleksnih faznih ravnovesij pri tvorbi kompleksnih spojin, pa tudi za izračun parametrov aditivnih lastnosti raztopin.
Uporabni problemi. Za reševanje večdimenzionalnih problemov analize in optimizacije kemijsko-tehnoloških sistemov (KTS) se uporabljajo naslednji kemijsko-tehnološki grafi (slika 4): pretočni, informacijsko-pretočni, signalni in zanesljivostni. Grafi toka, ki so uteženi digrafi, vključujejo parametrične, materialne v smislu skupnih masnih pretokov fizičnih tokov in masnih pretokov nekaterih kemičnih komponent ali elementov, pa tudi toplotne grafe. Navedeni grafi ustrezajo fizikalnim in kemijskim pretvorbam snovi in ​​energije v danem kemijskem sistemu.
Parametrični grafi toka prikazujejo transformacijo parametrov (masnih pretokov itd.) fizičnih tokov po elementih CTS; oglišča grafov ustrezajo matematičnim modelom naprav, kot tudi virom in ponorom navedenih tokov, loki pa ustrezajo samim tokovom, uteži lokov pa so enake številu parametrov ustrezen pretok. Parametrični grafi se uporabljajo za razvoj algoritmov za analizo tehnoloških načinov večkrožnih kemijskih sistemov. Takšni algoritmi vzpostavijo zaporedje računskih sistemov enačb matematičnih modelov posameznih naprav katerega koli sistema za določitev parametrov njegovih izhodnih tokov z znanimi vrednostmi spremenljivih vhodnih tokov.
Grafi snovnega toka prikazujejo spremembe v porabi snovi v kemičnih snoveh. Oglišča grafov ustrezajo napravam, v katerih se transformirajo skupni masni pretoki fizičnih tokov in masni pretoki nekaterih kemičnih komponent ali elementov, pa tudi viri in ponori snovi tokov ali teh komponent; V skladu s tem loki grafov ustrezajo fizičnim tokovom ali fizičnim in fiktivnim (kemične transformacije snovi v napravah) virom in ponorom katerih koli komponent, uteži lokov pa so enake masnim pretokom obeh vrst. Grafi toplotnega toka prikazujejo toplotne bilance v CTS; oglišča grafov ustrezajo napravam, v katerih se spreminja poraba toplote fizičnih tokov, poleg tega pa virom in ponorom toplotne energije sistema; loki ustrezajo fizičnim in fiktivnim (fizikalno-kemijska pretvorba energije v napravah) toplotnim tokovom, uteži lokov pa so enake entalpijam tokov. Materialni in toplotni grafi se uporabljajo za sestavljanje programov za avtomatiziran razvoj algoritmov za reševanje sistemov enačb za materialne in toplotne bilance kompleksnih kemijskih sistemov.
Informacijsko-borzni grafi prikazujejo logično-informacijsko strukturo sistemov enačb matematičnih modelov CTS; se uporabljajo za razvoj optimalnih algoritmov za izračun teh sistemov. Bipartitni informacijski graf (slika 4, e) je neusmerjen ali usmerjen graf, katerega oglišča ustrezajo enačbam f l -f 6 in spremenljivkam q 1 - V, veje pa odražajo njihov odnos. Informacijski graf (slika 4, g) - digraf, ki prikazuje vrstni red reševanja enačb; vozlišča grafa ustrezajo tem enačbam, virom in sprejemnikom XTS informacij, veje pa informacijskim spremenljivkam.
Signalni grafi ustrezajo linearnim sistemom enačb matematičnih modelov kemijsko tehnoloških procesov in sistemov. Oglišča grafov ustrezajo signalom (na primer temperatura), veje pa povezavam med njimi. Takšni grafi se uporabljajo za analizo statičnih in dinamičnih načinov večparametrskih procesov in kemijskih sistemov, pa tudi za kazalnike številnih njihovih najpomembnejših lastnosti (stabilnost, občutljivost, vodljivost).
Za izračun različnih kazalnikov zanesljivosti kemične opreme se uporabljajo grafi zanesljivosti. Med številnimi skupinami teh grafov (na primer parametrični, logično-funkcionalni) so še posebej pomembna tako imenovana drevesa napak. Vsako takšno drevo je utežen digraf, ki prikazuje medsebojno povezanost številnih enostavnih okvar posameznih procesov in naprav CTS, ki vodijo do številnih sekundarnih okvar in posledične odpovedi sistema kot celote.
Za ustvarjanje kompleksov programov za avtomatizirano sintezo optimalne visoko zanesljive proizvodnje (vključno z varčevanjem z viri), skupaj z načeli umetne inteligence, usmerjene semantike ali semantike, se uporabljajo grafi možnosti rešitve CTS. Ti grafi, ki so v določenem primeru drevesa, prikazujejo postopke za generiranje nabora racionalnih alternativnih shem CTS (na primer 14 možnih pri ločevanju petkomponentne mešanice ciljnih produktov z rektifikacijo) in postopke za urejeno izbiro med njimi shema, ki je optimalna po nekem kriteriju učinkovitosti sistema.
itd.............

Poleg tega je bil Euler zadnjih 12 let svojega življenja resno bolan, oslepel in kljub hudi bolezni nadaljeval z delom in ustvarjanjem.

Statistični izračuni kažejo, da je Euler naredil povprečno eno odkritje na teden.

Težko je najti matematični problem, ki ne bi bil obravnavan v delih Eulerja.

Vsi matematiki naslednjih generacij so tako ali drugače študirali pri Eulerju in ni brez razloga slavni francoski znanstvenik P.S. Laplace je rekel: "Berite Eulerja, on je učitelj vseh nas."

Lagrange pravi: "Če res ljubite matematiko, berite Eulerja; predstavitev njegovih del je izjemna zaradi neverjetne jasnosti in natančnosti." Dejansko je bila eleganca njegovih izračunov pripeljana do najvišje stopnje. Condorcet je svoj govor na Akademiji v spomin na Eulerja sklenil z naslednjimi besedami: "Euler je torej prenehal živeti in računati!" Življenje za izračun - kako dolgočasno se zdi od zunaj!

Matematika si je običajno predstavljati kot suhega in gluhega za vse vsakdanje, za tisto, kar zanima navadne ljudi.

Problem treh hiš in treh vodnjakov, imenovan po Eulerju.

Ena od vej topologije. Graf je geometrijski diagram, ki je sistem črt, ki povezujejo določene točke. Točke imenujemo oglišča, črte, ki jih povezujejo, pa robovi (ali loki). Vse probleme teorije grafov je mogoče rešiti v grafični in matrični obliki. V primeru pisanja v matrični obliki je možnost prenosa sporočila iz določene točke v drugo označena z enico, njena odsotnost pa z ničlo.

Izvor teorije grafov v 18. stoletju. povezan z matematičnimi ugankami, še posebej močan zagon za njegov razvoj pa je dobil v 19. stoletju. in predvsem v 20. stoletju, ko so bile odkrite možnosti njegove praktične uporabe: za izračun radioelektronskih vezij, reševanje t.i. prometne naloge ipd. Od 50. let. Teorija grafov se vedno bolj uporablja v socialni psihologiji in sociologiji.

Na področju teorije grafov je treba omeniti dela F. Harryja, J. Kemenyja, K. Flamenta, J. Snella, J. Frencha, R. Normana, O. Oyserja, A. Beivelasa, R. Weissa itd. V ZSSR, po T. g. M. Borodkin et al.

Jezik teorije grafov je zelo primeren za analizo različnih vrst struktur in prenos stanj. V skladu s tem lahko ločimo naslednje vrste socioloških in socialno-psiholoških problemov, ki jih rešujemo s teorijo grafov.

Formalizacija in konstrukcija splošnega strukturnega modela družbenega objekta na različnih ravneh njegove kompleksnosti. Na primer strukturni diagram organizacije, sociogrami, primerjava sorodstvenih sistemov v različnih družbah, analiza strukture vlog skupin itd.

Upoštevamo lahko, da struktura vloge vključuje tri komponente: osebe, položaje (v poenostavljeni različici - položaje) in naloge, ki se opravljajo na danem položaju.

Vsako komponento lahko predstavimo kot graf:

Možno je združiti vse tri grafe za vse položaje ali samo za enega in posledično dobimo jasno predstavo o specifični strukturi c.l. to vlogo. Tako imamo za vlogo položaja P5 graf (sl.). Vpletanje neformalnih odnosov v določeno formalno strukturo bo precej zapletlo graf, vendar bo bolj natančna kopija realnosti.

a) količine. ocenjevanje teže (statusa) posameznika v hierarhični organizaciji. Ena od možnih možnosti za določitev stanja je formula:

kjer je r (p) status določene osebe p, k je vrednost stopnje podrejenosti, definirana kot najmanjše število korakov od dane osebe do njenega podrejenega, nk je število oseb na dani ravni k . Na primer v organizaciji, ki jo predstavljajo naslednji. štetje:

teža a=1·2+2·7+3·4=28; 6=1·3+2·3=9 itd.

b) določitev vodje skupine. Za vodjo je običajno značilna večja povezanost z ostalimi v skupini v primerjavi z drugimi. Tako kot v prejšnji nalogi lahko tudi tukaj uporabimo različne metode za identifikacijo vodje.

Najenostavnejša metoda je podana s formulo: r=Σdxy/Σdqx, tj. količnik deljenja vsote vseh razdalj vsake osebe do vseh drugih z vsoto razdalj danega posameznika do vseh drugih.

4) Analiza učinkovitosti delovanja tega sistema, ki vključuje tudi naloge, kot so iskanje optimalne strukture organizacije, povečanje skupinske kohezije, analiza družbenega sistema z vidika njegove vzdržnosti; preučevanje informacijskih tokov (prenos sporočil pri reševanju problemov, vpliv članov skupine drug na drugega v procesu združevanja skupine); s pomočjo tehnologije rešujejo problem iskanja optimalnega komunikacijskega omrežja.

Ko se uporablja za teorijo grafov, kot tudi za kateri koli matematični aparat, je res, da osnovna načela za rešitev problema postavlja vsebinska teorija (v tem primeru sociologija).

Naloga : Trije sosedje imajo tri skupne vodnjake. Ali je mogoče zgraditi poti, ki se ne križajo od vsake hiše do vsakega vodnjaka? Poti ne morejo potekati skozi vodnjake in hiše (slika 1).

riž. 1. K problemu hiš in vodnjakov.

Za rešitev tega problema bomo uporabili izrek, ki ga je dokazal Euler leta 1752 in je eden glavnih v teoriji grafov. Prvo delo o teoriji grafov pripada Leonhardu Eulerju (1736), čeprav je izraz "graf" prvi uvedel leta 1936 madžarski matematik Dénes König. Grafi so bili imenovani diagrami, sestavljeni iz točk in segmentov ravnih črt ali krivulj, ki povezujejo te točke.

Izrek. Če je mnogokotnik razdeljen na končno število mnogokotnikov, tako da katera koli dva poligona particije nimata skupnih točk ali imata skupna oglišča ali skupne robove, potem velja enakost

B - P + G = 1, (*)

kjer je B skupno število oglišč, P skupno število robov, G število poligonov (ploskev).

Dokaz. Dokažimo, da se enakost ne spremeni, če v nekem mnogokotniku dane particije narišemo diagonalo (slika 2, a).

A) b)

Po risanju takšne diagonale bo imela nova particija B oglišč, P+1 robov, število poligonov pa se bo povečalo za enega. Zato imamo

B - (P + 1) + (G + 1) = B - P + G.

Z uporabo te lastnosti narišemo diagonale, ki razdelijo prihajajoče mnogokotnike na trikotnike, in za nastalo particijo pokažemo izvedljivost relacije.

Da bi to naredili, bomo zaporedno odstranili zunanje robove in zmanjšali število trikotnikov. V tem primeru sta možna dva primera:

če želite odstraniti trikotnik ABC, morate odstraniti dva robova, v našem primeru AB in BC;

Če želite odstraniti trikotnik MKN, morate odstraniti en rob, v našem primeru MN.

V obeh primerih se enakost ne bo spremenila. Na primer, v prvem primeru bo po odstranitvi trikotnika graf sestavljen iz oglišč B-1, robov P-2 in poligona G-1:

(B - 1) - (P + 2) + (G -1) = B - P + G.

Tako odstranitev enega trikotnika ne spremeni enakosti.

Če nadaljujemo s tem postopkom odstranjevanja trikotnikov, bomo na koncu prišli do particije, sestavljene iz enega samega trikotnika. Za takšno particijo je B = 3, P = 3, G = 1 in zato

To pomeni, da enakost velja tudi za prvotno razbitje, iz česar končno dobimo, da relacija velja za to razbitje mnogokotnika.

Upoštevajte, da Eulerjeva relacija ni odvisna od oblike mnogokotnikov. Poligone lahko deformiramo, povečamo, pomanjšamo ali celo ukrivimo stranice, če med stranicami ni vrzeli. Eulerjeva relacija se ne bo spremenila.

Nadaljujmo z reševanjem problema treh hiš in treh vodnjakov.

rešitev. Predpostavimo, da je to mogoče storiti. Hiše označimo s točkami D1, D2, D3, vodnjake pa s točkami K1, K2, K3 (slika 1). Vsako hišno točko povežemo z vsako vodnjaško točko. Dobimo devet robov, ki se ne sekajo v parih.

Ti robovi tvorijo mnogokotnik na ravnini, razdeljen na manjše mnogokotnike. Zato mora biti za to particijo izpolnjena Eulerjeva relacija B - P + G = 1.

Obravnavanim obrazom dodajmo še eno ploskev - zunanji del ravnine glede na poligon. Potem bo Eulerjeva relacija prevzela obliko B - P + G = 2, z B = 6 in P = 9.

Zato je G = 5. Vsaka od petih ploskev ima vsaj štiri robove, saj po pogojih problema nobena od poti ne sme neposredno povezovati dveh hiš ali dveh vodnjakov. Ker vsak rob leži na točno dveh ploskvah, mora biti število robov najmanj (5 4)/2 = 10, kar je v nasprotju s pogojem, da je njihovo število 9.

Nastalo protislovje kaže, da je odgovor na problem negativen - nemogoče je narisati poti, ki se ne križajo, od vsake hiše do vsake vasi

Teorija grafov v kemiji

Uporaba teorije grafov pri konstrukciji in analizi različnih razredov kemijskih in kemijsko-tehnoloških grafov, ki jih imenujemo tudi topologija, modeli, t.j. modeli, ki upoštevajo samo naravo povezav med vozlišči. Loki (robovi) in oglišča teh grafov odražajo kemijske in kemijsko-tehnološke pojme, pojave, procese ali objekte in s tem kvalitativne in kvantitativne odnose ali določene odnose med njimi.

Teoretični problemi. Kemijski grafi omogočajo napovedovanje kemijskih pretvorb, pojasnjujejo bistvo in sistematizirajo nekatere osnovne pojme kemije: zgradbo, konfiguracijo, potrditve, kvantno mehanske in statistično-mehanske interakcije molekul, izomerije itd. Kemijski grafi vključujejo molekularne, bipartitne in signalne grafe. enačb kinetične reakcije. Molekularni grafi, ki se uporabljajo v stereokemiji in strukturni topologiji, kemiji grozdov, polimerov itd., so neusmerjeni grafi, ki prikazujejo strukturo molekul. Oglišča in robovi teh grafov ustrezajo ustreznim atomom in kemičnim vezem med njimi.

V stereokemiji org. c-c najpogosteje uporabljena so molekularna drevesa - vpeta drevesa molekularnih grafov, ki vsebujejo samo vsa vozlišča, ki ustrezajo atomom, in ugotavljanje njihove izomorfnosti omogoča določanje molekulskih struktur in iskanje skupnega števila izomerov alkanov, alkeni in alkini. Molekularni grafi omogočajo zmanjšanje težav, povezanih s kodiranjem, nomenklaturo in strukturnimi značilnostmi (razvejanostjo, cikličnostjo itd.) molekul različnih spojin na analizo in primerjavo čisto matematičnih značilnosti in lastnosti molekularnih grafov in njihovih dreves ter njihove ustrezne matrike. Za ugotavljanje števila korelacij med strukturo molekul in fizikalno-kemijskimi (vključno s farmakološkimi) lastnostmi spojin je bilo razvitih več kot 20 tako imenovanih. Topološki indeksi molekul (Wiener, Balaban, Hosoya, Plata, Randic itd.), ki so določeni z uporabo matrik in numeričnih karakteristik molekularnih dreves. Na primer, Wienerjev indeks W = (m3 + m)/6, kjer je m število oglišč, ki ustrezajo atomom C, je v korelaciji z molekulskimi volumni in lomom, tvorbenimi entalpijami, viskoznostjo, površinsko napetostjo, kromatografskimi konstantami spojin, oktanom število ogljikovodikov in celo fiziol. aktivnost zdravil. Pomembna parametra molekularnih grafov, ki se uporabljajo za določanje tavtomernih oblik dane snovi in ​​njihove reaktivnosti ter pri razvrščanju aminokislin, nukleinskih kislin, ogljikovih hidratov in drugih kompleksnih naravnih spojin, sta povprečna in skupna (H) informacijska kapaciteta. Analiza molekularnih grafov polimerov, katerih oglišča ustrezajo monomernim enotam, robovi pa kemičnim vezem med njimi, omogoča razlago na primer učinkov izključenega volumna, ki vodijo do kvalitet. spremembe predvidenih lastnosti polimerov. Z uporabo teorije grafov in načel umetne inteligence je bila razvita programska oprema za sisteme za iskanje informacij v kemiji, pa tudi avtomatizirane sisteme za identifikacijo molekularnih struktur in racionalno načrtovanje organske sinteze. Za praktično izvedbo na računalniku operacij za izbiro racionalnih kemijskih poti. transformacije, ki temeljijo na retrosintetičnih in sintonskih principih, uporabljajo večnivojske razvejane iskalne grafe za možnosti rešitve, katerih oglišča ustrezajo molekularnim grafom reagentov in produktov, loki pa prikazujejo transformacije.

Za reševanje večdimenzionalnih problemov analize in optimizacije kemijsko tehnoloških sistemov (CTS) se uporabljajo naslednji kemijsko tehnološki grafi: tokovni, informacijski, signalni in zanesljivi grafi. Za študij kemije. Fizika motenj v sistemih, sestavljenih iz velikega števila delcev, uporablja t.i. Feynmanovi diagrami so grafi, katerih oglišča ustrezajo elementarnim interakcijam fizičnih delcev, robovi njihovih poti po trkih. Zlasti ti grafi omogočajo proučevanje mehanizmov nihajnih reakcij in določanje stabilnosti reakcijskih sistemov. Grafi toka materiala prikazujejo spremembe pretoka v sistemih za kemijsko ogrevanje. oglišča grafov ustrezajo napravam, v katerih se spreminja poraba toplote fizičnih tokov, poleg tega pa virom in ponorom toplotne energije sistema; loki ustrezajo fizičnim in fiktivnim (fizikalno-kemijska pretvorba energije v napravah) toplotnim tokovom, uteži lokov pa so enake entalpijam tokov. Materialni in toplotni grafi se uporabljajo za sestavljanje programov za avtomatiziran razvoj algoritmov za reševanje sistemov enačb za materialne in toplotne bilance kompleksnih kemijskih sistemov. Grafi informacijskega toka prikazujejo logično informacijsko strukturo sistemov matematičnih enačb. modeli XTS; se uporabljajo za razvoj optimalnih algoritmov za izračun teh sistemov. Bipartitni informacijski graf je neusmerjen ali usmerjen graf, katerega vozlišča si ustrezajo. enačbe fl -f6 in spremenljivke q1 – V, veje pa odražajo njihov odnos. Informacijski graf – digraf, ki prikazuje vrstni red reševanja enačb; oglišča grafa ustrezajo tem enačbam, virom in sprejemnikom informacij XTS, veje pa informacijam. spremenljivke. Signalni grafi ustrezajo linearnim sistemom enačb matematičnih modelov kemijsko tehnoloških procesov in sistemov. Za izračun različnih kazalnikov zanesljivosti X se uporabljajo grafi zanesljivosti.

Uporabljena literatura:

1.Berge K., T. g. in njegova uporaba, prevod iz francoščine, M., 1962;

2. Kemeny J., Snell J., Thompson J., Uvod v končno matematiko, prev. iz angleščine, 2. izd., M., 1963;

3.Ope O., Grafi in njihova uporaba, trans. iz angleščine, M., 1965;

4. Belykh O.V., Belyaev E.V., Možnosti uporabe tehnologije v sociologiji, v: Človek in družba, vol. 1, [L.], 1966;

5. Kvantitativne metode v sociološkem raziskovanju, M., 1966; Belyaev E.V., Problemi socioloških meritev, "VF", 1967, št. 7; Bavelas. Komunikacijski vzorci v nalogah usmerjenih skupinah, v knjigi. Lerner D., Lass well H., Politične vede, Stanford, 1951;

6. Kemeny J. G., Snell J., Mathematical models in the social sciences, N. Y., 1962; Filament C., Applications of graph theory to group structure, N. Y., 1963; Оeser Ο. A., Hararu F., Strukture vlog in opis v smislu teorije grafov, v knjigi: Biddle V., Thomas E. J., Teorija vlog: koncepti in raziskave, N. Y., 1966. E. Belyaev. Leningrad.