Grafy a chémia. Algebra a harmónia v chemických aplikáciách

Štúdium vzťahu medzi vlastnosťami látok a ich štruktúrou je jednou z hlavných úloh chémie. Veľký prínos k jeho riešeniu priniesla štruktúrna teória organických zlúčenín, medzi zakladateľov ktorej patrí veľký ruský chemik Alexander Michajlovič Butlerov (1828-1886). Bol to on, kto prvý zistil, že vlastnosti látky závisia nielen od jej zloženia (molekulárneho vzorca), ale aj od poradia, v ktorom sú atómy v molekule prepojené. Tento poriadok sa nazýval „chemická štruktúra“. Butlerov predpovedal, že kompozícia C 4 H 10 môže zodpovedať dvom látkam, ktoré majú odlišnú štruktúru - butánu a izobutánu, a potvrdili to syntézou poslednej menovanej látky.

Myšlienka, že poradie, v ktorom sú atómy spojené, má kľúčový význam pre vlastnosti hmoty, sa ukázala ako veľmi plodná. Je založená na znázornení molekúl pomocou grafov, v ktorých atómy zohrávajú úlohu vrcholov a chemické väzby medzi nimi sú hrany spájajúce vrcholy. V grafickom znázornení sa dĺžky väzieb a uhly medzi nimi ignorujú. Molekuly C opísané vyššie 4 H 10 sú zobrazené v nasledujúcich stĺpcoch:

Atómy vodíka nie sú v takýchto grafoch uvedené, pretože ich umiestnenie možno jednoznačne určiť zo štruktúry uhlíkovej kostry. Pripomeňme si, že uhlík v organických zlúčeninách je štvormocný, preto v zodpovedajúcich grafoch nemôžu z každého vrcholu vychádzať viac ako štyri hrany.

Grafy sú matematické objekty, preto ich možno charakterizovať pomocou čísel. Z toho vzišiel nápad vyjadriť štruktúru molekúl číslami, ktoré sú spojené so štruktúrou molekulových grafov. Tieto čísla sa v chémii nazývajú „topologické indexy“. Výpočtom nejakého topologického indexu pre veľký počet molekúl je možné vytvoriť vzťah medzi jeho hodnotami a vlastnosťami látok a potom použiť tento vzťah na predpovedanie vlastností nových, ešte nesyntetizovaných látok. K dnešnému dňu chemici a matematici navrhli stovky rôznych indexov charakterizujúcich určité vlastnosti molekúl.

Metódy výpočtu topologických indexov

Metódy na výpočet topologických indexov môžu byť veľmi rôznorodé, ale všetky musia spĺňať celkom prirodzené požiadavky:

1) každá molekula má svoj vlastný individuálny index;

2) Molekuly s podobnými vlastnosťami majú podobné indexy.

Pozrime sa, ako sa táto myšlienka realizuje na príklade nasýtených uhľovodíkov - alkánov. Kľúčom k konštruovaniu mnohých indexov je koncept „matice vzdialenosti“ D. Toto je názov matice, ktorej prvky ukazujú počet hrán oddeľujúcich zodpovedajúce vrcholy molekulárneho grafu. Zostrojme túto matricu pre tri izomérne uhľovodíky zloženia C 5 H 12 . Aby sme to dosiahli, nakreslíme ich molekulárne grafy a prečíslujeme vrcholy (v ľubovoľnom poradí):

Diagonálne prvky matice vzdialenosti pre uhľovodíky sú rovné 0. V prvom stĺpci je vrchol 1 spojený s vrcholom 2 jednou hranou, takže prvok matice d 12 = 1. Podobne d 13 = 2, d 14 = 3, d 15 = 4. Prvý riadok v matici vzdialenosti normálneho pentánu je: (0 1 2 3 4). Kompletné matice vzdialeností pre tri grafy:

molekulová chémia topologický index

Vzdialenosť medzi vrcholmi nezávisí od poradia ich enumerácie, takže matice vzdialenosti sú symetrické vzhľadom na uhlopriečku.

Prvý topologický index odrážajúci štruktúru molekulárneho grafu (G) navrhol v roku 1947 Wiener. Je definovaná ako súčet diagonálnych prvkov matice vzdialenosti plus polovica súčtu jej mimodiagonálnych prvkov:

(1)

