Problémy teórie grafov v chémii. Algebra a harmónia v chemických aplikáciách. Základné definície a vety teórie grafov

• Špeciálna HAC RF02.00.03
• Počet strán 410

Názov dizertačnej práce Doktor chémie Vonchev, Danail Georgiev

Pred polstoročím vyslovil Paul Dirac názor, že v princípe je všetka chémia obsiahnutá v zákonoch kvantovej mechaniky, no v skutočnosti vznikajú pri praktických výpočtoch neprekonateľné matematické ťažkosti. Elektronická výpočtová technológia pomohla zmenšiť vzdialenosť medzi možnosťami a implementáciou kvantovo-mechanického prístupu. Výpočty molekúl s veľkým počtom elektrónov sú však zložité a nie dostatočne presné a doteraz je možné týmto spôsobom vypočítať len niekoľko vlastností molekúl. Na druhej strane v organickej chémii existujú dôležité štruktúrne problémy, ktoré nie sú úplne vyriešené, a to je predovšetkým problém vzťahu medzi štruktúrou a vlastnosťami molekúl. V teoretickej chémii vzniká otázka kvantifikácie základných štruktúrnych charakteristík molekúl – ich vetvenia a cyklickosti. Táto otázka je nevyhnutná, pretože kvantitatívnu analýzu všeobecných zákonitostí v štruktúre rozvetvených a cyklických molekúl možno do značnej miery preniesť na ich ďalšie vlastnosti. Týmto spôsobom by bolo možné predpovedať usporiadanie skupiny izomérnych zlúčenín podľa hodnôt takých vlastností, ako je stabilita, reaktivita, spektrálne a termodynamické vlastnosti atď. To by mohlo uľahčiť predikciu vlastností ešte nesyntetizovaných triedy zlúčenín a hľadanie štruktúr "s vopred určenými vlastnosťami. Napriek značnému úsiliu je stále otvorená otázka racionálneho kódovania chemickej informácie za účelom jej efektívneho ukladania a využitia počítačmi. Optimálne riešenie tejto problematiky by malo vplyv o zlepšení klasifikácie a názvoslovia tak organických zlúčenín, ako aj mechanizmov chemických reakcií.Pred teóriou Periodického sys-4 chemických prvkov nastoľuje aj otázka celostnej a kvantitatívnej interpretácie periodicity vlastností chemických prvkov na základom veličín, ktoré odrážajú elektronickú štruktúru lepšie ako poradové číslo prvku.

V dôsledku toho sa v posledných desaťročiach podnietil vývoj nových teoretických metód v chémii, zjednotených pod názvom matematická chémia. Hlavné miesto v ňom zaujímajú topologické metódy, ktoré odrážajú najvšeobecnejšie štruktúrne a geometrické vlastnosti molekúl. Jedna z oblastí topológie, teória grafov, ponúka chemikom vhodný matematický jazyk na opis molekuly, pretože štruktúrne vzorce sú v podstate chemické grafy. Výhody, ktoré ponúka teória grafov v chemickom výskume, sú založené na možnosti priamej aplikácie jej matematického aparátu bez použitia počítača, čo je dôležité pre experimentálnych chemikov. Teória grafov umožňuje celkom jednoducho ponoriť sa do štruktúrnych charakteristík molekúl. Získané výsledky sú všeobecné a môžu byť formulované ako vety alebo pravidlá, a teda môžu byť aplikované na akékoľvek podobné chemické (a nechemické) objekty.

Po vydaní Shannonových a Wienerových fundamentálnych prác o teórii informácie a kybernetike sa neustále zvyšuje aj záujem o informačno-teoretické metódy výskumu. Pôvodný význam pojmu „informácia“ sa spája s informáciami, správami a ich prenosom. Tento koncept rýchlo opustil hranice komunikačnej teórie a kybernetiky a prenikol do rôznych vied o živej a neživej prírode, spoločnosti a poznaní. Proces rozvoja informačno-teoretického prístupu vo vede je komplikovanejší ako formálny prenos kybernetickej kategórie informácií do iných oblastí poznania. Informačný prístup nie je len preklad z menej bežných jazykov do metajazyka. Ponúka iný pohľad na systémy a javy a umožňuje získať nové výsledky. Rozšírením prepojení medzi rôznymi vednými disciplínami táto metóda umožňuje nájsť užitočné analógie a spoločné vzorce medzi výklenkami. Rozvíjajúca sa moderná veda smeruje k stále väčšej miere zovšeobecňovania, k jednote. V tomto smere je teória informácie jednou z najsľubnejších oblastí.

Významné miesto v tomto procese zaujíma aplikácia teórie informácie v chémii a iných prírodných vedách – fyzike, biológii a pod. V týchto vedách sa metódy teórie informácie využívajú pri štúdiu a popise tých vlastností objektov a procesov. ktoré sú spojené so štruktúrou, usporiadanosťou, organizačnými systémami „Užitočnosť informačného prístupu v chémii spočíva predovšetkým v tom, že sa ponúkajú nové možnosti pre kvantitatívnu analýzu rôznych aspektov chemických štruktúr – atómov, molekúl, kryštálov atď. prípady, pojmy „štrukturálna“ informácia a „informačný obsah“ atómov a molekúl.

V nadväznosti na uvedené je hlavným cieľom dizertačnej práce poukázať na úspešnosť grafo-teoretického a informačno-teoretického prístupu k štrukturálnym problémom v c. chémii, od atómov a molekúl po polyméry a kryštály, dosiahnutie tohto cieľa zahŕňa ako samostatné kroky:

