Report on the application of graph theory in chemistry. International Journal of Applied and Fundamental Research Application of Graph Theory in Chemistry

1 Over the past decades, the concepts of topology and graph theory have become widespread in theoretical chemistry. They are useful in searching for quantitative relationships “structure-property” and “structure-activity”, as well as in solving graph-theoretic and combinatorial-algebraic problems that arise during the collection, storage and processing of information on structure and properties substances.

Graphs serve primarily as a means of representing molecules. When describing a molecule topologically, it is depicted in the form of a molecular graph (MG), where vertices correspond to atoms and edges correspond to chemical bonds (graph-theoretic model of a molecule). Usually, in this representation, only skeletal atoms are considered, for example, hydrocarbons with “erased” hydrogen atoms.

The valency of chemical elements imposes certain restrictions on the degrees of vertices. For alkan trees (connected graphs that do not have cycles), the degrees of vertices (r) cannot exceed four (r = 1, 2, 3, 4).

Graphs can be specified in matrix form, which is convenient when working with them on a computer.

The adjacency matrix of the vertices of a simple graph is a square matrix A = [aσχ] with elements aσχ = 1 if the vertices σ and χ are connected by an edge, and σχ = 0 otherwise. The distance matrix is ​​a square matrix D = with elements dσχ, defined as the minimum number of edges (shortest distance) between vertices σ and χ. Sometimes matrices of adjacency and distances along edges (A e and D e) are also used.

The form of matrices A and D (A e and D e) depends on the method of numbering the vertices (or edges), which causes inconvenience when handling them. To characterize the graph, graph invariants are used - topological indices (TI).

Number of paths of length one

pi = xss 0 = m = n-1

Number of paths of length two

Number of triplets of adjacent edges (with a common vertex)

Wiener number (W), defined as half the sum of the elements of the distance matrix of the graph under consideration:

etc.

The methodology for studying the structure-property relationship through topological indices in the graph-theoretic approach includes the following steps.

Selection of research objects (training sample) and analysis of the state of numerical data on property P for a given range of compounds.

Selection of TIs taking into account their discriminatory ability, correlation ability with properties, etc.

Study of graphical dependencies “Property P - TI of a molecule graph”, for example, P on n - the number of skeletal atoms, P on W - Wiener number, etc.

Establishing a functional (analytical) relationship P = _DTI), for example,

P = a(TI) + b,

P = aln(TI) + b,

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

etc. Here a, b, c are some parameters (they should not be confused with the parameters of additive circuits) to be determined.

Numerical calculations of P, comparison of calculated values ​​with experimental ones.

Prediction of the properties of compounds that have not yet been studied or even obtained (outside this sample).

Topological indices are also used in the construction of additive calculation and forecasting schemes. They can be used in the development of new drugs, in assessing the carcinogenic activity of certain chemicals, in predicting the relative stability of new (not yet synthesized) compounds, etc.

However, it should be remembered that the choice of TI is often random; they may not reflect important structural features of molecules or duplicate information (obtained using other indices), and calculation schemes may not have a solid theoretical foundation and are difficult to physicochemical interpretation.

The team of the Department of Physical Chemistry of Tver State University has been conducting computational and theoretical research on the problem “Relationship of the properties of substances with the structure of molecules: mathematical (computer) modeling” for many years. The focus is on the targeted search for new structures, algorithms for solving a number of graph-theoretic and combinatorial problems that arise during the collection and processing of information about the structure and properties of substances, the creation of expert information retrieval systems and databases, the development quantitative methods of calculation and forecasting.

We constructed additive schemes and found analytical dependences of the form P = Y(TI) for a number of organic and other molecules. Using the obtained formulas, numerical calculations of the physicochemical properties of the compounds under consideration were performed, p.

References

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Quantitative correlations of “structure properties” of alkanes. Additive calculation schemes. Tver, 1999. 96 p.
2. Chemical applications of topology and graph theory / Ed. R. King. M.: Mir, 1987. 560 p.
3. Application of graph theory in chemistry / Ed. N.S. Zefirov and S.I. Kuchanova. Novo-Sibirsk: Nauka, 1988. 306 p.
4. Stankevich M.I., Stankevich I.V., Zefirov N.S. Topological indices in organic chemistry // Advances in Chemistry. 1988. T.57, No. 3, P.337-366.
5. Vinogradova M.G., Saltykova M.N. Graph-theoretical approach to studying the relationship between the structure and properties of alkylsilanes. // Fundamental Research, 2009. No. 1. pp. 17-19.
6. Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. The relationship between the structure and properties of alkylsilanes // Advances in modern natural science, No. 1, 2010. P. 136-137.
7. Vinogradova M.G., Saltykova M.N., Efremova A.O. “Structure-property” correlations of alkylsilanes: a graph-theoretical approach // Advances in modern science, No. 3, 2010. P. 141-142.

