Sažetak na temu viša matematika na temu:

Primjena teorije grafova u kemiji

Izvodi učenica grupe NH-202

Moskva 2011
Grafovi su područje konačne matematike koje proučava diskretne strukture; koristi se za rješavanje raznih teorijskih i primijenjenih problema.
Neki osnovni pojmovi. Graf je zbirka točaka (vrhova) i zbirka parova tih točaka (ne nužno svih) povezanih linijama (slika 1,a). Ako su linije u grafu orijentirane (tj. strelice pokazuju smjer povezivanja vrhova), nazivaju se lukovi ili grane; ako je neorijentiran, - rubovi. Prema tome, graf koji sadrži samo lukove naziva se usmjereni graf ili digraf; samo rubno neorijentiran; lukovi i rebra – mješoviti. Graf koji ima više bridova naziva se multigraf; graf koji sadrži samo bridove koji pripadaju dva njegova disjunktna ​​podskupa (dijela) je bipartitan; ponderirani su lukovi (rubovi) i (ili) vrhovi koji odgovaraju određenim težinama ili brojčanim vrijednostima bilo kojeg parametra. Put u grafu je izmjenični niz vrhova i lukova u kojima se nijedan od vrhova ne ponavlja (na primjer, a, b na slici 1,a); kontura - zatvorena staza u kojoj se prvi i zadnji vrh podudaraju (na primjer, f, h); petlja - luk (brid) koji počinje i završava na istom vrhu. Putanja grafa je slijed bridova u kojima se nijedan od vrhova ne ponavlja (na primjer, c, d, e); ciklus - zatvoreni lanac u kojem se njegovi početni i završni vrhovi podudaraju. Graf se naziva povezanim ako je bilo koji par njegovih vrhova povezan lancem ili stazom; inače se graf naziva nepovezanim.
Stablo je povezani neusmjereni graf koji ne sadrži cikluse ili konture (slika 1,b). Razapinjući podgraf grafa je njegov podskup koji sadrži sve vrhove i samo određene bridove. Razapinjuće stablo grafa je njegov razapinjući podgraf, koji je stablo. Grafovi se nazivaju izomorfnim ako postoji korespondencija jedan na jedan između skupova njihovih vrhova i bridova (lukova).
Za rješavanje problema teorije grafova i njezinih primjena grafovi se predstavljaju pomoću matrica (susjednih, incidencijalnih, dvorednih itd.), kao i posebnih. numeričke karakteristike. Na primjer, u matrici susjedstva (slika 1c), redovi i stupci odgovaraju brojevima vrhova grafa, a njegovi elementi imaju vrijednosti 0 i 1 (odsutnost i prisutnost luka između dati par vrhova); u matrici incidencije (slika 1d), redovi odgovaraju brojevima vrhova, stupci odgovaraju brojevima lukova, a elementi imaju vrijednosti 0, + 1 i - 1 (odnosno, odsutnost , prisutnost luka koji ulazi i izlazi iz vrha). Najčešće numeričke karakteristike: broj vrhova (m), broj lukova ili bridova (n), ciklomatski broj ili rang grafa (n - m + k, gdje je k broj povezanih podgrafova u nepovezani graf; na primjer, za graf na slici 1,b rang će biti: 10-6+ 1 =5).
Primjena teorije grafova temelji se na konstrukciji i analizi različitih klasa kemijskih i kemijsko-tehnoloških grafova, koji se nazivaju i topološki modeli, tj. modeli koji uzimaju u obzir samo prirodu veza između vrhova. Lukovi (rubovi) i vrhovi ovih grafova prikazuju kemijske i kemijsko-tehnološke pojmove, pojave, procese ili objekte te prema tome kvalitativne i kvantitativne odnose ili određene odnose među njima.

Riža. 1. Ilustracija nekih osnovnih pojmova: a-mješoviti graf; b-raspono stablo (puni lukovi a, h, d, f, h) i određeni podgraf (isprekidani lukovi c, e, g, k, l) digrafa; c, r-matrice odn. susjedstvo i pojavnost digrafa.
Teorijski problemi. Kemijski grafovi omogućuju predviđanje kemijskih pretvorbi, objašnjavaju bit i sistematiziraju neke temeljne pojmove kemije: strukturu, konfiguraciju, konformacije, kvantno-mehaničke i statističko-mehaničke interakcije molekula, izomeriju itd. Kemijski grafovi uključuju molekulske, bipartitne i signalne grafove. jednadžbi kinetičke reakcije.
Molekularni grafovi koji se koriste u stereokemiji i strukturnoj topologiji, kemiji klastera, polimera itd. su neusmjereni grafovi koji prikazuju strukturu molekula (slika 2). Vrhovi i rubovi ovih grafova odgovaraju atomima i kemijskim vezama između njih.

Riža. 2. Molekularni grafovi i stabla: a, b - multigrafovi, redom. etilen i formaldehid; kažu oni izomeri pentana (stabla 4, 5 su izomorfna stablu 2).
U stereokemiji organskih tvari najčešće se koriste molekularna stabla - razapeta stabla molekularnih grafova, koja sadrže samo sve vrhove koji odgovaraju atomima C (slika 2, a i b). Sastavljanjem skupova molekularnih stabala i utvrđivanjem njihovog izomorfizma moguće je odrediti molekularne strukture i pronaći ukupan broj izomera alkana, alkena i alkina (slika 2, c).
Molekularni grafovi omogućuju smanjenje problema povezanih s kodiranjem, nomenklaturom i strukturnim značajkama (grananje, cikličnost, itd.) molekula različitih spojeva na analizu i usporedbu čisto matematičkih značajki i svojstava molekularnih grafova i njihovih stabala, kao i njihove odgovarajuće matrice. Da bi se identificirale kvantitativne korelacije između strukture molekula i fizikalno-kemijskih (uključujući farmakološke) osobine spojeva, razvijeno je više od 20 tisuća naziva topoloških indeksa molekula (Wiener, Balaban, Hosoya, Plat, Randic itd.), koji su utvrđuje pomoću matrica i numeričkih karakteristika molekularnih stabala. Na primjer, Wienerov indeks W = (m 3 + m)/6, gdje je m broj vrhova koji odgovaraju C atomima, korelira s molekulskim volumenima i lomovima, entalpijama stvaranja, viskoznošću, površinskom napetosti, kromatografskim konstantama spojeva, oktanski broj ugljikovodika pa čak i fiziološka aktivnost lijekova.
Važni parametri molekularnih grafova koji se koriste za određivanje tautomernih oblika određene tvari i njihove reaktivnosti, kao i u klasifikaciji aminokiselina, nukleinskih kiselina, ugljikohidrata i drugih složenih prirodnih spojeva, jesu prosječni i ukupni (H) informacijski kapaciteti. Parametar se izračunava koristeći Shannonovu informacijsku entropijsku formulu: , gdje je p t vjerojatnost da vrhovi m grafa pripadaju i-tom tipu, ili klasi ekvivalencije, k; i = , Parametar. Proučavanje molekularnih struktura kao što su anorganski klasteri ili Möbiusove trake svodi se na utvrđivanje izomorfizma odgovarajućih molekularnih grafova njihovim postavljanjem (ugrađivanjem) u složene poliedre (na primjer, poliedre u slučaju klastera) ili posebne. višedimenzionalne površine (na primjer, Riemannove površine). Analiza molekularnih grafova polimera, čiji vrhovi odgovaraju monomernim jedinicama, a rubovi kemijskim vezama između njih, omogućuje objašnjenje, na primjer, učinaka isključenog volumena, što dovodi do kvalitativnih promjena u predviđenim svojstvima polimera. .

Riža. 3. Grafi reakcija: a-bipartitni; b-signalna razina kinetike; r 1, g 2 -r-cija; a1-a6-reagensi; k-konstante brzine p-tsny; s-kompleksna varijabla Laplaceove transformacije.
Koristeći teoriju grafova i principe umjetne inteligencije, razvijen je softver za sustave za pronalaženje informacija u kemiji, kao i automatizirane sustave za identifikaciju molekularnih struktura i racionalno planiranje organske sinteze. Za praktičnu primjenu na računalu operacija za odabir racionalnih putova kemijskih transformacija na temelju retrosintetskih i sintonskih principa koriste se višerazinski razgranati grafovi pretraživanja opcija rješenja, čiji vrhovi odgovaraju molekulskim grafovima reagensa i proizvoda, a lukovi prikazuju pretvorbe tvari.

