B - P + G = 1, (*)

ahol B a csúcsok száma, P az élek teljes száma, G a sokszögek (lapok) száma.

Bizonyíték. Bizonyítsuk be, hogy az egyenlőség nem változik, ha egy adott partíció valamelyik sokszögébe átlót húzunk (2. ábra, a).

a) b)

2. ábra

Valóban, egy ilyen átló megrajzolása után az új partíciónak B csúcsa, P+1 éle lesz, és a sokszögek száma eggyel nő. Ezért van

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

Ezt a tulajdonságot felhasználva olyan átlókat rajzolunk, amelyek a bejövő sokszögeket háromszögekre bontják, és a kapott partícióra megmutatjuk a kapcsolat megvalósíthatóságát.

Ehhez egymás után eltávolítjuk a külső éleket, csökkentve a háromszögek számát. Ebben az esetben két eset lehetséges:

az ABC háromszög eltávolításához két élt kell eltávolítani, esetünkben az AB-t és a BC-t;

Az MKN háromszög eltávolításához el kell távolítania az egyik élt, esetünkben az MN-t.

Az egyenlőség mindkét esetben nem változik. Például az első esetben a háromszög eltávolítása után a gráf B-1 csúcsokból, P-2 élekből és G-1 sokszögből fog állni:

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

Így egy háromszög eltávolítása nem változtatja meg az egyenlőséget.

Folytatva a háromszögek eltávolításának folyamatát, végül eljutunk egy olyan partícióhoz, amely egyetlen háromszögből áll. Egy ilyen partíciónál B = 3, P = 3, G = 1, és ezért

B - P + G = 1.

Ez azt jelenti, hogy az egyenlőség az eredeti partícióra is érvényes, amiből végül azt kapjuk, hogy a reláció a sokszög ezen partíciójára is érvényes.

Vegyük észre, hogy az Euler-reláció nem függ a sokszögek alakjától. A sokszögek oldalai deformálhatók, nagyíthatók, kicsinyíthetők vagy akár meg is görbíthetők, amennyiben az oldalakon nincs hézag. Euler relációja nem fog változni.

Most folytassuk a három ház és három kút problémájának megoldását.

Megoldás . Tegyük fel, hogy ezt meg lehet tenni. Jelöljük a házakat D1, D2, D3 pontokkal, a kutakat pedig K1, K2, K3 pontokkal (1. ábra). Minden házpontot összekötünk minden kútponttal. Kilenc olyan élt kapunk, amelyek páronként nem metszik egymást.

Ezek az élek sokszöget alkotnak a síkon, kisebb sokszögekre osztva. Ezért ehhez a partícióhoz teljesülnie kell a B - P + G = 1 Euler-relációnak.

Adjunk hozzá még egy arcot a vizsgált lapokhoz - a sík külső részét a sokszöghez képest. Ekkor az Euler-reláció a B - P + G = 2 alakot ölti majd, ahol B = 6 és P = 9.

Ezért Г = 5. Mind az öt lapnak van legalább négy éle, mivel a probléma feltételei szerint egyik út sem köthet össze közvetlenül két házat vagy két kutat. Mivel minden él pontosan két oldalon fekszik, az élek számának legalább (5 4)/2 = 10-nek kell lennie, ami ellentmond annak a feltételnek, hogy számuk 9.

Az ebből eredő ellentmondás azt mutatja, hogy a problémára a válasz nemleges - nem lehet nem keresztező utakat rajzolni minden házból minden faluba

Gráfelmélet a kémiában

A gráfelmélet alkalmazása különböző osztályú kémiai és kémiai-technológiai gráfok felépítésére és elemzésére, amelyeket topológiának, modellnek is neveznek, i.e. modellek, amelyek csak a csúcsok közötti kapcsolatok jellegét veszik figyelembe. E gráfok ívei (élei) és csúcsai kémiai és kémiai-technológiai fogalmakat, jelenségeket, folyamatokat vagy tárgyakat, és ennek megfelelően minőségi és mennyiségi összefüggéseket, illetve ezek közötti bizonyos kapcsolatokat tükröznek.

Elméleti problémák. A kémiai gráfok lehetővé teszik a kémiai átalakulások előrejelzését, a lényeg magyarázatát és a kémia néhány alapfogalmának rendszerezését: szerkezet, konfiguráció, megerősítések, molekulák kvantummechanikai és statisztikai-mechanikai kölcsönhatásai, izoméria stb. kinetikai reakcióegyenletek. A sztereokémiában és a szerkezeti topológiában, a klaszterek, polimerek kémiájában stb. használt molekuláris gráfok irányítatlan gráfok, amelyek a molekulák szerkezetét jelenítik meg. E gráfok csúcsai és élei megfelelnek a megfelelő atomoknak és a köztük lévő kémiai kötéseknek.

A sztereokémiában org. c-c a leggyakrabban használt molekulafák - olyan molekuláris gráfok fái, amelyek csak az atomoknak megfelelő összes csúcsot tartalmazzák. A molekulafák halmazainak összeállítása és izomorfizmusuk megállapítása lehetővé teszi a molekulaszerkezetek meghatározását és az alkánok teljes izomerszámának meghatározását. alkének és alkinek. A molekuláris gráfok lehetővé teszik a különböző vegyületek molekuláinak kódolásával, nómenklatúrájával és szerkezeti jellemzőivel (elágazás, ciklikusság stb.) kapcsolatos problémák csökkentését a molekuláris gráfok és fáik tisztán matematikai jellemzőinek és tulajdonságainak elemzésére és összehasonlítására, valamint a hozzájuk tartozó mátrixokat. A molekulák szerkezete és a vegyületek fizikai-kémiai (beleértve a farmakológiai) tulajdonságai közötti összefüggések számának azonosítására több mint 20 ún. Molekulák (Wiener, Balaban, Hosoya, Plata, Randich stb.) topológiai indexei, melyek meghatározása molekulafák mátrixaival és numerikus jellemzőivel történik. Például a Wiener-index W = (m3 + m)/6, ahol m a C atomoknak megfelelő csúcsok száma, korrelál a molekulatérfogatokkal és a fénytörésekkel, a képződési entalpiákkal, viszkozitással, felületi feszültséggel, a vegyületek kromatográfiás állandóival, oktánszámmal. szénhidrogének száma és még fiziol . a drogok aktivitása. Az adott anyag tautomer formáinak és reaktivitásuk meghatározására, valamint az aminosavak, nukleinsavak, szénhidrátok és egyéb összetett természetes vegyületek osztályozásánál használt molekuláris gráfok fontos paraméterei az átlagos és a teljes (H) információs kapacitás. A polimerek molekulagráfjainak elemzése, amelyek csúcsai monomer egységeknek, élei pedig a köztük lévő kémiai kötéseknek felelnek meg, lehetővé teszi például a kizárt térfogat minőségekhez vezető hatásainak magyarázatát. változások a polimerek előrejelzett tulajdonságaiban. A gráfelmélet és a mesterséges intelligencia alapelveit felhasználva szoftvereket fejlesztettek ki a kémia információkereső rendszereihez, valamint automatizált rendszereket a molekulaszerkezetek azonosítására és a szerves szintézis racionális tervezésére. A racionális kémiai utak kiválasztására szolgáló műveletek számítógépen történő gyakorlati megvalósításához. A retroszintetikus és szintonikus elven alapuló transzformációk többszintű elágazó keresési gráfokat használnak a megoldási lehetőségekhez, amelyek csúcsai a reagensek és termékek molekuláris gráfjainak felelnek meg, az ívek pedig transzformációkat ábrázolnak.

A kémiai technológiai rendszerek (CTS) elemzésének és optimalizálásának többdimenziós problémáinak megoldására a következő kémiai technológiai gráfokat használjuk: áramlási, információáramlási, jel- és megbízhatósági gráfok. Kémiai tanulmányokhoz. A nagyszámú részecskéből álló rendszerek zavarfizikája az ún. A Feynman-diagramok olyan gráfok, amelyek csúcsai megfelelnek a fizikai részecskék elemi kölcsönhatásainak, az ütközések utáni útjuk éleinek. Ezek a grafikonok különösen lehetővé teszik az oszcillációs reakciók mechanizmusainak tanulmányozását és a reakciórendszerek stabilitásának meghatározását. A hőáramlási grafikonok a hőegyensúlyt CTS-ben jelenítik meg; a grafikonok csúcsai megfelelnek azoknak az eszközöknek, amelyekben a fizikai áramlások hőfogyasztása változik, és ezen felül a rendszer hőenergia-forrásainak és nyelőinek; az ívek fizikai és fiktív (fizikai-kémiai energiaátalakítás az eszközökben) hőáramoknak felelnek meg, és az ívek súlya megegyezik az áramlások entalpiájával. Az anyag- és hőgráfokat olyan programok összeállítására használják, amelyek algoritmusok automatizált fejlesztésére szolgálnak összetett kémiai rendszerek anyag- és hőmérlegének egyenletrendszereinek megoldására. Az információáramlási grafikonok a matematikai egyenletrendszerek logikai információszerkezetét jelenítik meg. XTS modellek; optimális algoritmusok kidolgozására szolgálnak ezeknek a rendszereknek a kiszámításához. A kétrészes információs gráf egy irányítatlan vagy irányított gráf, amelynek csúcsai rendre megfelelnek. fl -f6 egyenletek és q1 – V változók, az ágak pedig ezek kapcsolatát tükrözik. Információs gráf – az egyenletek megoldási sorrendjét ábrázoló digráf; a gráf csúcsai ezeknek az egyenleteknek, az XTS információ forrásainak és vevőinek, az ágak pedig az információnak felelnek meg. változók. A jelgráfok a kémiai technológiai folyamatok és rendszerek matematikai modelljeinek lineáris egyenletrendszereinek felelnek meg. A megbízhatósági grafikonok segítségével különféle X megbízhatósági mutatókat számítanak ki.