Bibliographic link

Vinogradova M.G. GRAPH THEORY IN CHEMISTRY // International Journal of Applied and Fundamental Research. – 2010. – No. 12. – P. 140-142;
URL: https://applied-research.ru/ru/article/view?id=1031 (access date: 12/17/2019). We bring to your attention magazines published by the publishing house "Academy of Natural Sciences" 1 Over the past decades, the concepts of topology and graph theory have become widespread in theoretical chemistry. They are useful in searching for quantitative relationships “structure-property” and “structure-activity”, as well as in solving graph-theoretic and combinatorial-algebraic problems that arise during the collection, storage and processing of information on structure and properties substances.

Graphs serve primarily as a means of representing molecules. When describing a molecule topologically, it is depicted in the form of a molecular graph (MG), where vertices correspond to atoms and edges correspond to chemical bonds (graph-theoretic model of a molecule). Usually, in this representation, only skeletal atoms are considered, for example, hydrocarbons with “erased” hydrogen atoms.

The valency of chemical elements imposes certain restrictions on the degrees of vertices. For alkan trees (connected graphs that do not have cycles), the degrees of vertices (r) cannot exceed four (r = 1, 2, 3, 4).

Graphs can be specified in matrix form, which is convenient when working with them on a computer.

The adjacency matrix of the vertices of a simple graph is a square matrix A = [aσχ] with elements aσχ = 1 if the vertices σ and χ are connected by an edge, and σχ = 0 otherwise. The distance matrix is ​​a square matrix D = with elements dσχ, defined as the minimum number of edges (shortest distance) between vertices σ and χ. Sometimes matrices of adjacency and distances along edges (A e and D e) are also used.

The form of matrices A and D (A e and D e) depends on the method of numbering the vertices (or edges), which causes inconvenience when handling them. To characterize the graph, graph invariants are used - topological indices (TI).

Number of paths of length one

pi = xss 0 = m = n-1

Number of paths of length two

Number of triplets of adjacent edges (with a common vertex)

Wiener number (W), defined as half the sum of the elements of the distance matrix of the graph under consideration:

etc.

The methodology for studying the structure-property relationship through topological indices in the graph-theoretic approach includes the following steps.

Selection of research objects (training sample) and analysis of the state of numerical data on property P for a given range of compounds.

Selection of TIs taking into account their discriminatory ability, correlation ability with properties, etc.

Study of graphical dependencies “Property P - TI of a molecule graph”, for example, P on n - the number of skeletal atoms, P on W - Wiener number, etc.

Establishing a functional (analytical) relationship P = _DTI), for example,

P = a(TI) + b,

P = aln(TI) + b,

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

etc. Here a, b, c are some parameters (they should not be confused with the parameters of additive circuits) to be determined.

Numerical calculations of P, comparison of calculated values ​​with experimental ones.

Prediction of the properties of compounds that have not yet been studied or even obtained (outside this sample).

Topological indices are also used in the construction of additive calculation and forecasting schemes. They can be used in the development of new drugs, in assessing the carcinogenic activity of certain chemicals, in predicting the relative stability of new (not yet synthesized) compounds, etc.

However, it should be remembered that the choice of TI is often random; they may not reflect important structural features of molecules or duplicate information (obtained using other indices), and calculation schemes may not have a solid theoretical foundation and are difficult to physicochemical interpretation.

The team of the Department of Physical Chemistry of Tver State University has been conducting computational and theoretical research on the problem “Relationship of the properties of substances with the structure of molecules: mathematical (computer) modeling” for many years. The focus is on the targeted search for new structures, algorithms for solving a number of graph-theoretic and combinatorial problems that arise during the collection and processing of information about the structure and properties of substances, the creation of expert information retrieval systems and databases, the development quantitative methods of calculation and forecasting.

We constructed additive schemes and found analytical dependences of the form P = Y(TI) for a number of organic and other molecules. Using the obtained formulas, numerical calculations of the physicochemical properties of the compounds under consideration were performed, p.

