Aplikácia teórie grafov v chémii. Správa o aplikácii teórie grafov v chémii. Metóda riešenia problému obchodného cestujúceho

• Š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 nomenklatúry 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 holistickej a kvantitatívnej interpretácie periodicity vlastností chemických prvkov na základe na množstvách, 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. TEOREGIÓNOVÁ 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 súvislosti medzi teóriou informácie a termodynamikou, a najmä o vzťahu entropie a informácie, sú stále predmetom veľkej pozornosti (podrobný zoznam publikácií z tejto oblasti je uvedený v recenzii 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. Vzťah, 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äzobná 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, teda 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 agregáte, 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 neusporiadanosti v atómovo-molekulárnych pohyboch, je špeciálnym prípadom všeobecnejšieho konceptu entro-! PZI sú mierou akejkoľvek poruchy, 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

K je tu 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-Shein 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 ako použiteľné pre 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é uznaním pôvodných textov dizertačných prác (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ú.

MDT 547.12:541.14 (083.73)

CHEMIKOVI - O TEÓRII GRAFOV: GRAFY V CHEMICKEJ NOMENKLATURE

Bryuskc Y.E. Pre chemika o teórii grafov: Grafy v chemickej nomenklatúre. Autor sa v tomto článku venuje rôznym otázkam teórie grafov a úlohe grafov v chemickej nomenklatúre pre chemikov.

Monografia je špeciálne venovaná aplikácii grafov v chémii. Zo svojich troch sekcií je pre skúmanú tému najväčší záujem o sekciu „Grafy v štruktúrnej chémii“. A pre chemika, ktorý nevie nič o grafoch, môže celkom účinnú pomoc poskytnúť príloha [1d]. Možno sú monografie vhodné aj pre chemikov. A na zoznámenie sa so súčasným stavom teórie grafov je vhodná ťažká kniha, zrejme pre nematematika, ako niektoré iné knihy o teórii grafov.

Pri prezeraní dostupných informácií o aplikácii teórie grafov v chémii (do roku 2002 vrátane internetu) nadobudol dojem, že možnosť a nevyhnutnosť využitia tejto teórie v chemickom názvosloví bola obídená. Spolu so všeobecnými „chemickými“ informáciami o teórii grafov sa tu pokúšame mierne znížiť tento nedostatok.

1. MOLEKULÁRNE GRAFY

Čo je teda graf? Ide o množinu bodov (neprázdnych a zvyčajne konečných) s čiarami spájajúcimi niektoré z nich (niekedy žiadne, inokedy všetky) (ďalej sú potrebné definície a pojmy uvedené tučnou kurzívou). Pri pohľade na obr. 1 chemik povie, že ide o uhlíkové kostry etánu, butánu, izobutánu a cyklobutánu. A to, že sú inak nakreslené, tu nehrá rolu. A pre cyklobután nemôžete vkladať bodky, ako to robia chemici, kresliacimi napríklad molekuly cyklohexánu, benzénu a jeho analógov (pozri napríklad obr. 2d a ). Takže tu dostali takéto kostrové grafy názov molekulárne grafy (MG). . Zostáva dodať, že v teórii grafov sa body najčastejšie nazývajú vrcholy a čiary, ktoré ich spájajú, sa nazývajú hrany. Aké ďalšie vlastnosti grafov a podľa toho aj MG treba poznamenať. Pre graf je "je jedno", ako je dvojica jeho vrcholov spojená hranou, dôležité je len vedieť, či existuje alebo nie. Preto sa grafy s viacerými hranami nazývajú viacnásobné grafy. Multigrafy tu teda predstavujú MG s dvojitými a/alebo trojitými väzbami (obr. 2). Nepridáme k nim ale výraz „multigrafy“; nedávno to bolo urobené v samotnej teórii grafov (pozri ).

Tu uvedené MG sa teda líšia od grafu iba tým, že ich vrcholy predstavujú atómy.

sme uhlíkové kostry, t.j. bez atómov vodíka, pretože ich pridanie značne komplikuje MG (pozri). To už dávno pochopili organickí chemici, ktorí nepoznajú (samozrejme, nie všetky) grafy, ale vo veľkom využívajú MG. Rebrá symbolizujú väzby medzi niektorými atómami uhlíka.

Ryža. 1. Stupeň MG (a), bután (b, c), izobután (d, e) a cyklobután (f, g)

Ryža. 2. MG s násobnými väzbami (rebrami): butén-1 (a), butén-2 ​​(b), metylpropén (c) a cyklohexén (d)

Uveďme teraz všeobecnejšiu definíciu grafu, trochu upravenú v porovnaní s .

Graf je množina objektov (pevných a je jedno aké - viď definícia vyššie) a daná množina binárnych (párových) vzťahov medzi týmito objektmi.

Takáto definícia (samozrejme v prísnejšej matematickej forme) sa evidentne nachádza vo všetkých knihách o teórii grafov. Ukazuje, že graf zvyčajne ignoruje kvalitatívny rozdiel medzi vrcholmi a hranami. Pre konkrétny graf je dôležité len to, či v ňom tento vrchol-objekt (atóm uhlíka) existuje a tiež, či medzi touto dvojicou vrcholov (atómov) existuje alebo nie je hraničný vzťah (spojenie). Nie je to však vždy tak! A keď to tak nie je, potom sa objavia multigrafy (pozri vyššie) a ich komplikácie pseudografy (v ktorých je hrana pripojená k rovnakému vrcholu vo forme slučky), označené (číslované) grafy, farebné, orientované (digrafy) , vážené grafy a iné. Definícia takýchto grafov takmer vždy obsahuje slová: „Počítajte, kto ... (kto má ...)“. Rovnaké slová by mohli byť uvedené pred definíciou MG (pozri vyššie).

1.1. ŠTRUKTÚRA GRAFU

Čo ešte potrebuje vedieť chemik o grafoch (MG)?

Vrcholy grafu spojené hranou sa nazývajú susedné, spojený vrchol a hrana sa nazývajú incidenty. Počet hrán dopadajúcich na ten istý vrchol sa nazýva jeho stupeň alebo valencia. Obe možnosti sú v samotnej teórii grafov takmer rovnocenné a „jeden zo zakladateľov modernej teórie grafov“ W. Tatt vo svojej knihe používa iba termín „valencia“ a píše, že „Termín“ valencia „bol inšpirovaný chemickými analógiami“. Preto je tu použitie tohto pojmu o to opodstatnenejšie. Vrcholy, ktoré nemajú hrany (napr. MG metánu), sa nazývajú izolované, valencia 1 - visiaca, valencia 2 - bivalentná (v MG je zvyčajne väčšina takýchto vrcholov), valencie 3 a 4 - nodálne. A v MG by sa mali nazývať primárne, sekundárne (neuzlové), terciárne a kvartérne vrcholy alebo atómy uhlíka, ako ich nazývajú chemici.

Niekedy sa v procese štúdia z grafu odstránia niektoré hrany (spojenia) alebo vrcholy. Tieto sú nevyhnutne odstránené so všetkými ich spojeniami, čo vedie k zodpovedajúcemu zníženiu valencie každého z vrcholov susediacich s nimi, ktoré zostávajú v grafe. Zvyšok sa nazýva podgraf pôvodného grafu.

Po tomto postupe odstránime strednú väzbu z butánu MG (obr. 16). Zvyšok je podgraf. Nie je však možné „dostať sa“ z jedného konca tohto grafu na druhý pomocou spojení, hoci tento podgraf je jedným grafom „v pamäti“ butánu MG. V teórii grafov sa takýto graf nazýva rozpojený a jeho spojené časti sa nazývajú komponenty. Ak sa „pozriete pozorne“ z chemického hľadiska, potom takto získaný podgraf butánu MG pozostáva z dvoch etánových MG (pozri obr. 1a). Súvislý graf teda pozostáva z jednej zložky. Graf pozostávajúci iba z izolovaných vrcholov (pozri vyššie), na-

sa nazýva úplne odpojený a opačný graf, v ktorom je každý vrchol spojený hranami so všetkými ostatnými, sa nazýva úplný. Je celkom jasné, že všetky MG obyčajných organických molekúl sú spojené grafy, dokonca aj MG metánu, ktorý pozostáva z jedného izolovaného vrcholu.

1.2. REŤAZE A CYKLY

Na obr. 1 a 2 je vidieť, že v grafe (MG) je takmer vždy postupnosť striedajúcich sa atómov a väzieb. Takáto postupnosť v grafe sa nazýva reťazec. Ale počet jeho „spojov“ v MG sa nebude počítať počtom hran-spojení, ako je to obvyklé v teórii grafov, ale počtom vrcholov-atómov. V teórii grafov je etánový graf, obr. 1a jeden odkaz; budeme uvažovať dve jednotky v MG toho istého etánu a jednu v MG metánu. V teórii grafov bod grafu metánu nemá žiadne väzby. A v chémii je dôležitejšie poznať počet atómov v reťazci v porovnaní s počtom väzieb medzi nimi. Vzhľadom na MG izobutánu týmto spôsobom (obr. 1d) by sa mal považovať za pozostávajúci z dvoch reťazcov. Dlhší reťazec pozostáva z troch vrcholov-atómov, kratší reťazec pozostáva z jedného.

V chémii, najmä v organickom názvosloví, sa pre izobután a zložitejšie podobné štruktúry (napríklad obr. 3a) používa výraz „rozvetvený reťazec“, ako keby išlo o jeden reťazec s nejakými „vetvami“. Štúdia uplatňovania tejto definície ukázala, že zaviedla a zavádza veľmi významný zmätok v názvosloví organických zlúčenín, a preto by sa od nej malo rozhodne upustiť. Pojem „rozvetvenie“ možno ponechať len s ohľadom na prechod z jedného reťazca do druhého, ale nepovažujeme štruktúru za jeden reťazec.

Reťaz sa zmení na cyklus, ak jej začiatok a koniec spojíte novým článkom.

Na obr. Obrázok 3 ukazuje acyklický MG (a) s dvoma reťazcami: 1-5 a 6, 7. Rovnaký obrázok ukazuje, že MG naftalénu (b) a spiroundekánu (c) každý obsahuje dva jednoduché kondenzované cykly so spoločnými atómami. Naftalén MG má dva takéto atómy: 5 a 10, zatiaľ čo spiroundecan MG má jeden, 6. V difenyle sú cykly rozpojené: väzba 7, 6 nie je zahrnutá v žiadnom z nich.

10______ A 1_________________?

Ryža. 3. Očíslované MG: (a) 3-etylpentán, (b) naftalén, (c) spiroundekán a (d) difenyl. V MG'b a d nie je uvedená aromaticita kruhov

1.2.1. BLOKOVANIE, ČLÁNKY, MOSTKY

V teórii grafov sa rozlišujú také grafy, ktoré sa rozpoja až po odstránení viac ako jedného vrcholu. Takýto graf sa nazýva blok. MG cyklohexénu, obr. 2d a naftalén, obr. 3 - bloky a MG spiroundecany nie je blok, pretože na to, aby sa odpojil, stačí odstrániť jeden vrchol 6. Nazýva sa to artikulačný bod. V bifenyle MG sú dva artikulačné body - 6 a 7. A odstránením hrany spájajúcej tieto body tiež dochádza k rozpojenému grafu. Takáto hrana sa nazýva most alebo úžina, tieto hrany nie sú zahrnuté v štruktúre cyklov. V tomto aspekte nemá zmysel uvažovať o acyklickom grafe, pretože všetky hrany v ňom sú mosty a všetky vrcholy, okrem visiacich, sú body artikulácie. Kondenzované cykly, dokonca aj tie, ktoré majú artikulačný bod, sa v organickej chémii označujú ako integrálny cyklický systém a cykly oddelené aspoň jedným mostíkom sú samostatné systémy (v nomenklatúre súbory cyklov).

1.2.2. HAMILTONICKÝ CYKLUS

V MG jednoduchých cyklov je uzavretý reťazec obsahujúci všetky atómy cyklu. Názov takého cyklu je hamiltonovský cyklus (nie „hamiltonovský“). Okrem jednoduchých hamiltonovských cyklov existuje cyklus v mnohých kondenzovaných cykloch, napríklad v naftaléne MG, obr. 36. Na MG obr. Reťazce 3v a 3g obsahujú všetky atómy MG, ale nie sú uzavreté v cykloch. Takýto reťazec sa nazýva hamiltonovský reťazec. Hamiltonovský reťazec je prítomný v MG normálneho uhľovodíka, napríklad butánu (obr. 16, c).

1.2.3. STROMY. CYKLICKÝ RANK

V teórii grafov sú teda prezentované dve základné formy grafov: stromy a cykly (jednoduché a kondenzované), ktoré v chémii jednoznačne zodpovedajú dvom triedam MG: necyklickým (acyklickým) a cyklickým uhľovodíkom (obr. 3). Iba spojený acyklický graf sa nazýva strom, zodpovedajúci nesúvislý je les.

Chemici bez toho, aby poznali teóriu grafov, pracujú s jedným z jej základných pojmov – cyklomatickým číslom (cyklickým radom) grafu, ktorý definuje počet cyklov v kostre (MG) uhľovodíka ako počet väzieb, ktoré musia byť prerušené. aby sa získal necyklický MG z cyklického. V teórii grafov sa takto získaný strom z cyklického MG nazýva spanning tree a každé spojenie, ktoré v ňom tvorí cyklus v obrátenom postupe, sa nazýva akord. Cyklické poradie grafu a podľa toho aj počet cyklov (cyklov) v uhľovodíkovom MG sa určí ako počet takýchto akordov podľa vzorca (1):

c =

kde je počet väzieb, p je počet vrcholov-atómov v MG. V každom acyklickom MG je počet cyklov samozrejme rovný nule a z (1) vyplýva, že počet atómov v ňom je o 1 väčší ako počet väzieb, čo je známe nielen odborníkom.

teória grafov socialista, ale aj chemik. Chemickým analógom tohto vzorca je vzorec (2)

c \u003d 1 / 2p3 + /? 4 + 1, (2)

kde P3 je počet terciárnych a p4 je počet kvartérnych atómov uhlíka.

1.3. IZOMORFIZMUS A IZOMERIA

Veľmi dôležitý aspekt izomorfizmu, spoločný pre teóriu grafov a organickú nomenklatúru, sa zvyčajne zvažuje ako prvý v teórii grafov. „Nedobrovoľne“ sa tu odráža hneď v prvej postave. Na otázku, či sú MG páry bután (16, c), izobután (1 g, e) a cyklobután (1e, g) totožné, odpovie chemik „áno“ a v teórii grafov „nie“ . Odpoveď znie: sú izomorfné. Izomorfizmus je vzťah ekvivalencie na grafoch , , ktorých jedným z variantov môže byť ich identita (ekvivalencia), ak ich možno kombinovať bez zmeny jedného z výkresov. Autor knihy o základoch moderného názvoslovia organických zlúčenín ukazuje, že je možné transformovať rôzne formy rovnakej molekulárnej štruktúry (uhlíkový skelet) na spojenie, a tiež ako je možné pokusom o takúto kombináciu dosiahnuť istotu, že porovnávané štruktúry sa nekombinujú a predstavujú izomérne molekuly, ktoré sa líšia v inom poradí väzieb (štrukturálna izoméria) a samozrejme nie sú izomorfné [tamže, s. 43, 44]. Izomérne grafy, ako aj izomérne MG opisujúce izomérne molekuly, sú teda neizomorfné grafy, ktoré majú vrcholy s rovnakou danou distribúciou vaencie. Takéto grafy a presne ako izomérne MG sa začali študovať na konci 19. storočia, no v teórii grafov dostali chemický výraz „izomérny“ zjavne len veľmi nedávno. Grafová izoméria (MG) zodpovedá iba štruktúrnej izomérii molekúl a nezahŕňa optické, konformačné a iné chemické typy izomérie, aj keď podobne ako sľubná MG (pozri časť 2.2 nižšie) sa vytvorili špeciálne typy MG, ktoré odrážajú tieto a ďalšie aspekty štruktúrnej chémie.

1.3.1. PROBLÉM IZMORFIZMU

Najjednoduchší, na prvý pohľad, problém určenia, či rôzne izomorfné MG patria k rovnakej molekule, sa stáva veľmi zložitým a akútnym, pokiaľ ide o cyklické MG. Autori jedinečnej monografie o názvosloví organických zlúčenín podrobne analyzujú, koľko rôznych obrázkov uhlíkových skeletov tej istej komplexnej cyklickej molekuly možno nakresliť natoľko, že často nie je jasné, ktoré z týchto nákresov zobrazujú rovnakú štruktúru. . Ukázali tiež, koľko zmätku a rozporov v tomto smere vzniklo (a stále existuje).

Ryža. 4. Izomorfné MG uhľovodíka StsNm

história vývoja nomenklatúry organických zlúčenín. Napríklad na prvý pohľad nie je vôbec jasné, že všetkých päť MG znázornených na obr. 4 sú izomorfné a zodpovedajú rovnakému (hypotetickému) uhľovodíku. A ak sú niektoré z nich nakreslené nerovinné, s priesečníkmi väzieb mimo atómov, ako na obr. 4e (pozri § 2), je ich rozpoznanie ešte ťažšie. A obr. 4e ukazuje, že tento MG má hamiltonovský cyklus.

2. PLANARITA 2.1. STYLING

Vráťme sa k obrázkom MG na rovine, ako východiskovému základu teórie grafov (pozri prvú definíciu grafu). Ak je možné nakresliť graf (MG) na list papiera bez prekríženia väzieb mimo atómov, potom sa predpokladá, že takýto MG zapadá do roviny. Ak sa dá MG takto položiť na rovinu, aj keď je nakreslená s priesečníkmi, nazýva sa rovinná a ak je už položená (teda bez takýchto priesečníkov), tak plochá. Existujú nejaké nerovinné grafy, ktoré sa nedajú položiť na rovinu? Teória grafov potvrdila nielen ich existenciu, ale aj to, ako ju možno určiť. Avšak pri zvažovaní veľkého počtu cyklických MG na mnoho rokov nebolo možné nájsť ten, ktorý by bol nerovinný, hoci väčšinu z nich chemici kreslia ako nerovinné: často je jednoduchšie ich nakresliť takto. . Preto budeme všetky MG obyčajných organických molekúl považovať za planárne, kým to nevyvrátia ďalšie hľadania alebo syntézy.

2.2. NEPLANARITNÉ A BIpartitné grafy

Dve kritériá však naznačujú, že môžu existovať neplanárne molekulárne štruktúry. Prvým je „diagonálna“, zatiaľ nesyntetizovaná forma benzénu. Na obr. 5a je jeho MG znázornená vo forme, v akej je znázornená v knihách o chémii (v strede šesťuholníka nie je žiadny atóm) a na obr. 56 ukazuje ďalší MG rovnakého tvaru uhlopriečky, ktorý ukazuje, že nie je možné zbaviť sa "extra" priesečníka dvoch väzieb v rovine.

Každý, čo i len povrchná znalosť teórie grafov, hneď určí, že Obr. 56 predstavuje jeden z

Ryža. 5. Kompletný bipartitný graf K3,3 zodpovedajúci MG diagonálneho izoméru benzénu

dve formy najmenšieho nerovinného grafu, takzvaný úplný bipartitný graf A "3-3. Ide o taký graf, v ktorom je každý vrchol z jednej skupiny (skupiny (1, obr. 56) spojený so všetkými vrcholmi iná skupina (/, obr. 56) a naopak, ak existujú spojenia nie so všetkými vrcholmi inej skupiny, graf bude jednoducho bipartitný, ale jeho hlavná vlastnosť - absencia spojení v rámci skupiny - by nemala byť narušená.

Druhou formou najmenšieho nerovinného grafu je úplný graf (pozri časť 1.1.), čo je päťuholník so všetkými uhlopriečkami. Je jasné, že tento graf nemôže byť MG, pretože sú v ňom obsadené všetky valencie jeho uhlíkových atómov a na vodík nezostali žiadne.

2.3. TOPOLOGICKÁ KONEKTIVITA

A predsa existujú molekuly, ktorých MG nemožno nakresliť na rovinu bez kríženia väzieb. Sú to katenány, čo sú cyklické molekuly, ktorých dva (alebo viac) kruhov sú synteticky „navlečené“ jeden do druhého. Medzi jej časťami nie je žiadna chemická väzba, preto by sa MG tejto molekuly malo považovať za nekoherentné. Ale je nemožné oddeliť tieto krúžky bez porušenia chemickej väzby; je tiež nemožné nakresliť to na rovinu bez toho, aby sa krúžky prekrížili. Takéto spojenie medzi prstencami sa nazývalo mechanické alebo topologické. Z tohto dôvodu je účelné považovať katenán MG za pripojený a ponechať otázku, či je nerovinný alebo nie.

2.4. VONKAJŠIA SLUČKA

Je tu ešte jedna otázka, odpoveď na ktorú chemici prechádzajú mlčaním. Iba pre tri z piatich pravidelných konvexných mnohostenov možno v zásade syntetizovať chemické analógy: tetraedran (С4Н4), kuban (С8Н8) a dodekahedran (С|2Н12). Prečo sa z nich zrejme syntetizuje jediný uhľovodíkový kuban, ktorý má, samozrejme, šesť cyklov, v modernej organickej nomenklatúre sa nazýva pentacyklooktán. Čiastočná odpoveď na to je uvedená vyššie (cyklomatické číslo MG). Úplnú odpoveď, nevyhnutnú pre organickú chémiu a pre organickú nomenklatúru ako jej dôležitú súčasť, však dáva slávna Eulerova veta, ktorú pozná snáď každý matematik. Je formulovaný nasledovne: pre akýkoľvek mnohosten umiestnený na guli a s bodmi V

Ryža. 6. Perspektívny obraz (perspektívny MG) Kubánca (a) a jeho MG (položený na rovine - b)

(vrcholy), čiary E (hrany) a ^ plochy (plocha je ohraničená cyklom),

Y - E + E \u003d 2.

Kocka tu nie je položená na povrchu gule, sú na nej umiestnené iba jej vrcholy-body. Ak necháte takúto kocku bez gule, dostanete ryžu. 6a; ak ju položíme na guľu, potom jej plochy (vnútorné oblasti jednoduchých cyklov) zaberú celú jej plochu, ale ak ju položíme na rovinu, dostaneme obr. 66. Spočítajme v ňom počet cyklov (jednoducho). Dostaneme päť (penta). Kam sa podel cyklus 1238? Zvyšných päť cyklov je v ňom teraz zakomponovaných, prestalo to byť jednoduché a v teórii grafov ani v organickom názvosloví sa už takpovediac neuvažuje o tom, čo odráža vzorec 1. Prečo „akože“? Analogicky s guľou sa v teórii grafov verí, že cyklus 1238 „patrí“ celej nekonečnej „časti“ roviny, ktorá pri položení MG na obr. 6 na gule zodpovedá koncovej časti jej vnútorného povrchu. Preto sa pre mnohosten položený na rovinu, ale aj pre akýkoľvek plochý MG, cyklus, v ktorom sa nachádzajú všetky ostatné cykly, sa nazýva vonkajší cyklus a zodpovedajúca nekonečná „časť“ roviny sa nazýva vonkajšia plocha. A vzorec (3), ktorý sa líši od vzorca (1) „len“ o jednu, odráža „pridanie“ externého cyklu k akémukoľvek planárnemu MG. A tak sa hexaedrický kváder v nomenklatúre správne nazýva pentacyklický ooktán.

Pretože všetky doteraz známe MG obyčajných organických molekúl sú rovinné, všetky môžu byť ploché, naskladané vo vonkajšom cykle. Bolo dokázané, že rovinný graf je možné „refaktorovať“ takým spôsobom, že akýkoľvek vnútorný cyklus môže byť externý. Preto je vhodné, aby MG urobil najväčší (najdlhší) zo svojich cyklov externe. Najväčší vonkajší cyklus planárneho MG teda možno považovať za akýsi „rozmer“ nielen pre ňu, ale aj pre samotnú organickú molekulu, ktorú predstavuje. Jeden z postupov na získanie MG s najväčším externým cyklom je opísaný nižšie, časť 5.2.

2.5. SĽUBNÁ MG

Chemici zobrazujú veľmi významnú časť uhlíkových skeletov tak, ako by ich oko videlo v najstabilnejšej konfigurácii a (alebo) konformácii, t. j. nakreslené v perspektíve na rovine, ale nie položené na nej. Neodráža sa v teórii grafov

Ryža. 7. Štruktúrny vzorec (a), MG (b) a sľubný MG (c) bicyklického uhľovodíka Obr.

priestorové usporiadanie sústavy vrcholov a hrán, ktoré ich spájajú, ale tu je vhodné postupovať ako v, kde sú dané sľubné MG (PMG). Ak je potrebné ich odlíšiť od „skutočných“ planárnych MG, možno ich nazvať ako je uvedené vyššie. Vyššie uvedená veľká monografia o nasýtených (acyklických a cyklických) uhľovodíkoch obsahuje 253 nákresov cyklických uhlíkových skeletov. Z toho 136 sú rovinné (takmer všetky ploché) MG a zvyšných 117 sú sľubné MG spomínané vyššie. Na obr. 7 ukazuje, ako tiež demonštrujú "premenu" štruktúrneho vzorca na plochý MG a ten na perspektívny MG. Pomerne veľa takýchto perspektívnych MG je uvedených vo vyššie uvedenej učebnici organickej chémie.

Je zaujímavé pozrieť sa bližšie na MG na obr. 7. storočie Rovnako ako v prípade perspektívneho obrazu kocky (obr. 6a), jeho perspektívny obraz oslobodzuje vonkajší sedemčlenný cyklus od hniezdenia ďalších cyklov a dáva mu „právo“ s ostatnými cyklami. Nie je to však vždy tak. Ak sú cykly kondenzované v jednom (obr. 3c) alebo v dvoch atómoch (obr. 3b), potom perspektívny obraz nepovedie k uvoľneniu vonkajšieho cyklu, hoci ktorýkoľvek zo šesťčlenných cyklov v každom z týchto MG možno urobiť externé vložením ďalšieho do neho. A pre monocyklický MG sa v ňom samozrejme vonkajší cyklus „sám k sebe“ a druhý cyklus v perspektívnom obraze neobjaví.

3. SYMETRIA

Odhliadnuc od rozdielov vo vlastnostiach objektov vrcholov grafu, jeden nedobrovoľne upadá do druhého extrému, mlčky ich považuje za rovnaké. Rozdiely sú spôsobené iba rozdielom vo valencii vrcholov. Pre MG uhľovodíky má táto podobnosť reálny základ v podobe zhodnosti atómov uhlíkového skeletu. Chemici vedia, že všetky normálne alkány majú symetrické atómové skupiny, ktoré sú v rovnakej vzdialenosti od stredu reťazca, takže ich MG sú zodpovedajúce symetrické vrcholy. Symetria vyžaduje nielen rovnaké atómy

mov, ale aj identita (ekvivalencia) pozície, rovnaká pre akýkoľvek druh izomorfnej MG. Všetky MG s malým počtom atómov sú symetrické; najmenší acyklický MG, ktorý nemá ani jeden pár ekvivalentných atómov, ich má sedem (3-metylhexán).

Ak odstránime jeden vrchol z každého z dvoch izomorfných ekvivalentných MG, ktoré pri ich spojení zaujímajú rôzne pozície, potom získaný izomorfizmus podgrafov v tomto prípade znamená, že tieto vrcholy-atómy sú symetrické. Takýto vnútorný izomorfizmus grafu sa nazýva automorfizmus a symetrické vrcholy sa nazývajú podobné. Všeobecné abstraktné aspekty symetrie študuje matematická teória grúp. Rozmanitosť symetrických párov v rámci všetkých takýchto odstránení má určitý počet a nazýva sa skupina automorfizmu. Veľký význam pri ich číslovaní má symetria atómov (§ 4).

Pre organickú nomenklatúru a chémiu má veľký význam aj symetria atómov a ich skupín v molekulách, pretože uhľovodíkové deriváty získané rovnakou substitúciou vodíka na žiadnom zo symetrických atómov sa nelíšia štruktúrou a teda ani vlastnosťami.

4. ČÍSLOVANIE

Rovnosť atómov uhlíka v MG uvedená vyššie (§ 3) znižuje informačný obsah o štruktúre molekuly v dôsledku zníženia diverzity jej zložiek. Známou a vo všetkých variantoch organického názvoslovia používanou metódou zvyšovania informačného obsahu je číslovanie atómov molekuly (a jej MG). V teórii grafov sa takéto grafy nazývajú označené ("označenie" sa dá robiť nielen číslami). Číslovanie atómov umožňuje získať potrebné informácie o poradí väzieb v molekule a v MG, pre ktoré stačí napríklad uviesť počty priamo viazaných atómov. Vyššie (obr. 3 a 6) boli uvedené očíslované MG. Už tam toto číslovanie zvýšilo informačný obsah o nich a uľahčilo vysvetlenia uvedené v texte. A na obr. 7a je znázornené číslovanie atómov uhlíka štruktúrneho vzorca kondenzovaného uhľovodíka, ktoré sa používa v modernej organickej nomenklatúre.

Číslovanie vrcholov vám umožňuje znázorniť graf bez jeho kreslenia na papier. Najbežnejším spôsobom takejto reprezentácie je matica susednosti, ktorá je s rôznou mierou podrobností opísaná takmer vo všetkých knihách o teórii grafov (pozri napr. , ). Jednoduchším zoznamom je zoznam hrán (spojení), v ktorom sú zaznamenané čísla všetkých dvojíc susedných vrcholov. Tieto čísla sú oddelené medzerou, dvojice sa píšu pod sebou, . Obyčajne (nie vždy) sa v páre ako prvé píše nižšie číslo. Výhodnejšie je písať dvojice do jedného riadku, čísla v páre oddeľovať čiarkou a dvojice od seba oddeľovať pomlčkou alebo spojovníkom.

Chemikmi dobre známa nejednoznačnosť voľby poradia číslovania atómov v rovnakom MG však vedie k nadmernému zvyšovaniu diverzity a namiesto zvyšovania vedie k úbytku informácií o molekule a jej MG.

Preto tu potrebujeme kritériá, ktoré eliminujú takúto rôznorodosť číslovania a zabezpečia jeho jednoznačnosť. Pre grafy sú navrhnuté viaceré možnosti jedinečného číslovania vrcholov, pri ktorých sa cieľ dosiahne aplikáciou určitého systému pravidiel. A keďže sa tieto pravidlá v rôznych verziách líšia, existuje aj určitá variácia. Zdá sa, že najviac sa rozšírila maticová metóda jedinečného číslovania pomocou vyššie spomínanej matice susednosti, nazývaná kanonická.

4.1. ISOMORFIZMUS ČÍSLOVANÝCH MG

Aby sa očíslované grafy (MG) považovali za izomorfné, je potrebné, aby pri kombinovaní ekvivalentných (pozri časť 1.3) MG sa zhodovali nielen atómy (vrcholy) a väzby, ale aj čísla. Na obr. Obrázok 8 ukazuje nám známe (obr. 1) MG butánu a izobutánu. Je vidieť, že všetky sú očíslované inak. Ale MG 8a a 86 je možné kombinovať so všetkými číslami otočením jedného z nich o 180°, ale žiadne z týchto dvoch nemožno kombinovať s MG obr. 8c. Očíslované MG 8a, 86 sú teda izomorfné, zatiaľ čo MG 8c nie je izomorfné so žiadnym z nich, aj keď pri absencii číslovania by boli všetky tri izomorfné. Stalo sa to preto, že v MG 8a a 86 sú symetrické atómy označené rovnakými číslami, zatiaľ čo v MG 8c nie. Pre očíslované izobutánové MG, so zhodou všetkých čísel, je možné kombinovať akýkoľvek pár z trojice na obrázkoch 8d, 8e a 8f, pretože všetky tri primárne atómy sú symetrické a jediný asymetrický terciárny atóm je označený rovnakým číslom. A v MG 8g je asymetrický atóm označený iným číslom a tento MG nie je možné kombinovať so žiadnym z MG trojitých 8d, 8e, 8e.

Ryža. 8. Rozdielne číslovanie MG butánu (a - c) a izobutánu (d-g)

Porovnajme zoznamy spojení pre tieto MG. Pár MG 8a, 86 má rovnaké zoznamy: 1,2 - 2,3 - 3,4, zatiaľ čo MG 8c má iný zoznam: 1,2 - 2,4 - 3,4. Tiež trio MG 8d, 8d, 8e má identické zoznamy väzieb: 1,2 - 2,3 - 2,4 a zoznam MG 8g je tiež odlišný: 1,2 - 1,3 - 1,4.

Vyššie uvedené vedie k trom hlavným dôsledkom.

Najprv. Jedinečne očíslované izomorfné grafy (MG) zostávajú izomorfné aj v dôsledku takéhoto číslovania. Samozrejme, na to musíte použiť rovnaký systém pravidiel pre jednoznačné číslovanie.

Po druhé. Akákoľvek metóda jedinečného číslovania sa vykonáva až do symetrie vrcholov. To znamená, že permutácia čísel medzi podobnými vrcholmi nenarúša jedinečnosť číslovania.

Po tretie. Prirodzene to vyplýva z prvého: pre akýkoľvek pár neizomorfných neoznačených grafov po ich jedinečnom vyčíslení nie je možné získať zhodné zoznamy odkazov alebo zhodné matice kanonických susedností. To nám umožňuje vyriešiť problém izomorfizmu (článok 1.3.1.) prevedením číslovania porovnávaných grafov (MG) na kanonické.

Chemici vedia, že napríklad rovnaké číslovanie atómov benzénového kruhu možno získať tak, že sa začne od ktoréhokoľvek z atómov cyklu a pokračuje sa v ňom postupne v ľubovoľnom smere. Rovnaké číslovanie atómov naftalénového cyklu môžete získať aj vtedy, ak ho začnete od ktoréhokoľvek zo štyroch sekundárnych atómov susediacich s terciárnym atómom a pokračujete v reťazci v opačnom smere od neho (pozri obr. 36).

4.2. ČÍSLOVANIE REŤAZE

Reťazová štruktúra (pozri časť 1.2.) a cyklická štruktúra ako derivát reťazovej štruktúry sú integrálnou a prirodzenou vlastnosťou každého grafu, a teda aj MG. Preto sa postupné číslovanie vrcholov a hrán grafu pozostávajúceho z jedného reťazca alebo jedného cyklu nazývalo: prirodzené. Ak považujeme vrchol (atóm, pozri časť 1.2.) za reťazový článok v MG, potom reťazce a/alebo cykly existujú v každom MG. Toto číslovanie atómov MG sa nazýva číslovanie reťazcov. Väzby medzi atómami s po sebe idúcimi číslami sa nazývajú reťazce a tie s nekonzistentnými číslami sa nazývajú nehodnotné. A nie je prekvapujúce, že toto postupné číslovanie reťazcov uhlíkových atómov molekuly a jej MG sa v organickej chémii používa takmer od samého začiatku svojej existencie. Potom však autori rôznych systémov číslovania uhlíkových atómov kondenzovaných cyklických molekúl akoby po dohode zaviedli pravidlá, ktoré porušujú prirodzený reťazec tohto číslovania. Ale koniec koncov, v cyklickej štruktúre je takmer vždy menej reťazcov a sú dlhšie ako v acyklickej.

V číslovaných MG je teda viac článkov reťaze ako v nereťazových (pozri obr. 3, 6, 7 a 8) a objem číselného znázornenia MG možno výrazne zmenšiť, ak všetky články reťaze zohľadníme byť známe, že existujú. Okrem toho je prítomnosť najvyššieho atómového čísla (posledného čísla) v zázname jednoznačná

informuje, že všetky atómy s nižšími číslami v MG existujú a priame (explicitné) informácie o nich možno tiež vynechať. Táto nezaznamenateľná informácia je nepriama alebo implicitná. Skrátená digitálna informácia sa v modernej organickej nomenklatúre používa vo forme kódu (šifry) ako súčasť názvu zlúčeniny.

Keď sa takáto redukcia použije na zoznam spojení so záznamom v jednom riadku (pozri § 4.1), získa sa lineárny reťazový kód. V ňom sa reťazcové väzby neoznačujú a pri označení nereťazcovej väzby sa ako prvé píše väčšie číslo. Vyššie označené kódy lineárneho reťazca MG ukazujú, že je možné výrazne znížiť digitálnu reprezentáciu MG v porovnaní so zoznamom odkazov:

ryža. Pre: 06.3-7; 36: 10,1 - 10,5;

Sv: 6,1 - 11,6; Zg: 6,1 - 12,7; ryža. 6a a 66: 5,2 - 6,1 - 7,4 - 8,1 - 8,3; ryža. 8a a 86: 4; 8d, 8e a 8f: 04.2.

Lineárny reťazový kód MG teda pozostáva zo správ s oddeľovačmi obsahujúcimi informácie o nereťazových spojeniach, oddeľovačom je spojovník (pomlčka) s medzerami. Správa o poslednom atóme je daná vtedy, keď jeho číslo nie je v nereťazovej väzbe (kódy na obr. 3a a 8a, 86). Keďže sa všetky články reťaze v kóde považujú za existujúce, priama informácia o absencii niektorých z nich je daná „bezvýznamnou“ nulou bezprostredne pred číslom, od ktorého začína nová reťaz (počiatočné číslo: kódy obr. 3a a 4d, 4e, 4f). Správy, v ktorých sú nereťazové spojenia tvorené rovnakým väčším alebo menším (ale nie väčším alebo menším) číslom, sa spoja do jednej. V kombinovanej správe je väčšie spoločné číslo umiestnené ako prvé a ostatné čísla nasledujú za ním vo vzostupnom poradí: obr. 36:10,1,5;

ryža. 6a a 66: 5,2 - 6,1 - 7,4 - 8.1.3.

Ak je spoločné číslo menšie, umiestni sa v správe ako posledné a ďalšie čísla sa pred ním umiestnia tiež vo vzostupnom poradí. V kombinovanej správe sa spojenie medzi očíslovanými atómami považuje za existujúce, keď sa väčšie číslo nachádza pred menším (vľavo) a medzi atómami s nižším číslom vpredu nie je spojenie. To odhaľuje význam umiestnenia väčšieho čísla pred menšie v prítomnosti väzby medzi atómami s týmito číslami.

Na zabezpečenie vstupu informácií o organickej molekule do počítača boli vyvinuté ďalšie nezávislé kódovacie systémy pre štruktúrne vzorce. Lineárny zápis MG reťazového kódu je celkom vhodný aj na priame zadávanie do počítača.

K rôznym metódam jedinečného číslovania MG atómov uvedených vyššie bolo pridané jedinečné číslovanie reťazcov. Analogicky s kanonickým číslovaním pomocou matice susednosti (pozri § 4 vyššie) sa nazýva reťazové kanonické číslovanie. V ňom sa číslovanie začína atómami dlhších reťazcov; a zvoliť také poradie, v ktorom väzby s počtom atómov, ktoré nie sú za sebou, získajú maximálny možný počet takýchto čísel. Ako

Ryža. 9. Prepracovanie MG (a) na MG s veľkým vonkajším cyklom (b alebo c) pomocou kanonického číslovania reťazcov

reťazec je vhodný na číslovanie atómov MG a možno ho použiť v organickej nomenklatúre na jednoznačné číslovanie atómov štruktúry. Podrobnejší popis nájdete na .

Teraz je možné opísať výrobu stohovania MG s najväčším externým cyklom z MG na obr. 4a. Tu je vidieť, že vnútorný šesťčlenný cyklus je väčší ako vonkajší päťčlenný. Po nakreslení šesťčlenného cyklu 3, 4, 5, 6, 7, 8 externého ho označíme rovnakými číslami (obr. 96). Potom k nemu pripojíme vnútorné atómy, pričom dodržíme rovnaké poradie čísel väzieb. Vo vnútri päťčlenného cyklu na obr. 9a je ešte jeden šesťčlenný cyklus 1, 2, 3, 4, 5, 11. Ak ho nakreslíme zvonka a pripojíme k nemu vnútorné atómy, dostaneme MG obr. 9. storočia Reťazové kanonické číslovanie všetkých cyklov na obr. 9 uvádza rovnaký kód: 8.3 - 9.2 - 10.7 - 11.1.5, ktorý dokazuje izomorfizmus všetkých týchto MG.

LITERATÚRA

1. Aplikácia teórie grafov v chémii, Ed. Člen korešpondent Akadémia vied ZSSR N.S. Zefirova a Cand. chem. Sciences S.I. Kuchanovej. Novosibirsk: Nauka, 1988. 306 s.

a: Stankevič I.V. Grafy v štruktúrnej chémii. s. 7-69. b: Yablonsky G.S. Evstigneev V.A., Bykov V.I. Grafy v chemickej kinetike. s. 70-143.

in: Kuchanov S.I., Korolev S.V., Potokov S.V. Grafy v chemickej fyzike polymérov. s. 144-299.

g: Korolev S.V., Kuchanov S.I. Dodatok. Pojmy teórie grafov. s. 300-305.

2. Harari F. Teória grafov. M.: Mir, 1973. 302 s.

3. Wichson R. Úvod do teórie grafov. M.: Mir, 1977. 208 s.

4. Rudné O. Grafy a ich aplikácia. M.: Mir, 1965. 176 s.

5. Berezina L.Yu. Grafy a ich aplikácia: Príručka pre učiteľov. Moskva: Vzdelávanie, 1979. 144 s.

6. Distel R. Teória grafov: Per. z angličtiny. O.V. Borodin. Novosibirsk: Vydavateľstvo Ústavu matematiky, 2002. 336 s.

7. Tatt U. Graph Theory: Preložené z angličtiny. G.P. Gavrilov. M.: Mir, 1988. 424 s.

8. Banky J. Názvy organických zlúčenín. Moskva: Chémia, 1980. 304 s.

9. Shilov A.A. K systematizácii grafov na základe oddielov // Metódy a nástroje na prácu s dokumentmi: So. tr. Ústav systémovej analýzy RAS. M.: Úvodník URSS, 2000. 376 s.

10. Shilov A.A. K systematizácii bezhranových a zjednotených grafov na základe partícií // Riadenie informačných tokov: Sat. tr. Ústav systémovej analýzy RAS. M.: Úvodník URSS, 2002. 368 s.

11. Terentiev A.P., Kost A.N., Zukerman A.M., Potapov V.M. Nomenklatúra organických zlúčenín. Recenzia, kritika, návrhy. M.: Vydavateľstvo Akadémie vied ZSSR, 1955. 304 s.

12. Shill G. Katenany, rotaxány a uzly. M.: Mir, 1973. 212 s.

13. Clark T.. Mac Kervey M.A. Nasýtené uhľovodíky II Všeobecná organická chémia. G. I. M.: Chemistry, 1981. S. 56-168.

14. Neipand O.Ya. Organická chémia. M.: Vyššie. škola, 1990. 752 s.

15. Goodman S., Hidetniemi S. Úvod do analýzy a vývoja algoritmov. M.: Mir, 1981. 368 s.

16. Lipsky V. Kombinatorika pre programátorov. M.: Mir, 1988. 216s.

17. Bryuske Ya.E. Číslovanie a kódovanie reťazcov cyklických uhľovodíkov // Journal of Structural Chemistry. T. 36. č. 4. S. 729-734.

18. Matematický encyklopedický slovník. M.: Rada, encyklopédia, 1988. 848 s.

19. Bryuske Ya.E. Kódovanie lineárnych reťazcov a názvy acyklických uhľovodíkov // Vestn. Tambov, un. Ser. prirodzené a tech. veda. Tambov, 1996. T. 1. Vydanie. 1. S. 34-38.

20. Bryuske Ya.E. Lineárne reťazcové kódovanie vzorcov organických zlúčenín. VIII. Zvýšenie explicitných informácií o štruktúre v uhľovodíkových kódoch Vestn. Tambov, un. Ser. prirodzené a tech. veda. Tambov, 2000. V. 5. Vydanie. I. S. 38-43.

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 druhu 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; podľa toho 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ú rovniciam 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ď.................

Grafy slúžia predovšetkým ako prostriedok na znázornenie molekúl. V topologickom popise molekuly je znázornená ako molekulárny graf (MG), kde vrcholy zodpovedajú atómom a okraje zodpovedajú chemickým väzbám (graf-teoretický model molekuly). Zvyčajne sú v tomto znázornení uvažované iba skeletové atómy, napríklad uhľovodíky s "vymazanými" atómami vodíka.

Valencia chemických prvkov ukladá určité obmedzenia na stupne vrcholov. Alkánové stromy (spojené grafy, ktoré nemajú cykly) majú vrcholové stupne (r), ktoré nemôžu presiahnuť štyri (r = 1, 2, 3, 4).

Grafy je možné špecifikovať v maticovej forme, čo je výhodné pri práci s nimi na počítači.

Matica susednosti vrcholov jednoduchého grafu je štvorcová matica A = [aσχ] s prvkami aσχ = 1, ak sú vrcholy σ a χ spojené hranou a σχ = 0 v opačnom prípade. Matica vzdialenosti je štvorcová matica D = s prvkami dσχ definovaným ako minimálny počet hrán (najkratšia vzdialenosť) medzi vrcholmi σ a χ. Niekedy sa používajú aj matice susednosti a okrajovej vzdialenosti (A e a D e).

Typ matíc A a D (A e a D e) závisí od spôsobu číslovania vrcholov (alebo hrán), čo spôsobuje nepríjemnosti pri manipulácii s nimi. Na charakterizáciu grafu sa používajú grafové invarianty – topologické indexy (TI).

Počet ciest dĺžky jedna

pi = xcc 0 = m = n-1

Počet ciest dĺžky dva

Počet trojíc susedných hrán (so spoločným vrcholom)

Wienerovo číslo (W), definované ako polovičný súčet prvkov matice vzdialeností uvažovaného grafu:

atď.

Metodológia na štúdium vzťahu „štruktúra-vlastnosť“ prostredníctvom topologických indexov v grafovo-teoretickom prístupe zahŕňa nasledujúce kroky.

Výber predmetov štúdia (tréningová vzorka) a analýza stavu číselných údajov o vlastnosti P pre daný rozsah zlúčenín.

Výber TI s prihliadnutím na ich rozlišovaciu schopnosť, korelačnú schopnosť s vlastnosťami atď.

Štúdium grafických závislostí "Vlastnosť P - TI grafu molekuly", napríklad P na n - počet atómov skeletu, P na W - Wienerovo číslo atď.

Stanovenie funkčnej (analytickej) závislosti P = _DTI), napr.

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

P \u003d a (TI) 1 + b (TI) 2 + ... + n (TI) n + c

atď. Tu sú a, b, c niektoré parametre (nezamieňať s parametrami aditívnych obvodov), ktoré sa majú určiť.

Numerické výpočty Р, porovnanie vypočítaných hodnôt s experimentálnymi.

Predikcia vlastností zlúčenín, ktoré ešte neboli študované alebo dokonca získané (mimo tejto vzorky).

Topologické indexy sa používajú aj pri konštrukcii aditívnych výpočtov a prognostických schém. Môžu byť použité pri vývoji nových liečiv, pri hodnotení karcinogénnej aktivity určitých chemikálií, pri predpovedaní relatívnej stability nových (zatiaľ nesyntetizovaných) zlúčenín atď.

Malo by sa však pamätať na to, že výber TI je často náhodný; nemusia odrážať dôležité štrukturálne vlastnosti molekúl alebo duplicitné informácie (získané pomocou iných indexov) a výpočtové schémy nemusia mať pevný teoretický základ a je ťažké ich fyzikálno-chemicky interpretovať.

Tím Katedry fyzikálnej chémie TvSU už dlhé roky realizuje výpočtovo-teoretickú štúdiu na problém „Vzťah medzi vlastnosťami látok a štruktúrou molekúl: matematické (počítačové) modelovanie“. Dôraz je kladený na cielené hľadanie nových štruktúr, algoritmov na riešenie množstva grafo-teoretických a kombinatorických problémov, ktoré vznikajú pri zbere a spracovaní informácií o štruktúre a vlastnostiach látok, vytváranie expertných informačných systémov a databáz. rozvoj kvantitatívnych metód výpočtu a prognózovania.

Vytvorili sme aditívne schémy a našli analytické závislosti formy P = Y(TI) pre množstvo organických a iných molekúl. Podľa získaných vzorcov boli vykonané numerické výpočty fyzikálno-chemických vlastností uvažovaných zlúčenín, s .

Bibliografia

1. Vinogradova M.G., Papulov Yu.G., Smoljakov V.M. Kvantitatívne korelácie „vlastnosti štruktúry“ alkánov. Schémy aditívneho výpočtu. Tver, 1999. 96 s.
2. Chemické aplikácie topológie a teórie grafov / Ed. R. Kráľ. M.: Mir, 1987. 560 s.
3. Aplikácia teórie grafov v chémii / Ed. N.S. Zefirova a S.I. Kuchanovej. Novosibirsk: Nauka, 1988. 306 s.
4. Stankevich M.I., Stankevich I.V., Zefirov N.S. Topologické indexy v organickej chémii // Uspekhi khimii. 1988. V.57, č. 3, S.337-366.
5. Vinogradová M.G., Saltyková M.N. Graf-teoretický prístup pri štúdiu vzťahu medzi štruktúrou a vlastnosťami alkylsilánov.// Fundamental Research, 2009. č.1. s. 17-19.
6. Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Vzťah medzi štruktúrou a vlastnosťami alkylsilánov // Úspechy moderných prírodných vied, č. 1, 2010. S. 136-137.
7. Vinogradová M.G., Saltyková M.N., Efremová A.O. Korelácie "Štruktúra - vlastnosť" alkylsilánov: graf-teoretický prístup // Úspechy moderných prírodných vied, č. 3, 2010. S.141-142.

Bibliografický odkaz

Navyše, posledných 12 rokov svojho života bol Euler vážne chorý, oslepol a napriek ťažkej chorobe pokračoval v práci a tvorení.

Štatistické výpočty ukazujú, že Euler urobil v priemere jeden objav za týždeň.

Je ťažké nájsť matematický problém, ktorý sa v Eulerových dielach nedotkol.

Všetci matematici nasledujúcich generácií študovali s Eulerom tak či onak a nie nadarmo známy francúzsky vedec P.S. Laplace povedal: "Prečítaj si Eulera, je učiteľom nás všetkých."

Lagrange hovorí: "Ak naozaj milujete matematiku, prečítajte si Eulera; expozícia jeho diel sa vyznačuje úžasnou jasnosťou a presnosťou." Elegancia výpočtov je ním skutočne dovedená na najvyšší stupeň. Condorcet zakončil svoj prejav na akadémii na pamiatku Eulera nasledujúcimi slovami: "Tak, Euler prestal žiť a počítať!" Žiť s cieľom počítať - aké nudné sa to zdá zvonku! Je zvykom predstaviť si matematiku suchú a hluchú ku všetkému svetskému, k tomu, čo zaujíma obyčajných ľudí.

S menom Euler je problém troch domov a troch studní.

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.

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 do druhej 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 od všetkých ostatných súčtom vzdialeností jednotlivca od všetkých ostatných.

4) Analýza efektívnosti tohto systému, ktorá zahŕňa aj také úlohy ako 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).