Felhasznált irodalom:

1.Berge K., T. g. és alkalmazása, francia fordítás, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, ford. angolból, 2. kiadás, M., 1963;

3.Ope O., Grafikonok és alkalmazásuk, ford. angolból, M., 1965;

4. Belykh O.V., Belyaev E.V., A szociológia alkalmazási lehetőségei a szociológiában, in: Man and Society, vol. 1, [L.], 1966;

5. Kvantitatív módszerek a szociológiai kutatásban, M., 1966; Belyaev E.V., A szociológiai mérések problémái, "VF", 1967, 7. sz.; Bavelas. Kommunikációs minták feladatorientált csoportokban, a könyvben. Lerner D., Lass well H., Political sciences, Stanford, 1951;

ÖNKORMÁNYZAT AUTONÓM NEVELÉSI INTÉZMÉNY KÖZÉPISKOLA 2. sz.

Előkészített

Legkokonets Vladislav, a 10A osztály tanulója

A gráfelmélet gyakorlati alkalmazása

Felügyelő

L.I. Noskova, matematikatanár

Art. Bryukhovetskaya

2011

1. Bevezetés…………………………………………………………………………………….………….3

2. A gráfelmélet megjelenésének története……………………………………………….………..4

3. A gráfelmélet alapvető definíciói és tételei…………………………………………6

4. Gráfok segítségével megoldott feladatok…………………………………………………………..8

4.1 Híres problémák………………………………………………………………8

4.2 Számos érdekes probléma…………………………………………………..9

5. Grafikonok alkalmazása az emberek életének különböző területein………………………………….

6. Problémák megoldása…………………………………………………………………………12

7. Következtetés………………….……………………………………………………………….13

8. Hivatkozási jegyzék………….…………………………………………………………………

9. Függelék……………………………………………………………………………….…………15

Bevezetés

A rejtvények megoldásából és szórakoztató játékokból született gráfelmélet mára egy egyszerű, hozzáférhető és hatékony eszközzé vált a problémák széles skálájával kapcsolatos kérdések megoldására. A grafikonok szó szerint mindenütt jelen vannak. Grafikonok formájában értelmezhető például útiterv és elektromos áramkörök, földrajzi térképek és kémiai vegyületek molekulái, emberek és embercsoportok közötti kapcsolatok. Az elmúlt négy évtizedben a gráfelmélet a matematika egyik leggyorsabban fejlődő ágává vált. Ezt a gyorsan bővülő alkalmazási terület igényei vezérlik. Alkalmazása integrált áramkörök és vezérlőáramkörök tervezésénél, automaták, logikai áramkörök, programblokk diagramok tanulmányozásánál, közgazdaságtanban és statisztikában, kémiában és biológiában, ütemezéselméletben. azért relevanciáját A témát egyrészt a grafikonok és a kapcsolódó kutatási módszerek népszerűsége, másrészt a megvalósításának kidolgozatlan, holisztikus rendszere határozza meg.

Az élet számos problémájának megoldása hosszú számításokat igényel, és néha még ezek a számítások sem hoznak sikert. Ez az, amit kutatási probléma. Felmerül a kérdés: lehet-e ezek megoldására egyszerű, racionális, rövid és elegáns megoldást találni? Könnyebb a problémamegoldás, ha grafikonokat használ? Ez elhatározta kutatásom témája: „A gráfelmélet gyakorlati alkalmazása”

Cél A kutatás célja az volt, hogy grafikonok segítségével megtanulják, hogyan lehet gyorsan megoldani a gyakorlati problémákat.

Kutatási hipotézis. A gráf módszer nagyon fontos, és széles körben használják a tudomány és az emberi tevékenység különböző területein.

Kutatási célok:

1. Tanulmányozza a témával kapcsolatos szakirodalmat és internetes forrásokat.

2.Ellenőrizze a gráf módszer hatékonyságát a gyakorlati feladatok megoldásában.

3. Vond le a következtetést.

A vizsgálat gyakorlati jelentősége az, hogy az eredmények kétségtelenül sok ember érdeklődését felkeltik majd. Egyikőtök sem próbálta felépíteni a családfáját? Hogyan kell ezt helyesen csinálni? Egy fuvarozási vállalkozás vezetőjének valószínűleg meg kell oldania a fuvarozás jövedelmezőbb felhasználásának problémáját, amikor egy célállomásról több településre szállít árut. Minden iskolás találkozott logikai transzfúziós problémákkal. Kiderül, hogy grafikonok segítségével könnyen megoldhatók.

A következő módszereket alkalmazzák a munkában: megfigyelés, keresés, kiválasztás, elemzés.

A gráfelmélet története

A gráfelmélet megalapítója Leonhard Euler (1707-1783) matematikus. Ennek az elméletnek a története a nagy tudós levelezésén keresztül követhető nyomon. Íme a latin szöveg fordítása, amely Euler Marinoni olasz matematikusnak és mérnöknek írt leveléből származik, amelyet Szentpétervárról küldött 1736. március 13-án.

„Egyszer megkérdeztek tőlem egy problémát egy Königsberg városában található szigetről, amelyet hét hídon átívelő folyó vesz körül.

[Függelék 1. ábra] A kérdés az, hogy valaki folyamatosan megkerülheti-e őket úgy, hogy minden hídon csak egyszer halad át. És akkor azt a tájékoztatást kaptam, hogy ezt még senki sem tudta megtenni, de senki sem bizonyította, hogy ez lehetetlen. Ez a kérdés, bár triviális, de figyelmemre méltónak tűnt, mivel sem a geometria, sem az algebra, sem a kombinatorikus művészet nem elegendő a megoldásához. Hosszas gondolkodás után egy teljesen meggyőző bizonyítékon alapuló, egyszerű szabályt találtam, amelynek segítségével minden ilyen jellegű feladatban azonnal megállapítható, hogy egy ilyen kitérő megtehető-e tetszőleges számú és akárhány elhelyezkedő hídon keresztül. vagy nem. A koenigsbergi hidak úgy helyezkednek el, hogy a következő ábrán is ábrázolhatók [Függelék 2. ábra], amelyben A szigetet, B, C és D pedig a kontinensnek egymástól folyóágakkal elválasztott részeit jelöli

Az ilyen jellegű problémák megoldására általa felfedezett módszerről Euler ezt írta:

„Ennek a megoldásnak természeténél fogva láthatóan nem sok köze van a matematikához, és nem értem, miért várjuk el ezt a megoldást inkább egy matematikustól, mint bárki mástól, hiszen ezt a döntést pusztán az érvelés támasztja alá, és nincs Be kell vonnunk a megoldást, vannak a matematikában rejlő törvények, tehát nem tudom, hogyan derül ki, hogy azokat a kérdéseket, amelyeknek nagyon kevés közük van a matematikához, nagyobb valószínűséggel oldják meg a matematikusok, mint mások.

Megkerülhető tehát a königsbergi hidak úgy, hogy csak egyszer haladunk át ezeken a hidakon? A válasz megtalálásához folytassuk Euler Marinonihoz írt levelét:

"Az a kérdés, hogy meg lehet-e kerülni ezt a hét hidat úgy, hogy mindegyiken csak egyszer haladunk át, vagy sem. Szabályom a következő megoldáshoz vezet erre a kérdésre. Először is meg kell nézni, hány szakaszon vannak elválasztva vízzel - olyan , amelyeknek nincs más átmenete egyikről a másikra, kivéve egy hídon keresztül Ebben a példában négy ilyen szakasz van - A, B, C, D. Ezután meg kell különböztetni, hogy a szám Az ezekre az egyes szakaszokra vezető hidak száma páros vagy páratlan Tehát esetünkben öt híd vezet az A szakaszhoz, és három-három híd vezet a többihez, vagyis az egyes szakaszokhoz vezető hidak száma páratlan, és ez önmagában az. A probléma megoldásához a következő szabályt alkalmazzuk: ha az egyes szakaszokhoz vezető hidak száma páros lenne, akkor lehetséges lenne a szóban forgó kitérő, és egyúttal lehetséges lenne. Bármelyik szakaszból indítsa el ezt a kitérőt, ha ezek közül kettő páratlan lenne, mert csak az egyik nem lehet páratlan, akkor az átmenetet akkor is az előírás szerint be lehetne fejezni, de biztosan csak a kitérő elejét kell venni. azon két szakasz egyike, amelyhez páratlan számú híd vezet. Ha végül kettőnél több olyan szakasz lenne, ahová páratlan számú híd vezet, akkor egy ilyen mozgás általában lehetetlen ... ha más, komolyabb problémákat is be lehetne hozni, akkor ez a módszer még nagyobb hasznot hozhatna. nem szabad elhanyagolni."