Riža. 4. Jednokružni kemijsko-tehnološki sustav i pripadajući grafikoni: a-strukturni dijagram; b, c-grafovi protoka materijala, redom. ukupnim masenim protokom i protokom komponente A; r - graf toplinskog protoka; d-fragment sustava jednadžbi (f 1 - f 6) materijalne bilance, dobiven analizom grafikona na Sl. 4, b i c; e-bipartitni informacijski digraf; g-informacijski graf, I-mikser; II-reaktor; III-destilacijska kolona; IV-hladnjak; I 1 -I 8 -tehnol. potoci; q-maseni protok; H je entalpija protoka; ja s i i*, s* - odn. stvarni i fiktivni izvori i ponori materijalnih i toplinskih tokova; c-koncentracija reagensa; V je volumen reaktora.
Matrični prikazi molekularnih grafova različitih spojeva ekvivalentni su (nakon transformacije odgovarajućih matričnih elemenata) matričnim metodama kvantne kemije. Stoga se teorija grafova koristi pri izvođenju složenih kvantnokemijskih izračuna: za određivanje broja, svojstava i energija molekularnih orbitala, predviđanje reaktivnosti konjugiranih alternativnih i nealternantnih poliena, identificiranje aromatskih i antiaromatskih svojstava tvari itd.
Za proučavanje poremećaja u sustavima koji se sastoje od velikog broja čestica u kemijskoj fizici koriste se tzv. Feynmanovi dijagrami - grafovi čiji vrhovi odgovaraju elementarnim interakcijama fizičkih čestica, a bridovi njihovim stazama nakon sudara. Konkretno, ovi grafikoni omogućuju proučavanje mehanizama oscilatornih reakcija i određivanje stabilnosti reakcijskih sustava.
Za odabir racionalnih puteva za transformaciju molekula reagensa za zadani skup poznatih interakcija koriste se bipartitni reakcijski grafovi (vrhovi odgovaraju molekulama i tim reakcijama, lukovi odgovaraju interakcijama molekula u reakciji; sl. 3,a ). Takvi grafovi omogućuju razvoj interaktivnih algoritama za odabir optimalnih putanja kemijskih transformacija koje zahtijevaju najmanji broj međureakcija, minimalni broj reagensa s popisa prihvatljivih ili postižu najveći prinos proizvoda.
Signalni grafovi jednadžbi kinetike reakcije prikazuju sustave kinetičkih jednadžbi prikazanih u obliku algebarskog operatora (slika 3b). Vrhovi grafova odgovaraju takozvanim informacijskim varijablama, odnosno signalima, u obliku koncentracija reagensa, lukovi - odnosima signala, a težine lukova određene su kinetičkim konstantama. Takvi se grafovi koriste u proučavanju mehanizama i kinetike složenih katalitičkih reakcija, složenih faznih ravnoteža pri stvaranju kompleksnih spojeva, kao i za izračunavanje parametara aditivnih svojstava otopina.
Primijenjeni problemi. Za rješavanje višedimenzionalnih problema analize i optimizacije kemijsko-tehnoloških sustava (CTS) koriste se sljedeći kemijsko-tehnološki grafovi (slika 4): protok, protok informacija, signal i pouzdanost. Grafikoni protoka, koji su ponderirani digrafovi, uključuju parametarske, materijalne u smislu ukupne masene brzine protoka fizičkih protoka i masene brzine protoka nekih kemijskih komponenti ili elemenata, kao i toplinske grafove. Navedeni grafikoni odgovaraju fizikalnim i kemijskim pretvorbama tvari i energije u određenom kemijskom sustavu.
Parametarski dijagrami protoka prikazuju transformaciju parametara (maseni protok, itd.) fizičkih protoka pomoću CTS elemenata; vrhovi grafova odgovaraju matematičkim modelima uređaja, kao i izvorima i ponorima navedenih tokova, a lukovi odgovaraju samim tokovima, a težine lukova jednake su broju parametara odgovarajući protok. Parametarski grafovi koriste se za razvoj algoritama za analizu tehnoloških načina rada višekružnih kemijskih sustava. Takvi algoritmi uspostavljaju slijed izračunavanja sustava jednadžbi matematičkih modela pojedinačnih uređaja bilo kojeg sustava za određivanje parametara njegovih izlaznih tokova s ​​poznatim vrijednostima varijabilnih ulaznih tokova.
Grafikoni protoka materijala prikazuju promjene u potrošnji tvari u kemijskim tvarima. Vrhovi grafova odgovaraju uređajima u kojima se transformiraju ukupne masene brzine protoka fizičkih protoka i masene brzine protoka nekih kemijskih komponenti ili elemenata, kao i izvori i ponori tvari protoka ili tih komponenti; U skladu s tim, lukovi grafikona odgovaraju fizičkim tokovima ili fizičkim i fiktivnim (kemijske transformacije tvari u aparatima) izvorima i ponorima bilo kojih komponenti, a težine lukova jednake su masenim brzinama protoka obje vrste. Grafikoni toplinskog toka prikazuju toplinske bilance u CTS-u; vrhovi grafova odgovaraju uređajima u kojima se mijenja potrošnja topline fizičkih tokova, a osim toga, izvorima i ponorima toplinske energije sustava; lukovi odgovaraju fizičkim i fiktivnim (fizikalno-kemijska pretvorba energije u uređajima) toplinskim tokovima, a težine lukova jednake su entalpijama tokova. Materijalni i toplinski grafovi koriste se za sastavljanje programa za automatizirani razvoj algoritama za rješavanje sustava jednadžbi za materijalnu i toplinsku bilancu složenih kemijskih sustava.
Informacijsko-stock grafovi prikazuju logičko-informacijsku strukturu sustava jednadžbi matematičkih modela CTS-a; koriste se za sastavljanje optimalnih algoritama za izračun tih sustava. Bipartitni informacijski graf (slika 4, e) je neusmjereni ili orijentirani graf, čiji vrhovi odgovaraju jednadžbama f l - f 6 i varijablama q 1 - V, a grane odražavaju njihov odnos. Informacijski graf (slika 4, g) - digraf koji prikazuje redoslijed rješavanja jednadžbi; vrhovi grafa odgovaraju ovim jednadžbama, izvorima i primateljima XTS informacija, a grane odgovaraju informacijskim varijablama.
Signalni grafovi odgovaraju linearnim sustavima jednadžbi matematičkih modela kemijsko-tehnoloških procesa i sustava. Vrhovi grafova odgovaraju signalima (na primjer, temperatura), a grane odgovaraju vezama između njih. Takvi se grafovi koriste za analizu statičkih i dinamičkih načina višeparametarskih procesa i kemijskih sustava, kao i pokazatelji niza njihovih najvažnijih svojstava (stabilnost, osjetljivost, upravljivost).
Grafikoni pouzdanosti koriste se za izračun različitih pokazatelja pouzdanosti kemijske opreme. Među brojnim skupinama ovih grafova (npr. parametarski, logičko-funkcionalni) posebno su važna tzv. stabla kvarova. Svako takvo stablo je ponderirani digraf koji prikazuje međuodnos mnogih jednostavnih kvarova pojedinačnih procesa i CTS uređaja, koji dovode do mnogih sekundarnih kvarova i rezultirajućeg kvara sustava u cjelini.
Za izradu kompleksa programa za automatiziranu sintezu optimalne visoko pouzdane proizvodnje (uključujući uštedu resursa), uz načela umjetne inteligencije, koriste se orijentirane semantike ili semantike, grafovi opcija CTS rješenja. Ovi grafikoni, koji su u konkretnom slučaju stabla, prikazuju postupke za generiranje skupa racionalnih alternativnih CTS shema (na primjer, 14 mogućih pri odvajanju peterokomponentne smjese ciljnih proizvoda rektifikacijom) i postupke za uređen odabir između njih shema koja je optimalna prema nekom kriteriju učinkovitosti sustava.
itd.............

OPĆINSKA SAMOSTALNA OBRAZOVNA USTANOVA SREDNJA ŠKOLA BR. 2

Pripremljeno

Legkokonets Vladislav, učenik 10A razreda

Praktična primjena teorije grafova

Nadzornik

L.I. Noskova, učiteljica matematike

čl. Bryukhovetskaya

2011

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

2. Povijest nastanka teorije grafova………………………………………….………..4

3. Osnovne definicije i teoremi teorije grafova…………………………….………6

4. Problemi riješeni pomoću grafikona………………………………..………………………..8

4.1 Poznati problemi………………………………….………………………...8

4.2 Nekoliko zanimljivih problema………………………………….……………..9

5. Primjena grafikona u različitim područjima života ljudi………………………………...11

6. Rješavanje problema…………………………………………………………………………...12

7. Zaključak………………….…………………………………………………………….13

8. Popis literature………….………………………………………………………………14

9.Dodatak………………………………………………………………………………………………15

Uvod

Rođena iz rješavanja zagonetki i zabavnih igara, teorija grafova sada je postala jednostavan, pristupačan i moćan alat za rješavanje pitanja vezanih uz širok raspon problema. Grafikoni su doslovno sveprisutni. U obliku grafikona možete, primjerice, interpretirati cestovne karte i električne krugove, zemljopisne karte i molekule kemijskih spojeva, veze među ljudima i skupinama ljudi. Tijekom posljednja četiri desetljeća teorija grafova postala je jedna od grana matematike koja se najbrže razvija. To je potaknuto zahtjevima polja primjene koje se brzo širi. Koristi se u dizajnu integriranih krugova i upravljačkih krugova, u proučavanju automata, logičkih sklopova, programskih blok dijagrama, u ekonomiji i statistici, kemiji i biologiji, u teoriji rasporeda. Eto zašto relevantnost Tema je određena, s jedne strane, popularnošću grafova i srodnih istraživačkih metoda, as druge strane, nerazvijenim, holističkim sustavom za njihovu primjenu.