1. Definícia sústavy veličín (informačné a topologické indexy; na kvantitatívnu charakterizáciu atómov, molekúl, polymérov a kryštálov.

2. Vývoj na tomto základe nového, všeobecnejšieho prístupu k otázke korelácie medzi ich vlastnosťami, geometrickou a elektronickou štruktúrou. Predikcia vlastností niektorých organických zlúčenín, polymérov a nesyntetizovaných transaktinidových nMx prvkov.

Tvorba metód pre modelovanie rastu kryštálov a kryštálových vakancí.

3. Zovšeobecnená topologická charakterizácia molekúl vyjadrením podstaty ich vetvenia a cyklickosti v sérii matematicky overených štruktúrnych pravidiel a štúdium mapovania týchto pravidiel rôznymi molekulovými vlastnosťami.

4. Vytváranie nových účinných metód kódovania chemických zlúčenín a mechanizmov chemických reakcií v súvislosti so zlepšením ich klasifikácie a nomenklatúry a najmä v súvislosti s využívaním počítačov na spracovanie chemických informácií.

KAPITOLA 2. METÓDA VÝSKUMU 2L. TEOREGIO-VÝCHOVNÁ METÓDA 2.1.1 „Úvod

Informácie sú jedným z najzákladnejších pojmov modernej vedy, pojmom nie menej všeobecným ako pojmy hmoty a energie. Tento názor nachádza opodstatnenie v samotných definíciách informácií. Podľa Wienera „informácie nie sú ani hmota, ani energia“.

Ashby vníma informácie ako „meradlo diverzity v danom systéme“. Podľa Gluškova sú „informácie mierou nehomogenity v rozložení priestoru a času“. Na tomto základe sa dnes čoraz viac uznáva skutočnosť, že okrem materiálnej a energetickej povahy majú predmety a javy v prírode a technike aj informačné vlastnosti. Niektoré prognózy idú ďalej a predpovedajú, že ťažisko vedeckého výskumu sa bude čoraz viac presúvať smerom k informačnému charakteru procesov, ktoré budú hlavným objektom výskumu v 21. storočí. Tieto prognózy sú v podstate založené na možnosti optimálneho riadenia systémov a procesov prostredníctvom informácií, čo vlastne? je hlavnou funkciou informácií v kybernetike. Tieto myšlienky môžu v budúcnosti viesť k vytvoreniu technológií, v ktorých bude každý atóm a molekula riadená informáciou, čo je možnosť, ktorá sa doteraz realizovala iba v živej prírode.

Vznik teórie informácie sa zvyčajne vzťahuje na rok 1948, keď Claude Shannon publikoval svoje zásadné dielo. Myšlienka informácie ako veličiny súvisiacej s entropiou je však oveľa staršia. V roku 1894 Boltzmann zistil, že akákoľvek informácia získaná o danom systéme je spojená so znížením počtu jeho možných stavov, a preto zvýšenie entropie znamená „stratu informácie“. V roku 1929

Szilard rozvinul túto myšlienku pre všeobecný prípad informácie vo fyzike. jej CP

Neskôr Vrilluin „zovšeobecnil myšlienku vzťahu medzi entropiou a informáciou vo svojom negentropickom princípe vo forme, ktorá pokrýva aj informačnú stránku javov. Otázky o vzťahu medzi teóriou informácie a termodynamikou, a najmä o vzťahu medzi entropiou a informáciou, sú stále predmetom veľkej pozornosti (podrobný zoznam publikácií z tejto oblasti je uvedený v prehľade 58). Z najnovšieho vývoja problematiky treba osobitne poznamenať Kobozevovu prácu o termodynamike myslenia, v ktorej je podložená téza o antientropickom charaktere myšlienkových procesov.

Teória informácie, ktorá vznikla ako „špeciálna teória komunikácie“ rýchlo prerástla svoje pôvodné hranice a našla uplatnenie v rôznych oblastiach vedy a techniky: v chémii, biológii, medicíne, lingvistike, psychológii, estetike atď. biológia bola uznaná ako prvá. Máte vyriešené dôležité otázky týkajúce sa uchovávania, spracovania a prenosu informácií v živých organizmoch, vrátane kódovania genetickej informácie 60-7? posúdenie možnosti spontánneho spontánneho vzniku života na Zemi^, formulácia základných zákonov biologickej termodynamiky^, analýza bioenergetickej problematiky a pod. Ako kvantitatívne kritérium bol použitý informačný obsah objektov

A A A Evolúcia ". Bola nastolená otázka o informačnej povahe procesov výživy ^®^^.

Teória informácie stále pomaly preniká do chémie a fyziky, aj keď v tejto oblasti sa v posledných rokoch dosiahol určitý pokrok, bola nastolená otázka možnej existencie informačnej rovnováhy chemických reakcií. Vykonalo sa hodnotenie informačnej kapacity bioorganických molekúl a na základe toho bola navrhnutá nová klasifikácia týchto zlúčenín a bola posúdená aj špecifickosť chemických reakcií.

Levin, Bernstein a ďalší aplikovali teóriu informácie na molekulárnu dynamiku, aby opísali správanie molekulárnych systémov, ktoré sú ďaleko od rovnováhy. Podstatou tohto prístupu je koncept „prekvapenia“, odchýlky od toho, čo sa očakáva na základe mikrokanonickej distribúcie. Boli navrhnuté rôzne aplikácie, vrátane štúdia výkonu laserov, určenia pomeru vetvenia konkurenčných reakčných dráh (za predpokladu, že dráha zodpovedajúca maximu Shannonovej funkcie je najpravdepodobnejšia) atď.

Dodel a kol., navrhli rozdeliť priestor obsadený molekulárnym systémom do množstva vzájomne sa vylučujúcich podpriestorov nazývaných lóže. Najlepšie lóže obsahujúce lokalizované skupiny elektrónov sa nachádzajú minimalizáciou informačnej funkcie. Sears a kol., našli súvislosť medzi kvantovou mechanickou kinetickou energiou a informačnými veličinami. V dôsledku tohto výsledku možno variačný princíp kvantovej mechaniky formulovať ako princíp minimálnej informácie. ops

Kobozev et al. Tiež sformulovali optimálne informačné podmienky pre charakterizáciu a predikciu katalytických vlastností. Vznik a rast kris

Ou. rp oo tall boli považované za informačný proces“. Rakov podrobil informačnej analýze ošetrenie povrchov katalyzátorov rôznymi chemickými činidlami.

V modernej analytickej chémii narastá trend smerom k optimálnemu experimentovaniu s cieľom získať maximum informácií z minimálneho počtu experimentov.

Tieto nové myšlienky sú založené na teórii informácie, teórii hier a teórii systémov. Iní autori použili teóriu informácie na minimalizáciu chýb a času analýzy, na dosiahnutie vyššej selektivity, na vyhodnotenie účinnosti analytických metód atď. Výskum tohto druhu zahŕňa aj fyzikálne metódy v analytickej chémii vrátane plynovej chromatografie, atómovej emisnej spektrálnej analýzy atď.

Informačno-teoretické metódy sa osvedčili aj v geochémii na charakterizáciu frekvenčného rozloženia chemických zlúčenín v geochemických systémoch,170 na posúdenie stupňa zložitosti a na klasifikáciu týchto systémov.

V inžinierskej chémii možno informačnú analýzu využiť na riešenie takých problémov chemicko-technologických systémov, ako je voľba optimálnych prevádzkových podmienok, stanovenie požiadaviek na riadenie atď.101.

Príklady úspešnej aplikácie teórie informácie v chémii opäť naznačujú, že systémy v prírode a technológie majú aj informačný charakter. Ukazuje tiež, že informačný prístup funguje ako univerzálny jazyk na popis systémov, a najmä chemických štruktúr akéhokoľvek typu, ku ktorým priraďuje určitú informačnú funkciu a číselnú mieru. Rozširuje sa. oblasť možných aplikácií teórie informácie v chémii.

Užitočnosť informačného prístupu v chémii je predovšetkým v tom, že ponúka možnosť kvantitatívnej analýzy rôznych aspektov chemických štruktúr. Mieru zložitosti týchto štruktúr, ich organizáciu a špecifickosť možno porovnávať na jedinej kvantitatívnej škále. To umožňuje študovať niektoré z najvšeobecnejších vlastností chemických štruktúr, ako je ich vetvenie a cyklickosť, skúmať a porovnávať stupeň organizácie v rôznych triedach chemických zlúčenín, špecifickosť biologicky aktívnych látok a katalyzátorov a umožňuje priblížiť otázku miery podobnosti a rozdielu medzi dvoma chemickými objektmi.

Informačný prístup je veľmi vhodný na riešenie osobných klasifikačných problémov. V týchto prípadoch je možné odvodiť všeobecné informačné rovnice pre hlavné zoskupenia objektov klasifikácie (skupiny a obdobia v Periodickej sústave chemických prvkov, homologické rady chemických zlúčenín, rady izomérnych zlúčenín a pod.) *

Veľkú rozlišovaciu schopnosť informačných metód vzhľadom na zložité štruktúry (izoméry, izotopy a pod.) je možné využiť pri počítačovom spracovaní a uchovávaní chemických informácií. Tieto metódy sú užitočné nielen pri výbere medzi rôznymi štruktúrami, ale aj medzi alternatívnymi hypotézami a aproximáciami, čo je zaujímavé pre kvantovú chémiu. Možnosti predloženia nových hypotéz založených na teórii informácie sú však obmedzenejšie, keďže táto teória popisuje vzťah medzi premennými, ale nepopisuje správanie žiadnej z nich.

Problém. Spojenie, ktoré existuje medzi štruktúrou a vlastnosťami, je ďalšou oblasťou úspešnej aplikácie prístupu teórie informácie v chémii. Efektívnosť tohto prístupu ukáže dizertačná práca pre kvalitatívne odlišné štruktúrne úrovne v chémii – elektrónové obaly atómov, molekúl, polymérov, kryštálov a dokonca aj atómových jadier^»^. Dá sa implementovať z kvalitatívneho aj kvantitatívneho hľadiska. V prvom prípade možno na informačnom základe definovať rôzne štrukturálne pravidlá, odrážajúce vzájomný vplyv dvoch alebo viacerých štrukturálnych faktorov. Je tiež možné získať kvantitatívne korelácie medzi informačnými indexmi a vlastnosťami?®. Informačné indexy zároveň v zásade poskytujú lepšie korelácie v porovnaní s inými indexmi, pretože plnšie odrážajú vlastnosti chemických štruktúr. Úspešné korelácie sú možné nielen s veličinami priamo súvisiacimi s entropiou, ale aj s takými veličinami, ako je väzbová energia, ktorej vzťah s informáciou nie je ani zďaleka zrejmý. Tu sú zahrnuté vlastnosti ako samostatná molekula alebo atóm, ale aj ich veľké agregáty, tj vlastnosti, ktoré závisia od interakcie medzi molekulami a atómami, a nielen od ich vnútornej štruktúry. Okrem toho môžu byť procesy v chémii predmetom analýzy informácií na základe zmien informačných indexov počas interakcií.

Treba mať na pamäti aj niektoré obmedzenia informačného prístupu. Hoci sú .ton, kvantitatívne miery informácií sú relatívne, nie absolútne. Sú tiež štatistickými charakteristikami a vzťahujú sa na agregáty, nie však na ich jednotlivé prvky. Informačné indexy možno definovať pre rôzne vlastnosti atómov a molekúl, ale vzťah medzi nimi je často zložitý a implicitný.

Na druhej strane, mať viacero informačných indexov pre jednu štruktúru môže spôsobiť zmiešané pocity. Malo by sa však pamätať na to, že ktorýkoľvek z týchto indexov je legálny. Správna otázka je, ktoré z týchto veličín sú užitočné a do akej miery.

V tejto kapitole sú po prvýkrát predstavené informačno-teoretické indexy:, / charakterizujúce elektrónovú štruktúru atómov, ako aj nové informačné indexy o symetrii, topológii a elektrónovej štruktúre molekúl. Aplikácia týchto štrukturálnych charakteristík je diskutovaná v kapitole III, časti IV.2 a V 1.

2.1.2. Potrebné informácie z teórie informácie

Teória informácie ponúka kvantitatívne metódy na štúdium získavania, uchovávania, prenosu, transformácie a používania informácií. Hlavné miesto v týchto metódach zaujíma kvantitatívne meranie informácií.Definícia pojmu množstvo informácií si vyžaduje odmietnutie rozšírených, no nejasných predstáv o informáciách ako množine, faktoch, informáciách, poznatkoch.

Pojem množstvo informácií úzko súvisí s pojmom entropia ako miera neistoty. V roku 1923 Hartley charakterizoval neistotu experimentu s n rôznymi výsledkami číslom ¿od n. V Shannonovej štatistickej teórii informácie, publikovanej v roku 1948, je množstvo informácií definované prostredníctvom pojmu pravdepodobnosti. Je známe, že tento pojem sa používa na opis situácie, v ktorej existuje neistota spojená s výberom jedného alebo viacerých prvkov (výsledkov) z určitého súboru. Po Shannone, miera neistoty výsledku X/experiment X s pravdepodobnosťou p(X¡) -¿Oy(X)) . Miera priemernej neistoty celého experimentu X s Xt, X2, ♦ možnými výsledkami, s pravdepodobnosťami p(X4), p(X2). chp(Xn), je množstvo

H(x) = - pcx,) Log p(Xi) cg>

V teórii štatistickej informácie sa H(X) nazýva entropia rozdelenia pravdepodobnosti. Posledne menované v prípade /7 rôznych výsledkov tvoria konečnú pravdepodobnostnú schému, t.j.