A gráfelmélet alapvető definíciói és tételei

A gráfelmélet a matematikusok erőfeszítéseivel létrehozott matematikai tudományág, ezért bemutatása tartalmazza a szükséges szigorú definíciókat. Tehát folytassuk ennek az elméletnek az alapfogalmak szervezett bevezetését.

1. definíció. A gráf véges számú pont gyűjteménye, amelyeket a gráf csúcsainak nevezünk, és néhány ilyen csúcsot összekötő páronkénti vonalak, amelyeket a gráf éleinek vagy íveinek nevezünk.

Ez a meghatározás többféleképpen is megfogalmazható: a gráf pontok (csúcsok) és szegmensek (élek) nem üres halmaza, amelyek mindkét vége egy adott ponthalmazhoz tartozik.

A következőkben a gráf csúcsait latin A, B, C, D betűkkel jelöljük. Néha a grafikon egészét egy nagybetűvel jelöljük.

2. definíció. A gráf azon csúcsait, amelyek egyetlen élhez sem tartoznak, izoláltnak nevezzük.

3. definíció. A csak izolált csúcsokból álló gráfot nullnak nevezzük - gróf .

Jelölés: O "– olyan csúcsokkal rendelkező gráf, amelynek nincsenek élei

4. definíció. Teljesnek nevezzük azt a gráfot, amelyben minden csúcspárt egy él köt össze.

Megnevezés: U" – n csúcsból és e csúcsok összes lehetséges párját összekötő élből álló gráf. Egy ilyen gráf n-szögként ábrázolható, amelyben az összes átló megrajzolódik

5. definíció. Egy csúcs foka azon élek száma, amelyekhez a csúcs tartozik.

6. definíció. Azt a gráfot, amelynek minden k csúcsának foka azonos, homogén fokgráfnak nevezzük .

7. definíció. Egy adott gráf komplementere egy gráf, amely az összes élből és azok végéből áll, amelyeket hozzá kell adni az eredeti gráfhoz, hogy teljes gráfot kapjunk.

8. definíció. Planárisnak nevezzük azt a gráfot, amely egy síkon úgy ábrázolható, hogy élei csak a csúcsokban metszik egymást.

9. definíció. Egy síkgráf sokszögét, amely nem tartalmazza a gráf csúcsait vagy éleit, lapjának nevezzük.

A síkgráf és a gráflap fogalmát a különböző térképek „helyes” színezésével kapcsolatos feladatok megoldása során használjuk.

10. definíció. Az A-tól X-ig tartó út olyan élek sorozata, amelyek A-ból X-be vezetnek úgy, hogy minden két szomszédos élnek közös csúcsa van, és egyetlen él sem fordul elő többször.

11. definíció. A ciklus egy olyan út, amelyen a kezdő és a végpont egybeesik.

12. definíció. Az egyszerű ciklus olyan ciklus, amely a gráf egyik csúcsán sem halad át többször.

13. definíció. Az út hossza , hurokra fektették , ennek az útnak az éleinek számát nevezzük.

14. definíció. A gráf két A és B csúcsát összekapcsoltnak (bontottnak) nevezzük, ha létezik (nem létezik) A-ból B-be vezető út.

15. definíció. Egy gráfot összefüggőnek nevezünk, ha minden két csúcsa összefügg; ha a gráf legalább egy pár szétválasztott csúcsot tartalmaz, akkor a gráfot szétkapcsoltnak nevezzük.

16. definíció. A fa egy összefüggő gráf, amely nem tartalmaz ciklusokat.

Egy fagráf háromdimenziós modellje például egy valódi fa bonyolultan elágazó koronájával; a folyó és mellékfolyói szintén fát alkotnak, de már laposak - a föld felszínén.

17. definíció. A teljesen fákból álló szétválasztott gráfot erdőnek nevezzük.

18. meghatározás. Azt a fát, amelynek minden n csúcsa 1-től n-ig van számozva, újraszámozott csúcsokkal rendelkező fának nevezzük.

Tehát megvizsgáltuk a gráfelmélet alapvető definícióit, amelyek nélkül lehetetlen lenne tételeket bizonyítani, következésképpen problémákat megoldani.

Grafikonok segítségével megoldott feladatok

Híres problémák

Utazó eladó probléma

Az utazó eladó probléma a kombinatorika elméletének egyik híres problémája. 1934-ben terjesztették elő, és a legjobb matematikusok kitörték rajta a fogukat.

A probléma megfogalmazása a következő.
Az utazó eladónak (vándorkereskedő) el kell hagynia az első várost, egyszer ismeretlen sorrendben meg kell látogatnia a 2,1,3..n városokat és vissza kell térnie az első városba. A városok közötti távolságok ismertek. Milyen sorrendben kell körbejárni a városokat, hogy az utazó eladó zárt útja (túrája) a legrövidebb legyen?

Az utazó eladó probléma megoldásának módja

Mohó algoritmus "Menj a legközelebbi (amelybe még nem léptél be) városba."
Ezt az algoritmust „kapzsinak” nevezik, mert az utolsó lépésekben komolyan kell fizetni a kapzsiságért.
Tekintsük például az ábrán látható hálózatot [Függelék 3. ábra], amely keskeny rombuszt jelent. Hagyja, hogy egy utazó eladó az 1. városból induljon. Az „ugrás a legközelebbi városba” algoritmus a 2., majd 3., majd 4. városba viszi; az utolsó lépésben fizetnie kell kapzsiságáért, a gyémánt hosszú átlója mentén visszatérve. Az eredmény nem a legrövidebb, hanem a leghosszabb túra lesz.

Probléma a königsbergi hidakkal kapcsolatban.

A probléma a következőképpen fogalmazódik meg.
Koenigsberg városa a Pregel folyó és két sziget partján található. A város különböző részeit hét híd kötötte össze. Vasárnaponként a városlakók sétáltak a városban. Kérdés: lehet-e úgy sétálni, hogy miután elhagyta a házat, térjen vissza, minden hídon pontosan egyszer sétáljon.
A Pregel folyón átívelő hidak a képen láthatóak[Függelék 1. ábra].

Tekintsük a híddiagramnak megfelelő grafikont [Függelék 2. ábra].

A probléma kérdésének megválaszolásához elegendő kideríteni, hogy a gráf Euleri-e. (Legalább egy csúcsból páros számú hídnak kell kinyúlnia). Nem sétálhatsz körbe a városban, és egyszer átmész az összes hídon, és visszatérsz.

Több érdekes feladat

1. „Útvonalak”.

1. probléma

Emlékszel, a halott lelkek vadásza, Csicsikov egyszer meglátogatta a híres földbirtokosokat. A következő sorrendben kereste fel őket: Manilov, Korobocska, Nozdryov, Sobakevich, Plushkin, Tentetnikov, Betrischev tábornok, Petukh, Konstanzholgo, Koskarev ezredes. Találtak egy diagramot, amelyen Csicsikov felvázolta a birtokok egymáshoz viszonyított helyzetét és az azokat összekötő országutak helyzetét. Határozza meg, melyik birtok kié, ha Csicsikov egyik utat sem vezette többször [Függelék 4. ábra].

Megoldás:

Az útiterv azt mutatja, hogy Csicsikov az E birtokról kezdte útját, és az O birtokkal ért véget. Megjegyezzük, hogy csak két út vezet a B és C birtokra, így Csicsikovnak ezeken az utakon kellett haladnia. Jelöljük őket félkövér vonallal. Az A-n áthaladó útvonalszakaszokat azonosították: AC és AB. Csicsikov nem az AE, AK és AM utakon utazott. Húzzuk át őket. Jelöljük félkövér vonallal ED; Húzzuk át a DK-t. Húzzuk át MO-t és MN-t; Jelöljük az MF-et félkövér vonallal; áthúzni FO; Jelöljük félkövér vonallal az FH-t, NK-t és KO-t. Keressük meg az egyetlen lehetséges útvonalat ilyen feltételek mellett. És megkapjuk: E birtok - Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betriscsev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Függelék 5. ábra].

2. probléma

Az ábrán a terület térképe látható [Függelék 6. ábra].

Csak a nyilak irányába mozoghat. Minden pontot legfeljebb egyszer látogathat meg. Hányféleképpen juthatsz el az 1. pontból a 9. pontba? Melyik útvonal a legrövidebb és melyik a leghosszabb.

Megoldás:

Sorrendben „rétegezzük” az áramkört egy fává, az 1. csúcstól kezdve [Függelék 7. ábra]. Vegyünk egy fát. Az 1-ről 9-re jutó lehetséges módok száma megegyezik a fa „függő” csúcsainak számával (14 db van). Nyilvánvalóan a legrövidebb út az 1-5-9; a leghosszabb az 1-2-3-6-5-7-8-9.

2 "Csoportok, randevúzások"

1. probléma

A zenei fesztivál résztvevői, miután találkoztak, címzett borítékokat váltottak. Bizonyítsd be, hogy:

a) páros számú borítékot adtak át;

