Aplicarea teoriei grafurilor în chimie. Teoria grafurilor în chimie și probleme nerezolvate. Aplicarea graficelor în diverse domenii ale vieții oamenilor
Prefața editorului de traduceri
Prefață la ediția rusă
Prefaţă
TOPOLOGIA UNUI SET DE PUNCTE FINITE ȘI STRUCTURĂ MOLECULARĂ. R. Merrifield, X. Simmons
1. Introducere
2. Topologie finală
2.1. Graficul de topologie
2.2. Caracteristicile calitative ale topologiei de graf
2.3. Caracteristicile cantitative ale topologiei de graf: combinatorie
3. Topologia moleculelor alternative
3.1. Complexitatea structurii
3.2. Conectivitate și delocalizare
4. Topologia moleculelor nealternante
4.1. Grafic duplex
4.2. Topologie duplex
Literatură
TOPOLOGIE STEREOCHIMICĂ. D. Volba
1. Introducere
2. O abordare a sintezei stereoizomerilor topologici pe baza benzilor Möbius
2.1. Sinteza completă a primei benzi moleculare Möbius
3. Criterii de stereoizomerie topologică
3.1. Chiralitate topologică
3.2. Diastereoizomerie topologică
4. Reacția de tăiere și abordări ale sintezei nodului molecular trefoil
4.1. Ruperea treptelor scării Mobius
4.2. Nod de trefoil molecular
Literatură
STEREOCHIMIE CALITATIVĂ J. Dugundji
1. Introducere
2. Izomeri de permutare
3. Grupa de identitate chimică
Literatură
TEORIA STRUCTURII MOLECULARE. R. Bader
1. Revizuirea teoriei
2. Unele aplicații
Literatură
STRUCTURA ALGEBRICĂ ȘI TOPOLOGICĂ A CHIMIEI CUANTICE, CINETICĂ CHIMĂ ȘI REGULI VISUALE CARE VA PERMIT SĂ FACEȚI PREDICȚIUNI CALITATIVE PENTRU PRACTICA CHIMICĂ. O. Sinanoglu
1. Introducere
2. Microchimie sau reguli de chimie cuantică calitativă derivate direct din formule structurale sau diagrame ORTEP
2.1. Câmpul spațial vectorial de valență Vn(R) existent în spațiul tridimensional euclidian (?)
2.2. Principiul covarianței liniare în chimia cuantică
2.3. Clasificarea neunitară a moleculelor
2.4. De la formule structurale ale moleculelor la formule structural-electronice mai detaliate (și la grafice)
2.5. „Covarianța structurală și de deformare” a moleculelor și regulile grafice pentru obținerea de rezultate chimice cuantice de înaltă calitate
3. Morfologia mecanismelor de reacție, căi de sinteză și „reguli de etapă/compuși” topologice
4. Caracteristici de obținere a caracteristicilor calitative cuantice ale fiecărei etape de reacție a mecanismului sau a căii de reacție
Literatură
TOPOLOGIA REACȚIILOR: TEORIA MANIFESTĂȚILOR SUPRAFEȚELOR POTENCIALE ȘI PROIECTAREA CHIMICĂ CANTUMĂ A SINTEZEI. P. Mezhey
1. Introducere
2. Varietăți topologice, varietăți diferențiabile și topologie de reacție
3. Raportul punctelor critice; grafice de intersecție în spațiu topologic (M, Tc) și scheme de reacție chimică cuantică
4. Aspecte de calcul
5. Puncte critice degenerate și structuri chimice care nu corespund cu adevăratele minime PES
6. Concluzii
Literatură
TOPOLOGIA LEGĂRII ÎN MOLECULE POLIDEDRICE. R. Regele
1. Introducere
2. Concept de bază
3. Atomi de vârf
4. Sisteme poliedrice cu legare localizată
5. Sisteme cu legare complet delocalizată
6. Sisteme poliedrice bogate în electroni
7. Sisteme poliedrice electron-deficiente
8. Vârfuri anormale
9. Poliedre
10. Concluzii
Literatură
FORME DE CLUSTE DE ELEMENTE ALE PRINCIPALELOR SUBGRUPURI: O ABORDARE TOPOLOGICĂ A NUMĂRĂRII ELECTRONILOR SCHELETICI. M. McGlinchey, J. Tal
1. Introducere
2. Clustere cu legare complet delocalizată
3. Clustere cu localizare de legare pe margini
3.1. clustere de hexatomi
3.2. clustere de șapte atomi
3.3. clustere de opt atomi
4. Fundamentarea cuantico-topologică a modelului poliedric
5. Concluzii
Literatură
PROPRIETĂȚI TOPOLOGICE ALE COMPUSILOR BINARI AI SULFULUI CU AZOT. A. Turner
1. Introducere
2. Molecula prototip este tetranitrură de tetrasulf
3. Molecule ciclice planare și ioni SnNm
4. Sisteme neplanare - echivalența centrelor de distribuție a taxelor
5. Aplicarea teoriei funcționale a densității electronice
Literatură
TREBUIE SĂ DEZVOLȚI INDICI TOPOLOGICI? D. Rouvray
1. Introducere
2. Indicele Wiener
3. Construcția indexului
4. Indici matrici de distanță
5. Indicii matrici de adiacență
6. Indici topologici centrici
7. Indici informatici-teoretici
8. Indici topologici compoziti
9. Câteva relaţii matematice
10. Forma și dimensiunea moleculelor
11. Aplicații de bază ale indicilor
12. Clasificarea bibliografică a compuşilor
13. Determinarea parametrilor fizico-chimici
14. Dezvoltarea medicamentelor farmaceutice
15. Concluzii
Literatură
INDICI TOPOLOGICI PE BAZĂ DE SIMETRIA CARCATELOR: APLICAȚII CHIMICE ȘI BIOCHIMICE. V. Magnuson, D. Harris, S. Beysak
1. Introducere
2. Conținutul informațional al graficului
2.1. Definiții
2.2. Dispoziții de bază
2.3. Relația de echivalență
2.4. Calculul altor indici topologici
3. Calculul indicilor
4. Aplicații în studiile de corelație cantitativă structură-activitate (QSCA).
4.1. Solubilitatea alcoolilor
4.2. Inhibarea parahidroxilării microzomale a anilinei de către alcooli
4.3. Toxicitatea (DL50) a barbituricelor
Literatură
ORDINAREA GRAFICĂ CA O ABORDARE A STUDIILOR CORELATIILOR STRUCTURA-ACTIVITATE. M. Randic, J. Kraus, B. Dzonova-German-Blazic
1. Introducere
2. Principii de bază ale metodei
3. Aplicare la substanțe cu efecte antimalarice
3.1. Construirea unei secvențe de circuite
3.2. Comparația moleculelor A-M
4. Discutie
Literatură
MODEL MATEMATIC AL COMPLEXITĂȚII MOLECULARE. S. Bertz
1. Vaeding
2. Dezvoltarea modelului
2.1. Teoria grafurilor și topologia moleculară
2.2. Teoria informației și simetria moleculară
3. Verificarea modelului
3.1. Limitări ale modelului
4. Fiabilitatea modelului
5. Concluzii
Literatură
MATRICE DE DISTANȚE PENTRU MOLECULE CARE CONȚIN HETEROATOMI. M. Barish, J. Yashari, R. Lall, V. Srivastava, I. Trinaistich
1. Introducere
2. Relația dintre matricea de adiacență și matricea distanțelor
3. Matricea distanțelor pentru heterosisteme
Literatură
NUMEROAREA CANONICĂ ȘI SISTEMUL DE NOTAȚIE LINEARĂ PENTRU GRAFICE CHIMICE. W. Herndon
1. Introducere
2. Numerotarea canonică
3. Notație liniară fără ambiguitate
4. Numerotarea canonică a graficelor regulate
5. Concluzii
Literatură
SIMETRIA ȘI SPECTRELE GRAFICELOR. APLICAȚIILE LOR ÎN CHIMIE. K. Balasubramanian
1. Introducere
2. Tăierea copacilor
3. Tăierea arborilor și grupele de simetrie a arborilor
4. Polinoame spectrale de arbori obținute prin procesul de tăiere
5. Aplicații în chimie
Literatură
GRUPURI DE AUTOMORFISME ALE UNOR GRAFICE CHIMICE. G. Jones, E. Lloyd
1. Introducere
2. Câteva grafice și grupurile lor
3. Grafice de reacție
3.1. Exemplul 1: mecanism de fructe de pădure
3.2. Exemplul 2: 1,2-deplasări în ionii de carboniu
3.3. Exemplul 3: 1,2-deplasări în cationii homotetraedranil
3.4. Exemplul 4: răsuciri diagonale în complexe octaedrice
3.5. Exemplul 5: 1,3-deplasări în cationii homotetraedranil
4. Grafice suborbitale
5. Concluzii
Literatură
PROBLEMA RECONSTRUCȚIEI. W. Tutt
UTILIZAREA SUPRAFEȚELOR RIEMANN ÎN REPREZENTAREA GRAFEORETICĂ A SISTEMELOR MÖBIUS. A. Day, R. Mullion, M. Rigby
1. Introducere
2. Formalismul metodei
3. Aplicare
4. Concluzii
Literatură
DINAMICA GLOBALĂ A UNOR CLASE DE SISTEME DE REACȚIE. X. Dimensiunea
1. Introducere
2. Formularea grafico-teoretică
2.1. Structura ecuațiilor de control
2.2. Câteva concepte ale teoriei grafurilor
2.3. Invarianți de reacție
2.4. Existența stărilor staționare
3. Rețele conduse de vârfuri
3.1. Fluxuri de intrare constante
3.2. Fluxuri de intrare periodice
4. Concluzii
Literatură
„DESCRIEREA LOGICĂ” VERSUS „DESCRIEREA CONTINUĂ” A SISTEMELOR CU BUCLE DE FEEDBACK: RELAȚIA DINTRE ÎNTÂRZIERI ȘI PARAMETRI. R. Toma
1. Introducere
2. Descrierea logică a sistemelor care conțin bucle de feedback
2.1. Întârzieri „Pornit” și „Oprit”.
2.2. Ecuații logice
2.3. Tabelele de stat
2.4. Circuite (secvențe de stări)
2.5. Analiza de stabilitate
3. Descriere continuă
3.1. Întârzieri logice și parametri continui
Literatură
DINAMICA CALITATIVĂ ȘI STABILITATEA SISTEMELOR DE REACȚII CHIMICE. B. Clark
1. Introducere
2. Specificarea unui sistem chimic
3. Scale de timp – eliminarea substanțelor care reacționează prea repede și prea încet
4. Teoria rețelelor chimice
5. Dinamica sistemului
6. Varietate de stări staționare
7. Teoreme simple pentru analiza rețelelor
8. Discuție mai profundă despre stările staționare și existența lor
9. Corectitudine
10. Neambiguitate
11. Atracție globală
12. Rețele în care diversitatea nu este corectă, lipsită de ambiguitate și atractivă la nivel global
13. Topologia și stabilitatea rețelei
14. Observații finale
15. Aplicare
15.1. Caracteristici versatile
15.2. Funcții pentru prelucrarea simbolică și calculul matricei curente
15.3. Verificarea teoremei și funcții aferente
15.4. Funcții individuale
Literatură
HAS MAI MARE ÎN SISTEME DE REACȚIE SIMPLE. O. Ressler, J. Hudson
1. Introducere
2. Metodă de generare a haosului obișnuit
3. Metoda de a genera un haos mai mare
4. Discutie
Literatură
ATRACTORI CIUDATI ÎN FUNCȚIILE DE TRANSFER PERIODICE LINEAR CU PERTURBĂRI PERIODICE. X. Degn
1. Introducere
2. Rezultate
Literatură
UTILIZAREA ANALIZEI SENSIBILITĂȚII ÎN DETERMINAREA STABILITĂȚII STRUCTURALE A OSCILATOARELOR MULTIPARAMETRI. R. Larter
1. Introducere
2. Metoda
2.1. Teoria standard
2.2. Teoria modificată
3. Rezultate
3.1. Condiții inițiale
3.2. Constantele ratei
3.3. Situații mai complexe
Literatură
REPREZENTAREA SOIURILOR CHIMICE N-DIMENSIONALE FOLOSIND REȚELE ELECTRICE. L. Puzner
1. Introducere: analiza topologică și geometrică a proceselor chimice
2. Proprietăți geometrice de bază ale varietăților metrice n-dimensionale
3. Reprezentarea ca retea
4. Exemplu pentru un sistem bidimensional
5. Trasee optime
6. Un exemplu de utilizare a unei rețele chimice pentru tranziții liniare între mai multe stări
7. Rețele variaționale
Aplicație: Analiza rețelei
Literatură
LOGICA IDEILOR CHIMICE. P. Plyat, E. Hass
1. Introducere
2. Topologia reacțiilor periciclice
3. Rețele de reacții periciclice
4. Rețele cu patru dimensiuni ortomodulare și booleene
5. Concluzii
Literatură
MULTIDIMENSIONAL X-MODEL. ABORDAREA GRAFEORETICĂ ȘI ALGEBRICĂ PENTRU DESCRIEREA MECANISMELOR REACȚIILOR CHIMICE COMPLEXE. E. Hass, P. Plyat
1. Introducere
2. Model X cu un singur parametru
3. Model X multidimensional
3.1. Căi de reacție pentru -cicloadiții
4. Concluzii
Literatură
CLASIFICAREA MECANISMELOR REACȚILOR CHIMICE DIN PUNCT DE VEDERE GEOMETRIC. P. Vânzători
1. Introducere
2. Exemplul lui Milner
3. Mecanisme fără cicluri
4. Alte mecanisme
5. Reacții totale multiple
6. Concluzii
Literatură
GRAFICE, MODELE DE POLIMERE, VOLUM EXCLUS ȘI REALITATE CHIMĂ. D. Klein, W. Seitz
1. Introducere
2. Circuite liniare izolate
3. Numărarea izomerilor
4. Conformaţiile polimerilor ramificaţi
5. Teoria scalarii
6. Matrici de transfer
7. Autoasemănarea și renormalizarea
8. Discuție
Literatură
FUNCȚIE DE VOLUM PENTRU APĂ PE BAZĂ PE UN MODEL DE SUBGRAF ALEATORUL DE LATICĂ. L. Quintas
1. Introducere și observații matematice preliminare
2. Model grafic aleatoriu pentru apă
3. Funcție de volum pentru apă
4. Corespondența lui V(p) cu datele numerice
5. Observații finale
Literatură
ASPECTE TOPOLOGICE ALE RECUNOAȘTERII ENZIME-SUBSTRAT. S. Swaminathan
1. Problema recunoașterii enzimă-substrat
2. Modelul Edelstein-Rosen
3. Metoda calculului fenomenologic
4. Spațiul de descriere Hilbert
5. Postulate pentru dinamica sistemelor complexe
6. Model de recunoaștere enzimă-substrat
7. Observații finale
Literatură
DINAMICA FORMĂRII STRUCTURII SECUNDARE ARN. X. Martinets
1. Introducere
2. Metode de minimizare a energiei
3. Metoda simulării
4. Concluzii
Literatură
PROGRAM ÎN LIMBAJUL LISP PENTRU REPREZENTAREA FUNCȚIONAL-FRAGMENTALĂ A MOLECULELOR ȘI A GEOMETRIEI LOR. K. Trindl, R. Givan
1. Introducere
2. Lisp - limbaj de programare non-numeric
3. Reprezentarea moleculelor folosind limbajul Lisp
4. Algoritm de recunoaștere informală a fragmentelor
5. Câteva probleme speciale
6. Construirea unei matrice de distanțe folosind o bancă de date fragment
7. Analiza factorială și algoritmul Crippen pentru determinarea geometriei prin distanțe
8. Concluzii și perspective
Literatură
Index de subiect
B - P + G = 1, (*)
unde B este numărul total de vârfuri, P este numărul total de muchii, G este numărul de poligoane (fețe).
Dovada. Să demonstrăm că egalitatea nu se schimbă dacă este trasată o diagonală într-un poligon al unei partiții date (Fig. 2, a).
a) b)
Fig.2
Într-adevăr, după desenarea unei astfel de diagonale, noua partiție va avea B vârfuri, P+1 muchii, iar numărul de poligoane va crește cu unul. Prin urmare, avem
B - (P + 1) + (G+1) = B – P + G.
Folosind această proprietate, desenăm diagonale care împart poligoanele de intrare în triunghiuri, iar pentru partiția rezultată arătăm fezabilitatea relației.
Pentru a face acest lucru, vom elimina secvenţial marginile exterioare, reducând numărul de triunghiuri. În acest caz, sunt posibile două cazuri:
pentru a elimina triunghiul ABC, trebuie să eliminați două margini, în cazul nostru AB și BC;
Pentru a elimina triunghiul MKN, trebuie să eliminați o margine, în cazul nostru MN.
În ambele cazuri, egalitatea nu se va schimba. De exemplu, în primul caz, după îndepărtarea triunghiului, graficul va fi format din vârfuri B-1, muchii P-2 și poligon G-1:
(B - 1) - (P + 2) + (G -1) = B – P + G.
Astfel, eliminarea unui triunghi nu schimbă egalitatea.
Continuând acest proces de eliminare a triunghiurilor, vom ajunge în cele din urmă la o partiție formată dintr-un singur triunghi. Pentru o astfel de partiție B = 3, P = 3, G = 1 și, prin urmare,
B - P + G = 1.
Aceasta înseamnă că egalitatea este valabilă și pentru partiția originală, din care în final obținem că relația este valabilă pentru această partiție a poligonului.
Rețineți că relația lui Euler nu depinde de forma poligoanelor. Poligoanele pot fi deformate, mărite, reduse sau chiar laturile lor pot fi îndoite, atâta timp cât laturile nu se rupe. Relația lui Euler nu se va schimba.
Să trecem acum la rezolvarea problemei a trei case și trei fântâni.
Soluţie . Să presupunem că acest lucru se poate face. Să marchem casele cu punctele D1, D2, D3 și puțurile cu punctele K1, K2, K3 (Fig. 1). Conectăm fiecare punct de casă cu fiecare punct de puț. Obținem nouă muchii care nu se intersectează în perechi.
Aceste margini formează un poligon pe plan, împărțit în poligoane mai mici. Prin urmare, pentru această partiție trebuie îndeplinită relația Euler B - P + G = 1.
Să mai adăugăm o față fețelor luate în considerare - partea exterioară a planului în raport cu poligonul. Atunci relația Euler va lua forma B - P + G = 2, cu B = 6 și P = 9.
Prin urmare, Г = 5. Fiecare dintre cele cinci fețe are cel puțin patru margini, deoarece, conform condițiilor problemei, niciuna dintre căi nu ar trebui să conecteze direct două case sau două puțuri. Deoarece fiecare muchie se află pe exact două fețe, numărul muchiilor trebuie să fie de cel puțin (5 4)/2 = 10, ceea ce contrazice condiția ca numărul lor să fie 9.
Contradicția rezultată arată că răspunsul la problemă este negativ - este imposibil să se deseneze căi care nu se intersectează de la fiecare casă la fiecare sat
Teoria grafurilor în chimie
Aplicarea teoriei grafurilor la construirea și analiza diferitelor clase de grafuri chimice și chimico-tehnologice, care se mai numesc și topologie, modele, i.e. modele care iau în considerare doar natura legăturilor dintre vârfuri. Arcele (muchiile) și vârfurile acestor grafice reflectă concepte chimice și chimico-tehnologice, fenomene, procese sau obiecte și, în consecință, relații calitative și cantitative sau anumite relații între ele.
Probleme teoretice. Graficele chimice fac posibilă prezicerea transformărilor chimice, explicarea esenței și sistematizarea unor concepte de bază ale chimiei: structură, configurație, confirmări, mecanică cuantică și interacțiuni statistico-mecanice ale moleculelor, izomerie etc. Graficele chimice includ grafice moleculare, bipartite și de semnal. a ecuațiilor reacțiilor cinetice. Graficele moleculare, utilizate în stereochimie și topologia structurală, chimia clusterelor, polimerilor etc., sunt grafice nedirecționate care prezintă structura moleculelor. Vârfurile și muchiile acestor grafice corespund atomilor corespunzătoare și legăturilor chimice dintre ei.
În stereochimie org. c-c cei mai des utilizați sunt arbori moleculari - arbori care se întind de grafice moleculare care conțin numai toate vârfurile corespunzătoare atomilor. Compilarea seturi de arbori moleculari și stabilirea izomorfismului lor face posibilă determinarea structurilor moleculare și găsirea numărului total de izomeri ai alcanilor. alchene și alchine. Graficele moleculare fac posibilă reducerea problemelor legate de codificare, nomenclatură și caracteristici structurale (ramificare, ciclicitate etc.) ale moleculelor diferiților compuși la analiza și compararea caracteristicilor și proprietăților pur matematice ale graficelor moleculare și ale arborilor acestora, precum și matricele lor corespunzătoare. Pentru a identifica numărul de corelații dintre structura moleculelor și proprietățile fizico-chimice (inclusiv farmacologice) ale compușilor, au fost dezvoltate peste 20 de așa-zise. Indici topologici ai moleculelor (Wiener, Balaban, Hosoya, Plata, Randich etc.), care sunt determinați folosind matrici și caracteristici numerice ale arborilor moleculari. De exemplu, indicele Wiener W = (m3 + m)/6, unde m este numărul de vârfuri corespunzător atomilor de C, se corelează cu volumele moleculare și refracțiile, entalpiile de formare, vâscozitatea, tensiunea superficială, constantele cromatografice ale compușilor, octanul numărul de hidrocarburi și chiar physiol . activitatea drogurilor. Parametri importanți ai graficelor moleculare utilizați pentru determinarea formelor tautomerice ale unei substanțe date și reactivitatea acestora, precum și în clasificarea aminoacizilor, acizilor nucleici, carbohidraților și a altor compuși naturali complecși, sunt capacitatea informațională medie și totală (H). Analiza graficelor moleculare ale polimerilor, ale căror vârfuri corespund unităților monomerice, iar marginile corespund legăturilor chimice dintre ei, face posibilă explicarea, de exemplu, a efectelor volumului exclus care conduc la calități. modificări ale proprietăților prezise ale polimerilor. Folosind Teoria grafurilor și principiile inteligenței artificiale, a fost dezvoltat software pentru sistemele de regăsire a informațiilor din chimie, precum și sisteme automate pentru identificarea structurilor moleculare și planificarea rațională a sintezei organice. Pentru implementarea practică pe calculator a operațiilor de selectare a căilor chimice raționale. transformările bazate pe principiile retrosintetice și sintonice folosesc grafice de căutare ramificate pe mai multe niveluri pentru opțiunile de soluție, ale căror vârfuri corespund graficelor moleculare ale reactivilor și produselor, iar arcurile descriu transformări.
Pentru rezolvarea problemelor multidimensionale de analiză și optimizare a sistemelor tehnologice chimice (CTS) se folosesc următoarele grafice tehnologice chimice: grafice de flux, flux de informații, grafice de semnal și fiabilitate. Pentru studii în chimie. Fizica perturbațiilor în sistemele formate dintr-un număr mare de particule folosește așa-numita. Diagramele Feynman sunt grafice, ale căror vârfuri corespund interacțiunilor elementare ale particulelor fizice, marginile căilor lor după ciocniri. În special, aceste grafice fac posibilă studierea mecanismelor reacțiilor oscilatorii și determinarea stabilității sistemelor de reacție. Graficele fluxului de materiale afișează modificări ale consumului de substanțe în CTS. Graficele fluxului termic afișează bilanțele de căldură în CTS; vârfurile graficelor corespund dispozitivelor în care se modifică consumul de căldură al fluxurilor fizice și, în plus, surselor și absorbatoarelor de energie termică ale sistemului; arcurile corespund fluxurilor de căldură fizice și fictive (conversie fizico-chimică a energiei în dispozitive), iar greutățile arcurilor sunt egale cu entalpiile fluxurilor. Graficele de materiale și termice sunt utilizate pentru a compila programe pentru dezvoltarea automată a algoritmilor de rezolvare a sistemelor de ecuații pentru bilanțele materiale și termice ale sistemelor chimice complexe. Graficele fluxului de informații afișează structura logică a informațiilor a sistemelor de ecuații matematice. modele XTS; sunt folosite pentru a dezvolta algoritmi optimi pentru calcularea acestor sisteme. Un graf de informații bipartit este un graf nedirecționat sau direcționat ale cărui vârfuri corespund respectiv. ecuațiile fl -f6 și variabilele q1 – V, iar ramurile reflectă relația lor. Graficul de informații – un digraf care ilustrează ordinea rezolvării ecuațiilor; vârfurile graficului corespund acestor ecuații, surse și receptori de informații XTS, iar ramurile corespund informațiilor. variabile. Graficele semnalelor corespund sistemelor liniare de ecuații ale modelelor matematice ale proceselor și sistemelor tehnologice chimice. Graficele de fiabilitate sunt utilizate pentru a calcula diferiți indicatori de fiabilitate X.
Referințe:
1.Berge K., T. g şi aplicarea ei, traducere din franceză, M., 1962;
2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, trad. din engleză, ed. a II-a, M., 1963;
3.Ope O., Grafice și aplicarea lor, trad. din engleză, M., 1965;
4. Belykh O.V., Belyaev E.V., Posibilități de aplicare a sociologiei în sociologie, în: Omul și societatea, voi. 1, [L.], 1966;
5. Metode cantitative în cercetarea sociologică, M., 1966; Belyaev E.V., Probleme de măsurători sociologice, „VF”, 1967, nr. 7; Bavelas. Modele de comunicare în grupuri orientate spre sarcini, în carte. Lerner D., Lass well H., Political sciences, Stanford, 1951;
Rezumat la subiectul matematică superioară pe tema:
Aplicarea teoriei grafurilor în chimie
Realizat de un elev din grupa NH-202
Moscova 2011
Graficele sunt domeniul matematicii finite care studiază structurile discrete; folosit pentru rezolvarea diverselor probleme teoretice și aplicative.
niste Noțiuni de bază. Un grafic este o colecție de puncte (vârfurile) și o colecție de perechi ale acestor puncte (nu neapărat toate) conectate prin linii (Fig. 1, a). Dacă liniile dintr-un grafic sunt orientate (adică săgețile indică direcția de conectare a vârfurilor), ele se numesc arce, sau ramuri; dacă neorientate, - margini. În consecință, un grafic care conține doar arce se numește grafic direcționat sau digraf; numai marginea neorientată; arcuri și nervuri – mixte. Un grafic care are mai multe muchii se numește multigraf; un grafic care conține doar muchii aparținând la două dintre submulțimile (părți) sale disjunse este bipartit; sunt ponderate arcurile (muchiile) și (sau) vârfurile care corespund anumitor greutăți sau valori numerice ale oricăror parametri. O cale într-un grafic este o succesiune alternantă de vârfuri și arce în care niciunul dintre vârfuri nu este repetat (de exemplu, a, b în Fig. 1,a); contur - o cale închisă în care primul și ultimul vârf coincid (de exemplu, f, h); buclă - un arc (margine) care începe și se termină la același vârf. O cale de grafic este o succesiune de muchii în care niciunul dintre vârfuri nu este repetat (de exemplu, c, d, e); ciclu - un lanț închis în care vârfurile sale inițiale și finale coincid. Un graf se numește conectat dacă orice pereche de vârfuri este conectată printr-un lanț sau o cale; în caz contrar, graficul se numește deconectat.
Un arbore este un grafic nedirecționat conectat care nu conține cicluri sau contururi (Fig. 1, b). Subgraful de acoperire al unui graf este un subset al acestuia care conține toate vârfurile și numai anumite muchii. Arborele de întindere al unui grafic este subgraful său de întindere, care este un arbore. Graficele se numesc izomorfe dacă există o corespondență unu-la-unu între mulțimile vârfurilor și muchiilor lor (arce).
Pentru rezolvarea problemelor de teorie a grafurilor și a aplicațiilor acesteia, graficele sunt reprezentate folosind matrici (adiacență, incidență, pe două rânduri etc.), precum și cu ajutorul unor matrici speciale. caracteristici numerice. De exemplu, în matricea de adiacență (Fig. 1c), rândurile și coloanele corespund numerelor vârfurilor graficului, iar elementele acestuia iau valorile 0 și 1 (respectiv, absența și prezența unui arc între o pereche dată de vârfuri); în matricea de incidență (Fig. 1d), rândurile corespund numerelor vârfurilor, coloanele corespund numerelor arcelor, iar elementele iau valorile 0, + 1 și - 1 (respectiv, absența , prezența unui arc care intră și iese din vârf). Cele mai comune caracteristici numerice: numărul de vârfuri (m), numărul de arce sau muchii (n), numărul ciclomatic sau rangul graficului (n - m + k, unde k este numărul de subgrafe conectate în un grafic deconectat, de exemplu, pentru graficul din Fig. 1, rangul b va fi: 10-6+ 1 =5).
Aplicarea teoriei grafurilor se bazează pe construirea și analiza diferitelor clase de grafuri chimice și chimico-tehnologice, care sunt numite și modele topologice, i.e. modele care iau în considerare doar natura legăturilor dintre vârfuri. Arcele (muchiile) și vârfurile acestor grafice prezintă concepte chimice și chimico-tehnologice, fenomene, procese sau obiecte și, în consecință, relații calitative și cantitative sau anumite relații între ele.
Orez. 1. Ilustrarea unor concepte de bază: a-graf mixt; arborele b-spanning (arce solide a, h, d, f, h) și un anumit subgraf (arce întrerupte c, e, g, k, l) ale digrafului; c, r-matrice resp. adiacența și incidența unui digraf.
Probleme teoretice. Graficele chimice fac posibilă prezicerea transformărilor chimice, explicarea esenței și sistematizarea unor concepte de bază ale chimiei: structură, configurație, conformații, interacțiuni mecanice cuantice și statistico-mecanice ale moleculelor, izomerie etc. Graficele chimice includ grafice moleculare, bipartite și de semnal. a ecuațiilor reacțiilor cinetice.
Graficele moleculare, utilizate în stereochimie și topologia structurală, chimia clusterelor, polimerilor etc., sunt grafice nedirecționate care prezintă structura moleculelor (Fig. 2). Vârfurile și muchiile acestor grafice corespund, respectiv, atomilor și legăturilor chimice dintre ele.
Orez. 2. Grafice moleculare și arbori: a, b - multigrafii, respectiv. etilenă și formaldehidă; ei spun izomerii pentanului (arborele 4, 5 sunt izomorfi cu arborele 2).
În stereochimia substanțelor organice, arborii moleculari sunt cel mai des utilizați - arbori care se întind de grafice moleculare, care conțin numai toate vârfurile corespunzătoare atomilor de C (Fig. 2, a și b). Compilarea seturi de arbori moleculari și stabilirea izomorfismului acestora face posibilă determinarea structurilor moleculare și găsirea numărului total de izomeri ai alcanilor, alchenelor și alchinelor (Fig. 2, c).
Graficele moleculare fac posibilă reducerea problemelor legate de codificare, nomenclatură și caracteristici structurale (ramificare, ciclicitate etc.) ale moleculelor diferiților compuși la analiza și compararea caracteristicilor și proprietăților pur matematice ale graficelor moleculare și ale arborilor acestora, precum și matricele lor corespunzătoare. Pentru a identifica corelațiile cantitative dintre structura moleculelor și proprietățile fizico-chimice (inclusiv farmacologice) ale compușilor, au fost dezvoltate peste 20 de mii de nume de indici topologici ai moleculelor (Wiener, Balaban, Hosoya, Plat, Randic etc.), care sunt determinate folosind matrici și caracteristici numerice ale arborilor moleculari. De exemplu, indicele Wiener W = (m 3 + m)/6, unde m este numărul de vârfuri corespunzător atomilor de C, se corelează cu volumele moleculare și refracțiile, entalpiile de formare, vâscozitatea, tensiunea superficială, constantele cromatografice ale compușilor, cifrele octanice ale hidrocarburilor și chiar activitatea fiziologică a medicamentelor.
Parametri importanți ai graficelor moleculare utilizați pentru determinarea formelor tautomerice ale unei substanțe date și reactivitatea acestora, precum și în clasificarea aminoacizilor, acizilor nucleici, carbohidraților și a altor compuși naturali complecși, sunt capacitățile informaționale medii și totale (H). Parametrul este calculat folosind formula de entropie a informațiilor Shannon: , unde p t este probabilitatea ca vârfurile m ale graficului să aparțină tipului i, sau clasei de echivalență, k; i = , Parametru. Studiul structurilor moleculare precum clusterele anorganice sau benzile Möbius se rezumă la stabilirea izomorfismului graficelor moleculare corespunzătoare prin plasarea lor (înglobarea) în poliedre complexe (de exemplu, poliedre în cazul clusterelor) sau în unele speciale. suprafețe multidimensionale (de exemplu, suprafețe Riemann). Analiza graficelor moleculare ale polimerilor, ale căror vârfuri corespund unităților monomerice, iar marginile legăturilor chimice dintre ele, face posibilă explicarea, de exemplu, a efectelor volumului exclus, ducând la modificări calitative ale proprietăților prezise ale polimerilor. .
Orez. 3. Grafice de reacție: a-bipartite; b-nivelul de semnal al cineticii; r1, g2-r-tion; a 1 -a 6 -reactivi; k-rate constante p-tsny; variabilă transformată Laplace complexă s.
Folosind teoria grafurilor și principiile inteligenței artificiale, software-ul a fost dezvoltat pentru sisteme de regăsire a informațiilor din chimie, precum și sisteme automate pentru identificarea structurilor moleculare și planificarea rațională a sintezei organice. Pentru implementarea practică pe un computer a operațiunilor de selectare a căilor raționale ale transformărilor chimice bazate pe principiile retrosintetice și sintonice, sunt utilizate grafice de căutare ramificate pe mai multe niveluri pentru opțiuni de soluție, ale căror vârfuri corespund graficelor moleculare ale reactivilor și produselor, iar arcele înfăţişează transformările substanţelor.
Orez. 4. Sistem chimico-tehnologic cu un singur circuit și grafice corespunzătoare: a-schema structurală; b, grafice de flux c-material, respectiv. prin debitul masic total și debitul componentului A; r - graficul fluxului termic; d-fragment al sistemului de ecuaţii (f 1 - f 6) al bilanţului material, obţinut din analiza graficelor din Fig. 4, b și c; digraf informativ e-bipartit; g-grafic de informații, I-mixer; II-reactor; III-coloana de distilare; IV-frigider; I 1 -I 8 -tehn. cursuri; q-debit masic; H este entalpia curgerii; i. s și i*, s* - resp. surse și chiuvete reale și fictive de materiale și fluxuri de căldură; c-concentrarea reactivului; V este volumul reactorului.
Reprezentările matriceale ale graficelor moleculare ale diferiților compuși sunt echivalente (după transformarea elementelor matricei corespunzătoare) cu metodele matriceale ale chimiei cuantice. Prin urmare, teoria grafurilor este utilizată atunci când se efectuează calcule chimice cuantice complexe: pentru a determina numărul, proprietățile și energiile orbitalilor moleculari, prezicerea reactivității polienelor alternante și nealternante conjugate, identificarea proprietăților aromatice și antiaromatice ale substanțelor etc.
Pentru a studia perturbațiile în sistemele formate dintr-un număr mare de particule din fizica chimică, se folosesc așa-numitele diagrame Feynman - grafice ale căror vârfuri corespund interacțiunilor elementare ale particulelor fizice, marginile traseelor lor după ciocniri. În special, aceste grafice fac posibilă studierea mecanismelor reacțiilor oscilatorii și determinarea stabilității sistemelor de reacție.
Pentru a selecta căi raționale pentru transformarea moleculelor de reactiv pentru un set dat de interacțiuni cunoscute, se folosesc grafice de reacție bipartite (vârfurile corespund moleculelor și aceste reacții, arcurile corespund interacțiunilor moleculelor din reacție; Fig. 3,a). ). Astfel de grafice fac posibilă dezvoltarea algoritmilor interactivi pentru selectarea căilor optime de transformări chimice care necesită cel mai mic număr de reacții intermediare, numărul minim de reactivi din lista celor acceptabili sau obține cel mai mare randament de produse.
Graficele de semnal ale ecuațiilor cinetice ale reacțiilor afișează sisteme de ecuații cinetice prezentate sub formă de operator algebric (Fig. 3b). Vârfurile graficelor corespund așa-numitelor variabile informaționale, sau semnalelor, sub formă de concentrații de reactivi, arce - relațiilor de semnale, iar greutățile arcelor sunt determinate de constante cinetice. Astfel de grafice sunt utilizate în studierea mecanismelor și cineticii reacțiilor catalitice complexe, a echilibrelor de fază complexe în formarea compușilor complecși, precum și pentru calcularea parametrilor proprietăților aditive ale soluțiilor.
Probleme aplicate. Pentru rezolvarea problemelor multidimensionale de analiză și optimizare a sistemelor chimico-tehnologice (CTS) se folosesc următoarele grafice chimico-tehnologice (Fig. 4): grafice de flux, de informare-flux, de semnal și de fiabilitate. Graficele de flux, care sunt digrafe ponderate, includ parametri parametrici, materiale în ceea ce privește debitele totale de masă ale fluxurilor fizice și debitele de masă ale unor componente sau elemente chimice, precum și grafice termice. Graficele enumerate corespund transformărilor fizice și chimice ale substanțelor și energiei într-un sistem chimic dat.
Graficele parametrice de flux afișează transformarea parametrilor (debitele de masă, etc.) a fluxurilor fizice de către elementele CTS; vârfurile graficelor corespund modelelor matematice ale dispozitivelor, precum și surselor și chiuvetelor fluxurilor specificate, iar arcele corespund fluxurilor în sine, iar greutățile arcurilor sunt egale cu numărul de parametri ai fluxul corespunzător. Graficele parametrice sunt folosite pentru a dezvolta algoritmi pentru analiza modurilor tehnologice ale sistemelor chimice cu mai multe circuite. Astfel de algoritmi stabilesc succesiunea sistemelor de calcul de ecuații ale modelelor matematice ale dispozitivelor individuale ale oricărui sistem pentru a determina parametrii fluxurilor sale de ieșire cu valori cunoscute ale fluxurilor variabile de intrare.
Graficele fluxului de materiale afișează modificări ale consumului de substanțe în substanțe chimice. Vârfurile graficelor corespund dispozitivelor în care se transformă debitele masice totale ale fluxurilor fizice și debitele masice ale unor componente sau elemente chimice, precum și sursele și chiuvetele de substanțe ale fluxurilor sau ale acestor componente; În consecință, arcele graficelor corespund fluxurilor fizice sau surselor și chiuvetelor fizice și fictive (transformări chimice ale substanțelor în aparate) ale oricăror componente, iar greutățile arcurilor sunt egale cu debitele de masă ale ambelor tipuri. Graficele fluxului termic afișează bilanțele de căldură în CTS; vârfurile graficelor corespund dispozitivelor în care se modifică consumul de căldură al fluxurilor fizice și, în plus, surselor și absorbatoarelor de energie termică ale sistemului; arcurile corespund fluxurilor de căldură fizice și fictive (conversie fizico-chimică a energiei în dispozitive), iar greutățile arcurilor sunt egale cu entalpiile fluxurilor. Graficele de materiale și termice sunt utilizate pentru a compila programe pentru dezvoltarea automată a algoritmilor de rezolvare a sistemelor de ecuații pentru bilanțele materiale și termice ale sistemelor chimice complexe.
Graficele de stoc de informații afișează structura logico-informațională a sistemelor de ecuații ale modelelor matematice ale CTS; sunt folosite pentru a dezvolta algoritmi optimi pentru calcularea acestor sisteme. Un graf informațional bipartit (Fig. 4, e) este un graf nedirecționat sau orientat, ale cărui vârfuri corespund, respectiv, ecuațiilor f l - f 6 și variabilelor q 1 - V, iar ramurile reflectă relația lor. Graficul informațional (Fig. 4, g) - un digraf care prezintă ordinea rezolvării ecuațiilor; vârfurile graficului corespund acestor ecuații, surse și receptori de informații XTS, iar ramurile corespund unor variabile de informații.
Graficele semnalelor corespund sistemelor liniare de ecuații ale modelelor matematice ale proceselor și sistemelor tehnologice chimice. Vârfurile graficelor corespund semnalelor (de exemplu, temperatură), iar ramurile corespund conexiunilor dintre ele. Astfel de grafice sunt utilizate pentru a analiza modurile statice și dinamice ale proceselor multiparametrice și ale sistemelor chimice, precum și indicatorii unui număr dintre cele mai importante proprietăți ale acestora (stabilitate, sensibilitate, controlabilitate).
Graficele de fiabilitate sunt utilizate pentru a calcula diferiți indicatori ai fiabilității echipamentelor chimice. Dintre numeroasele grupuri ale acestor grafice (de exemplu, parametrice, logico-funcționale), așa-numiții arbori de defecte sunt deosebit de importanți. Fiecare astfel de arbore este un digraf ponderat care afișează interrelația dintre multe defecțiuni simple ale proceselor individuale și ale dispozitivelor CTS, care duc la multe defecțiuni secundare și la eșecul rezultat al sistemului în ansamblu.
Pentru a crea complexe de programe pentru sinteza automată a producției optime extrem de fiabile (inclusiv economisirea resurselor), împreună cu principiile inteligenței artificiale, semantice orientate sau semantice, sunt utilizate grafice ale opțiunilor de soluție CTS. Aceste grafice, care într-un anumit caz sunt arbori, descriu proceduri pentru generarea unui set de scheme CTS alternative raționale (de exemplu, 14 posibile atunci când se separă un amestec de cinci componente de produse țintă prin rectificare) și proceduri pentru selecția ordonată dintre acestea a o schemă care este optimă după un anumit criteriu de eficienţă a sistemului.
etc.................
INSTITUȚIA DE ÎNVĂȚĂMÂNT AUTONOM MUNICIPAL SCOALA GIME Nr.2
Pregătit
Legkokonets Vladislav, elev al clasei 10A
Aplicarea practică a teoriei grafurilor
Supraveghetor
L.I. Noskova, profesor de matematică
Art. Bryukhovetskaya
2011
1.Introducere…………………………………………………………………………………………….………….3
2. Istoria apariției teoriei grafurilor…………………………………………………….………..4
3. Definiții și teoreme de bază ale teoriei grafurilor……………………………………6
4. Probleme rezolvate cu ajutorul graficelor………………………………………..……………..8
4.1 Probleme celebre………………………………………….……………...8
4.2 Câteva probleme interesante…………………………………………….…..9
5. Aplicarea graficelor în diverse domenii ale vieții oamenilor………………..11
6. Rezolvarea problemelor…………………………………………………………………………..12
7. Concluzie……………………………………………………………………………………………………….13
8. Lista referințelor………….…………………………………………………………………………14
9.Anexa………………………………………………………………………………….…………15
Introducere
Născută din rezolvarea de puzzle-uri și jocuri distractive, teoria graficelor a devenit acum un instrument simplu, accesibil și puternic pentru rezolvarea întrebărilor legate de o gamă largă de probleme. Graficele sunt literalmente omniprezente. Sub formă de grafice, puteți, de exemplu, interpreta hărți rutiere și circuite electrice, hărți geografice și molecule de compuși chimici, conexiuni între oameni și grupuri de oameni. În ultimele patru decenii, teoria grafurilor a devenit una dintre ramurile cu cea mai rapidă dezvoltare a matematicii. Acest lucru este determinat de cerințele unui domeniu de aplicații în expansiune rapidă. Este utilizat în proiectarea circuitelor integrate și a circuitelor de control, în studiul automatelor, circuitelor logice, schemelor bloc de programe, în economie și statistică, chimie și biologie, în teoria programării. De aceea relevanţă Subiectul este determinat, pe de o parte, de popularitatea graficelor și a metodelor de cercetare aferente și, pe de altă parte, de un sistem holistic nedezvoltat pentru implementarea acestuia.
Rezolvarea multor probleme din viață necesită calcule lungi, iar uneori nici aceste calcule nu aduc succes. Acesta este ce problema de cercetare. Se pune întrebarea: este posibil să găsim o soluție simplă, rațională, scurtă și elegantă pentru a le rezolva. Rezolvarea problemelor este mai ușoară dacă folosiți grafice? Aceasta a determinat subiectul cercetării mele: „Aplicarea practică a teoriei grafurilor”
Scop Cercetarea a fost de a folosi grafice pentru a învăța cum să rezolvi rapid probleme practice.
Ipoteza cercetării. Metoda graficului este foarte importantă și utilizată pe scară largă în diverse domenii ale științei și ale activității umane.
Obiectivele cercetării:
1. Studiați literatura și resursele de pe Internet pe această temă.
2.Verificați eficacitatea metodei grafice în rezolvarea problemelor practice.
3. Trageți o concluzie.
Semnificația practică a studiului este că rezultatele vor stârni, fără îndoială, interesul multor oameni. Nu a încercat vreunul dintre voi să vă construiască arborele genealogic? Cum să faci asta corect? Șeful unei întreprinderi de transport probabil trebuie să rezolve problema utilizării mai profitabile a transportului la transportul mărfurilor de la o destinație la mai multe localități. Fiecare școlar s-a confruntat cu probleme logice de transfuzie. Se dovedește că pot fi rezolvate cu ușurință folosind grafice.
În lucrare sunt utilizate următoarele metode: observare, căutare, selecție, analiză.
Istoria teoriei grafurilor
Fondatorul teoriei grafurilor este considerat a fi matematicianul Leonhard Euler (1707-1783). Istoria acestei teorii poate fi urmărită prin corespondența marelui om de știință. Iată o traducere a textului latin, care este preluată din scrisoarea lui Euler către matematicianul și inginerul italian Marinoni, trimisă de la Sankt Petersburg la 13 martie 1736.
„Odată mi s-a dat o problemă cu o insulă situată în orașul Königsberg și înconjurată de un râu cu șapte poduri peste ea.
[Anexa Fig.1]Întrebarea este dacă cineva le poate ocoli continuu, trecând o singură dată peste fiecare pod. Și apoi am fost informat că nimeni nu a fost încă în stare să facă asta, dar nimeni nu a dovedit că este imposibil. Această întrebare, deși banală, mi s-a părut totuși demnă de atenție prin faptul că nici geometria, nici algebra, nici arta combinatorie nu sunt suficiente pentru a o rezolva. După multă gândire, am găsit o regulă ușoară, bazată pe o dovadă complet convingătoare, cu ajutorul căreia este posibil în toate problemele de acest gen să se stabilească imediat dacă un astfel de ocol se poate face prin orice număr și orice număr de poduri amplasate. sau nu. Podurile Koenigsberg sunt amplasate în așa fel încât să poată fi reprezentate în figura următoare [Anexa Fig.2], în care A denotă o insulă, iar B, C și D - părți ale continentului separate între ele prin ramuri ale râului
Referitor la metoda pe care a descoperit-o pentru a rezolva probleme de acest gen, Euler a scris:
„Această soluție, prin natura ei, se pare că are puțin de-a face cu matematica și nu înțeleg de ce ar trebui să se aștepte la această soluție de la un matematician mai degrabă decât de la orice altă persoană, deoarece această decizie este susținută doar de raționament și nu există Trebuie să implicăm pentru a găsi această soluție, există legi inerente în matematică. Deci, nu știu cum se dovedește că întrebările care au foarte puțin de-a face cu matematica sunt mai probabil să fie rezolvate de matematicieni decât de alții.
Deci, este posibil să ocoliți podurile Königsberg trecând o singură dată peste fiecare dintre aceste poduri? Pentru a găsi răspunsul, să continuăm scrisoarea lui Euler către Marinoni:
„Întrebarea este de a determina dacă este posibil să ocoliți toate aceste șapte poduri, trecând prin fiecare o singură dată, sau nu. Regula mea duce la următoarea soluție la această întrebare. În primul rând, trebuie să vă uitați la câte zone există. sunt separate de apă - astfel de , care nu au altă tranziție de la unul la altul, cu excepția unui pod În acest exemplu, există patru astfel de secțiuni - A, B, C, D. În continuare, trebuie să distingeți dacă numărul. de poduri care duc la aceste secțiuni individuale este par sau impar. Deci, în cazul nostru, cinci poduri duc la secțiunea A și trei poduri fiecare către restul, adică numărul de poduri care duc la secțiuni individuale este impar și doar acest lucru este suficient. Pentru a rezolva problema, când aceasta este determinată, aplicăm următoarea regulă: dacă numărul de poduri care duc la fiecare secțiune individuală ar fi posibil, atunci ocolirea în cauză ar fi posibilă. acest ocol de la orice secțiune Dacă două dintre aceste numere ar fi impare, deoarece doar unul nu poate fi impar, atunci chiar și atunci tranziția ar putea fi finalizată, dar numai începutul ocolirii trebuie luat de la unul. din acele două tronsoane la care duce un număr impar de poduri. Dacă, în cele din urmă, au existat mai mult de două secțiuni la care duc un număr impar de poduri, atunci o astfel de mișcare este în general imposibilă... dacă s-ar putea aduce aici alte probleme, mai grave, această metodă ar putea fi de beneficiu și mai mare și ar trebui a nu fi neglijat.” .
Definiții și teoreme de bază ale teoriei grafurilor
Teoria grafurilor este o disciplină matematică creată prin eforturile matematicienilor, prin urmare prezentarea sa include definițiile stricte necesare. Deci, să trecem la o introducere organizată a conceptelor de bază ale acestei teorii.
Definiția 1. Un grafic este o colecție de un număr finit de puncte, numite vârfuri ale graficului, și linii în perechi care leagă unele dintre aceste vârfuri, numite muchii sau arce ale graficului.
Această definiție poate fi formulată diferit: un grafic este un set nevid de puncte (vârfurile) și segmente (margini), ambele capete aparținând unui set dat de puncte
În cele ce urmează, vom desemna vârfurile graficului cu litere latine A, B, C, D. Uneori, graficul ca întreg va fi notat cu o literă majusculă.
Definiția 2. Vârfurile unui graf care nu aparțin niciunei muchii se numesc izolate.
Definiția 3. Un grafic format numai din vârfuri izolate se numește nul - numara .
Notație: O "– un grafic cu vârfuri care nu are muchii
Definiția 4. Un grafic în care fiecare pereche de vârfuri este conectată printr-o muchie se numește complet.
Denumire: U" – un grafic format din n vârfuri și muchii care conectează toate perechile posibile ale acestor vârfuri. Un astfel de grafic poate fi reprezentat ca un n-gon în care sunt desenate toate diagonalele
Definiția 5. Gradul unui vârf este numărul de muchii căruia îi aparține vârful.
Definiția 6. Un grafic ale cărui grade ale tuturor k vârfuri sunt aceleași se numește grafic de grad omogen .
Definiția 7. Complementul unui grafic dat este un grafic format din toate muchiile și capetele acestora care trebuie adăugat la graficul original pentru a obține un grafic complet.
Definiția 8. Un grafic care poate fi reprezentat pe un plan în așa fel încât marginile sale să se intersecteze doar la vârfuri se numește plan.
Definiția 9. Un poligon al unui graf plan care nu conține vârfuri sau muchii ale grafului se numește fața sa.
Conceptele de graf plan și față de graf sunt folosite la rezolvarea problemelor privind colorarea „corectă” a diferitelor hărți.
Definiția 10. O cale de la A la X este o succesiune de muchii care duc de la A la X astfel încât fiecare două muchii adiacente să aibă un vârf comun și nicio muchie nu apare de mai multe ori.
Definiția 11. Un ciclu este o cale în care punctele de început și de sfârșit coincid.
Definiția 12. Un ciclu simplu este un ciclu care nu trece prin niciunul dintre vârfurile graficului de mai multe ori.
Definiția 13. Lungimea traseului , pus pe o buclă , se numește numărul de muchii ale acestei căi.
Definiția 14. Două vârfuri A și B dintr-un graf se numesc conectate (deconectate) dacă există (nu există) o cale care duce de la A la B.
Definiția 15. Un graf se numește conexat dacă fiecare două vârfuri ale sale sunt conectate; dacă graficul conține cel puțin o pereche de vârfuri deconectate, atunci graficul se numește deconectat.
Definiția 16. Un arbore este un grafic conectat care nu conține cicluri.
Un model tridimensional al unui grafic arbore este, de exemplu, un copac real cu coroana sa complicat ramificată; râul și afluenții săi formează, de asemenea, un copac, dar deja plat - la suprafața pământului.
Definiția 17. Un grafic deconectat format în întregime din copaci se numește pădure.
Definiția 18. Un arbore în care toate n vârfuri sunt numerotate de la 1 la n se numește arbore cu vârfuri renumerotate.
Deci, am examinat definițiile de bază ale teoriei grafurilor, fără de care ar fi imposibil să se demonstreze teoreme și, în consecință, să se rezolve probleme.
Probleme rezolvate cu ajutorul graficelor
Probleme celebre
Problemă cu vânzătorul ambulant
Problema vânzătorului ambulant este una dintre problemele celebre din teoria combinatoriei. A fost prezentat în 1934, iar cei mai buni matematicieni și-au rupt dinții pe el.
Declarația problemei este următoarea.
Un vânzător ambulant (comerciant rătăcitor) trebuie să părăsească primul oraș, să viziteze orașele 2,1,3..n o dată într-o ordine necunoscută și să se întoarcă în primul oraș. Se cunosc distantele dintre orase. În ce ordine ar trebui să ocoliți orașele, astfel încât drumul închis (turul) al unui vânzător ambulant să fie cel mai scurt?
Metodă de rezolvare a problemei vânzătorului ambulant
Algoritm lacom
„du-te în cel mai apropiat oraș (în care nu ai intrat încă)”.
Acest algoritm se numește „lacom” pentru că în ultimii pași trebuie să plătești grav pentru lăcomie.
Luați în considerare, de exemplu, rețeaua din figură [Anexa Fig.3], reprezentând un romb îngust. Lăsați un vânzător ambulant să înceapă din orașul 1. Algoritmul „du-te în orașul cel mai apropiat” îl va duce în orașul 2, apoi 3, apoi 4; la ultimul pas va trebui să plătești pentru lăcomia ta, revenind de-a lungul diagonalei lungi a diamantului. Rezultatul nu va fi cel mai scurt, ci cel mai lung turneu.
Problemă cu podurile Königsberg.
Problema este formulată după cum urmează.
Orașul Koenigsberg este situat pe malul râului Pregel și pe două insule. Diferitele părți ale orașului erau conectate prin șapte poduri. Duminica, orășenii făceau plimbări prin oraș. Intrebare: este posibil sa faci o plimbare in asa fel incat, la iesirea din casa, sa te intorci mergand exact o data peste fiecare pod?
Podurile peste râul Pregel sunt situate ca în imagine[Anexa Fig.1].
Luați în considerare graficul corespunzător diagramei de punte [Anexa Fig. 2].
Pentru a răspunde la întrebarea problemei, este suficient să aflăm dacă graficul este eulerian. (Un număr par de punți trebuie să se extindă de la cel puțin un vârf). Nu poți să te plimbi prin oraș și să traversezi toate podurile o dată și să te întorci.
Mai multe sarcini interesante
1. „Rute”.
Problema 1
După cum vă amintiți, vânătorul de suflete moarte Cicikov a vizitat proprietarii celebri o dată fiecare. I-a vizitat în următoarea ordine: Manilov, Korobochka, Nozdryov, Sobakevici, Plyushkin, Tentetnikov, generalul Betrischev, Petukh, Konstanzholgo, colonelul Koshkarev. S-a găsit o diagramă pe care Cicikov a schițat pozițiile relative ale moșiilor și drumurile de țară care le leagă. Stabiliți ce moșie îi aparține cui, dacă Cicikov nu a condus niciunul dintre drumuri de mai multe ori [Anexa Fig. 4].
Soluţie:
Harta rutieră arată că Cicikov și-a început călătoria de la moșia E și s-a încheiat cu moșia O. Remarcăm că doar două drumuri duc la moșiile B și C, așa că Cicikov a trebuit să circule pe aceste drumuri. Să le marchem cu o linie îndrăzneață. Au fost identificate tronsoane ale traseului care trece prin A: AC si AB. Cicikov nu a călătorit pe drumurile AE, AK și AM. Să le tăiem. Să marchem cu o linie îndrăzneață ED; Să tăiem DK. Să tăiem MO și MN; Să marchem MF cu o linie îndrăzneață; bifați FO; Să marchem FH, NK și KO cu o linie îndrăzneață. Să găsim singura rută posibilă în această condiție. Și obținem: proprietatea E - aparține lui Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrischev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Anexa Fig.5].
Problema 2
Figura prezintă o hartă a zonei [Anexa Fig. 6].
Vă puteți deplasa doar în direcția săgeților. Puteți vizita fiecare punct nu mai mult de o dată. În câte moduri poți ajunge de la punctul 1 la punctul 9? Care traseu este cel mai scurt și care este cel mai lung.
Soluţie:
„Stratificăm” secvenţial circuitul într-un arbore, pornind de la vârful 1 [Anexa Fig.7]. Să luăm un copac. Numărul de moduri posibile de a ajunge de la 1 la 9 este egal cu numărul de vârfuri „atârnate” ale copacului (există 14 dintre ele). Evident că cea mai scurtă cale este 1-5-9; cel mai lung este 1-2-3-6-5-7-8-9.
2 „Grupuri, întâlniri”
Problema 1
Participanții la festivalul de muzică, întâlnindu-se, au schimbat plicuri cu adrese. Demonstrați că:
a) au fost predate un număr par de plicuri;
b) numărul de participanți care au schimbat plicurile de un număr impar de ori este par.
Soluție: Fie participanții la festival A 1, A 2, A 3. . . , Și n sunt vârfurile graficului, iar muchiile conectează perechi de vârfuri reprezentând băieții care fac schimb de plicuri [Anexa Fig.8]
Soluţie:
a) gradul fiecărui vârf A i arată numărul de plicuri pe care participantul A i le-a dat prietenilor săi. Numărul total de plicuri transmise N este egal cu suma gradelor tuturor vârfurilor graficului N = grad. Un pas de 1 +. A 2 + + . . . + pas. A n -1 + grad. Și n, N =2p, unde p este numărul de muchii ale graficului, adică. N – chiar. În consecință, au fost predate un număr par de plicuri;
b) în egalitatea N = grad. Un pas de 1 +. A 2 + + . . . + pas. A n -1 + grad. Și n, suma termenilor impari trebuie să fie pară, iar acest lucru poate fi cazul numai dacă numărul de termeni impari este par. Aceasta înseamnă că numărul de participanți care au schimbat plicuri de un număr impar de ori este par.
Problema 2
Într-o zi, Andrei, Boris, Volodya, Dasha și Galya au fost de acord să meargă seara la cinema. Au decis să coordoneze alegerea cinematografului și a spectacolului la telefon. De asemenea, s-a hotărât că dacă nu se va putea contacta pe cineva telefonic, atunci excursia la cinema să fie anulată. Seara, nu toată lumea s-a adunat la cinema și, prin urmare, vizita la film a fost anulată. A doua zi au început să afle cine a sunat pe cine. S-a dovedit că Andrei i-a numit pe Boris și Volodya, Volodya i-a numit pe Boris și Dasha, Boris i-a zis pe Andrey și Dasha, Dasha i-a zis pe Andrey și Volodya, iar Galya i-a numit pe Andrey, Volodya și Boris. Cine nu a putut să intre la telefon și, prin urmare, nu a venit la întâlnire?
Soluţie:
Să desenăm cinci puncte și să le etichetăm cu literele A, B, C, D, D. Acestea sunt primele litere ale numelor. Să conectăm punctele care corespund numelor băieților care au sunat.
[Anexa Fig.9]
Din imagine este clar că fiecare dintre băieți - Andrey, Boris și Volodya - i-a telefonat pe toți ceilalți. De aceea, tipii ăștia au venit la cinema. Dar Galya și Dasha nu au reușit să stea la telefon între ele (punctele G și E nu sunt conectate printr-un segment de linie) și, prin urmare, în conformitate cu acordul, nu au venit la cinema.
Aplicarea graficelor în diverse domenii ale vieții oamenilor
Pe lângă exemplele date, graficele sunt utilizate pe scară largă în construcții, inginerie electrică, management, logistică, geografie, inginerie mecanică, sociologie, programare, automatizarea proceselor și producției tehnologice, psihologie și publicitate. Deci, din toate cele de mai sus, rezultă în mod irefutat valoarea practică a teoriei grafurilor, a cărei dovadă a fost scopul acestui studiu.
În orice domeniu al științei și tehnologiei, întâlniți grafice. Graficele sunt obiecte matematice minunate cu care puteți rezolva probleme matematice, economice și logice, diverse puzzle-uri și simplifica condițiile problemelor din fizică, chimie, electronică și automatizare. Multe fapte matematice pot fi formulate convenabil în limbajul graficelor. Teoria grafurilor face parte din multe științe. Teoria grafurilor este una dintre cele mai frumoase și mai vizuale teorii matematice. Recent, teoria grafurilor găsește din ce în ce mai multe aplicații în probleme aplicate. A apărut chiar și chimia computațională - un domeniu relativ tânăr al chimiei bazat pe aplicarea teoriei grafurilor.
Grafice moleculare, utilizate în stereochimie și topologia structurală, chimia clusterelor, polimerilor etc., sunt grafice nedirecționate care afișează structura moleculelor [Anexa Fig. 10]. Vârfurile și muchiile acestor grafice corespund atomilor corespunzătoare și legăturilor chimice dintre ei.
Grafice moleculare și arbori: [Anexa Fig. 10] a, b - multigrafii, respectiv. etilenă și formaldehidă; ei spun izomerii pentanului (arborele 4, 5 sunt izomorfi cu arborele 2).
În stereochimia organismelor cel mai mult. Arborii moleculari sunt adesea folosiți - arborii principali ai graficelor moleculare, care conțin numai toate vârfurile corespunzătoare atomilor de C. Compilarea seturi de mol. arborii și stabilirea izomorfismului lor fac posibilă determinarea faptului că ei spun. structurile și găsiți numărul total de izomeri ai alcanilor, alchenelor și alchinelor
Rețele de proteine
Rețelele de proteine sunt grupuri de proteine care interacționează fizic care funcționează într-o celulă împreună și într-o manieră coordonată, controlând procesele interconectate care au loc în organism. [anexă fig. unsprezece].
Graficul sistemului ierarhic numit copac. O caracteristică distinctivă a unui arbore este că există o singură cale între oricare dintre două vârfuri. Arborele nu conține cicluri sau bucle.
De obicei, un arbore care reprezintă un sistem ierarhic are un vârf principal, care se numește rădăcina arborelui. Fiecare vârf al arborelui (cu excepția rădăcinii) are un singur strămoș - obiectul desemnat de acesta este inclus într-o clasă de nivel superior. Orice vârf al unui arbore poate genera mai mulți descendenți - vârfuri corespunzătoare claselor de nivel inferior.
Pentru fiecare pereche de vârfuri de arbore, există o cale unică care le conectează. Această proprietate este utilizată atunci când se găsesc toți strămoșii, de exemplu, în linia masculină, a oricărei persoane al cărei pedigree este reprezentat sub forma unui arbore genealogic, care este un „arboresc” în sensul teoriei grafurilor.
Exemplu al arborelui meu genealogic [Anexa Fig. 12].
Încă un exemplu. Imaginea arată arborele genealogic biblic [Anexa Fig. 13].
Rezolvarea problemelor
1.Sarcina de transport. Să existe o bază în orașul Krasnodar cu materii prime care trebuie distribuite în orașele Krymsk, Temryuk, Slavyansk-on-Kuban și Timașevsk într-o singură călătorie, petrecând cât mai puțin timp și combustibil și întorcându-se înapoi la Krasnodar .
Soluţie:
Mai întâi, să facem un grafic cu toate rutele posibile de călătorie [Anexa Fig.14], ținând cont de drumurile reale dintre aceste așezări și distanța dintre acestea. Pentru a rezolva această problemă, trebuie să creăm un alt grafic, un arbore [Anexa Fig.15].
Pentru comoditatea soluției, desemnăm orașele cu numere: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.
Rezultatul sunt 24 de soluții, dar avem nevoie doar de cele mai scurte căi. Dintre toate soluțiile, doar două sunt satisfăcătoare, adică 350 km.
În mod similar, este posibil și, cred, necesar să se calculeze transportul real dintr-o localitate în alta.
Problemă logică care implică transfuzia. Găleata conține 8 litri de apă, și sunt două tigăi cu o capacitate de 5 și 3 litri. trebuie să turnați 4 litri de apă într-o tigaie de cinci litri și să lăsați 4 litri în găleată, adică să turnați apă în mod egal în găleată și într-o tigaie mare.
Soluţie:
Situația în orice moment poate fi descrisă prin trei numere [Anexa Fig. 16].
Ca rezultat, obținem două soluții: una în 7 mișcări, cealaltă în 8 mișcări.
Concluzie
Așadar, pentru a învăța cum să rezolvi problemele, trebuie să înțelegi ce sunt, cum sunt structurate, din ce componente constau, care sunt instrumentele cu care se rezolvă problemele.
Rezolvând probleme practice folosind teoria grafurilor, a devenit clar că în fiecare pas, în fiecare etapă a soluționării lor, este necesară aplicarea creativității.
Încă de la început, în prima etapă, constă în faptul că trebuie să poți analiza și codifica starea problemei. A doua etapă este o notație schematică, care constă într-o reprezentare geometrică a graficelor, iar în această etapă elementul de creativitate este foarte important deoarece este departe de a fi ușor de găsit corespondențe între elementele condiției și elementele corespunzătoare ale grafic.
În timp ce rezolvăm o problemă de transport sau o sarcină de întocmire a unui arbore genealogic, am ajuns la concluzia că metoda graficului este cu siguranță interesantă, frumoasă și vizuală.
Am devenit convins că graficele sunt utilizate pe scară largă în economie, management și tehnologie. Teoria grafurilor este folosită și în programare Acest lucru nu a fost discutat în această lucrare, dar cred că este doar o chestiune de timp.
Această lucrare științifică examinează grafice matematice, domeniile lor de aplicare și rezolvă mai multe probleme folosind grafice. Cunoașterea elementelor de bază ale teoriei grafurilor este necesară în diverse domenii legate de producție și managementul afacerii (de exemplu, programul de construcție a rețelei, programul de livrare a corespondenței). În plus, în timp ce lucram la o lucrare științifică, am stăpânit lucrul pe computer folosind editorul de text WORD. Astfel, obiectivele lucrării științifice au fost îndeplinite.
Deci, din toate cele de mai sus, rezultă în mod irefutat valoarea practică a teoriei grafurilor, a cărei dovadă a fost scopul acestei lucrări.
Literatură
Berge K. Teoria grafurilor și aplicațiile sale. -M.: IIL, 1962.
Kemeny J., Snell J., Thompson J. Introducere în matematica finită. -M.: IIL, 1963.
Ore O. Grafice și aplicarea lor. -M.: Mir, 1965.
Harari F. Teoria grafurilor. -M.: Mir, 1973.
Zykov A.A. Teoria grafurilor finite. -Novosibirsk: Știință, 1969.
Berezina L.Yu. Grafice și aplicarea lor. -M.: Educaţie, 1979. -144 p.
„Revista Educațională Soros” Nr. 11 1996 (articol „Grafe plate”);
Gardner M. „Agrement matematic”, M. „Lumea”, 1972 (capitolul 35);
Olehnik S. N., Nesterenko Yu V., Potapov M. K. „Probleme de divertisment vechi”, M. „Știință”, 1988 (partea 2, secțiunea 8; anexa 4);
Aplicație
Aplicație
P 
Orez. 6
Orez. 7
Orez. 8
aplicareaAplicație
Aplicație
Aplicație
P 
Orez. 14
aplicareaAplicație
Graficele servesc în primul rând ca mijloc de reprezentare a moleculelor. Când descrieți o moleculă din punct de vedere topologic, aceasta este reprezentată sub forma unui grafic molecular (MG), unde vârfurile corespund atomilor și muchiile corespund legăturilor chimice (modelul graf-teoretic al unei molecule). De obicei, în această reprezentare, numai atomii scheletici sunt considerați, de exemplu, hidrocarburi cu atomi de hidrogen „șterși”.
Valența elementelor chimice impune anumite restricții asupra gradelor vârfurilor. Pentru arborii alcanici (grafice conectate care nu au cicluri), gradele vârfurilor (r) nu pot depăși patru (r = 1, 2, 3, 4).
Graficele pot fi specificate sub formă de matrice, ceea ce este convenabil atunci când lucrați cu ele pe un computer.
Matricea de adiacență a vârfurilor unui graf simplu este o matrice pătrată A = [aσχ] cu elemente aσχ = 1 dacă vârfurile σ și χ sunt legate printr-o muchie, iar σχ = 0 în caz contrar. Matricea distanțelor este o matrice pătrată D = cu elemente dσχ, definită ca numărul minim de muchii (cea mai mică distanță) dintre vârfurile σ și χ. Uneori sunt folosite și matrice de adiacență și distanțe de-a lungul muchiilor (A e și D e).
Forma matricelor A și D (A e și D e) depinde de metoda de numerotare a vârfurilor (sau a muchiilor), ceea ce provoacă inconveniente la manipularea acestora. Pentru caracterizarea graficului se folosesc invarianți de grafic - indici topologici (TI).
Numărul de căi de lungime unu
pi = xss 0 = m = n-1
Număr de căi de lungime doi
Numărul de triplete ale muchiilor adiacente (cu un vârf comun)
Numărul Wiener (W), definit ca jumătate din suma elementelor matricei distanțelor din graficul luat în considerare:
etc.
Metodologia de studiu a relației structură-proprietate prin indici topologici în abordarea graf-teoretică include următorii pași.
Selectarea obiectelor de cercetare (probă de antrenament) și analiza stării datelor numerice privind proprietatea P pentru o gamă dată de compuși.
Selectarea TI-urilor ținând cont de capacitatea lor discriminatorie, capacitatea de corelare cu proprietăți etc.
Studiul dependențelor grafice „Proprietatea P - TI a unui grafic de moleculă”, de exemplu, P pe n - numărul de atomi scheletici, P pe W - numărul Wiener etc.
Stabilirea unei relații funcționale (analitice) P = _DTI), de exemplu,
P = a(TI) + b,
P = aln(TI) + b,
P = a(TI)1 +b(TI)2 +...+n(TI) n +c
și așa mai departe. Aici a, b, c sunt câțiva parametri (nu trebuie confundați cu parametrii circuitelor aditive) care urmează să fie determinați.
Calcule numerice ale lui P, compararea valorilor calculate cu cele experimentale.
Predicția proprietăților compușilor care nu au fost încă studiati sau chiar obținuți (în afara acestei probe).
Indicii topologici sunt utilizați și în construirea schemelor de calcul aditiv și prognoză. Ele pot fi utilizate în dezvoltarea de noi medicamente, în evaluarea activității cancerigene a anumitor substanțe chimice, în prezicerea stabilității relative a compușilor noi (încă nesintetizați) etc.
Cu toate acestea, trebuie amintit că alegerea TI este adesea aleatorie; este posibil să nu reflecte caracteristici structurale importante ale moleculelor sau să dubleze informații (obținute folosind alți indici), iar schemele de calcul pot să nu aibă o bază teoretică solidă și să fie dificil de interpretat fizico-chimic.
Echipa Departamentului de Chimie Fizică a Universității de Stat din Tver desfășoară de mulți ani cercetări computaționale și teoretice pe problema „Relația proprietăților substanțelor cu structura moleculelor: modelare matematică (computerică)”. Accentul se pune pe căutarea direcționată a unor noi structuri, algoritmi pentru rezolvarea unui număr de probleme teoretice și combinatorii grafice care apar în timpul colectării și procesării informațiilor despre structura și proprietățile substanțelor, crearea de sisteme și baze de date expert de regăsire a informațiilor, dezvoltarea metodelor cantitative de calcul şi prognoză.
Am construit scheme aditive și am găsit dependențe analitice de forma P = Y(TI) pentru un număr de molecule organice și alte molecule. Cu ajutorul formulelor obţinute s-au efectuat calcule numerice ale proprietăţilor fizico-chimice ale compuşilor luaţi în considerare, p.
Bibliografie
- Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Corelații cantitative ale „proprietăților structurii” alcanilor. Scheme de calcul aditiv. Tver, 1999. 96 p.
- Aplicații chimice ale topologiei și teoriei grafurilor / Ed. R. Regele. M.: Mir, 1987. 560 p.
- Aplicarea teoriei grafurilor în chimie / Ed. N.S. Zefirov și S.I. Kuchanova. Novo-Sibirsk: Nauka, 1988. 306 p.
- Stankevich M.I., Stankevich I.V., Zefirov N.S. Indici topologici în chimie organică // Progrese în chimie. 1988. T.57, nr. 3, p.337-366.
- Vinogradova M.G., Saltykova M.N. Abordare graf-teoretică a studiului relației dintre structura și proprietățile alchilsilanilor // Cercetare fundamentală, 2009. Nr. 1. pp. 17-19.
- Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Relația dintre structura și proprietățile alchilsilanilor // Advances in modern natural science, Nr. 1, 2010. P. 136-137.
- Vinogradova M.G., Saltykova M.N., Efremova A.O. Corelații „structură-proprietate” ale alchilsilanilor: o abordare graf-teoretică // Advances in modern science, No. 3, 2010. P. 141-142.
Link bibliografic
Vinogradova M.G. TEORIA GRAFURILOR ÎN CHIMIE // International Journal of Applied and Fundamental Research. – 2010. – Nr. 12. – P. 140-142;URL: https://applied-research.ru/ru/article/view?id=1031 (data accesului: 17/12/2019). Vă aducem în atenție reviste apărute la editura „Academia de Științe ale Naturii”