Rješavanje mnogih životnih problema zahtijeva duge kalkulacije, a ponekad ni te kalkulacije ne donose uspjeh. Ovo je što problem istraživanja. Postavlja se pitanje je li moguće pronaći jednostavno, racionalno, kratko i elegantno rješenje za njihovo rješavanje. Je li rješavanje problema lakše ako koristite grafikone? Ovo je odredilo tema mog istraživanja: “Praktična primjena teorije grafova”

Svrha Istraživanje je trebalo koristiti grafikone kako bi naučili kako brzo riješiti praktične probleme.

Hipoteza istraživanja. Metoda grafova vrlo je važna i široko korištena u raznim područjima znanosti i ljudske djelatnosti.

Ciljevi istraživanja:

1. Proučite literaturu i internetske izvore o ovoj temi.

2.Provjeriti učinkovitost metode grafova u rješavanju praktičnih problema.

3. Izvedite zaključak.

Praktični značaj studije je da će rezultati nedvojbeno pobuditi interes mnogih ljudi. Zar nitko od vas nije pokušao izgraditi svoje obiteljsko stablo? Kako to učiniti ispravno? Voditelj prijevozničkog poduzeća vjerojatno mora riješiti problem isplativijeg korištenja prijevoza prilikom prijevoza robe od odredišta do nekoliko naselja. Svaki se školarac susreo s logičnim problemima transfuzije. Ispostavilo se da ih je lako riješiti pomoću grafova.

U radu se koriste sljedeće metode: promatranje, traženje, selekcija, analiza.

Povijest teorije grafova

Utemeljiteljem teorije grafova smatra se matematičar Leonhard Euler (1707-1783). Povijest ove teorije može se pratiti kroz korespondenciju velikog znanstvenika. Ovdje je prijevod latinskog teksta, koji je preuzet iz Eulerovog pisma talijanskom matematičaru i inženjeru Marinoniju, poslanog iz Sankt Peterburga 13. ožujka 1736. godine.

“Jednom su mi postavili problem o otoku koji se nalazi u gradu Königsbergu i okružen je rijekom sa sedam mostova preko nje.

[Dodatak sl.1] Pitanje je može li ih netko u kontinuitetu obilaziti, prolazeći samo jednom preko svakog mosta. A onda su me obavijestili da to još nitko nije uspio, ali nitko nije dokazao da je to nemoguće. Ovo pitanje, iako trivijalno, činilo mi se, međutim, vrijednim pažnje jer ni geometrija, ni algebra, ni kombinatorika nisu dovoljni da ga riješe. Nakon dugog razmišljanja, pronašao sam jednostavno pravilo, temeljeno na potpuno uvjerljivom dokazu, uz pomoć kojeg je moguće u svim problemima ove vrste odmah utvrditi može li se takav obilazak napraviti kroz bilo koji broj i bilo koji broj mostova koji se nalaze ili ne. Koenigsberški mostovi su smješteni na takav način da se mogu prikazati na sljedećoj slici [Dodatak sl.2], u kojem A označava otok, a B, C i D - dijelove kontinenta odvojene jedan od drugog riječnim ograncima

O metodi koju je otkrio za rješavanje problema ove vrste, Euler je napisao:

“Ovo rješenje, po svojoj prirodi, očito ima malo veze s matematikom i ne razumijem zašto bi se ovo rješenje trebalo očekivati ​​od matematičara, a ne od bilo koje druge osobe, jer je ova odluka potkrijepljena samo rezoniranjem, a nema potrebno uključiti da bismo pronašli ovo rješenje, postoje bilo kakvi zakoni svojstveni matematici, pa ne znam kako ispada da će pitanja koja imaju vrlo malo veze s matematikom vjerojatnije riješiti matematičari nego drugi.

Dakle, je li moguće zaobići Königsberške mostove prolaskom samo jednom preko svakog od ovih mostova? Kako bismo pronašli odgovor, nastavimo Eulerovo pismo Marinoniju:

"Pitanje je utvrditi je li moguće zaobići svih tih sedam mostova, prolazeći kroz svaki samo jednom, ili ne. Moje pravilo dovodi do sljedećeg rješenja ovog pitanja. Prije svega, morate pogledati koliko područja ima su, odvojeni vodom - takvi , koji nemaju drugog prijelaza iz jednog u drugi, osim preko mosta. U ovom primjeru postoje četiri takva odjeljka - A, B, C, D. Dalje, morate razlikovati je li broj Broj mostova koji vode do tih pojedinačnih dionica je paran ili neparan, dakle, u našem slučaju, pet mostova vodi do dionice A, a po tri mosta do ostalih, tj. broj mostova koji vode do pojedinih dionica je neparan, i samo ovo je dovoljno. da riješimo problem. Kada se to utvrdi, primjenjujemo sljedeće pravilo: kada bi broj mostova koji vode do svake pojedine dionice bio paran, tada bi dotična obilaznica bila moguća, au isto vrijeme bilo bi moguće započeti. Ako bi dva od ovih brojeva bila neparna, jer samo jedan ne može biti neparan, tada bi se čak i prijelaz mogao izvršiti, ali samo početak obilaska mora se uzeti iz jednog. od one dvije dionice do kojih vodi neparan broj mostova. Kad bi, konačno, postojalo više od dvije dionice do kojih vodi neparan broj mostova, onda je takvo kretanje općenito nemoguće ... ako bi se ovdje mogli dovesti neki drugi, ozbiljniji problemi, ova bi metoda mogla biti od još veće koristi i trebala bi ne smije se zanemariti."

Osnovne definicije i teoremi teorije grafova

Teorija grafova je matematička disciplina nastala radom matematičara, stoga njezino izlaganje uključuje potrebne stroge definicije. Dakle, prijeđimo na organizirano upoznavanje osnovnih pojmova ove teorije.

Definicija 1. Graf je zbirka konačnog broja točaka, koje se nazivaju vrhovi grafa, i parova linija koje povezuju neke od tih vrhova, koje se nazivaju bridovi ili lukovi grafa.

Ova se definicija može drugačije formulirati: graf je neprazan skup točaka (vrhova) i segmenata (brdova), čija oba kraja pripadaju danom skupu točaka.

U nastavku ćemo vrhove grafa označavati latiničnim slovima A, B, C, D. Ponekad će se graf kao cjelina označiti jednim velikim slovom.

Definicija 2. Vrhovi grafa koji ne pripadaju niti jednom bridu nazivaju se izolirani.

Definicija 3. Graf koji se sastoji samo od izoliranih vrhova naziva se null - računati .

Oznaka: O "– graf s vrhovima koji nema bridova

Definicija 4. Graf u kojem je svaki par vrhova povezan bridom naziva se potpunim.

Oznaka: U" – graf koji se sastoji od n vrhova i bridova koji povezuju sve moguće parove tih vrhova. Takav se graf može prikazati kao n-kut u kojem su ucrtane sve dijagonale

Definicija 5. Stupanj vrha je broj bridova kojima vrh pripada.

Definicija 6. Graf čiji su stupnjevi svih k vrhova isti naziva se homogeni graf stupnjeva .

Definicija 7. Komplement zadanog grafa je graf koji se sastoji od svih bridova i njihovih krajeva koji se moraju dodati izvornom grafu da bi se dobio potpuni graf.

Definicija 8. Graf koji se može prikazati na ravnini tako da mu se bridovi sijeku samo u vrhovima naziva se ravninski.

Definicija 9. Poligon planarnog grafa koji ne sadrži niti jedan vrh ili brid grafa naziva se njegova strana.

Koncepti planarnog grafa i lica grafa koriste se pri rješavanju problema o "ispravnom" bojanju raznih karata.

Definicija 10. Put od A do X je niz bridova koji vode od A do X tako da svaka dva susjedna brida imaju zajednički vrh, a niti jedan brid se ne pojavljuje više od jednom.

Definicija 11. Ciklus je staza u kojoj se početna i završna točka podudaraju.

Definicija 12. Jednostavni ciklus je ciklus koji ne prolazi ni jednim vrhom grafa više od jednom.

Definicija 13. Duljina staze , položen na petlju , zove se broj bridova ove staze.

Definicija 14. Dva vrha A i B u grafu nazivaju se povezanima (nepovezanima) ako postoji (ne postoji) put koji vodi od A do B.

Definicija 15. Graf se naziva povezanim ako su svaka dva njegova vrha povezana; ako graf sadrži barem jedan par nepovezanih vrhova, tada se graf naziva nepovezanim.

Definicija 16. Stablo je povezani graf koji ne sadrži cikluse.

Trodimenzionalni model grafa stabla je, na primjer, stvarno stablo sa svojom zamršeno razgranatom krošnjom; rijeka i njezini pritoci također tvore stablo, ali već ravno - na površini zemlje.