b) azoknak a résztvevőknek a száma, akik páratlan számú alkalommal cseréltek borítékot.

Megoldás: Legyen a fesztivál résztvevői A 1, A 2, A 3. . . , És n a gráf csúcsai, és az élek olyan csúcspárokat kötnek össze, amelyek a borítékot cserélő srácokat képviselik [Függelék 8. ábra]

Megoldás:

a) az egyes A i csúcsok foka azt mutatja, hogy A i résztvevő hány borítékot adott át barátainak. Az N átvitt burkológörbék teljes száma megegyezik a gráf összes csúcsának fokszámainak összegével N = fok. 1+ lépés. A 2++. . . + lépés. A n -1 + fok. És n, N =2p, ahol p a gráf éleinek száma, azaz. N – páros. Következésképpen páros számú borítékot adtak át;

b) az N = fok egyenlőségben. 1+ lépés. A 2++. . . + lépés. A n -1 + fok. És n a páratlan tagok összegének párosnak kell lennie, és ez csak akkor lehet, ha a páratlan tagok száma páros. Ez azt jelenti, hogy azoknak a résztvevőknek a száma, akik páratlan számú alkalommal cseréltek borítékot, páros.

2. probléma

Egy nap Andrej, Boris, Volodya, Dasha és Galya megegyeztek, hogy este moziba mennek. Úgy döntöttek, hogy telefonon egyeztetik a mozi- és bemutatóválasztást. Arról is döntöttek, hogy ha valakivel nem lehet telefonon felvenni a kapcsolatot, akkor a moziba való utazást lemondják. Este nem mindenki gyűlt össze a moziban, ezért a filmlátogatás elmaradt. Másnap kezdték kideríteni, ki hívott kit. Kiderült, hogy Andrej Borisznak és Volodjának, Volodya Borisznak és Dasának, Boriszt Andrejnak és Dasának, Dasát Andrejnak és Volodjának, Galját pedig Andrejnak, Volodjának és Borisznak hívta. Ki nem tudta elérni a telefont, és ezért nem jött el a találkozóra?

Megoldás:

Rajzoljunk öt pontot, és jelöljük meg őket A, B, C, D, D betűkkel. Ezek a nevek első betűi. Kössük össze azokat a pontokat, amelyek megfelelnek a hívó srácok nevének.

[Függelék 9. ábra]

A képen jól látható, hogy a srácok - Andrey, Boris és Volodya - mindenki másnak telefonált. Ezért jöttek ezek a srácok a moziba. De Galya és Dasha nem tudtak telefonálni egymással (a G és E pontot nem köti össze vonalszakasz), ezért a megállapodásnak megfelelően nem jöttek el a moziba.

Grafikonok alkalmazása az emberek életének különböző területein

A megadott példákon kívül a grafikonokat széles körben használják az építőiparban, az elektrotechnikában, a menedzsmentben, a logisztikában, a földrajzban, a gépészetben, a szociológiában, a programozásban, a technológiai folyamatok és termelés automatizálásában, a pszichológiában és a reklámozásban.

A tudomány és a technológia bármely területén találkozhatunk grafikonokkal. A grafikonok csodálatos matematikai objektumok, amelyekkel matematikai, gazdasági és logikai feladatokat, különféle rejtvényeket oldhat meg, és egyszerűsítheti a fizika, kémia, elektronika és automatizálási feladatok feltételeit. Számos matematikai tény kényelmesen megfogalmazható a gráfok nyelvén. A gráfelmélet számos tudomány része. A gráfelmélet az egyik legszebb és leglátványosabb matematikai elmélet. Az utóbbi időben a gráfelmélet egyre több alkalmazást talál alkalmazott kérdésekben. Még a számítógépes kémia is megjelent – ​​a kémia viszonylag fiatal területe, amely a gráfelmélet alkalmazásán alapul.

Molekulagráfok A sztereokémiában és a szerkezeti topológiában, a klaszterek kémiájában, polimerekben stb. használatos, irányítatlan gráfok, amelyek a molekulák szerkezetét jelenítik meg. [Függelék 10. ábra]. E gráfok csúcsai és élei megfelelnek a megfelelő atomoknak és a köztük lévő kémiai kötéseknek.

Molekulagráfok és fák: [Függelék 10. ábra] a, b - multigráfok, ill. etilén és formaldehid; azt mondják pentán izomerek (a 4., 5. fák izomorfak a 2. fával).

Az élőlények sztereokémiájában leginkább. Gyakran használják a molekuláris fákat - a molekuláris gráfok fő fáit, amelyek csak a C atomoknak megfelelő összes csúcsot tartalmazzák. fák és izomorfizmusuk megállapítása lehetővé teszi annak meghatározását, hogy azt mondják. szerkezeteket, és találja meg az alkánok, alkének és alkinok izomereinek teljes számát

Fehérje hálózatok

A fehérjehálózatok fizikailag kölcsönhatásba lépő fehérjék csoportjai, amelyek egy sejtben együtt és összehangoltan működnek, és szabályozzák a szervezetben zajló, egymással összefüggő folyamatokat. [melléklet ábra. 11].

Hierarchikus rendszergráf fának hívják. A fa megkülönböztető jellemzője, hogy bármely két csúcsa között csak egy út van. A fa nem tartalmaz ciklusokat vagy hurkokat.

Általában egy hierarchikus rendszert képviselő fának van egy fő csúcsa, amelyet a fa gyökerének neveznek. A fa minden csúcsának (a gyökér kivételével) csak egy őse van - az általa kijelölt objektum egy felső szintű osztályba tartozik. A fa bármely csúcsa több leszármazottat is generálhat - az alacsonyabb szintű osztályoknak megfelelő csúcsokat.

Minden fa csúcspárhoz egy egyedi útvonal köti össze őket. Ezt a tulajdonságot akkor használjuk, amikor minden olyan személy összes ősét megtaláljuk, például a férfi vonalban, akinek a törzskönyve családfa formájában van ábrázolva, ami a gráfelmélet értelmében „fa”.

Példa a családfámra [Függelék 12. ábra].

Egy másik példa. A képen a bibliai családfa látható [Függelék 13. ábra].

Problémamegoldás

1.Szállítási feladat. Legyen Krasznodar városában egy bázis olyan nyersanyagokkal, amelyeket egy utazás alatt ki kell osztani Krimszk, Temrjuk, Szlavjanszk-Kuban és Timasevszk városokba, a lehető legkevesebb időt és üzemanyagot eltöltve, majd visszatérve Krasznodarba. .

Megoldás:

Először készítsünk grafikont az összes lehetséges utazási útvonalról [Függelék 14. ábra], figyelembe véve az e települések közötti valós utakat és a köztük lévő távolságot. A probléma megoldásához létre kell hoznunk egy másik gráfot, egy faszerű gráfot [Függelék 15. ábra].

A megoldás kényelme érdekében a városokat számokkal jelöljük: Krasznodar - 1, Krimszk - 2, Temryuk - 3, Szlavjanszk - 4, Timasevszk - 5.

Az eredmény 24 megoldás, de csak a legrövidebb utakra van szükségünk. Az összes megoldás közül csak kettő kielégítő, ez 350 km.

Hasonlóképpen lehetséges és szerintem szükséges is kiszámítani a tényleges szállítást egyik helyről a másikra.

A transzfúzióval kapcsolatos logikai probléma. A vödörben 8 liter víz van, és két 5 és 3 literes edény található benne. öntsön 4 liter vizet egy ötliteres serpenyőbe, és hagyjon 4 litert a vödörben, azaz egyformán öntse a vizet a vödörbe és egy nagy serpenyőbe.

Megoldás:

A helyzet minden pillanatban három számmal írható le [Függelék 16. ábra].

Ennek eredményeként két megoldást kapunk: az egyiket 7 lépésben, a másikat 8 lépésben.

Következtetés

Tehát ahhoz, hogy megtanulja a problémák megoldását, meg kell értenie, hogy mik ezek, hogyan épülnek fel, milyen összetevőkből állnak, milyen eszközökkel oldják meg a problémákat.

A gyakorlati feladatokat gráfelmélet segítségével megoldva világossá vált, hogy minden lépésben, megoldásuk minden szakaszában szükség van a kreativitás alkalmazására.

Kezdettől fogva, az első szakaszban abban rejlik, hogy képesnek kell lennie elemezni és kódolni a probléma állapotát. A második szakasz egy sematikus jelölés, amely a gráfok geometriai ábrázolásából áll, és ebben a szakaszban nagyon fontos a kreativitás eleme, mert korántsem könnyű megfelelést találni a feltétel elemei és a megfelelő elemei között. grafikon.

Közlekedési probléma vagy családfa készítési feladat megoldása során arra a következtetésre jutottam, hogy a grafikonos módszer mindenképpen érdekes, szép és látványos.

Meggyőződésem, hogy a grafikonokat széles körben használják a közgazdaságtanban, a menedzsmentben és a technológiában. A gráfelméletet a programozásban is használják.

