B – P + G = 1, (*)

čia B – bendras viršūnių skaičius, P – bendras briaunų skaičius, G – daugiakampių (veidų) skaičius.

Įrodymas. Įrodykime, kad lygybė nekinta, jei tam tikros skaidinio daugiakampyje nubrėžta įstrižainė (2 pav., a).

a) b)

2 pav

Išties, nubrėžus tokią įstrižainę, naujoji pertvara turės B viršūnes, P+1 briaunas, o daugiakampių skaičius padidės vienu. Todėl mes turime

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

Naudodamiesi šia savybe, nubrėžiame įstrižaines, kurios padalina gaunamus daugiakampius į trikampius, o gautoje skaidinyje parodome ryšio pagrįstumą.

Norėdami tai padaryti, nuosekliai pašalinsime išorines briaunas, sumažindami trikampių skaičių. Šiuo atveju galimi du atvejai:

norint pašalinti trikampį ABC, reikia pašalinti dvi briaunas, mūsų atveju AB ir BC;

Norėdami pašalinti trikampį MKN, turite pašalinti vieną kraštą, mūsų atveju MN.

Abiem atvejais lygybė nepasikeis. Pavyzdžiui, pirmuoju atveju, pašalinus trikampį, grafiką sudarys B-1 viršūnės, P-2 briaunos ir G-1 daugiakampis:

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

Taigi, pašalinus vieną trikampį, lygybė nekeičiama.

Tęsdami šį trikampių pašalinimo procesą, galiausiai pasieksime skaidinį, sudarytą iš vieno trikampio. Tokiai pertvarai B = 3, P = 3, G = 1 ir todėl

B – P + G = 1.

Tai reiškia, kad lygybė galioja ir pirminiam skirsniui, iš kurio galiausiai gauname, kad santykis galioja šiai daugiakampio daliai.

Atkreipkite dėmesį, kad Eulerio ryšys nepriklauso nuo daugiakampių formos. Daugiakampiai gali būti deformuoti, padidinti, sumažinti ar net išlenkti savo šonus, jei tik šonuose nėra tarpų. Eulerio santykis nepasikeis.

Dabar pereikime prie trijų namų ir trijų šulinių problemos sprendimo.

Sprendimas . Tarkime, kad tai galima padaryti. Namus pažymėkime taškais D1, D2, D3, o šulinius – K1, K2, K3 (1 pav.). Kiekvieną namo tašką sujungiame su kiekvienu šulinio tašku. Gauname devynias briaunas, kurios nesikerta poromis.

Šios briaunos sudaro daugiakampį plokštumoje, padalintą į mažesnius daugiakampius. Todėl šiam skirsniui turi būti tenkinamas Eulerio santykis B - P + G = 1.

Prie nagrinėjamų veidų pridėkime dar vieną veidą – išorinę plokštumos dalį daugiakampio atžvilgiu. Tada Eulerio santykis bus B - P + G = 2, kai B = 6 ir P = 9.

Todėl Г = 5. Kiekvienas iš penkių paviršių turi bent keturias briaunas, nes, atsižvelgiant į problemos sąlygas, nė vienas kelias neturi tiesiogiai sujungti dviejų namų ar dviejų šulinių. Kadangi kiekviena briauna yra lygiai dviejuose paviršiuose, briaunų skaičius turi būti bent (5 4)/2 = 10, o tai prieštarauja sąlygai, kad jų skaičius yra 9.

Atsiradęs prieštaravimas rodo, kad atsakymas į problemą yra neigiamas - Neįmanoma nubrėžti nesusikertančių takų nuo kiekvieno namo iki kiekvieno kaimo

Grafų teorija chemijoje

Grafų teorijos taikymas kuriant ir analizuojant įvairių klasių cheminius ir cheminius-technologinius grafikus, kurie dar vadinami topologija, modeliais, t.y. modeliai, kuriuose atsižvelgiama tik į jungčių tarp viršūnių pobūdį. Šių grafikų lankai (briaunos) ir viršūnės atspindi chemines ir chemines-technologines sąvokas, reiškinius, procesus ar objektus ir atitinkamai kokybinius bei kiekybinius ryšius arba tam tikrus ryšius tarp jų.

Teorinės problemos. Cheminiai grafikai leidžia numatyti chemines transformacijas, paaiškinti esmę ir susisteminti kai kurias pagrindines chemijos sąvokas: struktūrą, konfigūraciją, patvirtinimus, kvantinę mechaninę ir statistinę-mechaninę molekulių sąveiką, izomerizmą ir kt. Cheminiai grafikai apima molekulinius, dvišalius ir signalinius grafikus. kinetinės reakcijos lygtis. Molekuliniai grafikai, naudojami stereochemijoje ir struktūrinėje topologijoje, klasterių, polimerų chemijoje ir kt., yra neorientuoti grafikai, rodantys molekulių struktūrą. Šių grafikų viršūnės ir briaunos atitinka atitinkamus atomus ir cheminius ryšius tarp jų.

Stereochemijos org. c-c dažniausiai naudojami molekuliniai medžiai – aprėpiantys molekulinių grafikų medžiai, kuriuose yra tik visos atomus atitinkančios viršūnės. Molekulinių medžių rinkinių sudarymas ir jų izomorfizmo nustatymas leidžia nustatyti molekulines struktūras ir rasti bendrą alkanų izomerų skaičių. alkenai ir alkinai. Molekuliniai grafikai leidžia sumažinti problemas, susijusias su įvairių junginių molekulių kodavimu, nomenklatūra ir struktūriniais ypatumais (išsišakojimu, cikliškumu ir kt.), iki grynai matematinių molekulinių grafų ir jų medžių savybių ir savybių analizės ir palyginimo, taip pat juos atitinkančias matricas. Molekulių struktūros ir junginių fizikinių ir cheminių (taip pat ir farmakologinių) savybių koreliacijų skaičiui nustatyti buvo sukurta daugiau nei 20 vadinamųjų. Molekulių (Wiener, Balaban, Hosoya, Plata, Randich ir kt.) topologiniai indeksai, kurie nustatomi naudojant molekulinių medžių matricas ir skaitines charakteristikas. Pavyzdžiui, Wienerio indeksas W = (m3 + m)/6, kur m yra viršūnių skaičius, atitinkantis C atomus, koreliuoja su molekulių tūriais ir lūžiais, susidarymo entalpija, klampumu, paviršiaus įtempimu, junginių chromatografinėmis konstantomis, oktanu. angliavandenilių skaičius ir net fiziolis . narkotikų aktyvumas. Svarbūs molekulinių grafikų parametrai, naudojami tam tikros medžiagos tautomerinėms formoms ir jų reaktyvumui nustatyti, taip pat aminorūgščių, nukleino rūgščių, angliavandenių ir kitų sudėtingų natūralių junginių klasifikacijoje yra vidutinė ir bendroji (H) informacinė talpa. Polimerų molekulinių grafikų, kurių viršūnės atitinka monomerų vienetus, o briaunos atitinka cheminius ryšius tarp jų, analizė leidžia paaiškinti, pavyzdžiui, išskirtinio tūrio, lemiančio savybes, poveikį. prognozuojamų polimerų savybių pokyčiai. Taikant Grafų teoriją ir dirbtinio intelekto principus, sukurta programinė įranga informacijos paieškos sistemoms chemijoje, taip pat automatizuotos sistemos molekulinėms struktūroms identifikuoti ir racionaliai planuoti organinę sintezę. Už praktinį racionalių cheminių kelių parinkimo operacijų įgyvendinimą kompiuteryje. retrosintetiniais ir sintoniniais principais pagrįstose transformacijose sprendinių variantams naudojami kelių lygių šakotosios paieškos grafikai, kurių viršūnės atitinka reagentų ir produktų molekulinius grafikus, o lankai vaizduoja transformacijas.

Daugiamatėms cheminių technologinių sistemų (CTS) analizės ir optimizavimo problemoms spręsti naudojami šie cheminiai technologiniai grafikai: srauto, informacijos srauto, signalų ir patikimumo grafikai. Dėl chemijos studijų. Sistemų, susidedančių iš daugybės dalelių, trikdžių fizikoje naudojama vadinamoji. Feynmano diagramos – tai grafikai, kurių viršūnės atitinka elementariąsias fizikinių dalelių sąveikas, jų takų briaunas po susidūrimų. Visų pirma, šie grafikai leidžia ištirti virpesių reakcijų mechanizmus ir nustatyti reakcijų sistemų stabilumą. Šiluminio srauto grafikai rodo šilumos balansą CTS; grafikų viršūnės atitinka įrenginius, kuriuose kinta fizikinių srautų šilumos suvartojimas, be to, sistemos šiluminės energijos šaltinius ir kriaukles; lankai atitinka fizikinius ir fiktyvius (fizinės-cheminės energijos konversijos įrenginiuose) šilumos srautus, o lankų svoriai lygūs srautų entalpijoms. Medžiagų ir šiluminiai grafikai naudojami sudėtingų cheminių sistemų medžiagų ir šilumos balansų lygčių sistemų sprendimo algoritmų automatizuoto kūrimo programoms sudaryti. Informacijos srauto grafikai atvaizduoja matematinių lygčių sistemų loginę informacijos struktūrą. XTS modeliai; yra naudojami kuriant optimalius šių sistemų skaičiavimo algoritmus. Dvišalis informacinis grafikas yra nenukreiptas arba nukreiptas grafikas, kurio viršūnės atitinkamai atitinka. lygtys fl -f6 ir kintamieji q1 – V, o šakos atspindi jų ryšį. Informacinis grafikas – dviženklis, vaizduojantis lygčių sprendimo tvarką; grafiko viršūnės atitinka šias lygtis, XTS informacijos šaltinius ir imtuvus, o šakos – informaciją. kintamieji. Signalų grafikai atitinka cheminių technologinių procesų ir sistemų matematinių modelių tiesines lygčių sistemas. Patikimumo grafikai naudojami įvairiems patikimumo rodikliams X apskaičiuoti.