ale) b)

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.

Preto Г = 5. Každá z piatich stien má aspoň štyri hrany, pretože podľa stavu problému by žiadna z ciest nemala priamo spájať dva domy alebo dve studne. Keďže každá hrana leží presne na dvoch plochách, počet hrán musí byť aspoň (5 4)/2 = 10, čo je v rozpore s podmienkou, že ich počet je 9.

Výsledný rozpor ukazuje, že odpoveď v úlohe je záporná. - nie je možné nakresliť nepretínajúce sa cesty z každého domu do každého stĺpca

Teória grafov v chémii

Aplikácia teórie grafov na konštrukciu a rozbor rôznych tried chemických a chemicko-technologických grafov, ktoré sa nazývajú aj topológia, modely, t.j. modely, ktoré berú do úvahy len charakter spojenia vrcholov. Oblúky (hrany) a vrcholy týchto grafov odrážajú chemické a chemicko-technologické pojmy, javy, procesy alebo objekty a teda kvalitatívny a kvantitatívny vzťah alebo určitý vzťah medzi nimi.

Teoretické úlohy. Chemické grafy umožňujú predpovedať chemické premeny, vysvetliť podstatu a systematizovať niektoré základné pojmy chémie: štruktúra, konfigurácia, konfirmá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. Vrcholy a hrany týchto grafov zodpovedajú zodpovedajúcim atómom a chemickým väzbám medzi nimi.