Ez a tudományos munka a matematikai gráfokat, azok alkalmazási területeit vizsgálja, és számos problémát old meg gráfok segítségével. A gráfelmélet alapjainak ismerete a termeléssel és üzletvezetéssel kapcsolatos különböző területeken szükséges (például hálózatépítési ütemezés, levélkézbesítési ütemezés). Emellett tudományos dolgozat készítése közben elsajátítottam a számítógépen való munkát a WORD szövegszerkesztő segítségével. Ezzel a tudományos munka célkitűzései teljesültek.

A fentiekből tehát cáfolhatatlanul következik a gráfelmélet gyakorlati értéke, melynek bizonyítása volt jelen munka célja.

Irodalom

Berge K. Gráfelmélet és alkalmazásai. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Bevezetés a véges matematikába. -M.: IIL, 1963.

Ore O. Grafikonok és alkalmazásuk. -M.: Mir, 1965.

Harari F. Gráfelmélet. -M.: Mir, 1973.

Zykov A.A. Véges gráf elmélet. -Novoszibirszk: Tudomány, 1969.

Berezina L.Yu. Grafikonok és alkalmazásuk. -M.: Nevelés, 1979. -144 p.

"Soros Educational Journal" 1996. 11. szám ("Síkgrafikonok" cikk);

Gardner M. "Mathematical szabadidő", M. "World", 1972 (35. fejezet);

Olehnik S. N., Nesterenko Yu., Potapov M. K. „Régi szórakoztató problémák”, M. „Tudomány”, 1988 (2. rész, 8. rész; 4. melléklet);

Alkalmazás

Alkalmazás

P

Rizs. 6

Rizs. 7

Rizs. 8

Alkalmazás

Alkalmazás

Alkalmazás

P

Rizs. 14

Alkalmazás

Absztrakt a témában felsőbb matematika a témában:

A gráfelmélet alkalmazása a kémiában

Előadja az NH-202 csoport diákja

Moszkva 2011
A gráfok a véges matematika területe, amely diszkrét struktúrákat vizsgál; különféle elméleti és alkalmazott problémák megoldására szolgál.
Néhány alapfogalmak. A gráf pontok (csúcsok) gyűjteménye, és ezeknek a pontoknak (nem feltétlenül az összesnek) párjainak gyűjteménye, amelyeket vonalak kötnek össze (1. ábra, a). Ha a gráf vonalai orientáltak (vagyis a nyilak jelzik a csúcsok kapcsolódási irányát), akkor íveknek vagy elágazásoknak nevezzük őket; ha tájolatlan, - élek. Ennek megfelelően a csak íveket tartalmazó gráfot irányított gráfnak vagy digráfnak nevezzük; csak él-orientált; ívek és bordák – vegyesen. A több élű gráfot multigráfnak nevezzük; egy gráf, amely csak két diszjunkt részhalmazához (részéhez) tartozó éleket tartalmaz, kétoldalú; az ívek (élek) és (vagy) csúcsok, amelyek megfelelnek bármely paraméter bizonyos súlyainak vagy számértékeinek, súlyozásra kerülnek. A gráfban lévő útvonal csúcsok és ívek váltakozó sorozata, amelyben egyik csúcs sem ismétlődik (például a, b az 1,a ábrán); kontúr - zárt út, amelyben az első és az utolsó csúcs egybeesik (például f, h); hurok - egy ív (él), amely ugyanabban a csúcsban kezdődik és végződik. A gráfútvonal olyan élsorozat, amelyben egyik csúcs sem ismétlődik (például c, d, e); ciklus - zárt lánc, amelyben a kezdeti és a végső csúcsok egybeesnek. Egy gráfot összefüggőnek nevezünk, ha bármely csúcspárját lánc vagy út köti össze; egyébként a gráfot szétkapcsoltnak nevezzük.
A fa egy összefüggő irányítatlan gráf, amely nem tartalmaz ciklusokat vagy kontúrokat (1. ábra, b). A gráf feszítő részgráfja annak egy részhalmaza, amely az összes csúcsot és csak bizonyos éleket tartalmazza. A gráf feszítőfája a feszítő részgráfja, amely egy fa. A gráfokat izomorfnak nevezzük, ha csúcsaik és éleik (íveik) halmazai között egy az egyhez egyezés van.
A gráfelmélet és alkalmazásai problémáinak megoldására a gráfokat mátrixokkal (szomszédsági, előfordulási, kétsoros stb.), valamint speciális mátrixokkal ábrázolják. numerikus jellemzők. Például a szomszédsági mátrixban (1c. ábra) a sorok és oszlopok a gráf csúcsainak számának felelnek meg, elemei pedig 0 és 1 értéket vesznek fel (illetve az ív hiánya és jelenléte a gráf között). adott csúcspár); az incidencia mátrixban (1d. ábra) a sorok a csúcsok számának, az oszlopok az ívek számának felelnek meg, és az elemek 0, + 1 és -1 értéket vesznek fel (illetve a hiány , a csúcsba belépő és onnan kilépő ív jelenléte). A leggyakoribb numerikus jellemzők: a csúcsok száma (m), az ívek vagy élek száma (n), a ciklomatikus szám vagy a gráf rangja (n - m + k, ahol k a kapcsolódó részgráfok száma egy szétválasztott gráf például az 1. ábrán látható gráf esetén: 10-6+ 1 =5).
A gráfelmélet alkalmazása különböző osztályú kémiai és kémiai-technológiai gráfok felépítésén és elemzésén alapul, amelyeket topológiai modelleknek is neveznek, i.e. modellek, amelyek csak a csúcsok közötti kapcsolatok jellegét veszik figyelembe. E gráfok ívei (élei) és csúcsai kémiai és kémiai-technológiai fogalmakat, jelenségeket, folyamatokat vagy objektumokat, és ennek megfelelően minőségi és mennyiségi összefüggéseket, illetve ezek közötti bizonyos kapcsolatokat jelenítenek meg.

Rizs. 1. Néhány alapfogalom szemléltetése: a-vegyes gráf; b-feszítő fa (a, h, d, f, h tömör ívek) és a digráf bizonyos részgráfja (c, e, g, k, l szaggatott ívei); c, r-mátrixok ill. kétszög szomszédossága és előfordulása.
Elméleti problémák. A kémiai gráfok lehetővé teszik a kémiai átalakulások előrejelzését, a lényeg magyarázatát és a kémia néhány alapfogalmának rendszerezését: szerkezet, konfiguráció, konformációk, molekulák kvantummechanikai és statisztikai-mechanikai kölcsönhatásai, izoméria stb. kinetikai reakcióegyenletek.
A sztereokémiában és a szerkezeti topológiában, a klaszterek, polimerek kémiájában stb. használt molekuláris gráfok irányítatlan gráfok, amelyek a molekulák szerkezetét jelenítik meg (2. ábra). Ezeknek a gráfoknak a csúcsai és élei az atomoknak, illetve a köztük lévő kémiai kötéseknek felelnek meg.

Rizs. 2. Molekuláris gráfok és fák: a, b - multigráfok, ill. etilén és formaldehid; azt mondják pentán izomerek (a 4., 5. fák izomorfak a 2. fával).
A szerves anyagok sztereokémiájában leggyakrabban molekuláris fákat használnak - molekuláris gráfok átívelő fáit, amelyek csak a C atomoknak megfelelő összes csúcsot tartalmazzák (2. ábra, a és b). A molekulafák halmazainak összeállítása és izomorfizmusuk megállapítása lehetővé teszi a molekulaszerkezetek meghatározását, valamint az alkánok, alkének és alkinek izomereinek összszámának meghatározását (2. ábra, c).
A molekuláris gráfok lehetővé teszik a különböző vegyületek molekuláinak kódolásával, nómenklatúrájával és szerkezeti jellemzőivel (elágazás, ciklikusság stb.) kapcsolatos problémák csökkentését a molekuláris gráfok és fáik tisztán matematikai jellemzőinek és tulajdonságainak elemzésére és összehasonlítására, valamint a hozzájuk tartozó mátrixokat. A molekulák szerkezete és a vegyületek fizikai-kémiai (beleértve a farmakológiai) tulajdonságai közötti kvantitatív összefüggések azonosítására több mint 20 ezer molekula topológiai mutatószámot fejlesztettek ki (Wiener, Balaban, Hosoya, Plat, Randich stb.), amelyek a következők: mátrixok és molekuláris fák numerikus jellemzői segítségével határozzuk meg. Például a Wiener-index W = (m 3 + m)/6, ahol m a C atomoknak megfelelő csúcsok száma, korrelál a molekulatérfogatokkal és a fénytörésekkel, a képződési entalpiákkal, a viszkozitással, a felületi feszültséggel, a vegyületek kromatográfiás állandóival, a szénhidrogének oktánszáma, sőt a gyógyszerek élettani aktivitása is.
Az adott anyag tautomer formáinak és reaktivitásuk meghatározására, valamint az aminosavak, nukleinsavak, szénhidrátok és egyéb összetett természetes vegyületek osztályozásánál használt molekuláris gráfok fontos paraméterei az átlagos és a teljes (H) információs kapacitás. A paramétert a Shannon információs entrópia képlet segítségével számítjuk ki: , ahol p t annak a valószínűsége, hogy a gráf m csúcsai az i-edik típusba, vagy ekvivalenciaosztályba tartoznak, k; i = , Paraméter. A molekuláris szerkezetek, például a szervetlen klaszterek vagy Möbius-csíkok vizsgálata a megfelelő molekulagráfok izomorfizmusának megállapításához vezet úgy, hogy azokat komplex poliéderekbe (klaszterek esetén például poliéderekbe) vagy speciális poliéderekbe helyezzük (beágyazzuk). többdimenziós felületek (például Riemann felületek). A polimerek molekulagráfjainak elemzése, amelyek csúcsai a monomer egységeknek, élei pedig a közöttük lévő kémiai kötéseknek felelnek meg, lehetővé teszi például a kizárt térfogat hatásainak magyarázatát, ami a polimerek előrejelzett tulajdonságaiban minőségi változásokhoz vezet. .