Definicija 17. Nepovezani graf koji se u potpunosti sastoji od stabala naziva se šuma.

Definicija 18. Stablo u kojem je svih n vrhova označeno brojevima od 1 do n naziva se stablo s prenumeriranim vrhovima.

Dakle, ispitali smo osnovne definicije teorije grafova, bez kojih bi bilo nemoguće dokazati teoreme, a time i rješavati probleme.

Zadaci riješeni pomoću grafikona

Poznati problemi

Problem trgovačkog putnika

Problem trgovačkog putnika jedan je od poznatih problema u teoriji kombinatorike. Iznesena je 1934. godine i na njoj su najbolji matematičari lomili zube.

Izjava problema je sljedeća.
Putujući trgovački putnik (lutajući trgovac) mora napustiti prvi grad, jednom posjetiti gradove 2,1,3..n nepoznatim redoslijedom i vratiti se u prvi grad. Poznate su udaljenosti između gradova. Kojim redom treba obilaziti gradove da zatvoreni put (obilazak) trgovačkog putnika bude najkraći?

Metoda rješavanja problema trgovačkog putnika

Pohlepni algoritam “idite do najbližeg (u koji još niste ušli) grada.”
Ovaj algoritam se naziva "pohlepan" jer u posljednjim koracima morate ozbiljno platiti za pohlepu.
Razmotrite na primjer mrežu na slici [Dodatak sl.3], koji predstavlja uski romb. Neka trgovački putnik krene iz grada 1. Algoritam "idi do najbližeg grada" odvest će ga u grad 2, zatim 3, zatim 4; na posljednjem koraku morat ćete platiti za svoju pohlepu, vraćajući se duž duge dijagonale dijamanta. Rezultat neće biti najkraća, već najduža tura.

Problem oko Königsberških mostova.

Problem je formuliran na sljedeći način.
Grad Koenigsberg nalazi se na obalama rijeke Pregel i dva otoka. Različite dijelove grada povezivalo je sedam mostova. Nedjeljom su građani šetali gradom. Pitanje: da li je moguće šetati na način da se nakon izlaska iz kuće vratite natrag, hodajući točno jednom po svakom mostu.
Mostovi preko rijeke Pregel nalaze se kao na slici[Dodatak sl.1].

Razmotrite graf koji odgovara dijagramu mosta [Dodatak Slika 2].

Za odgovor na pitanje problema dovoljno je saznati je li graf Eulerov. (Paran broj mostova mora se protezati iz najmanje jednog vrha). Ne možete prošetati gradom i jednom prijeći sve mostove pa se vratiti.

Nekoliko zanimljivih zadataka

1. "Rute".

Problem 1

Kao što se sjećate, lovac na mrtve duše Čičikov je jednom posjetio poznate veleposjednike. Posjetio ih je sljedećim redom: Manilov, Korobočka, Nozdrjov, Sobakevič, Pljuškin, Tentetnikov, general Betriščev, Petuh, Konstanžolgo, pukovnik Koškarev. Pronađen je dijagram na kojem je Čičikov skicirao međusobne položaje imanja i seoskih cesta koje ih povezuju. Odredite koji posjed kome pripada, ako Čičikov nijednom cestom nije vozio više puta [Dodatak Slika 4].

Otopina:

Putokaz pokazuje da je Čičikov započeo svoje putovanje od imanja E, a završio na imanju O. Napominjemo da samo dvije ceste vode do imanja B i C, pa je Čičikov morao putovati tim cestama. Označimo ih masnom linijom. Identificirane su dionice trase koje prolaze kroz A: AC i AB. Čičikov nije putovao cestama AE, AK i AM. Prekrižimo ih. Označimo masnom crtom ED; Precrtajmo DK. Prekrižimo MO i MN; Označimo MF masnom crtom; prekrižiti FO; Označimo FH, NK i KO podebljanom linijom. Pronađimo jedini mogući put pod ovim uvjetom. I dobivamo: imanje E - pripada Manilovu, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Dodatak sl.5].

Problem 2

Na slici je prikazana karta područja [Dodatak Slika 6].

Možete se kretati samo u smjeru strelica. Svaku točku možete posjetiti najviše jednom. Na koliko načina možete doći od točke 1 do točke 9? Koja ruta je najkraća, a koja najduža.

Otopina:

Sekvencijalno "stratificiramo" krug u stablo, počevši od vrha 1 [Dodatak sl.7]. Uzmimo drvo. Broj mogućih načina da dođete od 1 do 9 jednak je broju "visećih" vrhova stabla (ima ih 14). Očito je najkraći put 1-5-9; najduža je 1-2-3-6-5-7-8-9.

2 "Grupe, spojevi"

Problem 1

Sudionici glazbenog festivala nakon susreta razmijenili su omotnice s adresama. Dokažite da:

a) predan je paran broj koverti;

b) paran je broj sudionika koji su neparan broj puta izmijenili koverte.

Rješenje: Neka su sudionici festivala A 1, A 2, A 3. . . , A n su vrhovi grafa, a bridovi povezuju parove vrhova koji predstavljaju tipove koji razmjenjuju omotnice [Dodatak sl. 8]

Otopina:

a) stupanj svakog vrha A i pokazuje broj koverti koje je sudionik A i dao svojim prijateljima. Ukupan broj odaslanih ovojnica N jednak je zbroju stupnjeva svih vrhova grafa N = stupanj. Korak 1+. A 2 + + . . . + korak. A n -1 + stupanj. I n, N =2p, gdje je p broj rubova grafa, tj. N – parno. Slijedom toga, uručen je paran broj omotnica;

b) u jednakosti N = stupanj. Korak 1+. A 2 + + . . . + korak. A n -1 + stupanj. I n zbroj neparnih članova mora biti paran, a to može biti samo ako je broj neparnih članova paran. To znači da je broj sudionika koji su neparan broj puta razmijenili kuverte paran.

Problem 2

Jednog dana Andrej, Boris, Volodja, Daša i Galja dogovorili su se da navečer odu u kino. Odabir kina i projekcije odlučili su uskladiti telefonski. Odlučeno je i da se odlazak u kino, ako se s nekim ne može kontaktirati telefonom, otkazuje. Navečer se nisu svi okupili u kinu, pa je posjet kinu otkazan. Sutradan su počeli otkrivati ​​tko je koga zvao. Ispostavilo se da je Andrej nazvao Borisa i Volodju, Volodja Borisa i Dašu, Boris Andreja i Dašu, Daša Andreja i Volodju, a Galja Andreja, Volodju i Borisa. Tko se nije mogao javiti na telefon i zbog toga nije došao na sastanak?

Otopina:

Nacrtajmo pet točaka i označimo ih slovima A, B, C, D, D. Ovo su prva slova imena. Spojimo točkice koje odgovaraju imenima momaka koji su zvali.

[Dodatak sl.9]

Sa slike je jasno da su svi momci - Andrej, Boris i Volodja - telefonirali svima ostalima. Zato su ovi momci došli u kino. Ali Galya i Dasha nisu uspjele razgovarati (točke G i E nisu spojene crtom) i stoga, u skladu s dogovorom, nisu došle u kino.

Primjena grafova u različitim područjima života ljudi

Osim navedenih primjera, grafovi imaju široku primjenu u građevinarstvu, elektrotehnici, menadžmentu, logistici, geografiji, strojarstvu, sociologiji, programiranju, automatizaciji tehnoloških procesa i proizvodnje, psihologiji i oglašavanju.

Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čije je dokazivanje i bio cilj ovog rada.

U bilo kojem području znanosti i tehnologije susrećete se s grafovima. Grafovi su prekrasni matematički objekti s kojima možete rješavati matematičke, ekonomske i logičke probleme, razne zagonetke i pojednostaviti uvjete problema u fizici, kemiji, elektronici i automatizaciji. Mnoge matematičke činjenice mogu se zgodno formulirati jezikom grafikona. Teorija grafova dio je mnogih znanosti. Teorija grafova jedna je od najljepših i najzornijih matematičkih teorija. Teorija grafova u posljednje vrijeme nalazi sve više primjena u primijenjenim problemima. Pojavila se čak i računalna kemija - relativno mlado polje kemije koje se temelji na primjeni teorije grafova. Molekularni grafovi , koji se koriste u stereokemiji i strukturnoj topologiji, kemiji klastera, polimera itd., neusmjereni su grafovi koji prikazuju strukturu molekula[Dodatak sl. 10]

. Vrhovi i rubovi ovih grafova odgovaraju odgovarajućim atomima i kemijskim vezama među njima. Molekularni grafikoni i stabla: a, b - multigrafi, redom. etilen i formaldehid; kažu oni izomeri pentana (stabla 4, 5 su izomorfna stablu 2).

U stereokemiji organizama najviše. Često se koriste molekularna stabla - glavna stabla molekularnih grafova, koja sadrže samo sve vrhove koji odgovaraju C atomima Kompilacija skupova mol. stabla i utvrđivanje njihove izomorfnosti omogućuju utvrđivanje da kažu. strukture i pronaći ukupan broj izomera alkana, alkena i alkina