References

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Quantitative correlations of “structure properties” of alkanes. Additive calculation schemes. Tver, 1999. 96 p.
2. Chemical applications of topology and graph theory / Ed. R. King. M.: Mir, 1987. 560 p.
3. Application of graph theory in chemistry / Ed. N.S. Zefirov and S.I. Kuchanova. Novo-Sibirsk: Nauka, 1988. 306 p.
4. Stankevich M.I., Stankevich I.V., Zefirov N.S. Topological indices in organic chemistry // Advances in Chemistry. 1988. T.57, No. 3, P.337-366.
5. Vinogradova M.G., Saltykova M.N. Graph-theoretical approach to studying the relationship between the structure and properties of alkylsilanes. // Fundamental Research, 2009. No. 1. pp. 17-19.
6. Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. The relationship between the structure and properties of alkylsilanes // Advances in modern natural science, No. 1, 2010. P. 136-137.
7. Vinogradova M.G., Saltykova M.N., Efremova A.O. “Structure-property” correlations of alkylsilanes: a graph-theoretical approach // Advances in modern science, No. 3, 2010. P. 141-142.

Bibliographic link

Vinogradova M.G. GRAPH THEORY IN CHEMISTRY // International Journal of Applied and Fundamental Research. – 2010. – No. 12. – P. 140-142;
URL: http://dev.applied-research.ru/ru/article/view?id=1031 (access date: 12/17/2019). We bring to your attention magazines published by the publishing house "Academy of Natural Sciences"

Abstract on the subject higher mathematics on the topic:

Application of graph theory in chemistry

Performed by a student from group NH-202

Moscow 2011
Graphs are the field of finite mathematics that studies discrete structures; used to solve various theoretical and applied problems.
Some basic concepts. A graph is a collection of points (vertices) and a collection of pairs of these points (not necessarily all) connected by lines (Fig. 1, a). If the lines in the graph are oriented (that is, the arrows indicate the direction of connection of the vertices), they are called arcs, or branches; if unoriented, - edges. Accordingly, a graph containing only arcs is called a directed graph, or a digraph; only edge-unoriented; arcs and ribs - mixed. A graph having multiple edges is called a multigraph; a graph containing only edges belonging to two of its disjoint subsets (parts) is bipartite; arcs (edges) and (or) vertices that correspond to certain weights or numerical values ​​of any parameters are weighted. A path in a graph is an alternating sequence of vertices and arcs in which none of the vertices is repeated (for example, a, b in Fig. 1,a); contour - a closed path in which the first and last vertices coincide (for example, f, h); loop - an arc (edge) that begins and ends at the same vertex. A graph path is a sequence of edges in which none of the vertices are repeated (for example, c, d, e); cycle - a closed chain in which its initial and final vertices coincide. A graph is called connected if any pair of its vertices is connected by a chain or path; otherwise, the graph is called disconnected.
A tree is a connected undirected graph that does not contain cycles or contours (Fig. 1,b). The spanning subgraph of a graph is a subset of it that contains all the vertices and only certain edges. The spanning tree of a graph is its spanning subgraph, which is a tree. Graphs are called isomorphic if there is a one-to-one correspondence between the sets of their vertices and edges (arcs).
To solve problems of graph theory and its applications, graphs are represented using matrices (adjacency, incidence, two-row, etc.), as well as special ones. numerical characteristics. For example, in the adjacency matrix (Fig. 1c), the rows and columns correspond to the numbers of the vertices of the graph, and its elements take the values ​​0 and 1 (respectively, the absence and presence of an arc between a given pair of vertices); in the incidence matrix (Fig. 1d), the rows correspond to the numbers of the vertices, the columns correspond to the numbers of the arcs, and the elements take the values ​​0, + 1 and - 1 (respectively, the absence, presence of an arc entering and leaving the vertex). The most common numerical characteristics: the number of vertices (m), the number of arcs or edges (n), the cyclomatic number, or the rank of the graph (n - m + k, where k is the number of connected subgraphs in a disconnected graph; for example, for the graph in Fig. 1 ,b rank will be: 10-6+ 1 =5).
The application of graph theory is based on the construction and analysis of various classes of chemical and chemical-technological graphs, which are also called topological models, i.e. models that take into account only the nature of the connections between the vertices. The arcs (edges) and vertices of these graphs display chemical and chemical-technological concepts, phenomena, processes or objects and, accordingly, qualitative and quantitative relationships or certain relationships between them.

Rice. 1. Illustration of some basic concepts: a-mixed graph; b-spanning tree (solid arcs a, h, d, f, h) and a certain subgraph (dashed arcs c, e, g, k, l) of the digraph; c, r-matrices resp. adjacency and incidence of a digraph.
Theoretical problems. Chemical graphs make it possible to predict chemical transformations, explain the essence and systematize some basic concepts of chemistry: structure, configuration, conformations, quantum mechanical and statistical-mechanical interactions of molecules, isomerism, etc. Chemical graphs include molecular, bipartite and signal graphs of kinetic reaction equations.
Molecular graphs, used in stereochemistry and structural topology, chemistry of clusters, polymers, etc., are undirected graphs that display the structure of molecules (Fig. 2). The vertices and edges of these graphs correspond, respectively, to atoms and chemical bonds between them.