Rizs. 3. Reakciógráfok: a-bipartit; a kinetika b-jelszintje; r 1, g2-r-tion; a1-a6-reagensek; k-sebesség állandók p-tsny; s-komplex Laplace transzformációs változó.
A gráfelméletet és a mesterséges intelligencia alapelveit felhasználva szoftvereket fejlesztettek ki a kémia információkereső rendszereihez, valamint automatizált rendszereket a molekulaszerkezetek azonosítására és a szerves szintézis racionális tervezésére. A kémiai átalakulások racionális útjainak retroszintetikus és szintonikus elvek alapján történő kiválasztására szolgáló műveletek számítógépen történő gyakorlati megvalósításához többszintű elágazó keresési gráfokat használnak a megoldási lehetőségekhez, amelyek csúcsai megfelelnek a reagensek és termékek molekuláris grafikonjainak, az ívek pedig az anyagok átalakulását ábrázolják.

Rizs. 4. Egykörös kémiai-technológiai rendszer és a hozzá tartozó grafikonok: a-szerkezeti diagram; b, c-anyagáramlási grafikonok, ill. a teljes tömegáram és az A komponens áramlási sebessége alapján; r - hőáramlási grafikon; ábra grafikonjainak elemzéséből nyert anyagmérleg egyenletrendszerének (f 1 - f 6) d-töredéke. 4, b és c; e-bipartit információs digráf; g-információs gráf, I-keverő; II-reaktor; III-desztillációs oszlop; IV-hűtőszekrény; I 1 -I 8 -technol. patakok; q-tömegáram; H az áramlás entalpiája; én. s és i*, s* - ill. az anyag- és hőáramlás valós és fiktív forrásai és nyelői; a reagens c-koncentrációja; V a reaktor térfogata.
A különböző vegyületek molekuláris gráfjainak mátrixábrázolásai (a megfelelő mátrixelemek átalakítása után) egyenértékűek a kvantumkémia mátrixmódszereivel. Ezért a gráfelméletet komplex kvantumkémiai számítások végzésekor alkalmazzák: molekuláris pályák számának, tulajdonságainak és energiáinak meghatározására, a konjugált alternatív és nem-alternáns poliének reaktivitásának előrejelzésére, az anyagok aromás és antiaromás tulajdonságainak azonosítására stb.
A nagyszámú részecskéből álló rendszerek zavarainak tanulmányozására a kémiai fizikában úgynevezett Feynman-diagramokat használnak - olyan gráfokat, amelyek csúcsai megfelelnek a fizikai részecskék elemi kölcsönhatásainak, az élek pedig az ütközések utáni útvonaluknak. Ezek a grafikonok különösen lehetővé teszik az oszcillációs reakciók mechanizmusainak tanulmányozását és a reakciórendszerek stabilitásának meghatározását.
A reagens molekulák átalakulásának racionális utak kiválasztásához ismert kölcsönhatások adott halmazához kétrészes reakciógráfokat használnak (a csúcsok a molekuláknak felelnek meg, és ezek a reakciók, az ívek a molekulák kölcsönhatásainak a reakcióban; 3,a ábra). Az ilyen grafikonok lehetővé teszik interaktív algoritmusok kidolgozását a kémiai átalakulások optimális útjainak kiválasztására, amelyek a legkisebb számú köztes reakciót, a minimális számú reagenst az elfogadhatók listájából, vagy a termékek legmagasabb hozamát érik el.
A reakciókinetikai egyenletek jelgrafikonjai kinetikai egyenletrendszereket jelenítenek meg algebrai operátor formában (3b. ábra). A grafikonok csúcsai az úgynevezett információs változóknak, vagyis jeleknek felelnek meg, reagenskoncentrációk, ívek formájában - a jelek összefüggéseinek, az ívek súlyát pedig kinetikai állandók határozzák meg. Az ilyen grafikonokat a komplex katalitikus reakciók mechanizmusainak és kinetikájának, a komplex vegyületek képződésének komplex fázisegyensúlyainak tanulmányozására, valamint az oldatok additív tulajdonságainak paramétereinek kiszámítására használják.
Alkalmazott problémák. A kémiai-technológiai rendszerek (CTS) elemzésének és optimalizálásának többdimenziós problémáinak megoldására a következő kémiai-technológiai gráfokat használjuk (4. ábra): áramlási, információáramlási, jel- és megbízhatósági gráfok. Az áramlási grafikonok, amelyek súlyozott digráfok, a fizikai áramlások össztömegáramára és egyes kémiai komponensek vagy elemek tömegáramára vonatkozó paraméteres, anyagi adatokat, valamint termikus grafikonokat tartalmaznak. A felsorolt ​​grafikonok az anyagok és az energia fizikai és kémiai átalakulásának felelnek meg egy adott kémiai rendszerben.
Paraméteres áramlási grafikonok a fizikai áramlások paramétereinek (tömegáram, stb.) CTS-elemek általi átalakítását mutatják be; a grafikonok csúcsai megfelelnek az eszközök matematikai modelljeinek, valamint a megadott áramlások forrásainak és nyelőinek, az ívek pedig maguknak az áramlásoknak, az ívek súlya pedig megegyezik az áramlások paramétereinek számával. megfelelő áramlást. A paraméteres gráfokat többkörös kémiai rendszerek technológiai módozatainak elemzésére szolgáló algoritmusok kidolgozására használják. Az ilyen algoritmusok létrehozzák bármely rendszer egyedi eszközeinek matematikai modelljeiből álló egyenletrendszerek számítási sorrendjét, hogy meghatározzák a kimeneti áramlások paramétereit a változó bemeneti áramlások ismert értékeivel.
Az anyagáramlási grafikonok a vegyi anyagokban lévő anyagok fogyasztásának változásait jelenítik meg. A grafikonok csúcsai azoknak az eszközöknek felelnek meg, amelyekben a fizikai áramlások össztömegáramát és egyes kémiai komponensek vagy elemek tömegáramát transzformálják, valamint az áramlások anyagainak vagy ezen összetevőknek a forrásait és nyelőit; Ennek megfelelően a grafikonok ívei bármely komponens fizikai áramlásának vagy fizikai és fiktív (az anyagok kémiai átalakulása a készülékekben) forrásainak és nyelőinek felelnek meg, és az ívek súlya megegyezik mindkét típus tömegáramlási sebességével. A hőáramlási grafikonok a hőegyensúlyt CTS-ben jelenítik meg; a grafikonok csúcsai megfelelnek azoknak az eszközöknek, amelyekben a fizikai áramlások hőfogyasztása változik, és ezen felül a rendszer hőenergia-forrásainak és nyelőinek; az ívek fizikai és fiktív (fizikai-kémiai energiaátalakítás az eszközökben) hőáramoknak felelnek meg, és az ívek súlya megegyezik az áramlások entalpiájával. Az anyag- és hőgráfokat olyan programok összeállítására használják, amelyek algoritmusok automatizált fejlesztésére szolgálnak összetett kémiai rendszerek anyag- és hőmérlegének egyenletrendszereinek megoldására.
Az információs-állomány grafikonok a CTS matematikai modelljeinek egyenletrendszereinek logikai-információs szerkezetét mutatják be; optimális algoritmusok kidolgozására szolgálnak ezeknek a rendszereknek a kiszámításához. A bipartit információs gráf (4. ábra, e) egy irányítatlan vagy orientált gráf, amelynek csúcsai megfelelnek az f l -f 6 egyenleteknek és a q 1 - V változóknak, az ágak pedig ezek kapcsolatát tükrözik. Információs gráf (4. ábra, g) - az egyenletek megoldásának sorrendjét ábrázoló digráf; a gráf csúcsai ezeknek az egyenleteknek, az XTS információ forrásainak és vevőinek, az ágak pedig információs változóknak felelnek meg.
A jelgráfok a kémiai technológiai folyamatok és rendszerek matematikai modelljeinek lineáris egyenletrendszereinek felelnek meg. A grafikonok csúcsai jeleknek (például hőmérsékletnek), az ágak pedig a köztük lévő kapcsolatoknak felelnek meg. Az ilyen grafikonok segítségével elemzik a többparaméteres folyamatok és kémiai rendszerek statikus és dinamikus módozatait, valamint számos legfontosabb tulajdonságuk (stabilitás, érzékenység, szabályozhatóság) mutatóit.
A megbízhatósági grafikonokat a vegyi berendezések megbízhatóságának különféle mutatóinak kiszámítására használják. Ezen gráfok számos csoportja közül (például parametrikus, logikai-funkcionális) különösen fontosak az úgynevezett hibafák. Minden ilyen fa egy súlyozott digráf, amely az egyes folyamatok és a CTS-eszközök sok egyszerű meghibásodásának összefüggéseit jeleníti meg, amelyek sok másodlagos meghibásodáshoz és a rendszer egészének ebből adódó meghibásodásához vezetnek.
Az optimális, rendkívül megbízható termelés (beleértve az erőforrás-megtakarítást) automatizált szintézisére szolgáló programkomplexumok létrehozásához a mesterséges intelligencia elveivel együtt, a CTS megoldási lehetőségek orientált szemantikai vagy szemantikai gráfjait használják. Ezek a grafikonok, amelyek adott esetben fák, racionális alternatív CTS-sémák halmazának generálására szolgáló eljárásokat mutatnak be (például 14 lehetséges, ha a céltermékek ötkomponensű keverékét rektifikálással választják el) és a köztük lévő sorrend szerinti kiválasztási eljárásokat. olyan sémát, amely a rendszer hatékonyságának valamilyen kritériuma szerint optimális.
stb.............