Proteinske mreže

Proteinske mreže su skupine proteina koji fizički međusobno djeluju i funkcioniraju u stanici zajedno i na koordiniran način, kontrolirajući međusobno povezane procese koji se odvijaju u tijelu [privitak sl. 11].

Graf hijerarhijskog sustava zove stablo. Posebnost stabla je da postoji samo jedan put između bilo koja dva njegova vrha. Stablo ne sadrži cikluse ili petlje.

Tipično, stablo koje predstavlja hijerarhijski sustav ima jedan glavni vrh, koji se naziva korijen stabla. Svaki vrh stabla (osim korijena) ima samo jednog pretka - objekt koji je njime označen uključen je u jednu klasu najviše razine. Svaki vrh stabla može generirati nekoliko potomaka - vrhova koji odgovaraju klasama niže razine.

Za svaki par vrhova stabla postoji jedinstvena staza koja ih povezuje. Ovo se svojstvo koristi kada se pronalaze svi preci, na primjer, po muškoj liniji, bilo koje osobe čije je podrijetlo predstavljeno u obliku obiteljskog stabla, koje je "stablo" u smislu teorije grafova.

Primjer mog obiteljskog stabla [Dodatak sl. 12].

Drugi primjer. Slika prikazuje biblijsko obiteljsko stablo [Dodatak sl. 13].

Rješavanje problema

1.Prometni zadatak. Neka u gradu Krasnodaru bude baza sa sirovinama koje treba distribuirati u gradove Krymsk, Temryuk, Slavyansk-on-Kuban i Timashevsk u jednom putovanju, trošeći što manje vremena i goriva i vraćajući se natrag u Krasnodar .

Otopina:

Najprije napravimo grafikon svih mogućih ruta putovanja [Dodatak sl.14], uzimajući u obzir realne prometnice između ovih naselja i njihovu udaljenost. Da bismo riješili ovaj problem, moramo napraviti još jedan graf, nalik stablu [Dodatak sl.15].

Radi praktičnosti rješenja, gradove označavamo brojevima: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Rezultat su 24 rješenja, ali trebaju nam samo najkraći putevi. Od svih rješenja samo su dva zadovoljavajuća, ovo je 350 km.

Slično tome, moguće je i, mislim, potrebno izračunati stvarni prijevoz s jednog mjesta na drugo.

Logičan problem koji uključuje transfuziju. Kanta sadrži 8 litara vode, a tu su i dvije posude od 5 i 3 litre. potrebno je u posudu od pet litara uliti 4 litre vode i ostaviti 4 litre u kanti, odnosno uliti vode jednako u kantu i veliku tepsiju.

Otopina:

Stanje se u svakom trenutku može opisati s tri brojke [Dodatak sl. 16].

Kao rezultat, dobivamo dva rješenja: jedno u 7 poteza, drugo u 8 poteza.

Zaključak

Dakle, da biste naučili rješavati probleme, morate razumjeti što su oni, kako su strukturirani, od kojih se komponenti sastoje, koji su alati pomoću kojih se problemi rješavaju.

Rješavajući praktične probleme teorijom grafova postalo je jasno da je u svakom koraku, u svakoj fazi njihova rješavanja potrebno primijeniti kreativnost.

Od samog početka, u prvoj fazi, leži u činjenici da morate biti u stanju analizirati i kodirati stanje problema. Druga faza je shematski zapis, koji se sastoji od geometrijskog prikaza grafova, au ovoj fazi element kreativnosti je vrlo važan jer je daleko od lakog pronalaženja podudarnosti između elemenata uvjeta i odgovarajućih elemenata uvjeta. graf.

Rješavajući transportni problem ili zadatak sastavljanja obiteljskog stabla, došao sam do zaključka da je metoda grafikona svakako zanimljiva, lijepa i vizualna.

Uvjerio sam se da se grafikoni široko koriste u ekonomiji, menadžmentu i tehnologiji. Teorija grafova se također koristi u programiranju. O tome se nije raspravljalo u ovom radu, ali mislim da je to samo pitanje vremena.

Ovaj znanstveni rad ispituje matematičke grafove, područja njihove primjene, te rješava nekoliko problema pomoću grafova. Poznavanje osnova teorije grafova potrebno je u raznim područjima vezanim uz upravljanje proizvodnjom i poslovanjem (primjerice, raspored izgradnje mreže, raspored dostave pošte). Osim toga, radeći na znanstvenom radu, savladao sam rad na računalu koristeći uređivač teksta WORD. Time su ciljevi znanstvenog rada ispunjeni.

Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čije je dokazivanje i bio cilj ovog rada.

Književnost

Berge K. Teorija grafova i njezine primjene. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Uvod u konačnu matematiku. -M.: IIL, 1963.

Ore O. Grafovi i njihova primjena. -M.: Mir, 1965.

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

Zykov A.A. Teorija konačnih grafova. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Grafovi i njihova primjena. -M .: Obrazovanje, 1979. -144 str.

"Soros Educational Journal" broj 11 1996 (članak "Flat graphs");