Pre vyššie uvedené grafy zodpovedajúce pentánom C 5 H 12 Wienerov index nadobúda hodnoty 20, 18 a 16. Dá sa predpokladať, že popisuje stupeň rozvetvenia uhľovodíkov: najväčšie hodnoty zodpovedajú najmenej rozvetveným uhľovodíkom. S nárastom dĺžky uhlíkového skeletu sa Wienerov index zvyšuje, keďže v matici vzdialenosti je viac prvkov. Štatistická analýza na príklade niekoľkých stoviek uhľovodíkov ukázala, že Wienerov index koreluje s niektorými fyzikálnymi vlastnosťami alkánov: body varu, výparné teplo, molárny objem.

Iný typ indexu nie je založený na vzdialenostiach medzi vrcholmi, ale na počte najbližších susedov pre každý vrchol. Ako príklad si vypočítajme Randic index, ktorý je definovaný takto:

(2)

kde vi- stupeň i-tého vrcholu, teda počet hrán z neho vyčnievajúcich. Pre vyššie uvedené grafy je Randic index:

(3)

(4)

(5)

Tento index tiež klesá so zvyšujúcim sa stupňom rozvetvenia uhlíkového skeletu a možno ho použiť na opis fyzikálnych vlastností alkánov.

Alkány sú z chemického hľadiska najnudnejším typom organických molekúl, keďže neobsahujú žiadne „vlastnosti“ – dvojité a trojité väzby alebo atómy prvkov iných ako vodík a uhlík (takéto prvky sa nazývajú heteroatómy). Zavedenie heteroatómov do zloženia molekuly môže radikálne zmeniť vlastnosti látky. Pridanie len jedného atómu kyslíka teda premieňa skôr inertný plynný etán C 2 H 6 na tekutý etanol C 2 H 5 OH, ktorý vykazuje pomerne vysokú chemickú a biologickú aktivitu.

V dôsledku toho sa v topologických indexoch molekúl, ktoré sú zložitejšie ako alkány, musí brať do úvahy prítomnosť viacnásobných väzieb a heteroatómov. Robí sa to tak, že vrcholom a hranám grafov sa priraďujú určité číselné koeficienty – „váhy“. Napríklad v matici vzdialenosti môžu byť diagonálne prvky definované z hľadiska jadrového náboja Zi(pripomeňme, že pre uhlík Z = 6):

(6)

Mimodiagonálne prvky sú určené súčtom cez hrany a každá hrana spája atómy s nábojmi Zia Zj, je priradená váha

(7)

kde b sa rovná poradiu väzieb medzi atómami (1 pre jednoduchú väzbu, 2 pre dvojitú väzbu, 3 pre trojitú väzbu). Pre obyčajné jednoduché väzby uhlík-uhlík je k = 1. Porovnajte Wienerove indexy C propánu 3 H 8 a tri látky obsahujúce kyslík podobného zloženia: propylalkohol C 3 H 8 O, jeho izomérny izopropylalkohol C 3 H 8 O a acetón C 3 H 6 Oh

Na tento účel vypočítame matice vzdialenosti podľa uvedených pravidiel. V molekulových grafoch uvádzame všetky atómy okrem atómov vodíka 1) Propán

2) V molekule propylalkoholu je kyslík naviazaný na extrémny atóm uhlíka:

Pre jednoduchú väzbu C–O je váhový faktor 36/(68) = 0,75. Diagonálny prvok matrice zodpovedajúci kyslíku:

d 44 = 1 – 6/8 = 0.25.

Pre molekuly obsahujúce heteroatómy prestáva byť Wienerov index celým číslom. 3) V molekule izopropylalkoholu je kyslík viazaný na stredný atóm uhlíka:

4) V acetóne je poradie spojenia atómov rovnaké ako v izopropylalkohole, ale väzba medzi uhlíkom a kyslíkom je dvojitá:

Pre dvojitú väzbu C=O je váhový faktor 36/(268) = 0,375