Naudota literatūra:

1.Berge K., T. g ir jo taikymas, vertimas iš prancūzų kalbos, M., 1962;

2. Kemeny J., Snell J., Thompson J., Įvadas į baigtinę matematiką, vert. iš anglų k., 2 leidimas, M., 1963 m.;

3.Ope O., Grafikai ir jų taikymas, vert. iš anglų k., M., 1965;

4. Belykh O.V., Belyaev E.V., Sociologijos taikymo sociologijoje galimybės, in: Žmogus ir visuomenė, t. 1, [L.], 1966;

5. Kiekybiniai metodai sociologiniuose tyrimuose, M., 1966; Belyaev E.V., Sociologinių matavimų problemos, "VF", 1967, Nr. 7; Bavelas. Bendravimo modeliai į užduotis orientuotose grupėse, knygoje. Lerner D., Lass Well H., Political sciences, Stanford, 1951;

SAVIVALDYBĖS AUTONOMINĖ UGDYMO ĮSTAIGOS VIDURINĖ MOKYKLA Nr.

Parengta

Legkokonets Vladislav, 10A klasės mokinys

Praktinis grafų teorijos taikymas

Prižiūrėtojas

L.I. Noskova, matematikos mokytoja

Bryukhovetskaya str

2011 m

1. Įvadas…………………………………………………………………………………….………….3

2. Grafų teorijos atsiradimo istorija……………………………………………….………..4

3. Grafų teorijos pagrindiniai apibrėžimai ir teoremos…………………………………………6

4. Uždaviniai, sprendžiami naudojant grafikus……………………………..………………………..8

4.1 Įžymios problemos……………………………………………………………8

4.2 Kelios įdomios problemos…………………………………………………..9

5. Grafų taikymas įvairiose žmonių gyvenimo srityse…………………………………11

6. Problemų sprendimas…………………………………………………………………………………………12

7. Išvada………………………………………………………………………………….13

8. Literatūros sąrašas………….………………………………………………………………14

9. Priedas……………………………………………………………………………….…………15

Įvadas

Gimusi sprendžiant galvosūkius ir linksmus žaidimus, grafų teorija dabar tapo paprasta, prieinama ir galinga įrankiu sprendžiant klausimus, susijusius su įvairiausiomis problemomis. Grafikai tiesiogine prasme yra visur. Grafikų pavidalu galite, pavyzdžiui, interpretuoti kelių žemėlapius ir elektros grandines, geografinius žemėlapius ir cheminių junginių molekules, ryšius tarp žmonių ir žmonių grupių. Per pastaruosius keturis dešimtmečius grafų teorija tapo viena iš sparčiausiai besivystančių matematikos šakų. Tai lemia sparčiai besiplečiančios taikymo srities poreikiai. Jis naudojamas projektuojant integrinius grandynus ir valdymo grandines, tiriant automatus, logines grandines, programų blokines diagramas, ekonomikoje ir statistikoje, chemijoje ir biologijoje, planavimo teorijoje. Štai kodėl aktualumą Temą, viena vertus, lemia grafų ir su jais susijusių tyrimo metodų populiarumas, kita vertus, neišplėtota, holistinė jos įgyvendinimo sistema.

Daugelio gyvenimo problemų sprendimas reikalauja ilgų skaičiavimų, o kartais ir šie skaičiavimai neatneša sėkmės. Štai ką tyrimo problema. Kyla klausimas: ar įmanoma rasti paprastą, racionalų, trumpą ir elegantišką sprendimą joms išspręsti. Ar lengviau išspręsti problemas, jei naudojate grafikus? Tai nulėmė mano tyrimo tema: „Grafų teorijos praktinis pritaikymas“

Tikslas Tyrimo tikslas buvo naudoti grafikus, siekiant išmokti greitai išspręsti praktines problemas.

Tyrimo hipotezė. Grafo metodas yra labai svarbus ir plačiai naudojamas įvairiose mokslo ir žmogaus veiklos srityse.

Tyrimo tikslai:

1. Studijuokite literatūrą ir interneto šaltinius šia tema.

2.Patikrinti grafo metodo efektyvumą sprendžiant praktines problemas.

3. Padarykite išvadą.

Praktinė tyrimo reikšmė yra tai, kad rezultatai neabejotinai sukels daugelio žmonių susidomėjimą. Ar nė vienas iš jūsų nebandė kurti savo šeimos medžio? Kaip tai padaryti teisingai? Transporto įmonės vadovui, gabenant prekes iš paskirties vietos į kelias gyvenvietes, greičiausiai tenka spręsti pelningesnio transporto naudojimo problemą. Kiekvienas moksleivis susidūrė su loginėmis transfuzijos problemomis. Pasirodo, jas nesunkiai galima išspręsti naudojant grafikus.

Darbe naudojami šie metodai: stebėjimas, paieška, atranka, analizė.

Grafų teorijos istorija

Grafų teorijos pradininku laikomas matematikas Leonhardas Euleris (1707-1783). Šios teorijos istoriją galima atsekti per didžiojo mokslininko susirašinėjimą. Štai lotyniško teksto vertimas, paimtas iš Eulerio laiško italų matematikui ir inžinieriui Marinoni, atsiųsto iš Sankt Peterburgo 1736 m. kovo 13 d.

„Kažkada man buvo pateikta problema dėl salos, esančios Karaliaučiaus mieste ir apsuptos upės su septyniais tiltais per ją.

[Priedas 1 pav.] Kyla klausimas, ar kas nors gali juos apeiti nuolat, per kiekvieną tiltą pervažiuodamas tik vieną kartą. Ir tada man buvo pranešta, kad niekas to dar negalėjo padaryti, bet niekas neįrodė, kad tai neįmanoma. Šis klausimas, nors ir nereikšmingas, man atrodė vertas dėmesio, nes jam išspręsti neužtenka nei geometrijos, nei algebros, nei kombinatorinio meno. Po ilgų svarstymų radau nesudėtingą taisyklę, pagrįstą visiškai įtikinamu įrodymu, kurios pagalba visose tokio pobūdžio problemose galima iš karto nustatyti, ar tokį apvažiavimą galima padaryti per bet kokį skaičių ir bet kokį tiltų skaičių. ar ne. Koenigsbergo tiltai yra išdėstyti taip, kad juos būtų galima pavaizduoti toliau pateiktame paveikslėlyje [Priedas 2 pav.], kurioje A žymi salą, o B, C ir D – žemyno dalis, atskirtas viena nuo kitos upės šakomis

Apie metodą, kurį jis atrado tokio pobūdžio problemoms spręsti, Euleris rašė:

„Šis sprendimas pagal savo pobūdį, matyt, mažai susijęs su matematika, ir aš nesuprantu, kodėl šio sprendimo reikia tikėtis iš matematiko, o ne iš bet kurio kito žmogaus, nes šis sprendimas pagrįstas vien samprotavimu, o Norint rasti šį sprendimą, yra kokių nors matematikai būdingų dėsnių. Taigi, aš nežinau, kaip paaiškėja, kad klausimus, kurie labai mažai susiję su matematika, greičiausiai išspręs matematikai nei kiti.

Taigi ar galima apeiti Karaliaučiaus tiltus, pravažiavus tik vieną kartą per kiekvieną iš šių tiltų? Norėdami rasti atsakymą, tęskime Eulerio laišką Marinoniui:

"Klausimas yra nustatyti, ar galima apvažiuoti visus šiuos septynis tiltus, per kiekvieną pravažiuojant tik vieną kartą, ar ne. Mano taisyklė veda prie tokio šio klausimo sprendimo. Pirmiausia reikia pasižiūrėti, kiek atkarpų yra atskirti vandeniu - tokie , kurie neturi kito perėjimo iš vieno į kitą, išskyrus per tiltą Šiame pavyzdyje yra keturios tokios sekcijos - A, B, C, D. Toliau reikia atskirti, ar skaičius tiltų, vedančių į šias atskiras atkarpas, yra lyginis arba nelyginis. Taigi mūsų atveju penki tiltai veda į A ruožą, o trys tiltai veda į likusias dalis, t. Užtenka išspręsti problemą. pradėti šį apvažiavimą iš bet kurios atkarpos. viena iš tų dviejų sekcijų, į kurias veda nelyginis tiltų skaičius. Jei pagaliau būtų daugiau nei dvi atkarpos, į kurias veda nelyginis tiltų skaičius, tai toks judėjimas apskritai neįmanomas... jei čia būtų galima atnešti kitų, rimtesnių problemų, šis metodas galėtų būti dar didesnis ir turėtų būti naudingas. nereikia pamiršti“.

Grafų teorijos pagrindiniai apibrėžimai ir teoremos

Grafo teorija – matematikų pastangomis sukurta matematinė disciplina, todėl jos pateikimas apima būtinus griežtus apibrėžimus. Taigi, pereikime prie organizuoto pagrindinių šios teorijos sąvokų įvado.