Gardner M. "Matematička dokolica", M. "Svijet", 1972 (poglavlje 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Stari zabavni problemi”, M. “Science”, 1988 (dio 2, odjeljak 8; dodatak 4);

Primjena

Primjena

P

Riža. 6

Riža. 7

Riža. 8

primjena

Primjena

Primjena

Primjena

P

Riža. 14

primjena

Primjena

Predgovor urednika prijevoda
Predgovor ruskom izdanju
Predgovor
TOPOLOGIJA SKUPA KONAČNE TOČKE I MOLEKULARNA STRUKTURA. R. Merrifield, X. Simmons
1. Uvod
2. Konačna topologija
2.1. Topološki graf
2.2. Kvalitativne karakteristike topologije grafa
2.3. Kvantitativne karakteristike topologije grafa: kombinatorika
3. Topologija alternativnih molekula
3.1. Složenost strukture
3.2. Povezanost i delokalizacija
4. Topologija nealternantnih molekula
4.1. Duplex graf
4.2. Duplex topologija
Književnost
STEREOKEMIJSKA TOPOLOGIJA. D. Volba
1. Uvod
2. Pristup sintezi topoloških stereoizomera temeljen na Möbiusovim trakama
2.1. Potpuna sinteza prve molekularne Möbiusove trake
3. Kriteriji za topološku stereoizomeriju
3.1. Topološka kiralnost
3.2. Topološka dijastereoizomerija
4. Reakcija rezanja i pristupi sintezi molekularnog trolisnog čvora
4.1. Puknuće stepenica Mobiusovih ljestava
4.2. Molekularni trolisni čvor
Književnost
KVALITATIVNA STEREOKEMIJA J. Dugundji
1. Uvod
2. Permutacijski izomeri
3. Grupa kemijskog identiteta
Književnost
TEORIJA MOLEKULARNE STRUKTURE. R. Bader
1. Osvrt na teoriju
2. Neke aplikacije
Književnost
ALGEBARSKA I TOPOLOŠKA STRUKTURA KVANTNE KEMIJE, KEMIJSKA KINETIKA I VIZUALNA PRAVILA KOJA VAM OMOGUĆUJU KVALITATIVNA PREDVIĐANJA ZA KEMIJSKU PRAKSU. O. Sinanoglu
1. Uvod
2. Mikrokemija ili kvalitativna kvantnokemijska pravila izvedena izravno iz strukturnih formula ili ORTEP dijagrama
2.1. Valentno vektorsko prostorno polje Vn(R) koje postoji u euklidskom trodimenzionalnom prostoru (?)
2.2. Princip linearne kovarijance u kvantnoj kemiji
2.3. Neunitarna klasifikacija molekula
2.4. Od strukturnih formula molekula do detaljnijih strukturno-elektroničkih formula (i do grafikona)
2.5. “Strukturna i deformacijska kovarijanca” molekula i grafička pravila za dobivanje visokokvalitetnih kvantnokemijskih rezultata
3. Morfologija reakcijskih mehanizama, putovi sinteze i topološka “pravila faze/spoja”
4. Značajke dobivanja kvantnih kvalitativnih karakteristika svakog reakcijskog stupnja mehanizma ili reakcijskog puta
Književnost
TOPOLOGIJA REAKCIJE: TEORIJA MANIFESTIJA POTENCIJALNIH POVRŠINA I KVANTNO-KEMIJSKI DIZAJN SINTEZE. P. Mezhey
1. Uvod
2. Topološke mnogostrukosti, diferencijabilne mnogostrukosti i topologija reakcije
3. Omjeri kritičnih točaka; grafovi presjeka u topološkom prostoru (M, Tc) i sheme kvantnih kemijskih reakcija
4. Računalni aspekti
5. Degenerirane kritične točke i kemijske strukture koje ne odgovaraju pravim PES minimumima
6. Zaključci
Književnost
TOPOLOGIJA VEZANJA U POLIHEDRIČKIM MOLEKULAMA. R. Kralj
1. Uvod
2. Osnovni koncept
3. Vertex atomi
4. Poliedarski sustavi s lokaliziranim vezanjem
5. Sustavi s potpuno delokaliziranim vezanjem
6. Poliedarski sustavi bogati elektronima
7. Poliedarski sustavi s nedostatkom elektrona
8. Anomalni vrhovi
9. Poliedri
10. Zaključci
Književnost
OBLICI SKUPINA ELEMENATA GLAVNIH PODSKUPINA: TOPOLOŠKI PRISTUP BROJANJU SKETNIH ELEKTRONA. M. McGlinchey, J. Tal
1. Uvod
2. Grozdovi s potpuno delokaliziranim vezanjem
3. Grozdovi s veznom lokalizacijom na rubovima
3.1. Grozdovi heksatoma
3.2. Klasteri od sedam atoma
3.3. Klasteri od osam atoma
4. Kvantno topološko opravdanje poliedarskog modela
5. Zaključci
Književnost
TOPOLOŠKA SVOJSTVA BINARNIH SPOJEVA SUMPORA S DUŠIKOM. A. Turner
1. Uvod
2. Prototip molekule - tetrasumpor tetranitrid
3. Planarne cikličke molekule i ioni SnNm
4. Neplanarni sustavi - ekvivalentnost centara raspodjele naboja
5. Primjena teorije funkcionala elektronske gustoće
Književnost
BISTE LI TREBALI RAZVIJATI TOPOLOŠKE INDEKSE? D. Rouvray
1. Uvod
2. Wienerov indeks
3. Izrada indeksa
4. Indeksi matrice udaljenosti
5. Indeksi matrice susjedstva
6. Centrični topološki indeksi
7. Informacijsko-teorijski indeksi
8. Kompozitni topološki indeksi
9. Neki matematički odnosi
10. Oblik i veličina molekula
11. Osnovne primjene indeksa
12. Bibliografska klasifikacija spojeva
13. Određivanje fizikalno-kemijskih parametara
14. Razvoj farmaceutskih lijekova
15. Zaključci
Književnost
TOPOLOŠKI INDEKSI TEMELJENI NA SIMETRIJI SUSJEDA: KEMIJSKE I BIOKEMIJSKE PRIMJENE. V. Magnuson, D. Harris, S. Beysak
1. Uvod
2. Informacijski sadržaj grafa
2.1. Definicije
2.2. Osnovne odredbe
2.3. Relacija ekvivalencije
2.4. Izračunavanje ostalih topoloških indeksa
3. Izračun indeksa
4. Primjene u kvantitativnim studijama korelacije strukture i aktivnosti (QSCA).
4.1. Topljivost alkohola
4.2. Inhibicija mikrosomalne para-hidroksilacije anilina alkoholima
4.3. Toksičnost (LD50) barbiturata
Književnost
UREĐIVANJE GRAFOVA KAO PRISTUP PROUČAVANJU KORELACIJA STRUKTURA-AKTIVNOST. M. Randić, J. Kraus, B. Džonova-German-Blazić
1. Uvod
2. Temeljni principi metode
3. Primjena na tvari s antimalarijskim djelovanjem
3.1. Konstruiranje niza sklopova
3.2. Usporedba molekula A-M
4. Rasprava
Književnost
MATEMATIČKI MODEL MOLEKULARNE SLOŽENOSTI. S. Bertz
1. Vaeding
2. Razvoj modela
2.1. Teorija grafova i molekularna topologija
2.2. Teorija informacija i molekularna simetrija
3. Provjera modela
3.1. Ograničenja modela
4. Pouzdanost modela
5. Zaključci
Književnost
MATRICA UDALJENOSTI ZA MOLEKULE KOJE SADRŽE HETERO-ATOME. M. Barish, J. Yashari, R. Lall, V. Srivastava, I. Trinaistich
1. Uvod
2. Odnos između matrice susjedstva i matrice udaljenosti
3. Matrica udaljenosti za heterosustave
Književnost
KANONIČKO NUMERACIJA I SUSTAV LINEARNE NOTACIJE ZA KEMIJSKE GRAFOVE. W. Herndon
1. Uvod
2. Kanonsko numeriranje
3. Jednoznačna linearna notacija
4. Kanonsko numeriranje pravilnih grafova
5. Zaključci
Književnost
SIMETRIJA I SPEKTRI GRAFOVA. NJIHOVA PRIMJENA U KEMIJI. K. Balasubramanian
1. Uvod
2. Orezivanje stabala
3. Orezivanje stabala i grupe simetrije stabala
4. Spektralni polinomi stabala dobiveni postupkom rezidbe
5. Primjene u kemiji
Književnost
GRUPE AUTOMORFIZAMA NEKIH KEMIJSKIH GRAFOVA. G. Jones, E. Lloyd
1. Uvod
2. Neki grafovi i njihove grupe
3. Reakcijski grafikoni
3.1. Primjer 1: Berry mehanizam
3.2. Primjer 2: 1,2-pomaci karbonijevih iona
3.3. Primjer 3: 1,2-pomaci u homotetraedranilnim kationima
3.4. Primjer 4: Digonalni zavoji u oktaedarskim kompleksima
3.5. Primjer 5: 1,3-pomaci u homotetraedranilnim kationima
4. Suborbitalni grafovi
5. Zaključci
Književnost
PROBLEM OBNOVE. W. Tutt
UPORABA RIEMANNOVIH ploha u grafeoretskom prikazu MÖBIUSOVA SUSTAVA. A. Day, R. Mullion, M. Rigby
1. Uvod
2. Formalizam metode
3. Primjena
4. Zaključci
Književnost
GLOBALNA DINAMIKA NEKIH KLASA REAKCIJSKIH SUSTAVA. X. Dimenzija
1. Uvod
2. Teorijska formulacija grafova
2.1. Struktura jednadžbi upravljanja
2.2. Neki pojmovi teorije grafova
2.3. Invarijante reakcije
2.4. Postojanje stacionarnih stanja
3. Mreže vođene vrhovima
3.1. Konstantni ulazni tokovi
3.2. Periodični ulazni tokovi
4. Zaključci
Književnost
“LOGIČKI OPIS” NASPRAM “KONTINUIRANOG OPISA” SUSTAVA KOJI SADRŽE POVRATNE PETLJE: ODNOS IZMEĐU VREMENSKIH KAŠNJENJA I PARAMETARA. R. Thomas
1. Uvod
2. Logički opis sustava koji sadrže povratne sprege
2.1. Odgode “uključenja” i “isključenja”.
2.2. Logičke jednadžbe
2.3. Državni stolovi
2.4. Krugovi (nizovi stanja)
2.5. Analiza stabilnosti
3. Kontinuirano opisivanje
3.1. Logička vremenska kašnjenja i kontinuirani parametri
Književnost
KVALITATIVNA DINAMIKA I STABILNOST KEMIJSKIH REAKCIJSKIH SUSTAVA. B. Clark
1. Uvod
2. Određivanje kemijskog sustava
3. Vremenske skale - uklanjanje tvari koje reagiraju prebrzo i presporo
4. Teorija kemijskih mreža
5. Dinamika sustava
6. Raznolikost stacionarnih stanja
7. Jednostavni teoremi za analizu mreže
8. Dublja rasprava o stacionarnim stanjima i njihovom postojanju
9. Ispravnost
10. Jednoznačnost
11. Globalna privlačnost
12. Mreže u kojima različitost nije ispravna, jednoznačna i globalno atraktivna
13. Topologija i stabilnost mreže
14. Zaključna razmatranja
15. Primjena
15.1. Svestrane značajke
15.2. Funkcije za simboličku obradu i izračun strujne matrice
15.3. Provjera teorema i srodne funkcije
15.4. Individualne funkcije
Književnost
VIŠI KAOS U JEDNOSTAVNIM REAKCIJSKIM SUSTAVIMA. O. Ressler, J. Hudson
1. Uvod
2. Metoda generiranja običnog kaosa
3. Metoda generiranja višeg kaosa
4. Rasprava
Književnost
ČUDNI ATRAKTORI U LINEARNIM PERIODIČKIM PRIJENOSNIM FUNKCIJAMA S PERIODIČKIM POREMEĆAJIMA. X. Degn
1. Uvod
2. Rezultati
Književnost
PRIMJENA ANALIZE OSJETLJIVOSTI U ODREĐIVANJU STRUKTURNE STABILNOSTI VIŠEPARAMETARSKIH OSCILATORA. R. Kasnije
1. Uvod
2. Metoda
2.1. Standardna teorija
2.2. Modificirana teorija
3. Rezultati
3.1. Početni uvjeti
3.2. Konstante brzine
3.3. Složenije situacije
Književnost
PREDSTAVLJANJE n-DIMENZIONALNIH KEMIJSKIH RAZLIČITAK POMOĆU ELEKTRIČNIH MREŽA. L. Puzner
1. Uvod: topološka i geometrijska analiza kemijskih procesa
2. Osnovna geometrijska svojstva n-dimenzionalnih metričkih mnogoznačnika
3. Reprezentacija kao mreža
4. Primjer za dvodimenzionalni sustav
5. Optimalne staze
6. Primjer korištenja kemijske mreže za linearne prijelaze između više stanja
7. Varijacijske mreže
Primjena: Analiza mreže
Književnost
LOGIKA KEMIJSKIH IDEJA. P. Plyat, E. Hass
1. Uvod
2. Topologija pericikličkih reakcija
3. Rešetke pericikličkih reakcija
4. Ortomodularne i Booleove reakcijske četverodimenzionalne rešetke
5. Zaključci
Književnost
VIŠEDIMENZIONALNI X-MODEL. GRAFEORETIJSKI I ALGEBARSKI PRISTUP OPISU MEHANIZAMA SLOŽENIH KEMIJSKIH REAKCIJA. E. Hass, P. Plyat
1. Uvod
2. Jednoparametarski X-model
3. Višedimenzionalni X-model
3.1. Reakcijski putovi za -cikloadicije
4. Zaključci
Književnost
KLASIFIKACIJA MEHANIZAMA KEMIJSKIH REAKCIJA S GEOMETRIJSKOG GLEDIŠTA. P. Prodavači
1. Uvod
2. Milnerov primjer
3. Mehanizmi bez ciklusa
4. Ostali mehanizmi
5. Višestruke ukupne reakcije
6. Zaključci
Književnost
GRAFIKONI, MODELI POLIMERA, ISKLJUČENI VOLUMEN I KEMIJSKA STVARNOST. D. Klein, W. Seitz
1. Uvod
2. Izolirani linearni krugovi
3. Brojanje izomera
4. Konformacije razgranatih polimera
5. Teorija skaliranja
6. Prijenosne matrice
7. Samosličnost i renormalizacija
8. Rasprava
Književnost
FUNKCIJA VOLUMENA ​​ZA VODU NA TEMELJU NASLUČAJNOG MODELA PODGRAPA REŠETKE. L. Quintas
1. Uvod i prethodne matematičke napomene
2. Model slučajnog grafa za vodu
3. Funkcija volumena za vodu
4. Podudarnost V(p) s numeričkim podacima
5. Zaključna razmatranja
Književnost
TOPOLOŠKI ASPEKTI PREPOZNAVANJA ENZIMA-SUPSTRATA. S. Swaminathan
1. Problem prepoznavanja enzim-supstrat
2. Edelstein-Rosenov model
3. Metoda fenomenološkog računa
4. Hilbertov prostor opisa
5. Postulati za dinamiku složenih sustava
6. Model prepoznavanja enzim-supstrat
7. Zaključna razmatranja
Književnost
DINAMIKA STVARANJA SEKUNDARNE STRUKTURE RNK. X. Martinets
1. Uvod
2. Metode minimizacije energije
3. Metoda simulacije
4. Zaključci
Književnost
PROGRAM U LISP JEZIKU ZA FUNKCIONALNO-FRAGMENTALNO PRIKAZIVANJE MOLEKULA I NJIHOVE GEOMETRIJE. K. Trindl, R. Givan
1. Uvod
2. Lisp - nenumerički programski jezik
3. Predstavljanje molekula pomoću Lisp jezika
4. Neformalni algoritam za prepoznavanje fragmenata
5. Neki posebni problemi
6. Konstrukcija matrice udaljenosti korištenjem baze podataka fragmenata
7. Faktorska analiza i Crippenov algoritam za određivanje geometrije kroz udaljenosti
8. Zaključci i izgledi
Književnost
Indeks predmeta

Za izradu automatiziranih programskih kompleksa. sinteza optimalna. visoko pouzdana proizvodnja (uključujući uštedu resursa) zajedno s načelima umjetnosti. inteligencije, koriste orijentirane semantičke, ili semantičke, grafove opcija CTS rješenja. Ovi grafikoni, koji su u konkretnom slučaju stabla, prikazuju postupke za generiranje skupa racionalnih alternativnih CTS shema (na primjer, 14 mogućih pri odvajanju peterokomponentne smjese ciljnih proizvoda rektifikacijom) i postupke za uređen odabir između njih shema koja je optimalna prema određenom kriteriju učinkovitosti sustava (vidi Optimizacija).

Teorija grafova također se koristi za razvoj algoritama za optimizaciju vremenskih rasporeda za rad fleksibilne opreme za više proizvoda, optimizacijskih algoritama. postavljanje opreme i trasiranje cjevovodnih sustava, optimalni algoritmi. upravljanje kemijskom tehnologijom procesa i proizvodnje, tijekom mrežnog planiranja svog rada itd.

Lit.. Zykov A. A., Teorija konačnih grafova, [in. 1], Novosibirsk, 1969.; Yatsimirsky K. B., Primjena teorije grafova u kemiji, Kijev, 1973.; Kafarov V.V., Perov V.L., Meshalkin V.P., Principi matematičkog modeliranja kemijskih tehnoloških sustava, M., 1974; Christofides N., Teorija grafova. Algoritamski pristup, trans. s engleskog, M., 1978.; Kafarov V.V., Perov V.L., Meshalkin V.P., Matematičke osnove računalno potpomognutog projektiranja kemijske proizvodnje, M., 1979; Kemijske primjene topologije i teorije grafova, ur. R. King, prev. s engleskog, M., 1987.; Kemijske primjene teorije grafova, Balaban A.T. (Ed.), N.Y.-L., 1976. V. V. Kafarov, V. P. Meshalkin.
===
španjolski literatura za članak "TEORIJA GRAFOVA": nema podataka

Stranica "TEORIJA GRAFOVA" pripremljen na temelju materijala

E. Babaev.  Kandidat kemijskih znanosti.

      Kada se govori o matematizaciji znanosti, najčešće se misli samo na čisto pragmatičnu upotrebu računalnih metoda, zaboravljajući prikladnu izjavu A. A. Lyubishcheva o matematici kao ne toliko sluškinji, već kao kraljici svih znanosti. Razina matematizacije dovodi ovu ili onu znanost u kategoriju egzaktnih, ako pod tim ne mislimo na korištenje točnih kvantitativnih procjena, već na visoku razinu apstrakcije, slobodu operiranja pojmovima vezanim uz kategorije ne - numerička matematika.
      Među metodama takve kvalitativne matematike koje su našle učinkovitu primjenu u kemiji, glavna uloga pripada skupovima, grupama, algebrama, topološkim konstrukcijama i, prije svega, grafovima - najopćenitijoj metodi predstavljanja kemijskih struktura.

Uzmimo, na primjer, četiri točke proizvoljno smještene na ravnini ili prostoru i spojimo ih s tri pravca. Bez obzira na to kako su te točke (zvane vrhovi) smještene i bez obzira na to kako su međusobno povezane crticama (zvanim bridovi), dobivamo samo dvije moguće strukture grafa, koje se međusobno razlikuju po međusobnom rasporedu veza: jedan graf, sličan slovima "P" ili "I", a drugi graf sličan slovima "T", "E" ili "U". Ako umjesto četiri apstraktne točke uzmemo četiri atoma ugljika, a umjesto crtica uzmemo kemijske veze između njih, tada će dva navedena grafikona odgovarati dvama mogućim izomerima butana - normalnoj i izostrukturi.
      Što je uzrokovalo rastući interes kemičara za teoriju grafova, ovaj bizaran, ali vrlo jednostavan jezik točkica i linija?
      Graf ima izvanrednu osobinu da ostaje nepromijenjen bez obzira na deformacije strukture koje nisu popraćene prekidom veza između njegovih elemenata. Struktura grafa može biti iskrivljena, potpuno ga lišavajući simetrije u uobičajenom smislu; međutim, graf će i dalje imati simetriju u topološkom smislu, određenu istovjetnošću i zamjenjivošću krajnjih vrhova. S obzirom na ovu skrivenu simetriju, može se, na primjer, predvidjeti broj različitih izomernih amina dobivenih iz struktura butana i izobutana zamjenom atoma ugljika s atomima dušika; grafovi omogućuju korištenje jednostavnih fizičkih razmatranja za razumijevanje uzoraka tipa "svojstva strukture".
      Još jedna, pomalo neočekivana ideja je izraziti strukturne kvalitete grafova (na primjer, stupanj njihovog grananja) pomoću brojeva. Intuitivno osjećamo da je izobutan razgranatiji od normalnog butana; Kvantitativno se to može izraziti, recimo, činjenicom da se u molekuli izobutana strukturni fragment propana ponavlja tri puta, a u normalnom butanu samo dva puta. Ovaj strukturni broj (nazvan Wienerov topološki indeks) iznenađujuće dobro korelira sa karakteristikama zasićenih ugljikovodika kao što su vrelište ili toplina izgaranja. Nedavno se pojavila neobična moda za izum različitih topoloških indeksa; već ih je više od dvadeset; Njezina primamljiva jednostavnost čini ovu Pitagorinu metodu sve popularnijom *.
      Upotreba teorije grafova u kemiji nije ograničena na strukturu molekula. Još tridesetih godina A. A. Balandin, jedan od prethodnika moderne matematičke kemije, proglasio je princip izomorfne supstitucije, prema kojem isti graf nosi jedinstvenu informaciju o svojstvima najrazličitijih strukturiranih objekata; važno je samo jasno definirati koji se elementi odabiru kao vrhovi i kakvi će se odnosi među njima izražavati bridovima. Dakle, osim atoma i veza, kao vrhove i rubove možete odabrati faze i komponente, izomere i reakcije, makromolekule i interakcije među njima. Može se uočiti duboki topološki odnos između Gibbsovog faznog pravila, stehiometrijskog Horiuchijevog pravila i racionalne klasifikacije organskih spojeva prema stupnju njihove nezasićenosti. Uz pomoć grafova uspješno se opisuju interakcije među elementarnim česticama, spajanje kristala, dioba stanica... U tom smislu teorija grafova služi kao vizualni, gotovo univerzalni jezik interdisciplinarne komunikacije.

Razvoj svake znanstvene ideje tradicionalno prolazi kroz sljedeće faze: članak prikaz monografija udžbenik. Idejni cvat zvan matematička kemija već je prošao fazu recenzije, iako još nije dosegao status akademske discipline. Zbog raznolikosti područja, glavni oblik publikacija u ovom području sada su zbirke; nekoliko takvih zbirki objavljeno je 1987.-1988.
      Prva zbirka koju je uredio R. King "Kemijske primjene topologije i teorije grafova" (M., "Mir", 1987.) sadrži prijevod izvješća s međunarodnog simpozija na kojem su sudjelovali kemičari i matematičari iz različitih zemalja. Knjiga daje cjelovitu sliku šarolike palete pristupa koji su se pojavili na sjecištu teorije grafova i kemije. Dotiče se vrlo širokog spektra pitanja, počevši od algebarske strukture kvantne kemije i stereokemije, čarobnih pravila elektroničkog brojanja, pa sve do strukture polimera i teorije otopina. Organske kemičare nedvojbeno će privući nova strategija za sintezu molekularnih čvorova trolisnog tipa, eksperimentalna implementacija ideje molekularne Möbiusove trake. Od posebnog interesa bit će pregledni članci o korištenju već spomenutih topoloških indeksa za procjenu i predviđanje širokog spektra svojstava, uključujući biološku aktivnost molekula.
      Prijevod ove knjige koristan je i zato što pitanja koja se u njoj postavljaju mogu pomoći u rješavanju niza diskutabilnih problema na području metodologije kemijske znanosti. Tako je odbacivanje matematičke simbolike rezonancijskih formula od strane nekih kemičara u 50-ima ustupilo mjesto u 70-ima negiranju samog koncepta kemijske strukture od strane nekih fizičara. U okviru matematičke kemije takve se proturječnosti mogu eliminirati, primjerice, pomoću kombinatorno-topološkog opisa klasičnih i kvantnih kemijskih sustava.
      Iako radovi sovjetskih znanstvenika nisu predstavljeni u ovoj zbirci, zadovoljstvo je primijetiti povećani interes za probleme matematičke kemije u domaćoj znanosti. Primjer je prva radionica “Molekularni grafovi u kemijskim istraživanjima” (Odesa, 1987.), koja je okupila stotinjak stručnjaka iz cijele zemlje. U usporedbi s inozemnim istraživanjima, domaći se rad ističe izraženijom primijenjenom prirodom, usmjerenošću na rješavanje problema računalne sinteze i stvaranje različitih banaka podataka. Unatoč visokoj razini izvješća, na sastanku je konstatirano nedopustivo zaostajanje u školovanju specijalista matematičke kemije. Samo na sveučilištima u Moskvi i Novosibirsku održavaju se povremeni tečajevi o pojedinim pitanjima. U isto vrijeme, vrijeme je da se ozbiljno postavi pitanje: kakvu bi matematiku studenti kemije trebali učiti? Doista, čak ni u sveučilišnim matematičkim programima kemijskih odjela takvi dijelovi kao što su teorija grupa, kombinatorne metode, teorija grafova i topologija praktički nisu zastupljeni; zauzvrat, sveučilišni matematičari uopće ne studiraju kemiju. Uz problem obuke, hitno je pitanje znanstvenih komunikacija: potreban je svesavezni časopis o matematičkoj kemiji, koji bi izlazio barem jednom godišnje. Časopis "MATCH" (Mathematical Chemistry) već dugi niz godina izlazi u inozemstvu, a naše publikacije raspršene su po zbirkama i najrazličitijim časopisima.

Donedavno se sovjetski čitatelj mogao upoznati s matematičkom kemijom samo iz knjige V. I. Sokolova “Uvod u teorijsku stereokemiju” (M.: Nauka, 1979.) i brošure I. S. Dmitrieva “Molekule bez kemijskih veza” (L.: Khimiya). , 1977). Djelomično popunjavajući tu prazninu, sibirski ogranak izdavačke kuće Nauka objavio je prošle godine knjigu “Primjena teorije grafova u kemiji” (priredili N. S. Zefirov, S. I. Kuchanov). Knjiga se sastoji od tri dijela, od kojih je prvi posvećen korištenju teorije grafova u strukturnoj kemiji; drugi dio ispituje grafove reakcija; treći pokazuje kako se grafovi mogu koristiti za olakšavanje rješenja mnogih tradicionalnih problema u kemijskoj fizici polimera. Naravno, ova knjiga još nije udžbenik (značajan dio razmatranih ideja izvorni su rezultati autora); ipak se prvi dio zbirke može u potpunosti preporučiti za početno upoznavanje s temom.
      Još jedan zbornik radova seminara Kemijskog fakulteta Moskovskog državnog sveučilišta “Principi simetrije i sustavnosti u kemiji” (uredio N. F. Stepanov) objavljen je 1987. godine. Glavna tema zbornika su teorijske metode grupa, teorije grafova i sustava u kemiji. Raspon pitanja o kojima se raspravlja je nekonvencionalan, a odgovori na njih još su manje standardni. Čitatelj će doznati, primjerice, o razlozima trodimenzionalnosti prostora, o mogućem mehanizmu nastanka disimetrije u živoj prirodi, o principima oblikovanja periodnog sustava molekula, o ravninama simetrije kemijskih reakcijama, o opisu molekularnih oblika bez korištenja geometrijskih parametara i još mnogo toga. Nažalost, knjiga se može naći samo u znanstvenim knjižnicama, budući da nije otišla u opću prodaju.
    Budući da govorimo o principima simetrije i sustavnosti u znanosti, nemoguće je ne spomenuti još jednu neobičnu knjigu "Sustav" (M.: Mysl., 1988). Ova knjiga posvećena je jednoj od varijanti takozvane opće teorije sustava (GTS), koju je predložio i razvio Yu.A humanističke znanosti. Početna načela Urmantseva OTS-a su koncepti sustava i kaosa, polimorfizma i izomorfizma, simetrije i asimetrije, kao i harmonije i disharmonije.
      Čini se da bi Urmantsevljeva teorija trebala privući najveću pozornost kemičara, makar samo zato što tradicionalno uzdiže kemijske koncepte sastava, izomerije i disimetrije na rang onih koji se odnose na cijeli sustav. U knjizi možete pronaći zapanjujuće analogije simetrije između izomera lišća i molekularnih struktura **. Naravno, pri čitanju knjige ponegdje je nužna i određena razina profesionalne nepristranosti - primjerice, kada je riječ o kemijsko-glazbenim paralelama ili obrazloženju zrcalno-simetričnog sustava elemenata. Ipak, knjiga je prožeta središnjom idejom pronalaženja univerzalnog jezika koji izražava jedinstvo svemira, čemu je možda srodan kastalijski jezik “igre perlama” Hermanna Hessa.