Pojem pravdepodobnosti možno definovať všeobecnejšie z pohľadu teórie množín. Nech je konečná množina rozdelenie triedy A do triedy /T), v ktorej /\ sú disjunktné množiny; nejakým vzťahom ekvivalencie X * Množina tried ekvivalencie

R/X = (2,2; nazýva sa množina faktorov R v X

Kolmogorovova pravdepodobnostná funkcia (pravdepodobnostná korešpondencia) p podlieha trom podmienkam:

Číselný rad PfXf) , P(X2) , ., P(XGG)) sa nazýva rozdelenie oddielu A a Shannonova funkcia H(X) z rovnice (2.1) vyjadruje entropiu oddielu X

Treba mať na pamäti, že pojem entropia v teórii informácie je všeobecnejší ako termodynamická entropia. Ten druhý, považovaný za mieru neporiadku v atómových a molekulárnych pohyboch, je špeciálnym prípadom všeobecnejšieho konceptu entro-! PZI sú mierou akejkoľvek poruchy alebo neistoty alebo rozmanitosti.

Množstvo informácie X je vyjadrené hodnotou oddelenej neistoty. Potom sa priemerná entropia danej udalosti s mnohými možnými výsledkami rovná priemernému množstvu informácií potrebných na výber ľubovoľnej udalosti X z množiny ^ ,X^,. a určuje sa podľa Shannonovho vzorca (y-e 2.1):

I(x) = -K$Lp(x,-)logp(K) = Hw

Tu je K kladná konštanta, ktorá určuje jednotky merania informácií. Za predpokladu, že K \u003d 4 sa entropia (respektíve informácie) meria v desatinných jednotkách. Najpohodlnejší systém merania je založený na binárnych jednotkách (bitoch). V tomto prípade K ~ W2 a logaritmus wur-u(2.4) je vzatý v základe dva a \-! je skrátene označený t. Jedna binárna jednotka informácie (alebo 1 bit) je množstvo informácie, ktoré sa získa, keď výsledok výber medzi dvoma rovnako pravdepodobnými možnosťami je známy a v jednotkách entropie¿ .dgasG\ konverzným faktorom je Voltzmannova konštanta (1.38.10 yj.gra.d~delené /a?Yu.

Je dokázané, že výber logaritmickej funkcie pre množstvo informácií nie je náhodný a je to jediná funkcia, ktorá spĺňa podmienky aktivity a nezápornosti informácie.

Jednoduché aj priemerné informácie sú vždy pozitívne. Táto vlastnosť súvisí s tým, že pravdepodobnosť je vždy menšia ako jedna a konštanta v rovnici (2.4) je vždy kladná. E | & potom zazvoňte ^ Y

13 p(x, -) = H(x, o c2,5) a táto nerovnosť je zachovaná aj po spriemerovaní.

Priemerné množstvo informácií pre danú udalosť (zážitok) X dosahuje maximum pri rovnomernom rozložení pravdepodobností p(X,) - p(X2) =. . .=p(Xn)* t.j. pre p(X)) pre ľubovoľné P:

Pre dvojicu náhodne závislých udalostí X a y je priemerné množstvo informácií tiež vyjadrené Shannonovým vzorcom:

1(xy> = - р(х, yj) № pix, yj) (2,7)

Rovnicu (2.7) možno zovšeobecniť pre akúkoľvek konečnú množinu bez ohľadu na povahu jej prvkov:

1(xy) = -Z Z. P(X,nYj) 16P(X-,nYj) (2.8) sú dve kvocientové množiny P vzhľadom na dva rôzne vzťahy ekvivalencie x a y a K/xy je súčiniteľ- súbor sekcií X; a:

Po zapísaní spoločnej pravdepodobnosti do rovnice (2.7) ako súčin nepodmienenej a podmienenej pravdepodobnosti p(x;, y^ = p(><¡)"P(Уj/x¡) , и представив логарифм в виде сумш»получается уравнение:

1(Xy) = 1(X) x - 1(y/X) (2.9) kde T(x/y) je priemerné množstvo podmienených informácií obsiahnutých v y vo vzťahu k x a je dané:

1(y/X) = -Y p(X, y1) 1B p(Y;/X-,) (2,10)

Definovanie funkcie:

1 (X, y.! = 1 (Y> - 1 (y / X) (2-Sh a jeho nahradenie v rovnici (2.9):

1(xy) - 1(X) + 1(y) -1(x, y) (2.12) je zrejmé, že T(X, y) vyjadruje odchýlku informácie o komplexnom deji (X, y) od aditívnosť informácií o jednotlivých udalostiach (výsledkoch): x a y. Preto G (X, Y) je mierou miery štatistickej závislosti (súvislosti) medzi X a y.vzťah medzi x a y3 je symetrický.

Vo všeobecnom prípade pre štatistický vzťah medzi x a y a priemerným množstvom nepodmienených informácií o X alebo y platia tieto nerovnosti:

Rovnosť v sile, keď je druhý člen v rovnici (2.11) nulový, t.j. keď každé / zodpovedá I, pre ktoré p(y. ¡X))=

Ak sú veličiny X a y nezávislé, t.j. ak v rovnici (2.12) T (X, y) \u003d 0, potom

1(xy) = 1(X)<2Л5>

Táto rovnica vyjadruje vlastnosť aditivity množstva informácie a je zovšeobecnená pre nezávislé náhodné veličiny. prichádza na myseľ:

1(xnx2,.,xn) = 11 1(x/) (2,16)

Známe sú aj pravdepodobnostné prístupy ku kvantitatívnemu určovaniu informácií. Ingarden a Urbanich navrhli axiomatickú/sizvdelenie-Sheinovu informáciu bez pravdepodobnosti vo forme funkcie konečných booleovských kruhov. Značne zaujímavá je epsilon-entropia (kombinatorický prístup) navrhovaná Kolmogorovom^^ a najmä algoritmické určenie množstva informácie. Podľa Kolmogorova sa množstvo informácií obsiahnutých v jednom objekte (množine) vo vzťahu k inému objektu (množine) považuje za „minimálnu dĺžku“ programov, napísaných ako postupnosť núl a jednotiek a umožňujúcich vzájomný pomer jedna k jednej. konverzia; prvý objekt v druhom:: \u003d H (X / y) \u003d W "W I (R) (2-17)

Kolmogorovov algoritmický prístup ponúka nové

17 logických základov teórie informácie založených na pojmoch zložitosť a postupnosť, takcha&Yn-koncepty „entropia“ a „množstvo informácie“ sa ukázali byť aplikovateľné na jednotlivé objekty.

Neuveriteľné metódy v teórii informácie rozširujú obsah pojmu množstvo informácie z množstva zníženej neistoty na množstvo zníženej uniformity alebo na množstvo diverzity v súlade s Ashbyho výkladom. Akýkoľvek súbor pravdepodobností normalizovaných na jednotu možno považovať za zodpovedajúci určitému súboru prvkov, ktoré majú rozmanitosť. Rozmanitosť sa chápe ako charakteristika prvkov množiny, ktorá spočíva v ich odlišnosti, nezhode vzhľadom na nejaký vzťah ekvivalencie. Toto @ môže byť množina "rôznych prvkov, vzťahov, vzťahov, vlastností objektov. Najmenšia jednotka informácie, bit, pri tomto prístupe vyjadruje minimálny rozdiel, teda rozdiel medzi dvoma objektmi, ktoré nie sú totožné, líšia sa nejakou vlastnosťou .

V tomto aspekte sú informačno-teoretické metódy aplikovateľné na definíciu tzv. štruktúrna informácia je množstvo informácií obsiahnutých v štruktúre daného systému. Štruktúrou sa tu rozumie akákoľvek konečná množina, ktorej prvky sú rozdelené do podmnožín (tried ekvivalencie) v závislosti od určitého vzťahu ekvivalencie.

Nech táto štruktúra obsahuje prvky A/ a tie sú rozdelené podľa nejakého kritéria ekvivalencie do podmnožín ekvivalentných prvkov: . Toto rozdelenie zodpovedá konečnej pravdepodobnostnej schéme podmnožiny pravdepodobnosti ^ pn p2> . . ?Rp prvky

2.18) kde ¿TA/"u je pravdepodobnosť, že jeden (náhodne) vybraný prvok spadne do / - tej podmnožiny, pre ktorú sú A/,-prvky. Entropia H rozdelenia pravdepodobnosti prvkov tejto štruktúry, určená rovnicou (2.4), možno považovať / za mieru priemerného množstva informácií, I, ktoré sú obsiahnuté v jednom prvku štruktúry: - p

1u P/ , bity na prvok (2,19)

Všeobecný informačný obsah štruktúry je daný derivačnou rovnicou (2.19):

1-M1-A//0/h-hnmm,<*.»>

V literatúre neexistuje konsenzus o tom, ako pomenovať veličiny definované pomocou y-y (2.19) a (2.20). Niektorí autori ich radšej označujú ako priemerný a všeobecný informačný obsah, resp. Podľa Moushowitza teda I nie je mierou entropie v zmysle, v akom sa používa v teórii informácie, keďže nevyjadruje priemernú neistotu štruktúry pozostávajúcej z /\/ prvkov v súbore všetkých možných štruktúr, ktoré majú rovnaký: počet prvkov. I je skôr informačný obsah uvažovanej štruktúry vo vzťahu k systému transformácií, ktoré ponechávajú systém invariantný. Podľa Rema z rovnice (2.4) meria množstvo informácií po experimente a pred ním je H(x) mierou entropie spojenej s neistotou experimentu. Podľa nášho názoru je „experimentom“, ktorý znižuje neistotu chemických štruktúr (atómov, molekúl a pod.), sám „proces vytvárania týchto štruktúr z ich nesúvisiacich prvkov. Informácie sú tu v prepojenej forme, sú obsiahnuté v štruktúru, a preto sa často používa pojem „informačný obsah“ štruktúry.

Koncepcia štruktúrnej informácie založená na danej interpretácii1 rovníc (2.19) a (2.20) dobre súhlasí s Ashbyho predstavami o množstve informácií ako o množstve diverzity. Keď systém pozostáva z rovnakých prvkov, nie je v ňom žiadna rozmanitosť. V tomto prípade v y-s (2,19) a (2,20)/="/

Pri maximálnej rozmanitosti prvkov v štruktúre je Λ £ = / a informačný obsah štruktúry je maximálny:

4 "* -N16 u, T ^ ^ vi

2.1.3. Informačno-teoretické indexy na charakterizáciu elektrónovej štruktúry atómov chemických prvkov

Odporúčaný zoznam dizertačných prác v odbore "Organická chémia", 02.00.03 VAK kód

• Asymptotické problémy teórie kombinatorického kódovania a teórie informácie 2001, kandidát fyzikálnych a matematických vied Vilenkin, Pavel Alexandrovič2011, kandidát fyzikálnych a matematických vied Shutkin, Jurij Sergejevič

Upozorňujeme, že vyššie uvedené vedecké texty sú zverejnené na posúdenie a získané prostredníctvom rozpoznávania textu pôvodnej dizertačnej práce (OCR). V tejto súvislosti môžu obsahovať chyby súvisiace s nedokonalosťou rozpoznávacích algoritmov. V súboroch PDF dizertačných prác a abstraktov, ktoré dodávame, sa takéto chyby nevyskytujú.

TEÓRIA GRAFOV

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V – P + G = 1, (*)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Abstrakt na tému vyššia matematika na tému:

Aplikácie teórie grafov v chémii

Účinkuje študent skupiny HX-202

Moskva 2011
Grafy sú oblasťou konečnej matematiky, ktorá študuje diskrétne štruktúry; používané na riešenie rôznych teoretických a aplikovaných problémov.
Niektorí základné pojmy. Graf je množina bodov (vrcholov) a množina dvojíc týchto bodov (nie nevyhnutne všetkých) spojených čiarami (obr. 1, a). Ak sú čiary na grafe orientované (to znamená, že šípky ukazujú smer spojenia vrcholov), nazývajú sa oblúky alebo vetvy; ak je neorientovaný, - okraje. Podľa toho sa graf obsahujúci iba oblúky nazýva orientovaný alebo digraf; len okrajovo neorientovaný; oblúky a hrany - zmiešané. Graf, ktorý má viacero hrán, sa nazýva multigraf; graf obsahujúci iba hrany patriace do dvoch jeho nepretínajúcich sa podmnožín (častí) - bipartitný; oblúky (hrany) a (alebo) vrcholy, ktoré zodpovedajú určitým váham alebo číselným hodnotám akýchkoľvek parametrov - vážené. Dráha v grafe je striedavá postupnosť vrcholov a oblúkov, v ktorej sa žiadny z vrcholov neopakuje (napr. a, b na obr. 1, a); obrys - uzavretá dráha, v ktorej sa prvý a posledný vrchol zhodujú (napr. f, h); slučka - oblúk (hrana), ktorý začína a končí v rovnakom vrchole. Reťazec grafov - postupnosť hrán, v ktorých sa žiadny z vrcholov neopakuje (napríklad c, d, e); cyklus je uzavretý reťazec, v ktorom sa jeho počiatočné a konečné vrcholy zhodujú. Graf sa nazýva spojený, ak je ktorýkoľvek pár jeho vrcholov spojený reťazou alebo cestou; inak sa graf nazýva odpojený.
Strom je spojený neorientovaný graf, ktorý neobsahuje cykly ani obrysy (obr. 1b). Preklenutý podgraf nejakého grafu je jeho podmnožina obsahujúca všetky vrcholy a iba určité hrany. Preklenovacím stromom nejakého grafu je jeho kostrový podgraf, ktorým je strom. Grafy sa nazývajú izomorfné, ak existuje zhoda jedna ku jednej medzi množinami ich vrcholov a hrán (oblúkov).
Na riešenie problémov teórie grafov a jej aplikácií sú grafy reprezentované pomocou matíc (priľahlosť, výskyt, dvojriadkový atď.), ako aj špeciálnych. číselné charakteristiky. Napríklad v matici susednosti (obr. 1c) riadky a stĺpce zodpovedajú číslam vrcholov grafu a jej prvky nadobúdajú hodnoty 0 a 1 (resp. neprítomnosť a prítomnosť oblúka medzi daným pár vrcholov); v matici výskytu (obr. 1d) riadky zodpovedajú počtu vrcholov, stĺpce - počtu oblúkov a prvky majú hodnoty 0, + 1 a - 1 (v uvedenom poradí neprítomnosť, prítomnosť oblúka vstupujúceho do vrcholu a opúšťajúci ho). Najbežnejšie číselné charakteristiky: počet vrcholov (m), počet oblúkov alebo hrán (n), cyklomatické číslo alebo poradie grafu (n - m + k, kde k je počet spojených podgrafov v odpojený graf, napríklad pre graf na obr. 1,b bude poradie: 10-6+ 1 =5).
Aplikácia teórie grafov je založená na konštrukcii a analýze rôznych tried chemických a chemicko-technologických grafov, ktoré sa nazývajú aj topologické modely, t.j. modely, ktoré berú do úvahy len charakter spojenia vrcholov. Oblúky (hrany) a vrcholy týchto grafov predstavujú chemické a chemicko-technologické pojmy, javy, procesy alebo objekty a podľa toho aj kvalitatívne a kvantitatívne vzťahy alebo určité vzťahy medzi nimi.

Ryža. 1. Ilustrácia niektorých základných pojmov: a-zmiešaný graf; b-členný strom (plné oblúky a, h, d, f, h) a nejaký podgraf (prerušované oblúky c, e, g, k, l) digrafu; c, r-matice resp. susedstvo a výskyt digrafu.
Teoretické úlohy. Chemické grafy umožňujú predpovedať chemické premeny, vysvetliť podstatu a systematizovať niektoré základné pojmy chémie: štruktúra, konfigurácia, konformácie, kvantovo-mechanické a štatisticko-mechanické interakcie molekúl, izoméria atď. Chemické grafy zahŕňajú molekulárne, bipartitné a signálne grafy. kinetických rovníc reakcií.
Molekulové grafy používané v stereochémii a štruktúrnej topológii, chémii klastrov, polymérov atď., sú neorientované grafy, ktoré zobrazujú štruktúru molekúl (obr. 2). Vrcholy a hrany týchto grafov zodpovedajú atómom a chemickým väzbám medzi nimi.

Ryža. 2. Molekulové grafy a stromy: a, b - multigrafy resp. etylén a formaldehyd; in-mol. izoméry pentánu (stromy 4, 5 sú izomorfné so stromom 2).
V stereochémii organických látok sa najčastejšie využívajú molekulové stromy - kostry molekulových grafov, ktoré obsahujú len všetky vrcholy zodpovedajúce atómom C (obr. 2, a a b). Zostavenie súborov molekulárnych stromov a stanovenie ich izomorfizmu umožňuje určiť molekulárne štruktúry a nájsť celkový počet izomérov alkánov, alkénov a alkínov (obr. 2c).
Molekulové grafy umožňujú zredukovať problémy súvisiace s kódovaním, nomenklatúrou a štruktúrnymi znakmi (vetvenie, cyklickosť atď.) molekúl rôznych zlúčenín na analýzu a porovnávanie čisto matematických znakov a vlastností molekulových grafov a ich stromov, ako aj ako ich zodpovedajúce matice. Na identifikáciu kvantitatívnych korelácií medzi štruktúrou molekúl a fyzikálno-chemickými (vrátane farmakologickými) vlastnosťami zlúčenín bolo vyvinutých viac ako 20 tisíc názvov topologických indexov molekúl (Wiener, Balaban, Hosoyi, Plat, Randich atď.), ktoré sú určené pomocou matíc a numerických charakteristík molekulárnych stromov. Napríklad Wienerov index W \u003d (m 3 + m) / 6, kde m je počet vrcholov zodpovedajúcich atómom C, koreluje s molekulovými objemami a lommi, entalpiami tvorby, viskozitou, povrchovým napätím, chromatografickými konštantami zlúčenín. oktánové čísla uhľovodíkov a dokonca aj fyziologickú aktivitu liečiva.
Dôležitými parametrami molekulových grafov používaných na určenie tautomérnych foriem danej látky a ich reaktivity, ako aj pri klasifikácii aminokyselín, nukleových kyselín, sacharidov a iných komplexných prírodných zlúčenín sú priemerné a plné (H) informačné kapacity. Parameter sa vypočíta podľa Shannonovho vzorca informačnej entropie: , kde p t je pravdepodobnosť, že vrcholy m grafu patria do i-tého typu alebo triedy ekvivalencie k; i = , Parameter. Štúdium molekulárnych štruktúr, ako sú anorganické zhluky alebo Möbiove prúžky, sa redukuje na stanovenie izomorfizmu zodpovedajúcich molekulárnych grafov ukladaním (vkladaním) do zložitých mnohostenov (napríklad mnohostenov v prípade zhlukov) alebo špeciálnych. viacrozmerné povrchy (napríklad Riemannov). Analýza polymérnych molekulárnych grafov, ktorých vrcholy zodpovedajú monomérnym jednotkám a ktorých okraje zodpovedajú chemickým väzbám medzi nimi, umožňuje vysvetliť napríklad vylúčené objemové efekty, ktoré vedú ku kvalitatívnym zmenám v predpovedaných vlastnostiach polymérov.

Ryža. 3. Grafy reakcií: a-bipartitné; b-signál urovanie kinetiky; r1,g2-r-tion; a 1-a6 činidlá; k-rýchlostné konštanty p-tsny; s-komplex Laplaceova transformačná premenná.
Pomocou teórie grafov a princípov umelej inteligencie bol vyvinutý softvér pre systémy na vyhľadávanie informácií v chémii, ako aj automatizované systémy na identifikáciu molekulárnych štruktúr a racionálne plánovanie organickej syntézy. Na praktickú implementáciu operácií na výber racionálnych spôsobov chemických transformácií založených na retrosyntetických a syntonických princípoch na počítači sa používajú viacúrovňové rozvetvené grafy na hľadanie riešení, ktorých vrcholy zodpovedajú molekulovým grafom reaktantov a produktov a oblúky zobrazujú premeny látok.

Ryža. 4. Jednoslučkový chemicko-technologický systém a príslušné grafy: a-štrukturálny diagram; b, c-grafy toku materiálu resp. celkovým hmotnostným prietokom a prietokom zložky A; r - graf tepelného toku; d-fragment sústavy rovníc (f 1 - f 6) materiálovej bilancie, získaný z analýzy grafov na obr. 4b a c; e-bipartitný informačný digraf; g-informačný graf, I-mixér; II-reaktor; III-destilačná kolóna; IV-chladnička; I 1 - I 8 -technol. prúdy; q-hmotnostný tok; entalpia toku H; i. s a i*, s*- resp. skutočné a fiktívne zdroje a záchyty materiálových a tepelných tokov; c je koncentrácia činidla; V je objem reaktora.
Matricové znázornenia molekulových grafov rôznych zlúčenín sú ekvivalentné (po transformácii zodpovedajúcich prvkov matrice) maticovým metódam kvantovej chémie. Preto sa teória grafov používa na vykonávanie zložitých kvantovo-chemických výpočtov: na určenie počtu, vlastností a energií molekulových orbitálov, predpovedanie reaktivity konjugovaných alternantných a nealternantných polyénov, identifikáciu aromatických a antiaromatických vlastností látok atď.
Na štúdium porúch v systémoch pozostávajúcich z veľkého počtu častíc v chemickej fyzike sa používajú takzvané Feynmanove diagramy - grafy, ktorých vrcholy zodpovedajú elementárnym interakciám fyzikálnych častíc, hrán - ich dráham po zrážkach. Najmä tieto grafy umožňujú študovať mechanizmy oscilačných reakcií a určiť stabilitu reakčných systémov.
Na výber racionálnych spôsobov transformácie molekúl reaktantov pre daný súbor známych interakcií sa používajú dvojdielne reakčné grafy (vrcholy zodpovedajú molekulám a týmto reakciám, oblúky zodpovedajú interakciám molekúl v reakcii; obr. 3a). Takéto grafy umožňujú vyvinúť dialógové algoritmy na výber optimálnych spôsobov chemických transformácií, ktoré si vyžadujú čo najmenší počet medzireakcií, minimálny počet činidiel zo zoznamu prijateľných, alebo sa dosiahne najvyšší výťažok produktov.
Signálne grafy rovníc reakčnej kinetiky zobrazujú sústavy kinetických rovníc prezentované vo forme algebraických operátorov (obr. 3b). Vrcholy grafov zodpovedajú takzvaným informačným premenným alebo signálom vo forme koncentrácií činidiel, oblúky zodpovedajú prepojeniam signálov a váhy oblúkov sú určené kinetickými konštantami. Takéto grafy sa používajú na štúdium mechanizmov a kinetiky komplexných katalytických reakcií, komplexných fázových rovnováh pri tvorbe komplexných zlúčenín a tiež na výpočet parametrov aditívnych vlastností roztokov.
Aplikované úlohy. Na riešenie viacrozmerných problémov analýzy a optimalizácie chemicko-technologických systémov (CTS) sa používajú nasledujúce chemicko-technologické grafy (obr. 4): tok, informačný tok, signál a graf spoľahlivosti. Prietokové grafy, ktoré sú váženými digrafmi, zahŕňajú parametrické grafy, materiálové grafy z hľadiska celkových hmotnostných prietokov fyzikálnych tokov a hmotnostných prietokov niektorých chemických zložiek alebo prvkov, ako aj teplotné grafy. Uvedené grafy zodpovedajú fyzikálno-chemickým premenám hmoty a energie v danom CTS.
Parametrické prietokové grafy zobrazujú transformáciu parametrov (hmotnostný tok a pod.) fyzických tokov prvkami CTS; vrcholy grafov zodpovedajú matematickým modelom zariadení, ako aj zdrojom a záchytom uvedených tokov a oblúky zodpovedajú samotným tokom a váhy oblúkov sa rovnajú počtu parametrov zodpovedajúci prietok. Parametrické grafy sa používajú na vývoj algoritmov na analýzu technologických režimov CTS s viacerými slučkami. Takéto algoritmy stanovujú postupnosť výpočtov systémov rovníc matematických modelov jednotlivých zariadení akéhokoľvek systému na určenie parametrov jeho výstupných tokov so známymi hodnotami premenných vstupných tokov.
Grafy materiálových tokov zobrazujú zmeny v spotrebe látok v CTS. Vrcholy grafov zodpovedajú zariadeniam, v ktorých sa transformujú celkové hmotnostné prietoky fyzikálnych tokov a hmotnostné prietoky niektorých chemických zložiek alebo prvkov, ako aj zdroje a záchyty látok tokov alebo týchto zložiek; preto oblúky grafu zodpovedajú fyzikálnym tokom alebo fyzikálnym a fiktívnym (chemické premeny látok v prístrojoch) zdrojom a záchytom akýchkoľvek komponentov a hmotnosti oblúkov sa rovnajú hmotnostným prietokom oboch typov. Grafy tepelného toku zobrazujú tepelné bilancie v HTS; vrcholy grafov zodpovedajú zariadeniam, v ktorých sa menia tepelné náklady fyzických tokov, a navyše zdrojom a záchytom tepelnej energie systému; oblúky zodpovedajú fyzikálnym a fiktívnym (fyz.-chemická premena energie v prístrojoch) tepelným tokom a hmotnosti oblúkov sa rovnajú entalpiám tokov. Materiálové a tepelné grafy slúžia na zostavovanie programov pre automatizovaný vývoj algoritmov na riešenie sústav rovníc materiálových a tepelných bilancií komplexných CTS.
Informačné a akciové grafy zobrazujú logickú a informačnú štruktúru sústav rovníc matematických modelov CTS; sa používajú na vývoj optimálnych algoritmov na výpočet týchto systémov. Bipartitný informačný graf (obr. 4, e) je neorientovaný alebo orientovaný graf, ktorého vrcholy zodpovedajú rovnici f l -f 6 a premenným q 1 - V a vetvy zobrazujú ich vzťah. Informačný graf (obr. 4, g) - digraf zobrazujúci poradie riešenia rovníc; vrcholy grafu zodpovedajú týmto rovniciam, zdroje a prijímače XTS informácií a vetvy zodpovedajú informačným premenným.
Signálové grafy zodpovedajú lineárnym sústavám rovníc matematických modelov chemicko-technologických procesov a systémov. Vrcholy grafov zodpovedajú signálom (napríklad teplota), vetvy - spojeniam medzi nimi. Takéto grafy sa používajú na analýzu statických a dynamických režimov viacparametrových procesov a CTS, ako aj indikátorov mnohých ich najdôležitejších vlastností (stabilita, citlivosť, ovládateľnosť).
Grafy spoľahlivosti sa používajú na výpočet rôznych ukazovateľov spoľahlivosti CTS. Spomedzi početných skupín týchto grafov (napríklad parametrické, logicko-funkčné) sú dôležité najmä takzvané stromy porúch. Každý takýto strom je váženým digrafom, ktorý zobrazuje prepojenie množiny jednoduchých porúch jednotlivých procesov a zariadení CTS, ktoré vedú k množine sekundárnych porúch a výslednej poruche systému ako celku.
Na vytváranie softvérových komplexov pre automatizovanú syntézu optimálnych vysoko spoľahlivých odvetví (vrátane tých, ktoré šetria zdroje), spolu s princípmi umelej inteligencie, orientovanej sémantickej alebo sémantickej, sa využívajú grafy možností riešenia CTS. Tieto grafy, ktoré sú v konkrétnom prípade stromy, znázorňujú postupy na generovanie súboru racionálnych alternatívnych schém CTS (napríklad 14 možných pri oddelení päťzložkovej zmesi cieľových produktov rektifikáciou) a postupy na riadny výber z nich. schému, ktorá je optimálna podľa nejakého kritéria účinnosti systému.
atď.................

E. Babajev.  Kandidát chemických vied.

      Ak hovoríme o matematizácii vedy, najčastejšie sa tým myslí len čisto pragmatické využitie výpočtových metód, pričom sa zabúda na výstižný výrok A. A. Ljubiščeva o matematike ako ani nie tak sluhovi ako kráľovnej všetkých vied. Práve úroveň matematizácie zaraďuje tú či onú vedu do kategórie exaktných – ak tým nemyslíme používanie exaktných kvantitatívnych odhadov, ale vysokú mieru abstrakcie, slobodu pracovať s pojmami súvisiacimi s kategóriami tzv. nenumerická matematika.
      Medzi metódami takejto kvalitatívnej matematiky, ktoré našli efektívne uplatnenie v chémii, majú hlavnú úlohu množiny, grupy, algebry, topologické konštrukcie a predovšetkým grafy - najvšeobecnejšia metóda reprezentácie chemických štruktúr.

Vezmite napríklad štyri body ľubovoľne umiestnené v rovine alebo v priestore a spojte ich tromi čiarami. Bez ohľadu na to, ako sú tieto body (nazývané vrcholy) umiestnené a akokoľvek sú navzájom spojené čiarkami (nazývané hrany), dostaneme len dve možné štruktúry grafu, ktoré sa navzájom líšia vzájomným usporiadaním spojení: jeden graf , podobne ako písmená "П" alebo "I" a ďalší graf, ktorý vyzerá ako písmená "T", "E" alebo "U". Ak namiesto štyroch abstraktných bodov vezmeme štyri atómy uhlíka a namiesto pomlčiek - chemické väzby medzi nimi, potom dva uvedené grafy budú zodpovedať dvom možným izomérom butánu - normálnej a izoštruktúre.
      Aký je dôvod rastúceho záujmu chemikov o teóriu grafov, tento bizarný, ale veľmi jednoduchý jazyk bodiek a pomlčiek?
      Graf má tú pozoruhodnú vlastnosť, že zostáva nezmenený pri akýchkoľvek deformáciách štruktúry, ktoré nie sú sprevádzané prerušením väzieb medzi jeho prvkami. Štruktúra grafu môže byť skreslená, čím sa úplne zbaví symetrie v obvyklom zmysle; napriek tomu si graf zachová symetriu v topologickom zmysle určenú rovnakosťou, zameniteľnosťou koncových vrcholov. Vzhľadom na túto skrytú symetriu je možné napríklad predpovedať počet rôznych izomérnych amínov získaných zo štruktúr butánu a izobutánu nahradením atómov uhlíka atómami dusíka; Grafy umožňujú pomocou jednoduchých fyzikálnych úvah pochopiť aj vzorce typu „štruktúra-vlastnosť“.
      Ďalšou, trochu neočakávanou myšlienkou je použitie čísel na vyjadrenie štrukturálnych kvalít grafov (napríklad stupňa ich vetvenia). Intuitívne máme pocit, že izobután je viac rozvetvený ako normálny bután; Kvantitatívne sa to dá vyjadriť povedzme tak, že štruktúrny fragment propánu sa v molekule izobutánu opakuje trikrát a v normálnom butáne iba dvakrát. Toto štruktúrne číslo (nazývané topologický Wienerov index) prekvapivo dobre koreluje s charakteristikami nasýtených uhľovodíkov, ako je teplota varu alebo spaľovacie teplo. V poslednom čase sa objavila akási móda na vymýšľanie rôznych topologických indexov, je ich už viac ako dvadsať; zvodná jednoduchosť robí túto Pytagorovu metódu čoraz populárnejšou *.
      Použitie teórie grafov v chémii sa neobmedzuje len na štruktúru molekúl. Ešte v tridsiatych rokoch A. A. Balandin, jeden z predchodcov modernej matematickej chémie, hlásal princíp izomorfnej substitúcie, podľa ktorého ten istý graf nesie jednotné informácie o vlastnostiach najheterogénnejších štruktúrovaných objektov; dôležité je len jasne definovať, ktoré prvky sú zvolené ako vrcholy a ktoré vzťahy medzi nimi budú vyjadrené hranami. Takže okrem atómov a väzieb, fáz a komponentov, izomérov a reakcií možno ako vrcholy a hrany zvoliť makromolekuly a interakcie medzi nimi. Možno si všimnúť hlboký topologický vzťah medzi Gibbsovým fázovým pravidlom, Horiuchiho stechiometrickým pravidlom a racionálnou klasifikáciou organických zlúčenín podľa stupňa ich nenasýtenosti. Pomocou grafov sa úspešne opisujú interakcie medzi elementárnymi časticami, kryštálová fúzia, delenie buniek... Teória grafov v tomto zmysle slúži ako vizuálny, takmer univerzálny jazyk interdisciplinárnej komunikácie.

Vývoj každej vedeckej myšlienky tradične prechádza fázami: článok - recenzia - monografia - učebnica. Kvetenstvo myšlienok s názvom matematická chémia už prešlo štádiom recenzií, hoci ešte nedosiahlo status akademickej disciplíny. Vzhľadom na rôznorodosť smerov sú dnes zborníky hlavnou formou publikácií v tejto oblasti; v rokoch 1987-1988 vyšlo niekoľko takýchto zbierok.
      Prvý zborník redigovaný R. Kingom - "Chemické aplikácie topológie a teórie grafov" (M., "Mir", 1987) - obsahuje preklad správ medzinárodného sympózia za účasti chemikov a matematikov z r. rozdielne krajiny. Kniha podáva úplný obraz pestrej palety prístupov, ktoré sa objavili na priesečníku teórie grafov a chémie. Dotýka sa veľmi širokého spektra problémov – od algebraickej štruktúry kvantovej chémie a stereochémie, magických pravidiel elektronického počítania až po štruktúru polymérov a teóriu riešení. Organických chemikov nepochybne pritiahne nová stratégia syntézy molekulárnych uzlov, ako je trojlístok, experimentálna implementácia myšlienky molekulárneho prúžku Mobius. Súhrnné články o použití už uvedených topologických indexov na odhadovanie a predpovedanie širokej škály vlastností až po biologickú aktivitu molekúl budú mimoriadne zaujímavé.
      Preklad tejto knihy je užitočný aj v tom, že problémy v nej uvedené môžu pomôcť odstrániť množstvo diskutabilných problémov v oblasti metodológie chemickej vedy. Odmietanie matematickej symboliky rezonančných vzorcov niektorými chemikmi v 50. rokoch tak bolo v 70. rokoch nahradené odmietnutím samotného pojmu chemická štruktúra jednotlivými fyzikmi. V rámci matematickej chémie možno takéto rozpory eliminovať napríklad pomocou kombinatoriko-topologického opisu klasických aj kvantovo-chemických systémov.
      Hoci v tomto zborníku nie sú prezentované práce sovietskych vedcov, je potešujúce konštatovať zvýšený záujem o problémy matematickej chémie v domácej vede. Príkladom je prvý workshop „Molekulové grafy v chemickom výskume“ (Odessa, 1987), na ktorom sa stretlo asi sto odborníkov z celej krajiny. V porovnaní so zahraničnými štúdiami sa domáce práce vyznačujú výraznejším aplikovaným charakterom, zameraným na riešenie problémov počítačovej syntézy, vytváranie rôznych databáz. Napriek vysokej úrovni správ sa na stretnutí zaznamenalo neprijateľné oneskorenie vo vzdelávaní odborníkov v oblasti matematickej chémie. Len na univerzitách v Moskve a Novosibirsku sa príležitostne uskutočňujú kurzy o jednotlivých problémoch. Zároveň je čas vážne položiť otázku - akú matematiku by mali študenti chémie študovať? Veď ani vo vysokoškolských matematických programoch chemických odborov prakticky nie sú zastúpené také sekcie ako teória grúp, kombinatorické metódy, teória grafov, topológia; zasa univerzitní matematici neštudujú chémiu vôbec. Okrem problému vzdelávania je akútna aj otázka vedeckej komunikácie: je potrebný celoúnijný časopis o matematickej chémii, ktorý vychádza aspoň raz ročne. Časopis „MATCH“ (Mathematical Chemistry) vychádza už dlhé roky v zahraničí a naše publikácie sú roztrúsené po zbierkach a rôznych periodikách.

Donedávna sa sovietsky čitateľ mohol zoznámiť s matematickou chémiou iba prostredníctvom knihy V.I.Sokolova „Úvod do teoretickej stereochémie“ (M.: Nauka, 1979) a I.S., 1977). Čiastočne vypĺňajúc túto medzeru sibírska pobočka vydavateľstva "Nauka" vydala minulý rok knihu "Aplikácia teórie grafov v chémii" (editovali N. S. Zefirov, S. I. Kuchanov). Kniha pozostáva z troch častí, pričom prvá sa zaoberá využitím teórie grafov v štruktúrnej chémii; druhá časť sa zaoberá reakčnými grafmi; tretia ukazuje, ako možno použiť grafy na uľahčenie riešenia mnohých tradičných problémov v chemickej fyzike polymérov. Samozrejme, táto kniha ešte nie je učebnicou (značná časť diskutovaných myšlienok sú pôvodné výsledky autorov); napriek tomu možno prvú časť zborníka plne odporučiť na prvotné zoznámenie sa s témou.
      Ďalší zborník - zborník zo seminára Chemickej fakulty Moskovskej štátnej univerzity "Princípy symetrie a konzistencie v chémii" (editoval N. F. Stepanov) vyšiel v roku 1987. Hlavnou témou zborníka sú skupinovo-teoretické, grafo-teoretické a systémovo-teoretické metódy v chémii. Rozsah diskutovaných otázok je netradičný a odpovede na ne sú ešte menej štandardné. Čitateľ sa dozvie napríklad o príčinách trojrozmernosti priestoru, o možnom mechanizme vzniku disymetrie v živej prírode, o princípoch konštrukcie periodickej sústavy molekúl, o rovinách symetrie chemických reakcií. , o popise molekulárnych foriem bez použitia geometrických parametrov a mnoho ďalších. Knihu, žiaľ, nájdete len vo vedeckých knižniciach, keďže nebola bežne dostupná na predaj.
      Keďže hovoríme o princípoch symetrie a konzistencie vo vede, nemožno nespomenúť ešte jednu nezvyčajnú knihu - "Systém. Symetria. Harmónia" (M.: Thought, 1988). Táto kniha je venovaná jednému z variantov takzvanej všeobecnej teórie systémov (GTS), ktorú navrhol a vyvinul Yu.A. Počiatočnými princípmi Urmantsevovho GTS sú koncepty systému a chaosu, polymorfizmu a izomorfizmu, symetrie a asymetrie, ako aj harmónie a disharmónie.
      Zdá sa, že Urmancevova teória by mala vzbudiť najväčšiu pozornosť chemikov, už len preto, že v nej sú tradičné chemické pojmy zloženia, izoméria, disymetria povýšené na celosystémové. V knihe možno nájsť nápadné analógy symetrie – napríklad medzi izomérmi listov a molekulárnymi štruktúrami**. Samozrejme, pri čítaní knihy je miestami potrebná istá miera profesionálnej nestrannosti – napríklad keď ide o chemicko-hudobné paralely alebo zdôvodnenie zrkadlovo symetrického systému prvkov. Napriek tomu je kniha presiaknutá ústrednou myšlienkou – nájsť univerzálny jazyk vyjadrujúci jednotu vesmíru, ktorý je podobný len kastalštine z „korálkovej hry“ Hermana Hessa.
Keď už hovoríme o matematických konštrukciách modernej chémie, nemožno ignorovať úžasnú knihu A. F. Bochkova a V. A. Smitha „Organická syntéza“ (Moskva: Nauka, 1987). Hoci jej autori sú „čistými“ chemikmi, množstvo myšlienok, o ktorých sa v knihe hovorí, má veľmi blízko k vyššie uvedeným problémom. Bez toho, aby sme sa pozastavovali nad brilantnou formou prezentácie a hĺbkou obsahu tejto knihy, po prečítaní ktorej chcete urobiť organickú syntézu, zdôrazňujeme len dva body. Po prvé, zvažujúc organickú chémiu cez prizmu jej prínosu pre svetovú vedu a kultúru, autori uvádzajú jasnú paralelu medzi chémiou a matematikou ako univerzálnymi vedami, ktoré do seba vťahujú predmety a problémy svojho výskumu. Inými slovami, k tradičnému postaveniu matematiky ako kráľovnej a služobnice chémie možno pridať zvláštnu hypostázu jej sestry. Po druhé, presviedčajúc čitateľa, že organická syntéza je exaktná veda, autori apelujú na presnosť a dôslednosť tak samotnej štruktúrnej chémie, ako aj dokonalosti logiky chemických myšlienok.
      Ak to tvrdia experimentátori, možno pochybovať o tom, že udrela hodina matematickej chémie?

________________________
  * Pozri "Chémia a život", 1988, č. 7, s.22.
** Pozri "Chémia a život", 1989, č. 2.

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

Pripravené

Legkokonets Vladislav, 10A študent

Praktická aplikácia teórie grafov

Dozorca

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

st.Bryukhovetskaya

2011

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

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

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

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

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

4.2 Niektoré zaujímavé úlohy……………………………………….………..9

5. Aplikácia grafov v rôznych oblastiach života ľudí………………………………………...11

6. Riešenie problémov…………………………………………………………………………………...12

7. Záver……………………….………………………………………………………………………….13

8. Zoznam referencií………….……………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………….

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

Úvod

Teória grafov, ktorá sa zrodila pri riešení hádaniek a zábavných hier, sa teraz stala jednoduchým, prístupným a výkonným nástrojom na riešenie problémov súvisiacich so širokou škálou problémov. Grafy sú doslova všadeprítomné. Vo forme grafov je možné interpretovať napríklad cestné diagramy a elektrické obvody, geografické mapy a molekuly chemických zlúčenín, spojenia medzi ľuďmi a skupinami ľudí. Za posledné štyri desaťročia sa teória grafov stala jedným z najrýchlejšie sa rozvíjajúcich odvetví matematiky. Je to spôsobené požiadavkami rýchlo sa rozširujúcej oblasti použitia. Používa sa pri návrhu integrovaných obvodov a riadiacich obvodov, pri štúdiu automatov, logických obvodov, programových vývojových diagramov, v ekonómii a štatistike, chémii a biológii, v teórii plánovania. Preto relevantnosť Téma je spôsobená na jednej strane popularitou grafov a súvisiacich výskumných metód a na druhej strane nevyvinutým uceleným systémom ich implementácie.

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

cieľ výskum bol pomocou grafov naučiť sa rýchlo riešiť praktické problémy.

Výskumná hypotéza. Grafová metóda je veľmi dôležitá a široko používaná v rôznych oblastiach vedy a ľudského života.

Ciele výskumu:

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

2. Preverte efektivitu grafovej metódy pri riešení praktických úloh.

3. Urobte záver.

Praktický význam štúdie je, že výsledky nepochybne vzbudia záujem mnohých ľudí. Neskúšal niekto z vás zostaviť rodokmeň svojej rodiny? A ako to urobiť správne? Šéf dopravného podniku zrejme musí riešiť problém výhodnejšieho využívania dopravy pri preprave tovaru z destinácie do viacerých sídiel. Každý študent čelil logickým transfúznym úlohám. Ukazuje sa, že sa dajú ľahko vyriešiť pomocou grafov.

V práci sa používajú tieto metódy: pozorovanie, vyhľadávanie, výber, analýza.

História vzniku teórie grafov

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

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

[Príloha Obr. 1] Otázkou je, či ich niekto môže obchádzať nepretržite, pričom cez každý most prejde len raz. A potom som bol informovaný, že to ešte nikto nedokázal, ale nikto nedokázal, že je to nemožné. Táto otázka, hoci banálna, sa mi však zdala hodná pozornosti, pretože na jej riešenie nestačí ani geometria, ani algebra, ani kombinatorické umenie. Po dlhom premýšľaní som našiel ľahké pravidlo, založené na úplne presvedčivom dôkaze, pomocou ktorého sa vo všetkých problémoch tohto druhu dá okamžite určiť, či sa takéto kolo dá urobiť cez ľubovoľný počet a ľubovoľne umiestnených mostov alebo nie. Mosty Königsberg sú umiestnené tak, aby ich bolo možné znázorniť na nasledujúcom obrázku [Príloha Obr. 2], kde A označuje ostrov a B , C a D sú časti kontinentu oddelené od seba riečnymi ramenami

Pokiaľ ide o metódu, ktorú objavil na riešenie problémov tohto druhu, Euler napísal:

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

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

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

Základné definície a vety teórie grafov

Teória grafov je matematická disciplína vytvorená úsilím matematikov, preto jej prezentácia zahŕňa potrebné rigorózne definície. Poďme teda k organizovanému predstaveniu základných pojmov tejto teórie.

Definícia 1. Graf je súbor konečného počtu bodov nazývaných vrcholy grafu a párovo spájajúcich niektoré z týchto vrcholov čiar, nazývaných hrany alebo oblúky grafu.

Táto definícia môže byť formulovaná rôzne: graf je neprázdna množina bodov (vrcholov) a segmentov (hran), ktorých oba konce patria danej množine bodov.

V budúcnosti budeme vrcholy grafu označovať latinskými písmenami A, B, C, D. Niekedy je graf ako celok označený jedným veľkým písmenom.

Definícia 2. Vrcholy grafu, ktoré nepatria k žiadnej hrane, sa nazývajú izolované.

Definícia 3. Graf pozostávajúci iba z izolovaných vrcholov sa nazýva nula - počítať .

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

Definícia 4. Graf, v ktorom je každá dvojica vrcholov spojená hranou, sa nazýva úplný.

Označenie: U" – graf pozostávajúci z n vrcholov a hrán spájajúcich všetky možné dvojice týchto vrcholov. Takýto graf možno znázorniť ako n-uholník, v ktorom sú nakreslené všetky uhlopriečky

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

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

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

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

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

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

Definícia 10. Cesta z A do X je postupnosť hrán vedúcich z A do X tak, že každé dve susedné hrany majú spoločný vrchol a žiadna hrana sa nevyskytuje viac ako raz.

Definícia 11. Cyklus je cesta, ktorej začiatočný a koncový bod sú rovnaké.

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

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

Definícia 14. Dva vrcholy A a B v grafe sa nazývajú spojené (nespojené), ak v nich existuje (neexistuje) cesta vedúca z A do B.

Definícia 15. Graf sa nazýva spojený, ak sú spojené každé dva jeho vrcholy; ak graf obsahuje aspoň jeden pár odpojených vrcholov, potom sa graf nazýva rozpojený.

Definícia 16. Strom je súvislý graf, ktorý neobsahuje cykly.

Trojrozmerný model stromu grafu je napríklad skutočný strom so zložito rozvetvenou korunou; rieka a jej prítoky tiež tvoria strom, ale už plochý - na povrchu zeme.

Definícia 17. Neprepojený graf pozostávajúci výlučne zo stromov sa nazýva les.

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

Zvážili sme teda hlavné definície teórie grafov, bez ktorých by nebolo možné dokázať vety a následne riešiť problémy.

Problémy riešené pomocou grafov

Slávne výzvy

Problém obchodného cestujúceho

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

Vyhlásenie o probléme je nasledovné.
Cestujúci obchodník (cestujúci obchodník) musí opustiť prvé mesto, navštíviť mestá 2,1,3..n raz v neznámom poradí a vrátiť sa do prvého mesta. Vzdialenosti medzi mestami sú známe. V akom poradí treba prejsť mestami, aby uzavretá cesta (prehliadka) cestujúceho obchodníka bola čo najkratšia?

Metóda riešenia problému obchodného cestujúceho

Chamtivý algoritmus "choďte do najbližšieho (do ktorého ste ešte nezadali) mesta."
Tento algoritmus sa nazýva „chamtivý“, pretože v posledných krokoch musíte za chamtivosť draho zaplatiť.
Zoberme si napríklad sieť na obrázku [aplikácia obr. 3] predstavujúci úzky kosoštvorec. Nechajte obchodníka začať od mesta 1. Algoritmus „prejsť do najbližšieho mesta“ ho zavedie do mesta 2, potom 3, potom 4; na poslednom kroku budete musieť zaplatiť za chamtivosť a vrátiť sa pozdĺž dlhej uhlopriečky kosoštvorca. Výsledkom nie je najkratšia, ale najdlhšia túra.

Problém Königsbergských mostov.

Úloha je formulovaná nasledovne.
Mesto Königsberg sa nachádza na brehoch rieky Pregel a dvoch ostrovov. Rôzne časti mesta spájalo sedem mostov. V nedeľu mešťania podnikali prechádzky po meste. Otázka: Je možné ísť na prechádzku tak, že keď odídete z domu, vrátite sa a prejdete presne raz cez každý most?
Mosty cez rieku Pregel sú umiestnené ako na obrázku[Príloha Obr.1].

Zvážte graf zodpovedajúci schéme mosta [príloha obr.2].

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

Niekoľko zaujímavých výziev

1. "Trasy".

Úloha 1

Ako si pamätáte, lovec mŕtvych duší Čičikov raz navštívil slávnych vlastníkov pôdy. Navštívil ich v tomto poradí: Manilov, Korobochka, Nozdrev, Sobakevič, Pljuškin, Tentetnikov, generál Betriščev, Petuch, Konstanzholgo, plukovník Koshkarev. Našiel sa diagram, na ktorom Čichikov načrtol relatívnu polohu usadlostí a vidieckych ciest, ktoré ich spájajú. Určte, ktorá usadlosť patrí komu, ak Čičikov neprešiel niektorou z ciest viackrát [príloha obr.4].

Riešenie:

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

Úloha 2

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

Môžete sa pohybovať iba v smere šípok. Každý bod nie je možné navštíviť viac ako raz. Koľkými spôsobmi sa môžete dostať z bodu 1 do bodu 9? Ktorá trasa je najkratšia a ktorá najdlhšia.

Riešenie:

Postupne „stratifikujte“ schému do stromu, začínajúc od vrcholu 1 [aplikácia obr. 7]. Zoberme si strom. Počet možných spôsobov, ako sa dostať od 1 do 9, sa rovná počtu „visiacich“ vrcholov stromu (je ich 14). Je zrejmé, že najkratšia cesta je 1-5-9; najdlhšia je 1-2-3-6-5-7-8-9.

2 "Skupiny, zoznamka"

Úloha 1

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

a) celkovo bol odoslaný párny počet obálok;