1 apibrėžimas. Grafas – tai baigtinio skaičiaus taškų, vadinamų grafo viršūnėmis, ir kai kurias iš šių viršūnių jungiančių porinių linijų, vadinamų grafo kraštinėmis arba lankais, rinkinys.

Šis apibrėžimas gali būti suformuluotas skirtingai: grafikas yra netuščia taškų (viršūnių) ir atkarpų (kraštų) rinkinys, kurių abu galai priklauso tam tikrai taškų rinkiniui.

Toliau grafo viršūnes pažymėsime lotyniškomis raidėmis A, B, C, D. Kartais visas grafikas žymimas viena didžiąja raide.

2 apibrėžimas. Jokiai briaunai nepriklausančios grafo viršūnės vadinamos izoliuotomis.

3 apibrėžimas. Grafas, susidedantis tik iš izoliuotų viršūnių, vadinamas nuliniu - skaičiuoti .

Žymėjimas: O "– grafikas su viršūnėmis, neturintis briaunų

4 apibrėžimas. Grafas, kuriame kiekviena viršūnių pora yra sujungta briauna, vadinamas užbaigtu.

Pavadinimas: U" – grafas, susidedantis iš n viršūnių ir briaunų, jungiančių visas įmanomas šių viršūnių poras. Tokį grafiką galima pavaizduoti kaip n kampą, kuriame nubrėžtos visos įstrižainės

5 apibrėžimas. Viršūnės laipsnis yra briaunų, kurioms ta viršūnė priklauso, skaičius.

6 apibrėžimas. Grafas, kurio visų k viršūnių laipsniai yra vienodi, vadinamas vienalyčių laipsnių grafiku .

7 apibrėžimas. Pateikto grafo papildinys yra grafikas, susidedantis iš visų kraštinių ir jų galų, kuriuos reikia pridėti prie pradinio grafiko, kad būtų gautas pilnas grafas.

8 apibrėžimas. Grafas, kurį plokštumoje galima pavaizduoti taip, kad jo briaunos susikerta tik viršūnėse, vadinamas plokštuminiu.

9 apibrėžimas. Plokščiojo grafo daugiakampis, kuriame nėra jokių grafo viršūnių ar briaunų, vadinamas jo paviršiumi.

Sprendžiant įvairių žemėlapių „teisingo“ spalvinimo uždavinius, naudojamos plokštumos grafiko ir grafo veido sąvokos.

10 apibrėžimas. Kelias A iki X yra briaunų seka, vedanti nuo A iki X taip, kad kas dvi gretimos briaunos turi bendrą viršūnę ir nė viena briauna nepasitaiko daugiau nei vieną kartą.

11 apibrėžimas. Ciklas yra kelias, kuriame pradžios ir pabaigos taškai sutampa.

12 apibrėžimas. Paprastas ciklas yra ciklas, kuris nepereina per bet kurią grafo viršūnę daugiau nei vieną kartą.

13 apibrėžimas. Kelio ilgis , paguldytas ant kilpos , vadinamas šio kelio briaunų skaičius.

14 apibrėžimas. Dvi viršūnės A ir B grafe vadinamos sujungtomis (atjungtomis), jei yra (nėra) kelias, vedantis iš A į B.

15 apibrėžimas. Grafas vadinamas sujungtu, jei kas dvi jo viršūnės yra sujungtos; jei grafe yra bent viena nesusijusių viršūnių pora, tai grafikas vadinamas atjungtu.

16 apibrėžimas. Medis yra sujungtas grafikas, kuriame nėra ciklų.

Trimatis medžio grafiko modelis yra, pavyzdžiui, tikras medis su įmantriai išsišakojusia laja; upė ir jos intakai taip pat sudaro medį, bet jau plokščią - žemės paviršiuje.

17 apibrėžimas. Atjungtas grafikas, sudarytas tik iš medžių, vadinamas mišku.

18 apibrėžimas. Medis, kuriame visos n viršūnių sunumeruotos nuo 1 iki n, vadinamas medžiu su pernumeruotomis viršūnėmis.

Taigi, mes išnagrinėjome pagrindinius grafų teorijos apibrėžimus, be kurių būtų neįmanoma įrodyti teoremų ir, atitinkamai, išspręsti uždavinius.

Uždaviniai sprendžiami naudojant grafikus

Įžymios problemos

Keliaujančio pardavėjo problema

Keliaujančio pardavėjo problema yra viena iš žinomiausių kombinatorikos teorijos problemų. Jis buvo pateiktas 1934 m., o geriausi matematikai sulaužė dantis.

Problemos teiginys yra toks.
Keliaujantis pardavėjas (klajojantis pirklys) turi palikti pirmąjį miestą, vieną kartą nežinia tvarka aplankyti miestus 2,1,3..n ir grįžti į pirmą miestą. Atstumai tarp miestų žinomi. Kokia tvarka reikia apeiti miestus, kad uždaras keliaujančio pardavėjo kelias (ekskursija) būtų trumpiausias?

Keliaujančio pardavėjo problemos sprendimo būdas

Godus algoritmas „Eik į artimiausią (į kurį dar neįžengei) miestą“.
Šis algoritmas vadinamas „godžiu“, nes paskutiniuose žingsniuose už godumą reikia stipriai sumokėti.
Apsvarstykite, pavyzdžiui, tinklą paveikslėlyje [Priedas 3 pav.], vaizduojantis siaurą rombą. Tegul keliaujantis pardavėjas pradeda nuo 1 miesto. Algoritmas „eiti į artimiausią miestą“ nuves jį į 2 miestą, tada 3, tada 4; paskutiniame žingsnyje turėsite sumokėti už savo godumą, grįždami palei ilgą deimanto įstrižainę. Rezultatas bus ne trumpiausias, o ilgiausias turas.

Problema dėl Karaliaučiaus tiltų.

Problema suformuluota taip.
Koenigsbergo miestas yra ant Pregelio upės ir dviejų salų krantų. Įvairios miesto dalys buvo sujungtos septyniais tiltais. Sekmadieniais miestelėnai pasivaikščiodavo po miestą. Klausimas: ar galima pasivaikščioti taip, kad išėję iš namų grįžtumėte per kiekvieną tiltą eidami lygiai vieną kartą?
Tiltai per Pregelio upę yra kaip paveikslėlyje[Priedas 1 pav.].

Apsvarstykite grafiką, atitinkantį tilto diagramą [Priedas 2 pav.].

Norint atsakyti į problemos klausimą, pakanka išsiaiškinti, ar grafikas yra Eulerio. (Porinis tiltų skaičius turi tęstis bent iš vienos viršūnės). Negali vaikščioti po miestą ir vieną kartą pereiti visų tiltų ir grįžti atgal.

Keletas įdomių užduočių

1. „Maršrutai“.

1 problema

Kaip prisimenate, mirusių sielų medžiotojas Čičikovas kartą aplankė garsius dvarininkus. Jis juos aplankė tokia tvarka: Manilovas, Korobočka, Nozdryovas, Sobakevičius, Pliuškinas, Tentetnikovas, generolas Betriščevas, Petukas, Konstanzholgo, pulkininkas Koškarevas. Buvo rasta schema, kurioje Čičikovas nubrėžė dvarų ir jas jungiančių krašto kelių santykines padėtis. Nustatykite, kuri dvaras kam priklauso, jei Čičikovas nevažiavo jokiu keliu daugiau nei vieną kartą [Priedas 4 pav.].

Sprendimas:

Kelių žemėlapis rodo, kad Čičikovas savo kelionę pradėjo nuo E valdos, o baigė dvaru O. Pastebime, kad į valdas B ir C veda tik du keliai, todėl Čičikovas turėjo keliauti šiais keliais. Pažymėkime juos paryškinta linija. Išskirtos trasos atkarpos, einančios per A: AC ir AB. Čičikovas nevažiavo keliais AE, AK ir AM. Perbraukime juos. Pažymėkime paryškinta linija ED; Perbraukime DK. Nubraukime MO ir MN; Pažymėkime paryškinta linija MF; išbraukti FO; Pažymėkime FH, NK ir KO paryškinta linija. Suraskime vienintelį įmanomą maršrutą tokiomis sąlygomis. Ir mes gauname: dvaras E - priklauso Manilovui, D - Korobochka, C - Nozdrevas, A - Sobakevičius, B - Plyushkin, M - Tentetnikov, F - Betriščevas, N - Petuchas, K - Konstanzholgo, O - Koshkarev. [Priedas 5 pav.].

2 problema

Paveikslėlyje parodytas vietovės žemėlapis [Priedas 6 pav.].

Galite judėti tik rodyklių kryptimi. Kiekviename taške galite apsilankyti ne daugiau kaip vieną kartą. Keliais būdais galite patekti iš taško 1 į tašką 9? Kuris maršrutas trumpiausias, o kuris ilgiausias.

Sprendimas:

Mes nuosekliai „sluoksniuojame“ grandinę į medį, pradedant nuo 1 viršūnės [Priedas 7 pav.]. Paimkime medį. Galimų būdų gauti nuo 1 iki 9 skaičius yra lygus medžio „kabančių“ viršūnių skaičiui (jų yra 14). Akivaizdu, kad trumpiausias kelias yra 1-5-9; ilgiausias yra 1-2-3-6-5-7-8-9.

2 "Grupės, pažintys"

1 problema

Muzikos festivalio dalyviai, susitikę, apsikeitė vokais su adresais. Įrodykite, kad:

a) buvo įteiktas lyginis vokų skaičius;

b) nelyginį skaičių kartų keitusių vokus dalyvių skaičius yra lyginis.

Sprendimas: Tegul festivalio dalyviai būna A 1, A 2, A 3. . . , Ir n yra grafo viršūnės, o briaunos jungia viršūnių poras, vaizduojančias vokais besikeičiančius vyrukus. [Priedas 8 pav.]

Sprendimas:

a) kiekvienos viršūnės A i laipsnis parodo vokų, kuriuos dalyvis A i davė savo draugams, skaičių. Bendras perduotų vokų skaičius N lygus visų grafo viršūnių laipsnių sumai N = laipsnis. 1+ žingsnis. A 2++. . . + žingsnis. A n -1 + laipsnis. Ir n, N =2p, kur p – grafiko briaunų skaičius, t.y. N – lygus. Vadinasi, buvo įteiktas lyginis vokų skaičius;

b) lygybėje N = laipsnis. 1+ žingsnis. A 2++. . . + žingsnis. A n -1 + laipsnis. Ir n nelyginių narių suma turi būti lyginė, ir tai gali būti tik tada, jei nelyginių narių skaičius yra lyginis. Tai reiškia, kad nelyginį skaičių kartų keitusių vokus dalyvių skaičius yra lyginis.

2 problema

Vieną dieną Andrejus, Borisas, Volodia, Daša ir Galya sutiko vakare eiti į kiną. Kino ir pasirodymo pasirinkimą jie nusprendė derinti telefonu. Taip pat buvo nuspręsta, kad jei nepavyks su kuo nors susisiekti telefonu, kelionė į kiną bus atšaukta. Vakare ne visi susirinko į kiną, todėl apsilankymas filme buvo atšauktas. Kitą dieną jie pradėjo aiškintis, kas kam skambino. Paaiškėjo, kad Andrejus vadino Borisą ir Volodiją, Volodiją vadino Borisu ir Daša, Borisą vadino Andrejumi ir Daša, Dašą vadino Andrejumi ir Volodya, o Galiją vadino Andrejumi, Volodia ir Borisu. Kas negalėjo susisiekti telefonu ir dėl to neatvyko į susitikimą?

Sprendimas:

Nubrėžkime penkis taškus ir pažymėkime juos raidėmis A, B, C, D, D. Tai pirmosios vardų raidės. Sujunkime taškelius, atitinkančius skambinusių vaikinų vardus.

[Priedas 9 pav.]

Iš nuotraukos aišku, kad kiekvienas iš vaikinų - Andrejus, Borisas ir Volodia - skambino visiems kitiems. Štai kodėl šie vaikinai ir atėjo į kiną. Bet Galya ir Dasha negalėjo susikalbėti telefonu (taškai G ir E nėra sujungti linijos atkarpa) ir todėl pagal susitarimą neatvyko į kiną.

Grafų taikymas įvairiose žmonių gyvenimo srityse

Be pateiktų pavyzdžių, grafikai plačiai naudojami statybose, elektrotechnikoje, vadybos, logistikos, geografijos, mechanikos inžinerijos, sociologijos, programavimo, technologinių procesų ir gamybos automatizavimo, psichologijos, reklamos srityse.

Bet kurioje mokslo ir technologijų srityje susiduriate su grafikais. Grafikai yra nuostabūs matematiniai objektai, su kuriais galite spręsti matematines, ekonomines ir logines problemas, įvairius galvosūkius ir supaprastinti fizikos, chemijos, elektronikos, automatikos uždavinių sąlygas. Daugelį matematinių faktų galima patogiai suformuluoti grafų kalba. Grafų teorija yra daugelio mokslų dalis. Grafų teorija yra viena gražiausių ir vaizdingiausių matematinių teorijų. Pastaruoju metu grafų teorija randa vis daugiau pritaikymų taikomosiose problemose. Atsirado net kompiuterinė chemija – gana jauna chemijos sritis, paremta grafų teorijos taikymu.

Molekuliniai grafikai, naudojami stereochemijoje ir struktūrinėje topologijoje, klasterių chemijoje, polimeruose ir kt., yra neorientuoti grafikai, rodantys molekulių struktūrą [Priedas 10 pav.]. Šių grafikų viršūnės ir briaunos atitinka atitinkamus atomus ir cheminius ryšius tarp jų.

Molekuliniai grafikai ir medžiai: [Priedas 10 pav.] a, b - atitinkamai multigrafai. etilenas ir formaldehidas; jie sako pentano izomerai (4, 5 medžiai yra izomorfiški 2 medžiui).

Organizmų stereochemijoje labiausiai. Dažnai naudojami molekuliniai medžiai – pagrindiniai molekulinių grafų medžiai, kuriuose yra tik visos viršūnės, atitinkančios C atomus. Molų rinkinių kompiliacija. medžiai ir jų izomorfizmo nustatymas leidžia nustatyti, kad jie sako. struktūras ir rasti bendrą alkanų, alkenų ir alkinų izomerų skaičių

Baltymų tinklai

Baltymų tinklai yra fiziškai sąveikaujančių baltymų grupės, kurios veikia ląstelėje kartu ir koordinuotai, kontroliuojant tarpusavyje susijusius procesus, vykstančius organizme. [priedas pav. 11].

Hierarchinis sistemos grafikas vadinamas medžiu. Išskirtinis medžio bruožas yra tas, kad tarp bet kurių dviejų jo viršūnių yra tik vienas kelias. Medyje nėra ciklų ar kilpų.

Paprastai hierarchinę sistemą reprezentuojantis medis turi vieną pagrindinę viršūnę, kuri vadinama medžio šaknimi. Kiekviena medžio viršūnė (išskyrus šaknį) turi tik vieną protėvį – jos nurodytas objektas yra įtrauktas į vieną aukščiausio lygio klasę. Bet kuri medžio viršūnė gali generuoti keletą palikuonių – viršūnių, atitinkančių žemesnio lygio klases.

Kiekvienai medžio viršūnių porai yra unikalus kelias, jungiantis jas. Ši savybė naudojama ieškant visų protėvių, pavyzdžiui, vyriškoje linijoje, bet kurio asmens, kurio kilmė pavaizduota šeimos medžio pavidalu, kuris yra „medis“ grafų teorijos prasme.

Mano šeimos medžio pavyzdys [Priedas 12 pav.].

Kitas pavyzdys. Nuotraukoje pavaizduotas biblinis šeimos medis [Priedas 13 pav.].

Problemų sprendimas

1.Transportavimo užduotis. Tegul Krasnodaro mieste yra bazė su žaliavomis, kurias reikia išdalyti Krymo, Temriuko, Slavjansko prie Kubano ir Timaševsko miestams per vieną kelionę, sugaišant kuo mažiau laiko ir kuro ir grįžtant atgal į Krasnodarą. .

Sprendimas:

Pirma, padarykime visų galimų kelionės maršrutų grafiką [Priedas 14 pav.], atsižvelgiant į tikrus kelius tarp šių gyvenviečių ir atstumą tarp jų. Norėdami išspręsti šią problemą, turime sukurti kitą grafiką, panašų į medį [Priedas 15 pav.].

Sprendimo patogumui miestus nurodome numeriais: Krasnodaras - 1, Krymskas - 2, Temryukas - 3, Slavjanskas - 4, Timaševskas - 5.

Rezultatas yra 24 sprendimai, bet mums reikia tik trumpiausių kelių. Iš visų sprendimų tenkina tik du, tai yra 350 km.

Panašiai galima ir, manau, būtina apskaičiuoti faktinį pervežimą iš vienos vietovės į kitą.

Loginė problema, susijusi su transfuzija. Kibire yra 8 litrai vandens, yra dvi 5 ir 3 litrų talpos keptuvės. į penkių litrų talpos keptuvę reikia supilti 4 litrus vandens, o kibire palikti 4 litrus, t.y. vandens pilti po lygiai į kibirą ir didelę keptuvę.

Sprendimas:

Situaciją bet kuriuo momentu galima apibūdinti trimis skaičiais [Priedas 16 pav.].

Rezultate gauname du sprendimus: vieną iš 7 ėjimų, kitą – per 8 judesius.

Išvada

Taigi, norint išmokti spręsti problemas, reikia suprasti, kas jos yra, kaip jos sudarytos, iš kokių komponentų susideda, kokiais įrankiais problemos sprendžiamos.

Sprendžiant praktines problemas naudojant grafų teoriją, paaiškėjo, kad kiekviename žingsnyje, kiekviename jų sprendimo etape būtina taikyti kūrybiškumą.

Nuo pat pradžių, pirmajame etape, tai slypi tame, kad reikia mokėti analizuoti ir užkoduoti problemos būklę. Antrasis etapas yra schematinis žymėjimas, kurį sudaro geometrinis grafikų atvaizdavimas, o šiame etape kūrybiškumo elementas yra labai svarbus, nes toli gražu nėra lengva rasti atitikmenis tarp sąlygos elementų ir atitinkamų elementų. grafiką.

Spręsdamas transporto problemą ar užduotį sudaryti giminės medį, priėjau išvados, kad grafo metodas tikrai įdomus, gražus ir vaizdingas.

Įsitikinau, kad grafikai plačiai naudojami ekonomikoje, vadyboje ir technologijose. Grafų teorija taip pat naudojama programuojant Tai šiame darbe nebuvo aptarta, bet manau, kad tai tik laiko klausimas.