Sőt, élete utolsó 12 évében Euler súlyosan beteg volt, megvakult, és súlyos betegsége ellenére tovább dolgozott és alkotott.

A statisztikai számítások azt mutatják, hogy Euler átlagosan hetente egy felfedezést tett.

Nehéz olyan matematikai problémát találni, amellyel Euler munkái nem foglalkoztak.

A következő generációk minden matematikusa így vagy úgy tanult Eulerrel, és nem ok nélkül fordult elő, hogy a híres francia tudós P.S. Laplace azt mondta: „Olvasd Eulert, ő mindannyiunk tanítója.”

Lagrange azt mondja: "Ha igazán szereti a matematikát, olvassa el Euler-t; műveinek bemutatása figyelemre méltó az elképesztő tisztaságával és pontosságával." Valóban, számításainak eleganciáját a legmagasabb fokra vitték. Condorcet az Akadémián Euler emlékére mondott beszédét a következő szavakkal zárta: „Tehát Euler abbahagyta az életet és a számolgatást!” Számolni élni – milyen unalmasnak tűnik kívülről!

Szokás úgy képzelni, hogy egy matematikus száraz és süket minden mindennapi dologra, ami érdekli a hétköznapi embereket.

Az Eulerről elnevezett három ház és három kút problémája.

A topológia egyik ága. A gráf egy geometriai diagram, amely bizonyos pontokat összekötő vonalak rendszere. A pontokat csúcsoknak, az őket összekötő egyeneseket éleknek (vagy íveknek) nevezzük. Minden gráfelméleti probléma megoldható grafikus és mátrix formában is. Mátrix formájú írás esetén egy adott csúcsból a másikba üzenet továbbításának lehetőségét eggyel, a hiányát pedig nullával jelöljük.

A gráfelmélet eredete a 18. században. matematikai fejtörőkkel kötötték össze, de fejlődéséhez különösen erős lökést adott a XIX. században pedig főleg a 20. században, amikor felfedezték gyakorlati alkalmazási lehetőségeit: rádióelektronikai áramkörök számításához, megoldásához ún. szállítási feladatok, stb.. Az 50-es évektől. A gráfelméletet egyre gyakrabban használják a szociálpszichológiában és a szociológiában.

A gráfelmélet területén meg kell említeni F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss stb. A Szovjetunióban a T. g. M. Borodkin et al.

A Graph Theory nyelv kiválóan alkalmas különféle struktúrák elemzésére és állapotátvitelre. Ennek megfelelően a gráfelmélet segítségével megoldott szociológiai és szociálpszichológiai problémák alábbi típusait különböztethetjük meg.

Egy társadalmi objektum általános szerkezeti modelljének formalizálása és felépítése összetettségének különböző szintjein. Például egy szervezet szerkezeti diagramja, szociogramok, rokonsági rendszerek összehasonlítása különböző társadalmakban, csoportok szerepstruktúrájának elemzése stb.

Tekinthetjük, hogy a szerepstruktúra három összetevőt foglal magában: személyeket, beosztásokat (leegyszerűsített változatban - beosztások) és az adott pozícióban végzett feladatokat.

Mindegyik komponens ábrázolható grafikonként:

Lehetőség van arra, hogy mindhárom grafikont az összes pozícióhoz vagy csak egyhez kombináljuk, és ennek eredményeként világos képet kapunk a c.l sajátos szerkezetéről. ezt a szerepet. Így a P5 pozíció szerepére van egy grafikonunk (ábra). Az informális relációk a megadott formális struktúrába szövése jelentősen bonyolítja a gráfot, de a valóság pontosabb mása lesz.

a) mennyiségek. az egyén súlyának (státuszának) felmérése egy hierarchikus szervezetben. Az állapot meghatározásának egyik lehetséges lehetősége a képlet:

ahol r (p) egy bizonyos p személy státusza, k az alárendeltségi szint értéke, amely egy adott személytől a beosztottig tartó legkisebb lépések számaként definiálható, nk egy adott k szinten lévő személyek száma . Például az alábbiak által képviselt szervezetben. Szám:

tömeg a=1·2+2·7+3·4=28; 6=1·3+2·3=9 stb.

b) a csoportvezető meghatározása. A vezetőt általában a csoport többi tagjával való nagyobb kapcsolat jellemzi, mint másokkal. Az előző feladathoz hasonlóan itt is különböző módszerek használhatók a vezető azonosítására.

A legegyszerűbb módszert a következő képlet adja meg: r=Σdxy/Σdqx, azaz. annak hányadosa, hogy az egyes személyek és az összes többi távolság összegét elosztjuk egy adott egyénnek az összes többihez való távolságának összegével.

4) E rendszer tevékenységének eredményességének elemzése, amely olyan feladatokat is tartalmaz, mint a szervezet optimális struktúrájának felkutatása, a csoportkohézió növelése, a társadalmi rendszer elemzése a fenntarthatóság szempontjából; az információáramlás tanulmányozása (üzenetek továbbítása problémák megoldása során, a csoporttagok egymásra gyakorolt ​​hatása a csoport egyesítésének folyamatában); a technológia segítségével megoldják az optimális kommunikációs hálózat megtalálásának problémáját.

A gráfelméletre, valamint bármely matematikai apparátusra alkalmazva igaz, hogy a problémamegoldás alapelveit egy szubsztantív elmélet (jelen esetben a szociológia) határozza meg.

Feladat : Három szomszédnak három közös kútja van. Lehet-e nem keresztező utakat építeni minden háztól minden kúthoz? Az utak nem haladhatnak át kutakon és házakon (1. ábra).

Rizs. 1. A házak és kutak problémájához.

A probléma megoldására egy Euler által 1752-ben bizonyított tételt használunk, amely a gráfelmélet egyik fő tétele. Az első gráfelméleti munka Leonhard Euler (1736) nevéhez fűződik, bár a „gráf” kifejezést először König Dénes magyar matematikus vezette be 1936-ban. A grafikonokat diagramoknak nevezték, amelyek pontokból és az ezeket a pontokat összekötő egyenesek vagy görbék szakaszaiból álltak.

Tétel. Ha egy sokszög véges sok sokszögre van felosztva úgy, hogy a partíció bármely két sokszögének nincs közös pontja, vagy közös csúcsai vannak, vagy közös élei vannak, akkor az egyenlőség érvényes

B - P + G = 1, (*)

ahol B a csúcsok száma, P az élek teljes száma, G a sokszögek (lapok) száma.

Bizonyíték. Bizonyítsuk be, hogy az egyenlőség nem változik, ha egy adott partíció valamelyik sokszögébe átlót húzunk (2. ábra, a).

A) b)

Valóban, egy ilyen átló megrajzolása után az új partíciónak B csúcsa, P+1 éle lesz, és a sokszögek száma eggyel nő. Ezért van

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

Ezt a tulajdonságot felhasználva olyan átlókat rajzolunk, amelyek a bejövő sokszögeket háromszögekre bontják, és a kapott partícióra megmutatjuk a kapcsolat megvalósíthatóságát.

Ehhez egymás után eltávolítjuk a külső éleket, csökkentve a háromszögek számát. Ebben az esetben két eset lehetséges:

az ABC háromszög eltávolításához két élt kell eltávolítani, esetünkben az AB-t és a BC-t;

Az MKN háromszög eltávolításához el kell távolítania az egyik élt, esetünkben az MN-t.

Az egyenlőség mindkét esetben nem változik. Például az első esetben a háromszög eltávolítása után a gráf B-1 csúcsokból, P-2 élekből és G-1 sokszögből fog állni:

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

Így egy háromszög eltávolítása nem változtatja meg az egyenlőséget.

Folytatva a háromszögek eltávolításának folyamatát, végül eljutunk egy olyan partícióhoz, amely egyetlen háromszögből áll. Egy ilyen partíciónál B = 3, P = 3, G = 1, és ezért

Ez azt jelenti, hogy az egyenlőség az eredeti partícióra is érvényes, amiből végül azt kapjuk, hogy a reláció a sokszög ezen partíciójára is érvényes.