Rice. 2. Molecular graphs and trees: a, b - multigraphs, respectively. ethylene and formaldehyde; they say pentane isomers (trees 4, 5 are isomorphic to tree 2).
In the stereochemistry of organic substances, molecular trees are most often used - spanning trees of molecular graphs, which contain only all vertices corresponding to C atoms (Fig. 2, a and b). Compiling sets of molecular trees and establishing their isomorphism makes it possible to determine molecular structures and find the total number of isomers of alkanes, alkenes and alkynes (Fig. 2, c).
Molecular graphs make it possible to reduce problems related to coding, nomenclature and structural features (branching, cyclicity, etc.) of molecules of various compounds to the analysis and comparison of purely mathematical features and properties of molecular graphs and their trees, as well as their corresponding matrices. To identify quantitative correlations between the structure of molecules and the physicochemical (including pharmacological) properties of compounds, more than 20 thousand names of topological indices of molecules (Wiener, Balaban, Hosoya, Plat, Randich, etc.) have been developed, which are determined using matrices and numerical characteristics of molecular trees. For example, the Wiener index W = (m 3 + m)/6, where m is the number of vertices corresponding to C atoms, correlates with molecular volumes and refractions, enthalpies of formation, viscosity, surface tension, chromatographic constants of compounds, octane numbers of hydrocarbons and even physiological activity of drugs.
Important parameters of molecular graphs used to determine the tautomeric forms of a given substance and their reactivity, as well as in the classification of amino acids, nucleic acids, carbohydrates and other complex natural compounds, are the average and total (H) information capacities. The parameter is calculated using the Shannon information entropy formula: , where p t is the probability that the vertices m of the graph belong to the i-th type, or equivalence class, k; i = , Parameter. The study of molecular structures such as inorganic clusters or Möbius strips comes down to establishing the isomorphism of the corresponding molecular graphs by placing them (embedding) in complex polyhedra (for example, polyhedra in the case of clusters) or special ones. multidimensional surfaces (for example, Riemann surfaces). Analysis of molecular graphs of polymers, the vertices of which correspond to monomer units, and the edges to chemical bonds between them, makes it possible to explain, for example, the effects of excluded volume, leading to qualitative changes in the predicted properties of polymers.

Rice. 3. Reaction graphs: a-bipartite; b-signal level of kinetics; r 1, g 2 -r-tion; a 1 -a 6 -reagents; k-rate constants p-tsny; s-complex Laplace transform variable.
Using graph theory and principles of artificial intelligence, software has been developed for information retrieval systems in chemistry, as well as automated systems for identifying molecular structures and rational planning of organic synthesis. For the practical implementation on a computer of operations for selecting rational paths of chemical transformations based on the retrosynthetic and syntonic principles, multi-level branched search graphs for solution options are used, the vertices of which correspond to the molecular graphs of reagents and products, and the arcs depict the transformations of substances.