Šiame moksliniame darbe nagrinėjami matematiniai grafikai, jų taikymo sritys, sprendžiama keletas uždavinių naudojant grafikus. Grafų teorijos pagrindų žinios būtinos įvairiose su gamyba ir verslo valdymu susijusiose srityse (pavyzdžiui, tinklo tiesimo grafikas, pašto pristatymo grafikai). Be to, dirbdamas mokslinį darbą įvaldžiau darbą kompiuteriu, naudodamas WORD teksto rengyklę. Taigi mokslinio darbo tikslai pasiekti.

Taigi iš viso to, kas išdėstyta aukščiau, nenuginčijamai išplaukia praktinė grafų teorijos vertė, kurios įrodymas buvo šio darbo tikslas.

Literatūra

Bergė K. Grafų teorija ir jos taikymai. -M.: IIL, 1962 m.

Kemeny J., Snell J., Thompson J.Įvadas į baigtinę matematiką. -M.: IIL, 1963 m.

Rūda O. Grafikai ir jų taikymas. -M.: Mir, 1965 m.

Harari F. Grafų teorija. -M.: Mir, 1973 m.

Zykovas A.A. Baigtinių grafų teorija. -Novosibirskas: mokslas, 1969 m.

Berezina L.Yu. Grafikai ir jų taikymas. -M.: Išsilavinimas, 1979. -144 p.

„Soro edukacinis žurnalas“ Nr. 1996 11 (straipsnis „Plokštieji grafikai“);

Gardner M. „Matematinis laisvalaikis“, M. „Pasaulis“, 1972 (35 skyrius);

Olehnik S. N., Nesterenko Yu., Potapov M. K. „Senos pramoginės problemos“, M. „Mokslas“, 1988 (2 dalis, 8 skyrius; 4 priedas);

Taikymas

Taikymas

P

Ryžiai. 6

Ryžiai. 7

Ryžiai. 8

Taikymas

Taikymas

Taikymas

P

Ryžiai. 14

Taikymas

Santrauka aukštoji matematika šia tema:

Grafų teorijos taikymas chemijoje

Atlieka studentas iš grupės NH-202

Maskva 2011 m
Grafikai yra baigtinės matematikos sritis, tirianti atskiras struktūras; naudojami įvairiems teoriniams ir taikomiesiems uždaviniams spręsti.
Kai kurie pagrindinės sąvokos. Grafas – tai taškų (viršūnių) ir šių taškų porų (nebūtinai visų) rinkinys, sujungtas linijomis (1 pav., a). Jei grafike linijos yra orientuotos (tai yra rodyklės rodo viršūnių jungimosi kryptį), jos vadinamos lankais arba šakomis; jei neorientuotas, - briaunos. Atitinkamai, grafikas, kuriame yra tik lankai, vadinamas nukreiptu grafiku, arba dviženkliu; tik neorientuotas į kraštą; lankai ir šonkauliai – sumaišyti. Grafas, turintis kelias briaunas, vadinamas multigrafu; grafas, kuriame yra tik briaunos, priklausančios dviems jo disjunktiniams poaibiams (dalims), yra dvišalis; lankai (kraštai) ir (arba) viršūnės, atitinkančios tam tikrus svorius ar bet kokių parametrų skaitines reikšmes, yra pasverti. Kelias grafe – tai kintama viršūnių ir lankų seka, kurioje nė viena viršūnė nesikartoja (pavyzdžiui, a, b 1,a pav.); kontūras – uždaras kelias, kurio pirmoji ir paskutinė viršūnės sutampa (pavyzdžiui, f, h); kilpa – lankas (kraštas), kuris prasideda ir baigiasi toje pačioje viršūnėje. Grafo kelias – tai briaunų seka, kurioje nesikartoja nė viena viršūnė (pavyzdžiui, c, d, e); ciklas – uždara grandinė, kurios pradinė ir galutinė viršūnės sutampa. Grafas vadinamas sujungtu, jei bet kuri jo viršūnių pora yra sujungta grandine arba keliu; kitu atveju grafikas vadinamas atjungtu.
Medis yra sujungtas neorientuotas grafikas, kuriame nėra ciklų ar kontūrų (1 pav., b). Grafo apimantis pografis yra jo poaibis, kuriame yra visos viršūnės ir tik tam tikros briaunos. Grafo aprėpiamasis medis yra jo aprėpiamasis pografas, kuris yra medis. Grafai vadinami izomorfiniais, jei tarp jų viršūnių ir briaunų (lankų) aibių yra vienas su vienu atitikimas.
Grafų teorijos ir jos pritaikymo uždaviniams spręsti grafikai vaizduojami naudojant matricas (gretimos, dažnumo, dvieilės ir kt.), taip pat specialiąsias. skaitinės charakteristikos. Pavyzdžiui, gretimų matricoje (1c pav.) eilutės ir stulpeliai atitinka grafiko viršūnių skaičius, o jos elementai turi reikšmes 0 ir 1 (atitinkamai, lanko nebuvimas ir buvimas tarp duotoji viršūnių pora); kritimo matricoje (1d pav.) eilutės atitinka viršūnių skaičius, stulpeliai atitinka lankų skaičius, o elementai turi reikšmes 0, + 1 ir - 1 (atitinkamai nebuvimas , lanko, įeinančio ir išeinančio iš viršūnės, buvimas). Dažniausios skaitinės charakteristikos: viršūnių skaičius (m), lankų arba briaunų skaičius (n), ciklomatinis skaičius arba grafo rangas (n - m + k, kur k yra sujungtų pografų skaičius atjungtas grafikas, pavyzdžiui, 1 pav. grafikui b rangas bus: 10-6+ 1 =5).
Grafų teorijos taikymas remiasi įvairių klasių cheminių ir cheminių-technologinių grafų, kurie dar vadinami topologiniais modeliais, konstravimu ir analize, t.y. modeliai, kuriuose atsižvelgiama tik į jungčių tarp viršūnių pobūdį. Šių grafikų lankuose (kraštuose) ir viršūnėse atvaizduojamos cheminės ir cheminės-technologinės sąvokos, reiškiniai, procesai ar objektai ir atitinkamai kokybiniai ir kiekybiniai ryšiai arba tam tikri santykiai tarp jų.

Ryžiai. 1. Kai kurių pagrindinių sąvokų iliustracija: a-mišrus grafikas; b-tempiamasis medis (vientisieji lankai a, h, d, f, h) ir tam tikras dviračio pografas (brūkšniniai lankai c, e, g, k, l); c, r-matricos resp. digrafo gretimumas ir dažnumas.
Teorinės problemos. Cheminiai grafikai leidžia numatyti chemines transformacijas, paaiškinti esmę ir susisteminti kai kurias pagrindines chemijos sąvokas: struktūrą, konfigūraciją, konformacijas, kvantinę mechaninę ir statistinę-mechaninę molekulių sąveiką, izomerizmą ir kt. Cheminiai grafikai apima molekulinius, dvišalius ir signalinius grafikus. kinetinės reakcijos lygtis.
Molekuliniai grafikai, naudojami stereochemijoje ir struktūrinėje topologijoje, klasterių, polimerų chemijoje ir kt., yra neorientuoti grafikai, rodantys molekulių struktūrą (2 pav.). Šių grafikų viršūnės ir briaunos atitinkamai atitinka atomus ir cheminius ryšius tarp jų.

Ryžiai. 2. Molekuliniai grafikai ir medžiai: a, b - atitinkamai multigrafai. etilenas ir formaldehidas; jie sako pentano izomerai (4, 5 medžiai yra izomorfiški 2 medžiui).
Organinių medžiagų stereochemijoje dažniausiai naudojami molekuliniai medžiai - apimantys molekulinių grafikų medžius, kuriuose yra tik visos C atomus atitinkančios viršūnės (2 pav., a ir b). Molekulinių medžių rinkinių sudarymas ir jų izomorfizmo nustatymas leidžia nustatyti molekulines struktūras ir rasti bendrą alkanų, alkenų ir alkinų izomerų skaičių (2 pav., c).
Molekuliniai grafikai leidžia sumažinti problemas, susijusias su įvairių junginių molekulių kodavimu, nomenklatūra ir struktūriniais ypatumais (išsišakojimu, cikliškumu ir kt.), iki grynai matematinių molekulinių grafų ir jų medžių savybių ir savybių analizės ir palyginimo, taip pat juos atitinkančias matricas. Siekiant nustatyti kiekybines molekulių struktūros ir junginių fizikinių ir cheminių (taip pat ir farmakologinių) savybių koreliacijas, buvo sukurta daugiau nei 20 tūkstančių molekulių topologinių indeksų pavadinimų (Wiener, Balaban, Hosoya, Plat, Randich ir kt.), kurie yra nustatomi naudojant molekulinių medžių matricas ir skaitines charakteristikas. Pavyzdžiui, Wienerio indeksas W = (m 3 + m)/6, kur m yra viršūnių, atitinkančių C atomus, skaičius, koreliuoja su molekulių tūriais ir lūžiais, formavimosi entalpijomis, klampumu, paviršiaus įtempimu, junginių chromatografinėmis konstantomis, angliavandenilių oktaniniai skaičiai ir netgi fiziologinis vaistų aktyvumas.
Svarbūs molekulinių grafikų parametrai, naudojami tam tikros medžiagos tautomerinėms formoms ir jų reaktyvumui nustatyti, taip pat aminorūgščių, nukleino rūgščių, angliavandenių ir kitų sudėtingų natūralių junginių klasifikacijoje yra vidutinės ir bendrosios (H) informacijos talpos. Parametras apskaičiuojamas naudojant Šenono informacijos entropijos formulę: , kur p t – tikimybė, kad grafo viršūnės m priklauso i-tajam tipui, arba ekvivalentiškumo klasei, k; i = , Parametras. Molekulinių struktūrų, tokių kaip neorganiniai klasteriai ar Möbius juostelės, tyrimas susijęs su atitinkamų molekulinių grafų izomorfizmo nustatymu, įterpiant juos į sudėtingus daugiakampius (pavyzdžiui, daugiakampius klasterių atveju) arba specialius. daugiamačiai paviršiai (pavyzdžiui, Riemann paviršiai). Polimerų molekulinių grafikų, kurių viršūnės atitinka monomerų vienetus, o briaunos – cheminius ryšius tarp jų, analizė leidžia paaiškinti, pavyzdžiui, pašalinto tūrio poveikį, lemiantį kokybinius numatomų polimerų savybių pokyčius. .