b) počet účastníkov, ktorí si vymenili obálky nepárny počet krát, je párny.

Riešenie: Účastníci festivalu nech sú A 1 , A 2 , A 3 . . . , A n sú vrcholy grafu a hrany spájajú dvojice vrcholov reprezentujúcich chlapcov, ktorí si vymenili obálky [Príloha Obr. 8]

Riešenie:

a) stupeň každého vrcholu A i ukazuje počet obálok, ktoré dal účastník A i svojim priateľom. Celkový počet prenesených obálok N sa rovná súčtu stupňov všetkých vrcholov grafu N = krok. Krok 1 +. A 2 + + . . . + krok. A n -1 + krok. A n , N =2p , kde p je počet hrán grafu, t.j. N je párne. Preto bol odoslaný párny počet obálok;

b) v rovnosti N = krok. Krok 1 +. A 2 + + . . . + krok. A n -1 + krok. A n súčet nepárnych členov musí byť párny, a to môže byť len vtedy, ak je počet nepárnych členov párny. A to znamená, že počet účastníkov, ktorí si vymenili obálky nepárny počet krát, je párny.

Úloha 2

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

Riešenie:

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

[aplikácia obr. 9]

Z obrázku je vidieť, že každý z chlapcov - Andrey, Boris a Voloďa - telefonoval všetkým ostatným. Preto títo chalani prišli do kina. Ale Galya a Dasha sa nedokázali dovolať (body D a D nie sú spojené segmentom) a preto v súlade s dohodou neprišli do kina.