Rice. 4. Single-circuit chemical-technological system and corresponding graphs: a-structural diagram; b, c-material flow graphs, respectively. by total mass flow rates and component A flow rate; r - thermal flow graph; d-fragment of the system of equations (f 1 - f 6) of the material balance, obtained from the analysis of the graphs in Fig. 4, b and c; e-bipartite information digraph; g-information graph, I-mixer; II-reactor; III-distillation column; IV-refrigerator; I 1 -I 8 -technol. streams; q-mass flow; H is the enthalpy of the flow; i. s and i*, s* - resp. real and fictitious sources and sinks of material and heat flows; c-concentration of the reagent; V is the volume of the reactor.
Matrix representations of molecular graphs of various compounds are equivalent (after transforming the corresponding matrix elements) to matrix methods of quantum chemistry. Therefore, graph theory is used when performing complex quantum chemical calculations: to determine the number, properties and energies of molecular orbitals, predicting the reactivity of conjugated alternant and non-alternant polyenes, identifying aromatic and anti-aromatic properties of substances, etc.
To study disturbances in systems consisting of a large number of particles in chemical physics, so-called Feynman diagrams are used - graphs whose vertices correspond to the elementary interactions of physical particles, the edges to their paths after collisions. In particular, these graphs make it possible to study the mechanisms of oscillatory reactions and determine the stability of reaction systems.
To select rational paths for the transformation of reagent molecules for a given set of known interactions, bipartite reaction graphs are used (vertices correspond to molecules and these reactions, arcs correspond to the interactions of molecules in the reaction; Fig. 3,a). Such graphs make it possible to develop interactive algorithms for selecting optimal paths of chemical transformations that require the smallest number of intermediate reactions, the minimum number of reagents from the list of acceptable ones, or achieve the highest yield of products.
Signal graphs of reaction kinetics equations display systems of kinetic equations presented in algebraic-operator form (Fig. 3b). The vertices of the graphs correspond to the so-called information variables, or signals, in the form of concentrations of reagents, arcs - to the relationships of signals, and the weights of the arcs are determined by kinetic constants. Such graphs are used in studying the mechanisms and kinetics of complex catalytic reactions, complex phase equilibria in the formation of complex compounds, as well as for calculating the parameters of the additive properties of solutions.
Applied problems. To solve multidimensional problems of analysis and optimization of chemical-technological systems (CTS), the following chemical-technological graphs are used (Fig. 4): flow, information-flow, signal and reliability graphs. Flow graphs, which are weighted digraphs, include parametric, material in terms of the total mass flow rates of physical flows and the mass flow rates of some chemical components or elements, as well as thermal graphs. The listed graphs correspond to the physical and chemical transformations of substances and energy in a given chemical system.
Parametric flow graphs display the transformation of parameters (mass flow rates, etc.) of physical flows by CTS elements; the vertices of the graphs correspond to the mathematical models of the devices, as well as the sources and sinks of the specified flows, and the arcs correspond to the flows themselves, and the weights of the arcs are equal to the number of parameters of the corresponding flow. Parametric graphs are used to develop algorithms for analyzing technological modes of multi-circuit chemical systems. Such algorithms establish the sequence of calculating systems of equations of mathematical models of individual devices of any system to determine the parameters of its output flows with known values ​​of variable input flows.
Material flow graphs display changes in the consumption of substances in chemical substances. The vertices of the graphs correspond to devices in which the total mass flow rates of physical flows and the mass flow rates of some chemical components or elements are transformed, as well as sources and sinks of substances of flows or these components; Accordingly, the arcs of the graphs correspond to physical flows or physical and fictitious (chemical transformations of substances in apparatuses) sources and sinks of any components, and the weights of the arcs are equal to the mass flow rates of both types. Thermal flow graphs display heat balances in CTS; the vertices of the graphs correspond to devices in which the heat consumption of physical flows changes, and, in addition, to the sources and sinks of thermal energy of the system; arcs correspond to physical and fictitious (physical-chemical energy conversion in devices) heat flows, and the weights of the arcs are equal to the enthalpies of the flows. Material and thermal graphs are used to compile programs for the automated development of algorithms for solving systems of equations for material and heat balances of complex chemical systems.
Information-stock graphs display the logical-information structure of systems of equations of mathematical models of CTS; are used to develop optimal algorithms for calculating these systems. A bipartite information graph (Fig. 4, e) is an undirected or oriented graph, the vertices of which correspond, respectively, to the equations f l -f 6 and the variables q 1 - V, and the branches reflect their relationship. Information graph (Fig. 4, g) - a digraph depicting the order of solving equations; the vertices of the graph correspond to these equations, sources and receivers of XTS information, and the branches correspond to information variables.
Signal graphs correspond to linear systems of equations of mathematical models of chemical technological processes and systems. The vertices of the graphs correspond to signals (for example, temperature), and the branches correspond to connections between them. Such graphs are used to analyze the static and dynamic modes of multiparameter processes and chemical systems, as well as indicators of a number of their most important properties (stability, sensitivity, controllability).
Reliability graphs are used to calculate various indicators of the reliability of chemical equipment. Among the numerous groups of these graphs (for example, parametric, logical-functional), the so-called fault trees are especially important. Each such tree is a weighted digraph that displays the interrelationship of many simple failures of individual processes and CTS devices, which lead to many secondary failures and the resulting failure of the system as a whole.
To create complexes of programs for automated synthesis of optimal highly reliable production (including resource-saving), along with the principles of artificial intelligence, oriented semantic, or semantic, graphs of CTS solution options are used. These graphs, which in a particular case are trees, depict procedures for generating a set of rational alternative CTS schemes (for example, 14 possible when separating a five-component mixture of target products by rectification) and procedures for the ordered selection among them of a scheme that is optimal according to some criterion of system efficiency.
etc.............