V stereochémii org. cc najčastejšie používajú molekulárne stromy - kostry molekulárnych grafov, ktoré obsahujú iba všetky vrcholy zodpovedajúce atómom. Zostavovanie množín 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 . 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 množstva korelácií medzi štruktúrou molekúl a fyzikálno-chemickými (vrátane farmakologickými) vlastnosťami zlúčenín sa používa viac ako 20 tzv. Topologické indexy molekúl (Wiener, Balaban, Hosoyya, Plat, Randich, atď.), ktoré sú určené pomocou matíc a číselných charakteristík molekulárnych stromov. Napríklad Wienerov index W \u003d (m3 + 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 fyziol . drogová aktivita. Dôležitými parametrami molekulárnych 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, uhľohydrátov a iných komplexných prírodných zlúčenín je priemerná a plná (H) informačná kapacita. . Analýza molekulárnych grafov polymérov, ktorých vrcholy zodpovedajú monomérnym jednotkám a hrany chemickým väzbám medzi nimi, umožňuje vysvetliť napríklad: účinky vylúčeného objemu, vedúce ku kvalite. zmeny v predpokladaných vlastnostiach polymérov. Pomocou teórie grafov a princípov umelej inteligencie bol vyvinutý softvér pre systémy vyhľadávania 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. Pre praktickú realizáciu na počítači operácií výberu racionálnych spôsobov chemických látok. transformácie založené na retrosyntetickom a syntonickom princípe využívajú na hľadanie riešení viacúrovňové rozvetvené grafy, ktorých vrcholy zodpovedajú molekulovým grafom reaktantov a produktov a oblúky predstavujú transformácie.

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: tok, informačný tok, signál a graf spoľahlivosti. Na štúdium chem. fyzika porúch v systémoch pozostávajúcich z veľkého počtu častíc, využívajú tzv. Feynmanove diagramy sú grafy, ktorých vrcholy zodpovedajú elementárnym interakciám fyzikálnych častíc, hrán ich dráh po zrážkach. Tieto grafy umožňujú najmä skúmať mechanizmy oscilačných reakcií a určiť stabilitu reakčných systémov. 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. Grafy toku informácií zobrazujú logicko-informačnú štruktúru sústav rovníc mat. modely XTS; sa používajú na vývoj optimálnych algoritmov na výpočet týchto systémov. Bipartitný informačný graf je neorientovaný alebo orientovaný graf, ktorého vrcholy zodpovedajú resp. rovnice fl -f6 a premenné q1 - V a vetvy odrážajú ich vzťah. Informačný graf - digraf zobrazujúci poradie riešenia rovníc; vrcholy grafu zodpovedajú týmto rovniciam, zdrojom a prijímačom informácie XTS a vetvám informácií. premenné. Signálové grafy zodpovedajú lineárnym sústavám rovníc matematických modelov chemicko-technologických procesov a systémov. Grafy spoľahlivosti sa používajú na výpočet rôznych ukazovateľov spoľahlivosti X.

Referencie:

1. Berzh K., T. g. a jeho aplikácia, preložené z francúzštiny, M., 1962;

2. Kemeny J., Snell J., Thompson J., Úvod do konečnej matematiky, prel. z angličtiny, 2. vydanie, M., 1963;

3.Ope O., Grafy a ich aplikácia, prel. z angličtiny, M., 1965;

4. O. V. Belykh, E. V. Belyaev, Možnosti využitia T. g. v sociológii, in: Človek a spoločnosť, roč. 1, [L.], 1966;

5. Kvantitatívne metódy v sociologickom výskume, M., 1966; Beljajev E. V., Problémy sociologického merania, "VF", 1967, č. 7; Bavelas. Komunikačné vzorce v skupinách zameraných na úlohy, v knihe. Lerner, D., Lasswell H., Politické vedy, Stanford, 1951;

6. Kemeny J. G., Snell J., Matematické modely v sociálnych vedách, N. Y., 1962; Filament C., Applications of graph theory to group structure, N. Y., 1963; Oeser Ο. A., Hararu F., Štruktúry rolí a popis z hľadiska teórie grafov, v Viddle B., Thomas E. J., Teória rolí: koncepty a výskum, N. Y., 1966. E. Belyaev. Leningrad.