Ako je možné vidieť, pridanie heteroatómu do štruktúry alkánov vedie k zvýšeniu Wienerovho indexu v dôsledku zväčšenia veľkosti matice vzdialenosti. Pridanie viacnásobných väzieb a zvýšenie stupňa rozvetvenia molekuly tento index znižuje. Tieto pravidlá platia aj pre zložitejšie molekuly. Spočiatku boli topologické indexy vyvinuté len na účely predpovedania fyzikálno-chemických vlastností látok. Neskôr sa však začali využívať na riešenie iných problémov. Uvažujme o niektorých z nich. Jedna z aplikácií topologických indexov súvisí s klasifikáciou organických zlúčenín a vytváraním organických databáz. Problémom je nájsť taký index, ktorý by charakterizoval chemickú štruktúru jedna k jednej a z ktorého by sa táto štruktúra dala obnoviť. Požadovaný index musí mať dobrú rozlišovaciu schopnosť, to znamená rozlišovať medzi sebou aj molekuly, ktoré sú si svojou štruktúrou blízke. Táto úloha je náročná, keďže už je známych viac ako 20 miliónov organických štruktúr. Jeho riešenie sa zrejme nájde ako výsledok použitia kompozitných topologických indexov.

Predslov editora prekladu
Predslov k ruskému vydaniu
Predslov
TOPOLÓGIA KONEČNEJ BODOVEJ Množiny A MOLEKULÁRNEJ ŠTRUKTÚRY. R. Merrifield, X. Simmons
1. Úvod
2. Konečná topológia
2.1. Graf topológie
2.2. Kvalitatívne charakteristiky topológie grafov
2.3. Kvantitatívne charakteristiky topológie grafov: kombinatorika
3. Topológia alternatívnych molekúl
3.1. Zložitosť štruktúry
3.2. Konektivita a delokalizácia
4. Topológia nealternatívnych molekúl
4.1. Gróf Duplex
4.2. duplexná topológia
Literatúra
STEREOCHEMICKÁ TOPOLÓGIA. D. Volba
1. Úvod
2. Prístup k syntéze topologických stereoizomérov založených na Möbiových prúžkoch
2.1. Kompletná syntéza prvého molekulárneho Möbiovho prúžku
3. Kritériá pre topologickú stereoizomériu
3.1. Topologická chiralita
3.2. Topologická diastereoizoméria
4. Orezávacia reakcia a prístupy k syntéze molekulárneho trifoliátového uzla
4.1. Pretrhnutie stupňov Möbiovho rebríka
4.2. Molekulárny trojlístok uzol
Literatúra
KVALITATÍVNA STEREOCHÉMIA J. Dugundji
1. Úvod
2. Permutačné izoméry
3. Skupina chemickej identity
Literatúra
TEÓRIA MOLEKULÁRNEJ ŠTRUKTÚRY. R. Bader
1. Prehľad teórie
2. Niektoré aplikácie
Literatúra
ALGEBRAICKÁ A TOPOLOGICKÁ ŠTRUKTÚRA KVANTOVEJ CHÉMIE, CHEMICKEJ KINETIKY A VIZUÁLNE PRAVIDLÁ UMOŽŇUJÚCE KVALITATÍVNE PREDPOKLADY PRE CHEMICKÚ PRAX. O. Sinanoglu
1. Úvod
2. Mikrochémia alebo kvalitatívne kvantovo-chemické pravidlá odvodené priamo zo štruktúrnych vzorcov alebo ORTEP diagramov
2.1. Pole vektorového priestoru valencií Vn(R), ktoré existuje v euklidovskom trojrozmernom priestore (?)
2.2. Princíp lineárnej kovariancie v kvantovej chémii
2.3. Nejednotná klasifikácia molekúl
2.4. Od štruktúrnych vzorcov molekúl k podrobnejším štruktúrno-elektronickým vzorcom (a ku grafom)
2.5. "Štrukturálna a deformačná kovariancia" molekúl a grafické pravidlá na získanie kvalitatívnych kvantových chemických výsledkov
3. Morfológia reakčných mechanizmov, cesty syntézy a topologické „pravidlá krokov/zložiek“
4. Vlastnosti získavania kvantových kvalitatívnych charakteristík každého reakčného štádia reakčného mechanizmu alebo dráhy
Literatúra
REAKČNÁ TOPOLÓGIA: TEÓRIA ROZMANITOSTÍ POTENCIÁLNYCH PLOCH A KVANTOVO-CHEMICKÝ NÁVRH SYNTÉZY. P. Mezhey
1. Úvod
2. Topologické variety, diferencovateľné variety a topológia reakcie
3. pomery kritických bodov; priesečníkové grafy v topologickom priestore (M, Tc) a schémy kvantových chemických reakcií
4. Výpočtové aspekty
5. Degenerujte kritické body a chemické štruktúry, ktoré nezodpovedajú skutočným minimám PES
6. Závery
Literatúra
TOPOLÓGIA VÄZBY V POLYHEDRÁLNYCH MOLEKULÁCH. R. Kráľ
1. Úvod
2. Základ koncepcie
3. Atómy vrcholov
4. Polyedrické systémy s lokalizovanou väzbou
5. Systémy s plne delokalizovanou väzbou
6. Elektrónovo redundantné polyedrické systémy
7. Elektrón-deficientné polyedrické systémy
8. Anomálne vrcholy
9. Mnohosteny
10. Závery
Literatúra
FORMY KLUSTROV PRVKOV HLAVNÝCH PODSKUPÍN: TOPOLOGICKÝ PRÍSTUP K POČÍTANIU ELEKTRONOV KOSY. M. McGlinchy, Y. Tal
1. Úvod
2. Klastre s plne delokalizovanou väzbou
3. Zhluky s väzbovou lokalizáciou na okrajoch
3.1. Šesťatómové klastre
3.2. Poloatómové klastre
3.3. Zhluky ôsmich atómov
4. Kvantovo-topologické zdôvodnenie polyedrického modelu
5. Závery
Literatúra
TOPOLOGICKÉ VLASTNOSTI BINÁRNYCH ZLÚČENÍN SÍRY S DUSÍKOM. A. Turner
1. Úvod
2. Prototypová molekula - tetranitrid tetrasulfur
3. Planárne cyklické molekuly a ióny SnNm
4. Neplanárne systémy - ekvivalencia centier distribúcie náboja
5. Aplikácia teórie funkcionálu elektrónovej hustoty
Literatúra
MALI BY STE VYPRACOVAŤ VÝVOJ TOPOLOGICKÝCH INDEXOV? D. Rouvray
1. Úvod
2. Wienerov index
3. Konštrukcia indexu
4. Indexy matice vzdialenosti
5. Indexy matice susednosti
6. Centrické topologické indexy
7. Informačno-teoretické indexy
8. Zložené topologické indexy
9. Niektoré matematické vzťahy
10. Tvar a veľkosť molekúl
11. Hlavné aplikácie indexov
12. Bibliografická klasifikácia zlúčenín
13. Stanovenie fyzikálno-chemických parametrov
14. Vývoj farmaceutických liečiv
15. Závery
Literatúra
TOPOLOGICKÉ INDEXY ZALOŽENÉ NA OKOLITEJ SYMETRII: CHEMICKÉ A BIOCHEMICKÉ APLIKÁCIE. V. Magnuson, D. Harris, S. Beisak
1. Úvod
2. Informačný obsah grafu
2.1. Definície
2.2. Základné ustanovenia
2.3. Vzťah ekvivalencie
2.4. Výpočet iných topologických indexov
3. Výpočet indexov
4. Aplikácie v štúdiách korelácie kvantitatívnej štruktúry a aktivity (QKSA).
4.1. Rozpustnosť alkoholov
4.2. Inhibícia mikrozomálnej para-hydroxylácie anilínu alkoholmi
4.3. Toxicita (LD50) barbiturátov
Literatúra
RADENIE GRAFOV AKO PRÍSTUP K ŠTÚDIU KORELÁCIÍ ŠTRUKTÚRA A ČINNOSŤ. M. Randič, J. Kraus, B. Dzonová-Jerman-Blažič
1. Úvod
2. Základné princípy metódy
3. Aplikácia na látky s antimalarickým účinkom
3.1. Vytvorenie postupnosti obvodov
3.2. Porovnanie molekúl A-M
4. Diskusia
Literatúra
MATEMATICKÝ MODEL MOLEKULÁRNEJ ZLOŽITOSTI. S. Bertz
1. Hľadanie
2. Vývoj modelu
2.1. Teória grafov a molekulárna topológia
2.2. Teória informácie a molekulová symetria
3. Overenie modelu
3.1. Obmedzenia modelu
4. Spoľahlivosť modelu
5. Závery
Literatúra
MATICE VZDIALENOSTI PRE MOLEKULY OBSAHUJÚCE HETERO-ATÓMY. M. Barish, J. Yashari, R. Lall, V. Srivastava, I. Trinaistich
1. Úvod
2. Vzťah medzi maticou susednosti a maticou vzdialenosti
3. Matica vzdialenosti pre heterosystémy
Literatúra
KANONICKÉ ČÍSLOVANIE A SYSTÉM LINEÁRNEHO ZÁPISU CHEMICKÝCH GRAFOV. W. Herndon
1. Úvod
2. Kanonické číslovanie
3. Jednohodnotový lineárny zápis
4. Kanonické vyčíslenie regulárnych grafov
5. Závery
Literatúra
SYMETRIA A SPEKTRA GRAFOV. ICH APLIKÁCIE V CHÉMII. K. Balasubramanian
1. Úvod
2. Orezávanie stromov
3. Prerezávanie stromov a skupiny symetrie stromov
4. Spektrálne polynómy stromov získané procesom orezávania
5. Aplikácie v chémii
Literatúra
AUTOMORFIZMUS SKUPINY NIEKTORÝCH CHEMICKÝCH GRAFOV. G. Jones, E. Lloyd
1. Úvod
2. Niektoré grafy a ich skupiny
3. Reakčné grafy
3.1. Príklad 1: Berry mechanizmus
3.2. Príklad 2: 1,2 posun v karbóniových iónoch
3.3. Príklad 3: 1,2-posuny v homotetraedranylových katiónoch
3.4. Príklad 4: Digonálne zákruty v oktaedrických komplexoch
3.5. Príklad 5: 1,3-posuny v homotetraedranylových katiónoch
4. Suborbitálne grafy
5. Závery
Literatúra
PROBLÉM REKONŠTRUKCIE. W. Tutt
VYUŽITIE POVRCHU RIEMANN V GRAFOVOTEORETICKOM ZOBRAZENÍ SYSTÉMOV MÖBIUS. A. Day, R. Mallion, M. Rigby
1. Úvod
2. Formalizmus metódy
3. Aplikácia
4. Závery
Literatúra
GLOBÁLNA DYNAMIKA NIEKTORÝCH TRIED REAKČNÝCH SYSTÉMOV. X. Meranie
1. Úvod
2. Grafo-teoretická formulácia
2.1. Štruktúra riadiacich rovníc
2.2. Niektoré pojmy z teórie grafov
2.3. Reakčné invarianty
2.4. Existencia stacionárnych stavov
3. Vertexom riadené siete
3.1. Konštantné vstupné toky
3.2. Periodické vstupné toky
4. Závery
Literatúra
„LOGICKÝ POPIS“ V POROVNANÍ S „PRIEBEŽNÝM POPISOM“ SYSTÉMOV OBSAHUJÚCICH SLUČKY SPÄTNEJ VÄZBY: VZŤAH MEDZI ČASOVÝMI ONESKORENIAMI A PARAMETRAMI. R. Thomas
1. Úvod
2. Logický popis systémov obsahujúcich spätnoväzbové slučky
2.1. Oneskorenia „zapnuté“ a „vypnuté“
2.2. Logické rovnice
2.3. Stavové tabuľky
2.4. Reťazce (sekvencie stavov)
2.5. Analýza stability
3. Priebežný popis
3.1. Logické časové oneskorenia a spojité parametre
Literatúra
KVALITATÍVNA DYNAMIKA A STABILITA SYSTÉMOV CHEMICKÝCH REAKCIÍ. B. Clark
1. Úvod
2. Nastavenie chemického systému
3. Časové škály – odstránenie látok, ktoré reagujú príliš rýchlo a príliš pomaly
4. Teória chemických sietí
5. Dynamika systému
6. Rozmanitosť stacionárnych stavov
7. Jednoduché vety pre sieťovú analýzu
8. Hlbšia diskusia o stacionárnych stavoch a ich existencii
9. Správnosť
10. Jedinečnosť
11. Globálna príťažlivosť
12. Siete, v ktorých nie je rozdeľovač pravidelný, jednoznačný a globálne atraktívny
13. Topológia a stabilita siete
14. Záverečné poznámky
15. Aplikácia
15.1. Univerzálne funkcie
15.2. Funkcie pre symbolické spracovanie a výpočet aktuálnej matice
15.3. Kontrolné funkcie teorémov a súvisiace funkcie
15.4. Jednotlivé funkcie
Literatúra
NAJVYŠŠÍ CHAOS V JEDNODUCHÝCH REAKČNÝCH SYSTÉMOCH. O. Ressler, J. Hudson
1. Úvod
2. Metóda generovania obyčajného chaosu
3. Metóda generovania vyššieho chaosu
4. Diskusia
Literatúra
PODIVNÉ ATRAKTORY VO FUNKCIÁCH LINEÁRNEHO PERIODICKÉHO PRENOSU S PRAVIDELNÝMI PERTURBÁCIAMI. X. Degn
1. Úvod
2. Výsledky
Literatúra
POUŽITIE ANALÝZY CITLIVOSTI PRI URČOVANÍ ŠTRUKTURÁLNEJ STABILITY MULTIPARAMETROVÝCH OSCILÁTOROV. R. Larter
1. Úvod
2. Metóda
2.1. Štandardná teória
2.2. Upravená teória
3. Výsledky
3.1. Počiatočné podmienky
3.2. Sadzobné konštanty
3.3. Ťažšie situácie
Literatúra
ZOBRAZENIE n-ROZMERNÝCH CHEMICKÝCH ROZVODOV POMOCOU ELEKTRICKÝCH SIETE. L. Pusener
1. Úvod: topologická a geometrická analýza chemických procesov
2. Základné geometrické vlastnosti n-rozmerných metrických variet
3. Reprezentácia ako sieť
4. Príklad pre dvojrozmerný systém
5. Optimálne cesty
6. Príklad použitia chemickej siete na lineárne prechody medzi viacerými stavmi
7. Variačné siete
Aplikácia: sieťová analýza
Literatúra
LOGIKA CHEMICKÝCH NÁPADOV. P. Plyat, E. Hass
1. Úvod
2. Topológia pericyklických reakcií
3. Mriežky pericyklických reakcií
4. Ortomodulárne a booleovské reaktívne štvorrozmerné mriežky
5. Závery
Literatúra
VIACDIMENZIONÁLNY X-MODEL. TEÓRIA GRAFOV A ALGEBRAICKÝ PRÍSTUP K POPISU MECHANIZMOV KOMPLEXNÝCH CHEMICKÝCH REAKCIÍ. E. Hass, P. Plyat
1. Úvod
2. Jednoparametrový X-model
3. Viacrozmerný X-model
3.1. Reakčné dráhy pre -cykloadície
4. Závery
Literatúra
KLASIFIKÁCIA MECHANIZMOV CHEMICKÝCH REAKCIÍ Z GEOMETRICKÉHO POHĽADU. P. Predajcovia
1. Úvod
2. Milnerov príklad
3. Mechanizmy bez cyklov
4. Iné mechanizmy
5. Viacnásobné celkové reakcie
6. Závery
Literatúra
GRAFY, POLYMÉROVÉ MODELY, VYLÚČENÝ OBJEM A CHEMICKÁ REALITA. D. Klein, W. Seitz
1. Úvod
2. Izolované lineárne obvody
3. Počítanie izomérov
4. Konformácie rozvetvených polymérov
5. Teória škálovania
6. Prevodové matice
7. Sebapodobnosť a renormalizácia
8. Diskusia
Literatúra
FUNKCIA OBJEMU PRE VODU NA ZÁKLADE MODELU NÁHODNÉHO MRIEŽKOVÉHO PODGRAFU. L. Quintas
1. Úvod a úvodné matematické poznámky
2. Model náhodných grafov pre vodu
3. Funkcia objemu vody
4. Korešpondencia V(p) s číselnými údajmi
5. Záverečné poznámky
Literatúra
TOPOLOGICKÉ ASPEKTY ROZPOZNÁVANIA ENZÝM-SUBSTRÁT. S. Swaminathan
1. Problém rozpoznávania enzým-substrát
2. Edelstein-Rosenov model
3. Metóda fenomenologického počtu
4. Hilbertov priestor popisu
5. Postuláty pre dynamiku zložitých systémov
6. Model rozpoznávania enzým-substrát
7. Záverečné poznámky
Literatúra
DYNAMIKA VZNIKU SEKUNDÁRNEJ ŠTRUKTÚRY RNA. X. Martinets
1. Úvod
2. Metódy minimalizácie energie
3. Metóda modelovania
4. Závery
Literatúra
LISP PROGRAM PRE FUNKČNO-FRAGMENTOVÚ REPREZENTÁCIU MOLEKÚL A ICH GEOMETRIE. K. Trindle, R. Givan
1. Úvod
2. Lisp je nenumerický programovací jazyk
3. Reprezentácia molekúl pomocou jazyka Lisp
4. Neformálny algoritmus rozpoznávania fragmentov
5. Niektoré špeciálne problémy
6. Vytvorenie matice vzdialenosti pomocou databanky fragmentov
7. Faktorová analýza a Crippenov algoritmus na určovanie geometrie pomocou vzdialeností
8. Závery a perspektívy
Literatúra
Predmetový index