Moreover, for the last 12 years of his life, Euler was seriously ill, went blind, and, despite his serious illness, continued to work and create. Statistical calculations show that Euler made on average one discovery per week. It is difficult to find a mathematical problem that was not addressed in the works of Euler. All mathematicians of subsequent generations studied with Euler in one way or another, and it was not without reason that the famous French scientist P.S. Laplace said: “Read Euler, he is the teacher of us all.” Lagrange says: "If you really love mathematics, read Euler; the presentation of his works is remarkable for its amazing clarity and accuracy." Indeed, the elegance of his calculations was brought to the highest degree. Condorcet concluded his speech at the Academy in memory of Euler with the following words: “So Euler stopped living and calculating!” Living to calculate - how boring it seems from the outside! It is customary to imagine a mathematician as dry and deaf to everything everyday, to what interests ordinary people. Named after Euler, is the problem of three houses and three wells.

GRAPH THEORY

One of the branches of the topology. A graph is a geometric diagram that is a system of lines connecting certain points. The points are called vertices, and the lines connecting them are called edges (or arcs). All graph theory problems can be solved in both graphical and matrix form. In the case of writing in matrix form, the possibility of transmitting a message from a given vertex to another is denoted by one, and its absence is denoted by zero.

The origin of Graph Theory in the 18th century. associated with mathematical puzzles, but a particularly strong impetus for its development was given in the 19th century. and mainly in the 20th century, when the possibilities of its practical applications were discovered: for calculating radio-electronic circuits, solving the so-called. transport tasks, etc. Since the 50s. Graph theory is increasingly used in social psychology and sociology.

In the field of Graph Theory, one should mention the works of F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss, etc. In the USSR, according to T. g. work Φ. M. Borodkin et al.

The Graph Theory language is well suited for analyzing various kinds of structures and transferring states. In accordance with this, we can distinguish the following types of sociological and socio-psychological problems solved using Graph Theory.

1) Formalization and construction of a general structural model of a social object at different levels of its complexity. For example, a structural diagram of an organization, sociograms, comparison of kinship systems in different societies, analysis of the role structure of groups, etc. We can consider that the role structure includes three components: persons, positions (in a simplified version - positions) and tasks performed in a given position. Each component can be represented as a graph:

It is possible to combine all three graphs for all positions or only for one, and as a result we get a clear idea of ​​the specific structure of a c.l. this role. Thus, for the role of position P5 we have a graph (Fig.). Weaving informal relations into the specified formal structure will significantly complicate the graph, but it will be a more accurate copy of reality.

2) Analysis of the resulting model, identification of structural units (subsystems) in it and study of their connections. In this way, for example, subsystems in large organizations can be distinguished.

3) Studying the levels of the structure of hierarchical organizations: the number of levels, the number of connections going from one level to another and from one person to another. Based on this, the following tasks are solved:

a) quantities. assessing the weight (status) of an individual in a hierarchical organization. One of the possible options for determining status is the formula:

where r (p) is the status of a certain person p, k is the value of the level of subordination, defined as the smallest number of steps from a given person to his subordinate, nk is the number of persons at a given level k. For example, in the organization represented by the following. Count:

weight a=1·2+2·7+3·4=28; 6=1·3+2·3=9, etc.

b) determination of the group leader. The leader is usually characterized by greater connectedness with the rest of the group compared to others. As in the previous task, various methods can also be used here to identify the leader.

The simplest method is given by the formula: r=Σdxy/Σdqx, i.e. the quotient of dividing the sum of all distances of each person to all others by the sum of the distances of a given individual to all others.

4) Analysis of the effectiveness of the activity of this system, which also includes such tasks as searching for the optimal structure of the organization, increasing group cohesion, analyzing the social system from the point of view of its sustainability; study of information flows (transmission of messages when solving problems, the influence of group members on each other in the process of uniting the group); with the help of technology, they solve the problem of finding an optimal communication network.

When applied to Graph Theory, as well as to any mathematical apparatus, it is true that the basic principles for solving a problem are set by a substantive theory (in this case, sociology).

Task : Three neighbors have three common wells. Is it possible to build non-intersecting paths from each house to each well? Paths cannot pass through wells and houses (Fig. 1).

Rice. 1. To the problem of houses and wells.

To solve this problem, we will use a theorem proven by Euler in 1752, which is one of the main ones in graph theory. The first work on graph theory belongs to Leonhard Euler (1736), although the term “graph” was first introduced in 1936 by the Hungarian mathematician Dénes König. Graphs were called diagrams consisting of points and segments of straight lines or curves connecting these points.

Theorem. If a polygon is divided into a finite number of polygons such that any two polygons of the partition either do not have common points, or have common vertices, or have common edges, then the equality holds

B - P + G = 1, (*)

where B is the total number of vertices, P is the total number of edges, G is the number of polygons (faces).

Proof. Let us prove that the equality does not change if a diagonal is drawn in some polygon of a given partition (Fig. 2, a).

b)