Využitie grafov v rôznych oblastiach života ľudí

Okrem uvedených príkladov majú grafy široké využitie v stavebníctve, elektrotechnike, manažmente, logistike, geografii, strojárstve, sociológii, programovaní, automatizácii technologických procesov a odvetví, psychológii, reklame. Takže zo všetkého vyššie uvedeného nevyvrátiteľne vyplýva praktická hodnota teórie grafov, ktorej dôkaz bol cieľom tejto štúdie.

V akejkoľvek oblasti vedy a techniky sa stretnete s grafmi. Grafy sú nádherné matematické objekty, s ktorými môžete riešiť matematické, ekonomické a logické úlohy, rôzne hlavolamy a zjednodušiť podmienky problémov vo fyzike, chémii, elektronike, automatizácii. Mnohé matematické fakty je vhodné formulovať v jazyku grafov. Teória grafov je súčasťou mnohých vied. Teória grafov je jednou z najkrajších a najkrajších matematických teórií. V poslednej dobe nachádza teória grafov čoraz viac aplikácií v aplikovanej problematike. Objavila sa dokonca aj počítačová chémia – pomerne mladá oblasť chémie založená na aplikácii teórie grafov.

Molekulové grafy, používané v stereochémii a štruktúrnej topológii, chémii klastrov, polymérov atď., sú neorientované grafy, ktoré zobrazujú štruktúru molekúl [aplikácia obr. 10]. Vrcholy a hrany týchto grafov zodpovedajú zodpovedajúcim atómom a chemickým väzbám medzi nimi.

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

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