Š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 zatiaľ 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žívania počítačmi. Optimálne riešenie tejto problematiky by malo dopad 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 atď. 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émia, 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 na modelovanie rastu kryštálov a kryštálových vakancií.

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. Tvorba nových efektívnych 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žití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 pohľad 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ákladné 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 každá získaná informácia 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. Sformulovali tiež optimálne informačné podmienky pre charakterizáciu a predikciu katalytických vlastností. Tvorba 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 aplikovali 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 ukladaní 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čnej báze 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 veličinami, ako je väzbová energia, ktorej vzťah s informáciou nie je ani zďaleka zrejmý. Tu sú zahrnuté vlastnosti ako samostatná molekula alebo atóm, ale aj ich veľké agregáty, t. j. 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ú to tiež štatistické charakteristiky a vzťahujú sa na agregáty, ale nie 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 využí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ácie 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 je určený podľa Shannonovho vzorca (y-e 2.1):

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

Tu je K kladná konštanta, ktorá určuje jednotky merania informácií. Za predpokladu, že K \u003d 4 sa entropia (respektíve informácie) meria v desatinných jednotkách. Najpohodlnejší systém merania je založený na binárnych jednotkách (bitoch). V tomto prípade K ~ W2 a logaritmus wur-u(2.4) je vzatý v základe dva a \-! je skrátene označený t. Jedna binárna jednotka informácie (alebo 1 bit) je množstvo informácií, 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.