Indeed, after drawing such a diagonal, the new partition will have B vertices, P+1 edges, and the number of polygons will increase by one. Therefore, we have

B - (P + 1) + (G+1) = B – P + G.

Using this property, we draw diagonals that split the incoming polygons into triangles, and for the resulting partition we show the feasibility of the relation.

To do this, we will sequentially remove external edges, reducing the number of triangles. In this case, two cases are possible:

to remove triangle ABC, you need to remove two edges, in our case AB and BC;

To remove triangle MKN, you need to remove one edge, in our case MN.

In both cases the equality will not change. For example, in the first case, after removing the triangle, the graph will consist of B-1 vertices, P-2 edges and G-1 polygon:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Thus, removing one triangle does not change the equality.

Continuing this process of removing triangles, we will eventually arrive at a partition consisting of a single triangle. For such a partition B = 3, P = 3, G = 1 and, therefore,

This means that equality also holds for the original partition, from which we finally obtain that the relation is valid for this partition of the polygon.

Note that Euler's relation does not depend on the shape of the polygons. Polygons can be deformed, enlarged, reduced, or even curved their sides, as long as there are no gaps in the sides. Euler's relation will not change.

Let us now proceed to solving the problem of three houses and three wells.

Solution. Let's assume that this can be done. Let us mark the houses with points D1, D2, D3, and the wells with points K1, K2, K3 (Fig. 1). We connect each house point with each well point. We get nine edges that do not intersect in pairs.

These edges form a polygon on the plane, divided into smaller polygons. Therefore, for this partition the Euler relation B - P + G = 1 must be satisfied.

Let's add one more face to the faces under consideration - the outer part of the plane in relation to the polygon. Then the Euler relation will take the form B - P + G = 2, with B = 6 and P = 9.

B - P + G = 1, (*)

where B is the total number of vertices, P is the total number of edges, G is the number of polygons (faces).

Proof. Let us prove that the equality does not change if a diagonal is drawn in some polygon of a given partition (Fig. 2, a).

a) b)

Fig.2

Indeed, after drawing such a diagonal, the new partition will have B vertices, P+1 edges, and the number of polygons will increase by one. Therefore, we have

B - (P + 1) + (G+1) = B – P + G.

Using this property, we draw diagonals that split the incoming polygons into triangles, and for the resulting partition we show the feasibility of the relation.

To do this, we will sequentially remove external edges, reducing the number of triangles. In this case, two cases are possible:

to remove triangle ABC, you need to remove two edges, in our case AB and BC;

To remove triangle MKN, you need to remove one edge, in our case MN.

In both cases the equality will not change. For example, in the first case, after removing the triangle, the graph will consist of B-1 vertices, P-2 edges and G-1 polygon:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Thus, removing one triangle does not change the equality.

Continuing this process of removing triangles, we will eventually arrive at a partition consisting of a single triangle. For such a partition B = 3, P = 3, G = 1 and, therefore,

B - P + G = 1.

This means that equality also holds for the original partition, from which we finally obtain that the relation is valid for this partition of the polygon.

Note that Euler's relation does not depend on the shape of the polygons. Polygons can be deformed, enlarged, reduced, or even curved their sides, as long as there are no gaps in the sides. Euler's relation will not change.

Let us now proceed to solving the problem of three houses and three wells.

Solution . Let's assume that this can be done. Let us mark the houses with points D1, D2, D3, and the wells with points K1, K2, K3 (Fig. 1). We connect each house point with each well point. We get nine edges that do not intersect in pairs.

These edges form a polygon on the plane, divided into smaller polygons. Therefore, for this partition the Euler relation B - P + G = 1 must be satisfied.

Let's add one more face to the faces under consideration - the outer part of the plane in relation to the polygon. Then the Euler relation will take the form B - P + G = 2, with B = 6 and P = 9.

Therefore, Г = 5. Each of the five faces has at least four edges, since, according to the conditions of the problem, none of the paths should directly connect two houses or two wells. Since each edge lies on exactly two faces, the number of edges must be at least (5 4)/2 = 10, which contradicts the condition that their number is 9.

The resulting contradiction shows that the answer to the problem is negative - it is impossible to draw non-intersecting paths from each house to each village

Graph Theory in Chemistry

Application of graph theory to the construction and analysis of various classes of chemical and chemical-technological graphs, which are also called topology, models, i.e. models that take into account only the nature of the connections between the vertices. The arcs (edges) and vertices of these graphs reflect chemical and chemical-technological concepts, phenomena, processes or objects and, accordingly, qualitative and quantitative relationships or certain relationships between them.