Ryžiai. 3. Reakcijų grafikai: a-dvišalė; b-signalo kinetikos lygis; r 1, g2 -r-tionas; a1 -a 6 -reagentai; k-greičio konstantos p-tsny; s komplekso Laplaso transformacijos kintamasis.
Naudojant grafų teoriją ir dirbtinio intelekto principus, sukurta programinė įranga informacijos paieškos sistemoms chemijoje, taip pat automatizuotos sistemos molekulinėms struktūroms identifikuoti ir racionaliai planuoti organinę sintezę. Praktiniam operacijų, skirtų racionalių cheminių transformacijų kelių parinkimo retrosintetiniais ir sintoniniais principais, įgyvendinimui kompiuteryje naudojami daugiapakopiai šakotieji tirpalo variantų paieškos grafikai, kurių viršūnės atitinka reagentų ir produktų molekulinius grafikus, o lankai vaizduoja medžiagų virsmus.

Ryžiai. 4. Viengrandė cheminė-technologinė sistema ir atitinkami grafikai: a-struktūrinė diagrama; b, c-medžiagos srauto grafikai, atitinkamai. pagal bendrą masės srautą ir A komponento srautą; r - terminio srauto grafikas; medžiagų balanso lygčių sistemos (f 1 - f 6) d-fragmentas, gautas išanalizavus grafikus pav. 4, b ir c; e-dvišalis informacijos dvibalsis; g-informacinis grafikas, I-mikseris; II-reaktorius; III-distiliavimo kolonėlė; IV-šaldytuvas; I 1 -I 8 -technol. upeliai; q-masės srautas; H yra srauto entalpija; i. s ir i*, s* - atitinkamai. tikri ir fiktyvūs medžiagų ir šilumos srautų šaltiniai ir kriauklės; c-reagento koncentracija; V yra reaktoriaus tūris.
Įvairių junginių molekulinių grafikų matriciniai atvaizdavimai yra lygiaverčiai (transformavus atitinkamus matricos elementus) kvantinės chemijos matriciniams metodams. Todėl grafų teorija naudojama atliekant sudėtingus kvantinius cheminius skaičiavimus: nustatyti molekulinių orbitų skaičių, savybes ir energijas, numatant konjuguotų alternantinių ir nealternantinių polienų reaktyvumą, identifikuojant aromatines ir antiaromatines medžiagų savybes ir kt.
Trikdžiams tirti sistemose, susidedančiose iš daugybės dalelių cheminėje fizikoje, naudojamos vadinamosios Feynmano diagramos – grafikai, kurių viršūnės atitinka elementarias fizikinių dalelių sąveikas, kraštai – jų kelius po susidūrimų. Visų pirma, šie grafikai leidžia ištirti virpesių reakcijų mechanizmus ir nustatyti reakcijų sistemų stabilumą.
Norint parinkti racionalius reagentų molekulių transformacijos kelius tam tikrai žinomų sąveikų rinkiniui, naudojami dvišaliai reakcijų grafikai (viršūnės atitinka molekules ir šias reakcijas, lankai atitinka molekulių sąveikas reakcijoje; 3,a pav.). Tokie grafikai leidžia sukurti interaktyvius algoritmus, leidžiančius parinkti optimalius cheminių virsmų kelius, kuriems reikia mažiausio tarpinių reakcijų skaičiaus, minimalaus reagentų skaičiaus iš priimtinų sąrašo arba pasiekti didžiausią produktų išeigą.
Reakcijų kinetikos lygčių signalų grafikai atvaizduoja kinetinių lygčių sistemas, pateiktas algebrinio operatoriaus forma (3b pav.). Grafų viršūnės atitinka vadinamuosius informacinius kintamuosius, arba signalus, reagentų koncentracijų pavidalu, lankus – signalų ryšius, o lankų svoriai nustatomi kinetinėmis konstantomis. Tokie grafikai naudojami tiriant kompleksinių katalizinių reakcijų mechanizmus ir kinetiką, kompleksinių fazių pusiausvyrą susidarant kompleksiniams junginiams, taip pat skaičiuojant tirpalų adityvinių savybių parametrus.
Taikomos problemos. Daugiamatėms cheminių-technologinių sistemų (CTS) analizės ir optimizavimo problemoms spręsti naudojami šie cheminiai-technologiniai grafikai (4 pav.): srauto, informacijos srauto, signalo ir patikimumo grafikai. Srauto grafikai, kurie yra svertiniai digrafai, apima parametrinius, medžiagą pagal bendrus fizinių srautų masės srautus ir kai kurių cheminių komponentų ar elementų masės srautus, taip pat terminius grafikus. Pateikti grafikai atitinka fizikinius ir cheminius medžiagų ir energijos virsmus tam tikroje cheminėje sistemoje.
Parametrinių srautų grafikai rodo fizinių srautų parametrų (masių srautų ir kt.) transformaciją pagal CTS elementus; grafikų viršūnės atitinka prietaisų matematinius modelius, taip pat nurodytų srautų šaltinius ir kriaukles, o lankai – pačius srautus, o lankų svoriai lygūs srauto parametrų skaičiui. atitinkamas srautas. Parametriniai grafikai naudojami kelių grandinių cheminių sistemų technologinių režimų analizės algoritmams kurti. Tokie algoritmai nustato bet kurios sistemos atskirų įrenginių matematinių modelių lygčių sistemų skaičiavimo seką, kad nustatytų jos išėjimo srautų parametrus su žinomomis kintamųjų įvesties srautų reikšmėmis.
Medžiagų srauto grafikai rodo cheminių medžiagų suvartojimo pokyčius. Grafikų viršūnės atitinka įrenginius, kuriuose transformuojami bendrieji fizikinių srautų masės srautai ir kai kurių cheminių komponentų ar elementų masės srautai, taip pat srautų ar šių komponentų medžiagų šaltiniai ir kriauklės; Atitinkamai, grafikų lankai atitinka fizinius srautus arba fizinius ir fiktyvius (cheminės medžiagų transformacijos aparatuose) bet kokių komponentų šaltinius ir kriaukles, o lankų svoriai yra lygūs abiejų tipų masės srautams. Šiluminio srauto grafikai rodo šilumos balansą CTS; grafikų viršūnės atitinka įrenginius, kuriuose kinta fizikinių srautų šilumos suvartojimas, be to, sistemos šiluminės energijos šaltinius ir kriaukles; lankai atitinka fizikinius ir fiktyvius (fizinės-cheminės energijos konversijos įrenginiuose) šilumos srautus, o lankų svoriai lygūs srautų entalpijoms. Medžiagų ir šiluminiai grafikai naudojami sudėtingų cheminių sistemų medžiagų ir šilumos balansų lygčių sistemų sprendimo algoritmų automatizuoto kūrimo programoms sudaryti.
Informaciniai grafikai atvaizduoja CTS matematinių modelių lygčių sistemų loginę-informacinę struktūrą; yra naudojami kuriant optimalius šių sistemų skaičiavimo algoritmus. Dvišalis informacinis grafikas (4 pav., e) – tai nenukreiptas arba orientuotas grafikas, kurio viršūnės atitinka atitinkamai lygtis f l -f 6 ir kintamuosius q 1 - V, o šakos – jų ryšį. Informacinis grafikas (4 pav., g) - dviženklis, vaizduojantis lygčių sprendimo tvarką; grafiko viršūnės atitinka šias lygtis, XTS informacijos šaltinius ir imtuvus, o šakos – informacinius kintamuosius.
Signalų grafikai atitinka cheminių technologinių procesų ir sistemų matematinių modelių tiesines lygčių sistemas. Grafų viršūnės atitinka signalus (pavyzdžiui, temperatūrą), o šakos – ryšius tarp jų. Tokie grafikai naudojami analizuojant daugiaparametrų procesų ir cheminių sistemų statinius ir dinaminius režimus, taip pat daugelio svarbiausių jų savybių (stabilumo, jautrumo, valdomumo) rodiklius.
Patikimumo grafikai naudojami įvairiems cheminės įrangos patikimumo rodikliams apskaičiuoti. Tarp daugybės šių grafikų grupių (pavyzdžiui, parametrinių, loginių-funkcinių) ypač svarbūs vadinamieji gedimų medžiai. Kiekvienas toks medis yra svertinis digrafas, rodantis daugelio paprastų atskirų procesų ir CTS įrenginių gedimų, dėl kurių atsiranda daug antrinių gedimų ir dėl to visos sistemos gedimų, tarpusavio ryšį.
Kuriant programų kompleksus, skirtus optimaliai labai patikimai gamybai automatizuotai sintezei (įskaitant išteklių taupymą), kartu su dirbtinio intelekto principais naudojami orientuoti semantiniai arba semantiniai CTS sprendimo variantų grafikai. Šiuose grafikuose, kurie konkrečiu atveju yra medžiai, pavaizduotos racionalių alternatyvių CTS schemų rinkinio generavimo procedūros (pavyzdžiui, 14 galima, kai ištaisant išskiriamas penkių komponentų tikslinių produktų mišinys) ir užsakyto pasirinkimo tarp jų procedūros. schema, kuri yra optimali pagal tam tikrą sistemos efektyvumo kriterijų.
ir tt............