Proteínové siete

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

Hierarchický systémový graf nazývaný strom. Charakteristickým znakom stromu je, že medzi akýmikoľvek dvoma jeho vrcholmi je len jedna cesta. Strom neobsahuje cykly a slučky.

Strom reprezentujúci hierarchický systém má zvyčajne jeden hlavný vrchol, ktorý sa nazýva koreň stromu. Každý vrchol stromu (okrem koreňa) má len jedného predka – ním určený objekt patrí do jednej triedy najvyššej úrovne. Ktorýkoľvek vrchol stromu môže generovať niekoľko potomkov - vrcholov zodpovedajúcich triedam nižšej úrovne.

Pre každý pár vrcholov stromov existuje jedinečná cesta, ktorá ich spája. Táto vlastnosť sa využíva pri hľadaní všetkých predkov, napríklad v mužskej línii, akejkoľvek osoby, ktorej rodokmeň je prezentovaný vo forme rodokmeňa, čo je „strom“ aj v zmysle teórie grafov.

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

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

Riešenie problémov

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

Riešenie:

Najprv si vytvoríme graf všetkých možných trás. [aplikácia obr. 14], berúc do úvahy skutočné cesty medzi týmito sídlami a vzdialenosť medzi nimi. Na vyriešenie tohto problému musíme vytvoriť ďalší graf, strom [aplikácia obr. 15].