Theoretical problems. Chemical graphs make it possible to predict chemical transformations, explain the essence and systematize some basic concepts of chemistry: structure, configuration, confirmations, quantum mechanical and statistical-mechanical interactions of molecules, isomerism, etc. Chemical graphs include molecular, bipartite and signal graphs of kinetic reaction equations. Molecular graphs, used in stereochemistry and structural topology, chemistry of clusters, polymers, etc., are undirected graphs that display the structure of molecules. The vertices and edges of these graphs correspond to the corresponding atoms and chemical bonds between them.

In stereochemistry org. c-c the most commonly used are molecular trees - spanning trees of molecular graphs that contain only all the vertices corresponding to atoms. Compiling sets of molecular trees and establishing their isomorphism makes it possible to determine molecular structures and find the total number of isomers of alkanes, alkenes and alkynes. Molecular graphs make it possible to reduce problems related to coding, nomenclature and structural features (branching, cyclicity, etc.) of molecules of various compounds to the analysis and comparison of purely mathematical features and properties of molecular graphs and their trees, as well as their corresponding matrices. To identify the number of correlations between the structure of molecules and the physicochemical (including pharmacological) properties of compounds, more than 20 so-called ones have been developed. Topological indices of molecules (Wiener, Balaban, Hosoya, Plata, Randic, etc.), which are determined using matrices and numerical characteristics of molecular trees. For example, the Wiener index W = (m3 + m)/6, where m is the number of vertices corresponding to C atoms, correlates with molecular volumes and refractions, enthalpies of formation, viscosity, surface tension, chromatographic constants of compounds, octane numbers of hydrocarbons and even physiol . activity of drugs. Important parameters of molecular graphs used to determine the tautomeric forms of a given substance and their reactivity, as well as in the classification of amino acids, nucleic acids, carbohydrates and other complex natural compounds, are the average and total (H) information capacity. Analysis of molecular graphs of polymers, the vertices of which correspond to monomer units, and the edges correspond to chemical bonds between them, makes it possible to explain, for example, the effects of excluded volume leading to qualities. changes in the predicted properties of polymers. Using Graph Theory and the principles of artificial intelligence, software for information retrieval systems in chemistry, as well as automated systems for identifying molecular structures and rational planning of organic synthesis, has been developed. For the practical implementation on a computer of operations for selecting rational chemical paths. transformations based on the retrosynthetic and syntonic principles use multi-level branched search graphs for solution options, the vertices of which correspond to the molecular graphs of reagents and products, and the arcs depict transformations.

To solve multidimensional problems of analysis and optimization of chemical technological systems (CTS), the following chemical technological graphs are used: flow, information flow, signal and reliability graphs. For study in chemistry. The physics of disturbances in systems consisting of a large number of particles uses the so-called. Feynman diagrams are graphs, the vertices of which correspond to the elementary interactions of physical particles, the edges of their paths after collisions. In particular, these graphs make it possible to study the mechanisms of oscillatory reactions and determine the stability of reaction systems. Material flow graphs display changes in the consumption of substances in the CTS. Thermal flow graphs display heat balances in CTS; the vertices of the graphs correspond to devices in which the heat consumption of physical flows changes, and, in addition, to the sources and sinks of thermal energy of the system; arcs correspond to physical and fictitious (physical-chemical energy conversion in devices) heat flows, and the weights of the arcs are equal to the enthalpies of the flows. Material and thermal graphs are used to compile programs for the automated development of algorithms for solving systems of equations for material and heat balances of complex chemical systems. Information flow graphs display the logical information structure of systems of mathematical equations. XTS models; are used to develop optimal algorithms for calculating these systems. A bipartite information graph is an undirected or directed graph whose vertices correspond respectively. equations fl -f6 and variables q1 – V, and the branches reflect their relationship. Information graph – a digraph depicting the order of solving equations; the vertices of the graph correspond to these equations, sources and receivers of XTS information, and the branches correspond to information. variables. Signal graphs correspond to linear systems of equations of mathematical models of chemical technological processes and systems. Reliability graphs are used to calculate various reliability indicators X.

Literature used:

1.Berge K., T. g. and its application, translation from French, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, trans. from English, 2nd ed., M., 1963;

3.Ope O., Graphs and their application, trans. from English, M., 1965;

4. Belykh O.V., Belyaev E.V., Possibilities of using technology in sociology, in: Man and Society, vol. 1, [L.], 1966;

5. Quantitative methods in sociological research, M., 1966; Belyaev E.V., Problems of sociological measurements, "VF", 1967, No. 7; Bavelas. Communication patterns in task oriented groups, in the book. Lerner D., Lass well H., Political sciences, Stanford, 1951;