Be to, pastaruosius 12 savo gyvenimo metų Euleris sunkiai sirgo, apako ir, nepaisant sunkios ligos, toliau dirbo ir kūrė.

Statistiniai skaičiavimai rodo, kad Euleris vidutiniškai padarė vieną atradimą per savaitę.

Sunku rasti matematinę problemą, kuri nebuvo nagrinėjama Eulerio darbuose.

Visi vėlesnių kartų matematikai vienaip ar kitaip mokėsi su Euleriu, ir ne be reikalo garsus prancūzų mokslininkas P.S. Laplasas pasakė: „Paskaityk Eulerį, jis yra mūsų visų mokytojas“.

Lagranžas sako: "Jei tikrai mylite matematiką, skaitykite Eulerį; jo darbų pristatymas yra nuostabus dėl savo nuostabaus aiškumo ir tikslumo." Iš tiesų, jo skaičiavimų elegancija buvo pasiekta aukščiausiu laipsniu. Condorcetas savo kalbą akademijoje Eulerio atminimui baigė šiais žodžiais: „Taigi Euleris nustojo gyventi ir skaičiuoti! Gyventi tam, kad skaičiuotum – kaip tai atrodo nuobodu iš šalies!

Įprasta įsivaizduoti, kad matematikas yra sausas ir kurčias viskam, kas kasdienybė, tam, kas domina paprastus žmones.

Eulerio vardu pavadinta trijų namų ir trijų šulinių problema.

Viena iš topologijos šakų. Grafas yra geometrinė diagrama, kuri yra linijų, jungiančių tam tikrus taškus, sistema. Taškai vadinami viršūnėmis, o juos jungiančios linijos – briaunomis (arba lankais). Visos grafų teorijos problemos gali būti sprendžiamos tiek grafine, tiek matricine forma. Rašant matricine forma, galimybė perduoti pranešimą iš tam tikros viršūnės į kitą žymima vienetu, o jo nebuvimas – nuliu.

Grafo teorijos atsiradimas XVIII a. siejamas su matematiniais galvosūkiais, tačiau ypač stiprų postūmį jo plėtrai davė XIX a. ir daugiausia 20 a., kai buvo atrastos jo praktinio pritaikymo galimybės: radioelektroninėms grandinėms skaičiuoti, sprendžiant vadinamąsias. transporto užduotys ir kt. Nuo 50 m. Grafų teorija vis dažniau naudojama socialinėje psichologijoje ir sociologijoje.

Grafų teorijos srityje paminėtini F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss darbai ir kt. SSRS pagal T. g. M. Borodkin ir kt.

Grafų teorijos kalba puikiai tinka įvairioms struktūroms analizuoti ir būsenoms perduoti. Remiantis tuo, galime išskirti šiuos sociologinių ir socialinių-psichologinių problemų tipus, sprendžiamus naudojant grafų teoriją.

Socialinio objekto bendro struktūrinio modelio įforminimas ir konstravimas įvairiuose jo sudėtingumo lygiuose. Pavyzdžiui, organizacijos struktūrinė schema, sociogramos, skirtingose ​​visuomenėse giminystės sistemų palyginimas, grupių vaidmenų struktūros analizė ir kt.

Galime manyti, kad vaidmenų struktūra apima tris komponentus: asmenis, pareigas (supaprastintame variante – pareigas) ir užduotis, atliekamas tam tikroje pozicijoje.

Kiekvienas komponentas gali būti pavaizduotas kaip grafikas:

Galima sujungti visus tris grafikus visoms pozicijoms arba tik vienai, ir dėl to gauname aiškų supratimą apie specifinę c.l struktūrą. šį vaidmenį. Taigi, padėties P5 vaidmeniui turime grafiką (pav.). Neformalių santykių įpynimas į nurodytą formalią struktūrą gerokai apsunkins grafiką, tačiau tai bus tikslesnė tikrovės kopija.

a) kiekiai. vertinant individo svorį (statusą) hierarchinėje organizacijoje. Viena iš galimų būsenos nustatymo parinkčių yra formulė:

čia r (p) yra tam tikro asmens p statusas, k yra pavaldumo lygio reikšmė, apibrėžiama kaip mažiausias žingsnių skaičius nuo konkretaus asmens iki jo pavaldinio, nk yra asmenų skaičius tam tikrame lygyje k . Pavyzdžiui, organizacijoje, kuriai atstovauja toliau. Skaičiavimas:

svoris a=1·2+2·7+3·4=28; 6=1·3+2·3=9 ir kt.

b) grupės vadovo nustatymas. Lyderiui paprastai būdingas didesnis ryšys su likusia grupe, palyginti su kitais. Kaip ir ankstesnėje užduotyje, čia taip pat gali būti naudojami įvairūs lyderio nustatymo metodai.

Paprasčiausias būdas pateikiamas formule: r=Σdxy/Σdqx, t.y. koeficientas, padalijus kiekvieno asmens visų atstumų iki visų kitų atstumų sumos iš konkretaus individo atstumų iki visų kitų.

4) Šios sistemos veiklos efektyvumo analizė, kuri apima ir tokius uždavinius kaip optimalios organizacijos struktūros paieška, grupės sanglaudos didinimas, socialinės sistemos analizė jos tvarumo požiūriu; informacijos srautų tyrimas (pranešimų perdavimas sprendžiant problemas, grupės narių įtaka vieni kitiems grupės vienijimosi procese); technologijų pagalba jie išsprendžia optimalaus ryšio tinklo suradimo problemą.

Taikant grafų teoriją, kaip ir bet kuriam matematiniam aparatui, tiesa, pagrindinius problemos sprendimo principus nustato esminė teorija (šiuo atveju sociologija).

Užduotis : Trys kaimynai turi tris bendrus šulinius. Ar galima nuo kiekvieno namo iki kiekvieno šulinio nutiesti nesikertančius takus? Takai negali praeiti per šulinius ir namus (1 pav.).

Ryžiai. 1. Prie namų ir šulinių problemos.

Norėdami išspręsti šią problemą, naudosime Eulerio 1752 metais įrodytą teoremą, kuri yra viena iš pagrindinių grafų teorijoje. Pirmasis darbas apie grafų teoriją priklauso Leonhardui Euleriui (1736), nors terminą „grafas“ 1936 m. pirmą kartą įvedė vengrų matematikas Dénesas Königas. Grafikai buvo vadinami diagramomis, susidedančiomis iš taškų ir tiesių linijų arba kreivių, jungiančių šiuos taškus, atkarpų.

Teorema. Jei daugiakampis yra padalintas į baigtinį daugiakampių skaičių taip, kad bet kurie du skaidinio daugiakampiai arba neturi bendrų taškų, turi bendrų viršūnių arba turi bendrų briaunų, tada galioja lygybė

B – P + G = 1, (*)

čia B – bendras viršūnių skaičius, P – bendras briaunų skaičius, G – daugiakampių (veidų) skaičius.

Įrodymas. Įrodykime, kad lygybė nekinta, jei tam tikros skaidinio daugiakampyje nubrėžta įstrižainė (2 pav., a).

A) b)

Išties, nubrėžus tokią įstrižainę, naujoji pertvara turės B viršūnes, P+1 briaunas, o daugiakampių skaičius padidės vienu. Todėl mes turime

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

Naudodamiesi šia savybe, nubrėžiame įstrižaines, kurios padalina gaunamus daugiakampius į trikampius, o gautoje skaidinyje parodome ryšio pagrįstumą.

Norėdami tai padaryti, nuosekliai pašalinsime išorines briaunas, sumažindami trikampių skaičių. Šiuo atveju galimi du atvejai:

norint pašalinti trikampį ABC, reikia pašalinti dvi briaunas, mūsų atveju AB ir BC;

Norėdami pašalinti trikampį MKN, turite pašalinti vieną kraštą, mūsų atveju MN.

Abiem atvejais lygybė nepasikeis. Pavyzdžiui, pirmuoju atveju, pašalinus trikampį, grafiką sudarys B-1 viršūnės, P-2 briaunos ir G-1 daugiakampis:

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

Taigi, pašalinus vieną trikampį, lygybė nekeičiama.

Tęsdami šį trikampių pašalinimo procesą, galiausiai pasieksime skaidinį, sudarytą iš vieno trikampio. Tokiai pertvarai B = 3, P = 3, G = 1 ir todėl

Tai reiškia, kad lygybė galioja ir pradiniam skirsniui, iš kurio galiausiai gauname, kad santykis galioja šiai daugiakampio skaidiniams.