Govoreći o matematičkim strukturama moderne kemije, ne može se zanemariti prekrasna knjiga A.F. Bočkova i V.A. Smitha “Organska sinteza” (M.: Nauka, 1987.). Iako su njezini autori “čisti” kemičari, brojne ideje o kojima se govori u knjizi vrlo su bliske gore navedenim problemima. Ne zadržavajući se na briljantnoj formi prezentacije i dubini sadržaja ove knjige, nakon čijeg čitanja želite prihvatiti organsku sintezu, naglasit ćemo samo dvije točke. Prvo, razmatrajući organsku kemiju kroz prizmu njezina doprinosa svjetskoj znanosti i kulturi, autori povlače jasnu paralelu između kemije i matematike kao univerzalnih znanosti koje objekte i probleme svojih istraživanja crpe iz sebe. Drugim riječima, tradicionalnom statusu matematike kao kraljice i sluškinje kemije, može se dodati osebujna hipostaza njezine sestre. Drugo, uvjeravajući čitatelja da je organska sinteza egzaktna znanost, autori pozivaju na točnost i strogost kako same strukturne kemije tako i na savršenstvo logike kemijskih ideja.
      Ako tako kažu eksperimentatori, ima li sumnje da je došao čas matematičke kemije?

________________________
  * Vidi "Chemistry and Life", 1988, br. 7, str.
** Vidi "Chemistry and Life", 1989, br. 2.