Vegyük észre, hogy az Euler-reláció nem függ a sokszögek alakjától. A sokszögek oldalai deformálhatók, nagyíthatók, kicsinyíthetők vagy akár meg is görbíthetők, amennyiben az oldalakon nincs hézag. Euler relációja nem fog változni.

Most folytassuk a három ház és három kút problémájának megoldását.

Megoldás. Tegyük fel, hogy ezt meg lehet tenni. Jelöljük a házakat D1, D2, D3 pontokkal, a kutakat pedig K1, K2, K3 pontokkal (1. ábra). Minden házpontot összekötünk minden kútponttal. Kilenc olyan élt kapunk, amelyek páronként nem metszik egymást.

Ezek az élek sokszöget alkotnak a síkon, kisebb sokszögekre osztva. Ezért ehhez a partícióhoz teljesülnie kell a B - P + G = 1 Euler-relációnak.

Adjunk hozzá még egy arcot a vizsgált lapokhoz - a sík külső részét a sokszöghez képest. Ekkor az Euler-reláció a B - P + G = 2 alakot ölti majd, ahol B = 6 és P = 9.

Ezért Г = 5. Mind az öt lapnak van legalább négy éle, mivel a probléma feltételei szerint egyik út sem köthet össze közvetlenül két házat vagy két kutat. Mivel minden él pontosan két oldalon fekszik, az élek számának legalább (5 4)/2 = 10-nek kell lennie, ami ellentmond annak a feltételnek, hogy számuk 9.

Az ebből eredő ellentmondás azt mutatja, hogy a problémára a válasz nemleges - nem lehet nem keresztező utakat rajzolni minden házból minden faluba

Gráfelmélet a kémiában

A gráfelmélet alkalmazása különböző osztályú kémiai és kémiai-technológiai gráfok felépítésére és elemzésére, amelyeket topológiának, modellnek is neveznek, i.e. modellek, amelyek csak a csúcsok közötti kapcsolatok jellegét veszik figyelembe. E gráfok ívei (élei) és csúcsai kémiai és kémiai-technológiai fogalmakat, jelenségeket, folyamatokat vagy tárgyakat, és ennek megfelelően minőségi és mennyiségi összefüggéseket, illetve ezek közötti bizonyos kapcsolatokat tükröznek.

Elméleti problémák. A kémiai gráfok lehetővé teszik a kémiai átalakulások előrejelzését, a lényeg magyarázatát és a kémia néhány alapfogalmának rendszerezését: szerkezet, konfiguráció, megerősítések, molekulák kvantummechanikai és statisztikai-mechanikai kölcsönhatásai, izoméria stb. kinetikai reakcióegyenletek. A sztereokémiában és a szerkezeti topológiában, a klaszterek, polimerek kémiájában stb. használt molekuláris gráfok irányítatlan gráfok, amelyek a molekulák szerkezetét jelenítik meg. E gráfok csúcsai és élei megfelelnek a megfelelő atomoknak és a köztük lévő kémiai kötéseknek.

A sztereokémiában org. c-c a leggyakrabban használt molekulafák - olyan molekuláris gráfok fái, amelyek csak az atomoknak megfelelő összes csúcsot tartalmazzák. A molekulafák halmazainak összeállítása és izomorfizmusuk megállapítása lehetővé teszi a molekulaszerkezetek meghatározását és az alkánok teljes izomerszámának meghatározását. alkének és alkinek. A molekuláris gráfok lehetővé teszik a különböző vegyületek molekuláinak kódolásával, nómenklatúrájával és szerkezeti jellemzőivel (elágazás, ciklikusság stb.) kapcsolatos problémák csökkentését a molekuláris gráfok és fáik tisztán matematikai jellemzőinek és tulajdonságainak elemzésére és összehasonlítására, valamint a hozzájuk tartozó mátrixokat. A molekulák szerkezete és a vegyületek fizikai-kémiai (beleértve a farmakológiai) tulajdonságai közötti összefüggések számának azonosítására több mint 20 ún. Molekulák (Wiener, Balaban, Hosoya, Plata, Randich stb.) topológiai indexei, melyek meghatározása molekulafák mátrixaival és numerikus jellemzőivel történik. Például a Wiener-index W = (m3 + m)/6, ahol m a C atomoknak megfelelő csúcsok száma, korrelál a molekulatérfogatokkal és a fénytörésekkel, a képződési entalpiákkal, viszkozitással, felületi feszültséggel, a vegyületek kromatográfiás állandóival, oktánszámmal. szénhidrogének száma és még fiziol . a drogok aktivitása. Az adott anyag tautomer formáinak és reaktivitásuk meghatározására, valamint az aminosavak, nukleinsavak, szénhidrátok és egyéb összetett természetes vegyületek osztályozásánál használt molekuláris gráfok fontos paraméterei az átlagos és a teljes (H) információs kapacitás. A polimerek molekulagráfjainak elemzése, amelyek csúcsai monomer egységeknek, élei pedig a köztük lévő kémiai kötéseknek felelnek meg, lehetővé teszi például a kizárt térfogat minőségekhez vezető hatásainak magyarázatát. változások a polimerek előrejelzett tulajdonságaiban. A gráfelmélet és a mesterséges intelligencia alapelveit felhasználva szoftvereket fejlesztettek ki a kémia információkereső rendszereihez, valamint automatizált rendszereket a molekulaszerkezetek azonosítására és a szerves szintézis racionális tervezésére. A racionális kémiai utak kiválasztására szolgáló műveletek számítógépen történő gyakorlati megvalósításához. A retroszintetikus és szintonikus elven alapuló transzformációk többszintű elágazó keresési gráfokat használnak a megoldási lehetőségekhez, amelyek csúcsai a reagensek és termékek molekuláris gráfjainak felelnek meg, az ívek pedig transzformációkat ábrázolnak.

A kémiai technológiai rendszerek (CTS) elemzésének és optimalizálásának többdimenziós problémáinak megoldására a következő kémiai technológiai gráfokat használjuk: áramlási, információáramlási, jel- és megbízhatósági gráfok. Kémiai tanulmányokhoz. A nagyszámú részecskéből álló rendszerek zavarfizikája az ún. A Feynman-diagramok olyan gráfok, amelyek csúcsai megfelelnek a fizikai részecskék elemi kölcsönhatásainak, az ütközések utáni útjuk éleinek. Ezek a grafikonok különösen lehetővé teszik az oszcillációs reakciók mechanizmusainak tanulmányozását és a reakciórendszerek stabilitásának meghatározását. a grafikonok csúcsai megfelelnek azoknak az eszközöknek, amelyekben a fizikai áramlások hőfogyasztása változik, és ezen felül a rendszer hőenergia-forrásainak és nyelőinek; az ívek fizikai és fiktív (fizikai-kémiai energiaátalakítás az eszközökben) hőáramoknak felelnek meg, és az ívek súlya megegyezik az áramlások entalpiájával. Az anyag- és hőgráfokat olyan programok összeállítására használják, amelyek algoritmusok automatizált fejlesztésére szolgálnak összetett kémiai rendszerek anyag- és hőmérlegének egyenletrendszereinek megoldására. Az információáramlási grafikonok a matematikai egyenletrendszerek logikai információszerkezetét jelenítik meg. XTS modellek; optimális algoritmusok kidolgozására szolgálnak ezeknek a rendszereknek a kiszámításához. A kétrészes információs gráf egy irányítatlan vagy irányított gráf, amelynek csúcsai rendre megfelelnek. fl -f6 egyenletek és q1 – V változók, az ágak pedig ezek kapcsolatát tükrözik. Információs gráf – az egyenletek megoldási sorrendjét ábrázoló digráf; a gráf csúcsai ezeknek az egyenleteknek, az XTS információ forrásainak és vevőinek, az ágak pedig az információnak felelnek meg. változók. A jelgráfok a kémiai technológiai folyamatok és rendszerek matematikai modelljeinek lineáris egyenletrendszereinek felelnek meg. A megbízhatósági grafikonok segítségével különféle X megbízhatósági mutatókat számítanak ki.

Felhasznált irodalom:

1.Berge K., T. g. és alkalmazása, francia fordítás, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, ford. angolból, 2. kiadás, M., 1963;

3.Ope O., Grafikonok és alkalmazásuk, ford. angolból, M., 1965;

4. Belykh O.V., Belyaev E.V., A szociológia alkalmazási lehetőségei a szociológiában, in: Man and Society, vol. 1, [L.], 1966;

5. Kvantitatív módszerek a szociológiai kutatásban, M., 1966; Belyaev E.V., A szociológiai mérések problémái, "VF", 1967, 7. sz.; Bavelas. Kommunikációs minták feladatorientált csoportokban, a könyvben. Lerner D., Lass well H., Political sciences, Stanford, 1951;

6. Kemeny J. G., Snell J., Matematikai modellek a társadalomtudományokban, N. Y., 1962; Filament C., A gráfelmélet alkalmazásai csoportstruktúrára, N. Y., 1963; Оeser Ο. A., Hararu F., Szerepstruktúrák és leírás a gráfelmélet szempontjából, a könyvben: Biddle V., Thomas E. J., Role theory: concepts and research, N. Y., 1966. E. Belyaev. Leningrád.