Atkreipkite dėmesį, kad Eulerio ryšys nepriklauso nuo daugiakampių formos. Daugiakampiai gali būti deformuoti, padidinti, sumažinti ar net išlenkti savo šonus, jei tik šonuose nėra tarpų. Eulerio santykis nepasikeis.

Dabar pereikime prie trijų namų ir trijų šulinių problemos sprendimo.

Sprendimas. Tarkime, kad tai galima padaryti. Namus pažymėkime taškais D1, D2, D3, o šulinius – K1, K2, K3 (1 pav.). Kiekvieną namo tašką sujungiame su kiekvienu šulinio tašku. Gauname devynias briaunas, kurios nesikerta poromis.

Šios briaunos sudaro daugiakampį plokštumoje, padalintą į mažesnius daugiakampius. Todėl šiam skirsniui turi būti tenkinamas Eulerio santykis B - P + G = 1.

Prie nagrinėjamų veidų pridėkime dar vieną veidą – išorinę plokštumos dalį daugiakampio atžvilgiu. Tada Eulerio santykis bus B - P + G = 2, kai B = 6 ir P = 9.

Todėl Г = 5. Kiekvienas iš penkių paviršių turi bent keturias briaunas, nes, atsižvelgiant į problemos sąlygas, nė vienas kelias neturi tiesiogiai sujungti dviejų namų ar dviejų šulinių. Kadangi kiekviena briauna yra lygiai dviejuose paviršiuose, briaunų skaičius turi būti bent (5 4)/2 = 10, o tai prieštarauja sąlygai, kad jų skaičius yra 9.

Atsiradęs prieštaravimas rodo, kad atsakymas į problemą yra neigiamas - Neįmanoma nubrėžti nesusikertančių takų nuo kiekvieno namo iki kiekvieno kaimo

Grafų teorija chemijoje

Grafų teorijos taikymas kuriant ir analizuojant įvairių klasių cheminius ir cheminius-technologinius grafikus, kurie dar vadinami topologija, modeliais, t.y. modeliai, kuriuose atsižvelgiama tik į jungčių tarp viršūnių pobūdį. Šių grafikų lankai (briaunos) ir viršūnės atspindi chemines ir chemines-technologines sąvokas, reiškinius, procesus ar objektus ir atitinkamai kokybinius bei kiekybinius ryšius arba tam tikrus ryšius tarp jų.

Teorinės problemos. Cheminiai grafikai leidžia numatyti chemines transformacijas, paaiškinti esmę ir susisteminti kai kurias pagrindines chemijos sąvokas: struktūrą, konfigūraciją, patvirtinimus, kvantinę mechaninę ir statistinę-mechaninę molekulių sąveiką, izomerizmą ir kt. Cheminiai grafikai apima molekulinius, dvišalius ir signalinius grafikus. kinetinės reakcijos lygtis. Molekuliniai grafikai, naudojami stereochemijoje ir struktūrinėje topologijoje, klasterių, polimerų chemijoje ir kt., yra neorientuoti grafikai, rodantys molekulių struktūrą. Šių grafikų viršūnės ir briaunos atitinka atitinkamus atomus ir cheminius ryšius tarp jų.

Stereochemijos org. c-c dažniausiai naudojami molekuliniai medžiai – aprėpiantys molekulinių grafikų medžiai, kuriuose yra tik visos atomus atitinkančios viršūnės. Molekulinių medžių rinkinių sudarymas ir jų izomorfizmo nustatymas leidžia nustatyti molekulines struktūras ir rasti bendrą alkanų izomerų skaičių. alkenai ir alkinai. Molekuliniai grafikai leidžia sumažinti problemas, susijusias su įvairių junginių molekulių kodavimu, nomenklatūra ir struktūriniais ypatumais (išsišakojimu, cikliškumu ir kt.), iki grynai matematinių molekulinių grafų ir jų medžių savybių ir savybių analizės ir palyginimo, taip pat juos atitinkančias matricas. Molekulių struktūros ir junginių fizikinių ir cheminių (taip pat ir farmakologinių) savybių koreliacijų skaičiui nustatyti buvo sukurta daugiau nei 20 vadinamųjų. Molekulių (Wiener, Balaban, Hosoya, Plata, Randich ir kt.) topologiniai indeksai, kurie nustatomi naudojant molekulinių medžių matricas ir skaitines charakteristikas. Pavyzdžiui, Wienerio indeksas W = (m3 + m)/6, kur m yra viršūnių skaičius, atitinkantis C atomus, koreliuoja su molekulių tūriais ir lūžiais, susidarymo entalpija, klampumu, paviršiaus įtempimu, junginių chromatografinėmis konstantomis, oktanu. angliavandenilių skaičius ir net fiziolis . narkotikų aktyvumas. Svarbūs molekulinių grafikų parametrai, naudojami tam tikros medžiagos tautomerinėms formoms ir jų reaktyvumui nustatyti, taip pat aminorūgščių, nukleino rūgščių, angliavandenių ir kitų sudėtingų natūralių junginių klasifikacijoje yra vidutinė ir bendroji (H) informacinė talpa. Polimerų molekulinių grafikų, kurių viršūnės atitinka monomerų vienetus, o briaunos atitinka cheminius ryšius tarp jų, analizė leidžia paaiškinti, pavyzdžiui, išskirtinio tūrio, lemiančio savybes, poveikį. prognozuojamų polimerų savybių pokyčiai. Naudojant Grafų teoriją ir dirbtinio intelekto principus, sukurta programinė įranga informacijos paieškos sistemoms chemijoje, taip pat automatizuotos sistemos molekulinėms struktūroms identifikuoti ir racionaliai planuoti organinę sintezę. Už praktinį racionalių cheminių kelių parinkimo operacijų įgyvendinimą kompiuteryje. retrosintetiniais ir sintoniniais principais pagrįstose transformacijose sprendinių variantams naudojami kelių lygių šakotosios paieškos grafikai, kurių viršūnės atitinka reagentų ir produktų molekulinius grafikus, o lankai vaizduoja transformacijas.

Daugiamatėms cheminių technologinių sistemų (CTS) analizės ir optimizavimo problemoms spręsti naudojami šie cheminiai technologiniai grafikai: srauto, informacijos srauto, signalų ir patikimumo grafikai. Dėl chemijos studijų. Sistemų, susidedančių iš daugybės dalelių, trikdžių fizikoje naudojama vadinamoji. Feynmano diagramos – tai grafikai, kurių viršūnės atitinka elementariąsias fizikinių dalelių sąveikas, jų takų briaunas po susidūrimų. Visų pirma, šie grafikai leidžia ištirti svyravimo reakcijų mechanizmus ir nustatyti reakcijų sistemų stabilumą. grafikų viršūnės atitinka įrenginius, kuriuose kinta fizikinių srautų šilumos suvartojimas, be to, sistemos šiluminės energijos šaltinius ir kriaukles; lankai atitinka fizikinius ir fiktyvius (fizinės-cheminės energijos konversijos įrenginiuose) šilumos srautus, o lankų svoriai lygūs srautų entalpijoms. Medžiagų ir šiluminiai grafikai naudojami sudėtingų cheminių sistemų medžiagų ir šilumos balansų lygčių sistemų sprendimo algoritmų automatizuoto kūrimo programoms sudaryti. Informacijos srauto grafikai atvaizduoja matematinių lygčių sistemų loginę informacijos struktūrą. XTS modeliai; yra naudojami kuriant optimalius šių sistemų skaičiavimo algoritmus. Dvišalis informacinis grafikas yra nenukreiptas arba nukreiptas grafikas, kurio viršūnės atitinkamai atitinka. lygtys fl -f6 ir kintamieji q1 – V, o šakos atspindi jų ryšį. Informacinis grafikas – dviženklis, vaizduojantis lygčių sprendimo tvarką; grafiko viršūnės atitinka šias lygtis, XTS informacijos šaltinius ir imtuvus, o šakos – informaciją. kintamieji. Signalų grafikai atitinka cheminių technologinių procesų ir sistemų matematinių modelių tiesines lygčių sistemas. Patikimumo grafikai naudojami įvairiems patikimumo rodikliams X apskaičiuoti.

Naudota literatūra:

1.Berge K., T. g ir jo taikymas, vertimas iš prancūzų kalbos, M., 1962;

2. Kemeny J., Snell J., Thompson J., Įvadas į baigtinę matematiką, vert. iš anglų k., 2 leidimas, M., 1963 m.;

3.Ope O., Grafikai ir jų taikymas, vert. iš anglų k., M., 1965;

4. Belykh O.V., Belyaev E.V., Sociologijos taikymo sociologijoje galimybės, in: Žmogus ir visuomenė, t. 1, [L.], 1966;

5. Kiekybiniai metodai sociologiniuose tyrimuose, M., 1966; Belyaev E.V., Sociologinių matavimų problemos, "VF", 1967, Nr. 7; Bavelas. Bendravimo modeliai į užduotis orientuotose grupėse, knygoje. Lerner D., Lass Well H., Political sciences, Stanford, 1951;

6. Kemeny J. G., Snell J., Matematiniai modeliai socialiniuose moksluose, N. Y., 1962; Filament C., Grafų teorijos taikymas grupės struktūrai, N. Y., 1963; Оeser Ο. A., Hararu F., Vaidmenų struktūros ir aprašymas grafų teorijos požiūriu, knygoje: Biddle V., Thomas E. J., Role theory: concepts and research, N. Y., 1966. E. Belyaev. Leningradas.