Pre pohodlie riešenia označujeme mestá číslami: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Výsledkom je 24 riešení, ale potrebujeme len najkratšie cesty. Zo všetkých riešení sú spokojné len dve, ide o 350 km.

Podobne je to možné a myslím si, že je potrebné počítať aj s reálnou prepravou z jednej lokality do druhej.

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

Riešenie:

Situáciu v každom okamihu možno opísať tromi číslami [príloha obr.16].

Výsledkom sú dve riešenia: jedno na 7 ťahov, druhé na 8 ťahov.

Záver

Aby ste sa naučili riešiť problémy, musíte pochopiť, čo sú, ako sú usporiadané, z akých komponentov sa skladajú, aké sú nástroje, ktoré sa používajú na riešenie problémov.

Pri riešení praktických úloh pomocou teórie grafov sa ukázalo, že na každom kroku, v každej fáze ich riešenia je potrebné uplatniť kreativitu.

Od samého začiatku, v prvej fáze, spočíva v tom, že musíte byť schopní analyzovať a zakódovať stav problému. Druhým stupňom je schematický zápis, ktorý spočíva v geometrickom znázornení grafov a v tomto štádiu je prvok tvorivosti veľmi dôležitý, pretože nie je ľahké nájsť zhody medzi prvkami podmienky a zodpovedajúcimi prvkami grafu. .

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

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

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

Takže zo všetkého uvedeného nevyvrátiteľne vyplýva praktická hodnota teórie grafov, ktorej dôkaz bol cieľom tejto práce.

Literatúra

Berge K. Teória grafov a jej aplikácie. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J.Úvod do konečnej matematiky. -M.: IIL, 1963.

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

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

Zykov A.A. Teória konečných grafov. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Grafy a ich aplikácia. -M.: Školstvo, 1979. -144 s.

"Soros Educational Journal" č. 11 1996 (článok "Ploché grafy");

Gardner M. "Matematický voľný čas", M. "Mir", 1972 (kapitola 35);

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

Dodatok

Dodatok

P

Ryža. 6

Ryža. 7

Ryža. 8

aplikácie

Dodatok

Dodatok

Dodatok

P

Ryža. štrnásť

aplikácie

Dodatok