Jednotlivá aj priemerná informácia 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) = -Yp(X,y1)1Bp(Y;/X-,) (2,10)

Definovanie funkcie:

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

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

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

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

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

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

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

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

Známe sú aj pravdepodobnostné prístupy ku kvantitatívnemu určovaniu informácií. Ingarden a Urbanich navrhli axiomatickú/sizvdelenie-Sheinovu informáciu bez pravdepodobnosti vo forme funkcie konečných booleovských kruhov. Značne zaujímavá je epsilon-entropia (kombinatorický prístup) navrhovaná Kolmogorovom^^ a najmä algoritmické určenie množstva informácie. Podľa Kolmogorova sa množstvo informácií obsiahnutých v jednom objekte (množine) vo vzťahu k inému objektu (množine) považuje za „minimálnu dĺžku“ programov, napísaných ako postupnosť núl a jednotiek, a umožňujúcich vzájomný pomer jedna k jednej. transformácia; 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, v tomto prístupe vyjadruje minimálny rozdiel, teda rozdiel medzi dvoma objektmi, ktoré nie sú totožné, líšia sa v niektorých nehnuteľnosť.

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é na podmnožiny (triedy 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 ¿T - A/"u je pravdepodobnosť, že jeden (náhodne) vybraný prvok spadne do / - tej podmnožiny, pre ktorú 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ácie I, ktorá je 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 štrukturálnej 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ď sa systém skladá z rovnakých prvkov, nie je v ňom žiadna rozmanitosť. V tomto prípade v y-s (2,19) a (2,20)/="/

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

4 "* -N16 u, T ^ ^ vi

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

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

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

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

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

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

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

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

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

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

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

Pripravené

Legkokonets Vladislav, 10A študent

Praktická aplikácia teórie grafov

Dozorca

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

st.Bryukhovetskaya

2011

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

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

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

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

4.1 Slávne úlohy………………………………………………………………...8

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

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

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

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

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

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

Úvod

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

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

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

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

Ciele výskumu:

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

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

3. Urobte záver.

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

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

História vzniku teórie grafov

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Problémy riešené pomocou grafov

Slávne výzvy

Problém obchodného cestujúceho

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

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

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

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

Problém Königsbergských mostov.

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

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

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

Niekoľko zaujímavých výziev

1. "Trasy".

Úloha 1

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

rozhodnutie:

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

Úloha 2

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

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

rozhodnutie:

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

2 "Skupiny, zoznamka"

Úloha 1

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

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

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

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

rozhodnutie:

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

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

Úloha 2

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

rozhodnutie:

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

[aplikácia obr. 9]

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

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

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

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

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

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

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

Proteínové siete

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

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

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

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

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

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

Riešenie problémov

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

rozhodnutie:

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

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

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

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

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

rozhodnutie:

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

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

Záver

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

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

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

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

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

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

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

Literatúra

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

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

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

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

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

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

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

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

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

Aplikácia