home / Relationship/ Graph theory. Chemical applications of topology and graph theory Application of graphs in various areas of human life

Graph theory. Chemical applications of topology and graph theory Application of graphs in various areas of human life

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 valence 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

and so on. 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.

Bibliography

Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Quantitative correlations of “structure properties” of alkanes. Additive calculation schemes. Tver, 1999. 96 p.
Chemical applications of topology and graph theory / Ed. R. King. M.: Mir, 1987. 560 p.
Application of graph theory in chemistry / Ed. N.S. Zefirov and S.I. Kuchanova. Novo-Sibirsk: Nauka, 1988. 306 p.
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.
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.
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.
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"

Studying the connection between the properties of substances and their structure is one of the main tasks of chemistry. A great contribution to its solution was made by the structural theory of organic compounds, whose creators included the great Russian chemist Alexander Mikhailovich Butlerov (1828-1886). It was he who first established that the properties of a substance depend not only on its composition (molecular formula), but also on the order in which the atoms in the molecule are connected to each other. This order was called "chemical structure". Butlerov predicted that composition C 4 H 10 may correspond to two substances having different structures - butane and isobutane, and confirmed this by synthesizing the latter substance.

The idea that the order in which atoms are connected is key to the properties of matter has proven to be very fruitful. It is based on the representation of molecules using graphs, in which atoms play the role of vertices, and chemical bonds between them act as edges connecting the vertices. In the graphical representation, the lengths of the bonds and the angles between them are ignored. The C molecules described above 4 H 10 are represented by the following graphs:

Hydrogen atoms are not indicated in such graphs, since their location can be unambiguously determined by the structure of the carbon skeleton. Recall that carbon in organic compounds is tetravalent, so in the corresponding graphs no more than four edges can extend from each vertex.

Graphs are mathematical objects, so they can be characterized using numbers. This is where the idea came from to express the structure of molecules with numbers that are related to the structure of molecular graphs. These numbers are called “topological indices” in chemistry. By calculating any topological index for a large number of molecules, it is possible to establish a connection between its values and the properties of substances, and then use this connection to predict the properties of new, not yet synthesized substances. To date, chemists and mathematicians have proposed hundreds of different indices that characterize certain properties of molecules.

Methods for calculating topological indices

Methods for calculating topological indices can be very diverse, but all of them must satisfy quite natural requirements:

1) each molecule has its own individual index;

2) molecules with similar properties have similar indices.

Let's see how this idea is implemented using the example of saturated hydrocarbons - alkanes. The key concept for constructing many indices is the concept of “distance matrix” D. This is the name of a matrix whose elements show the number of edges separating the corresponding vertices of the molecular graph. Let's construct this matrix for three isomeric hydrocarbons of composition C 5 H 12 . To do this, let’s draw their molecular graphs and renumber the vertices (in random order):

The diagonal elements of the distance matrix for hydrocarbons are equal to 0. In the first graph, vertex 1 is connected to vertex 2 by one edge, so the matrix element d 12 = 1. Similarly, d 13 = 2, d 14 = 3, d 15 = 4. The first row in the distance matrix of normal pentane has the form: (0 1 2 3 4). Complete distance matrices for three graphs:

molecule chemistry topological index

The distance between vertices does not depend on the order in which they are listed, so the distance matrices are symmetrical with respect to the diagonal.

The first topological index reflecting the structure of a molecular graph (G) was proposed in 1947 by Wiener. It is defined as the sum of the diagonal elements of the distance matrix plus half the sum of its non-diagonal elements:

(1)

For the above graphs corresponding to pentanes C 5 H 12 , the Wiener index takes values 20, 18 and 16. It can be assumed that it describes the degree of branching of the hydrocarbon: the highest values correspond to the least branched hydrocarbons. As the length of the carbon skeleton increases, the Wiener index increases, as there are more elements in the distance matrix. Statistical analysis using the example of several hundred hydrocarbons showed that the Wiener index correlates with some physical properties of alkanes: boiling points, heats of evaporation, molar volume.

Another type of index is based not on the distances between vertices, but on the number of nearest neighbors for each vertex. As an example, let's calculate the Randić index, which is defined as follows:

(2)

where vi– degree of the i-th vertex, that is, the number of edges extending from it. For the above graphs, the Randić index is equal to:

(3)

(4)

(5)

This index also decreases with increasing degree of branching of the carbon skeleton and can be used to describe the physical properties of alkanes.

Alkanes are the most boring type of organic molecules from a chemical point of view, since they do not contain any “features” - double and triple bonds or atoms of elements other than hydrogen and carbon (such elements are called heteroatoms). The introduction of heteroatoms into a molecule can radically change the properties of a substance. Thus, the addition of just one oxygen atom converts the rather inert gaseous ethane C 2 H 6 into liquid ethanol C 2 H 5 OH, exhibiting fairly high chemical and biological activity.

Consequently, in the topological indices of molecules more complex than alkanes, it is necessary to take into account the presence of multiple bonds and heteroatoms. This is done by assigning certain numerical coefficients - “weights” - to the vertices and edges of the graphs. For example, in a distance matrix, the diagonal elements can be defined in terms of the nuclear charge Zi(remember that for carbon Z = 6):

(6)

Off-diagonal elements are determined by summing over edges, with each edge connecting atoms with charges Ziand Zj, weight is assigned

(7)

where b is equal to the bond order between the atoms (1 for a single bond, 2 for a double bond, 3 for a triple bond). For ordinary carbon-carbon single bonds, k = 1. Let us compare the Wiener indices of propane C 3 H 8 and three oxygen-containing substances similar in composition: propyl alcohol C 3 H 8 O, its isomeric isopropyl alcohol C 3 H 8 O and acetone C 3 H 6 O.

To do this, we calculate the distance matrix according to the specified rules. In molecular graphs we indicate all atoms except hydrogen atoms.1) Propane

2) In the propyl alcohol molecule, oxygen is bonded to the outermost carbon atom:

For a single C–O bond, the weighting coefficient is 36/(68) = 0.75. Diagonal matrix element corresponding to oxygen:

d 44 = 1 – 6/8 = 0.25.

For molecules containing heteroatoms, the Wiener index ceases to be integer. 3) In the isopropyl alcohol molecule, oxygen is bonded to the middle carbon atom:

4) In acetone, the order of connection of atoms is the same as in isopropyl alcohol, but the bond between carbon and oxygen is double:

For the C=O double bond the weighting factor is 36/(268) = 0.375

As can be seen, the addition of a heteroatom to the structure of alkanes leads to an increase in the Wiener index due to an increase in the size of the distance matrix. Adding multiple bonds and increasing the degree of branching of the molecule reduces this index. These rules also apply to more complex molecules. Initially, topological indices were developed only for the purpose of predicting the physicochemical properties of substances. However, later they began to be used to solve other problems. Let's look at some of them. One application of topological indices is related to the classification of organic compounds and the creation of organic databases. The task is to find an index that one-to-one characterizes the chemical structure and from which this structure can be reconstructed. The required index must have good discriminatory ability, that is, it must distinguish between even molecules that are similar in structure. This task is enormous, since more than 20 million organic structures are already known. Its solution will apparently be found through the use of composite topological indices.

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 both in 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.

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 the 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).

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 their sides bent, as long as the sides do not break. 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, Randich, 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 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 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 flow rates in chemical heating systems. Thermal flow graphs display heat balances in chemical heating systems; 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.

References:

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;

6. Kemeny J. G., Snell J., Mathematical models in the social sciences, N. Y., 1962; Filament C., Applications of graph theory to group structure, N. Y., 1963; Оeser Ο. A., Hararu F., Role structures and description in terms of graph theory, in the book: Biddle V., Thomas E. J., Role theory: concepts and research, N. Y., 1966. E. Belyaev. Leningrad.

Page 8, like inorganic, ... marry an adventurer Law >> Historical figures

Of the fundamental tasks theories measures and ergodic theories(V theories decreasing... in the field of physics, chemistry, physiology or medicine, ... Maximum flow Let there be graph(with oriented ribs), ... remained for a long time unresolved. The ellipsoid method has...

MUNICIPAL AUTONOMOUS EDUCATIONAL INSTITUTION SECONDARY SCHOOL No. 2

Prepared

Legkokonets Vladislav, student of class 10A

Practical application of Graph Theory

Supervisor

L.I. Noskova, mathematics teacher

Art. Bryukhovetskaya

2011

1.Introduction…………………………………………………………………………………….………….3

2. History of the emergence of graph theory………………………………………….………..4

3. Basic definitions and theorems of graph theory…………………………….………6

4. Problems solved using graphs……………………………..………………………..8

4.1 Famous problems………………………………….………………………...8

4.2 Several interesting problems………………………………….……………..9

5. Application of graphs in various areas of people’s lives……………………………...11

6. Solving problems………………………………………………………………………………………...12

7. Conclusion………………….…………………………………………………………….13

8. List of references………….……………………………………………………………14

9.Appendix……………………………………………………………………………….…………15

Introduction

Born from solving puzzles and entertaining games, graph theory has now become a simple, accessible and powerful tool for solving questions related to a wide range of problems. Graphs are literally omnipresent. In the form of graphs, you can, for example, interpret road maps and electrical circuits, geographical maps and molecules of chemical compounds, connections between people and groups of people. Over the past four decades, graph theory has become one of the most rapidly developing branches of mathematics. This is driven by the demands of a rapidly expanding application field. It is used in the design of integrated circuits and control circuits, in the study of automata, logical circuits, program block diagrams, in economics and statistics, chemistry and biology, in scheduling theory. That's why relevance The topic is determined, on the one hand, by the popularity of graphs and related research methods, and on the other, an undeveloped, holistic system for its implementation.

Solving many problems in life requires long calculations, and sometimes even these calculations do not bring success. This is what research problem. The question arises: is it possible to find a simple, rational, short and elegant solution to solve them. Is problem solving easier if you use graphs? This determined topic of my research: “Practical application of graph theory”

Purpose The research was to use graphs to learn how to quickly solve practical problems.

Research hypothesis. The graph method is very important and widely used in various fields of science and human activity.

Research objectives:

1. Study literature and Internet resources on this issue.

2.Check the effectiveness of the graph method in solving practical problems.

3. Draw a conclusion.

Practical significance of the study is that the results will undoubtedly arouse the interest of many people. Haven't any of you tried to build your family tree? How to do this correctly? The head of a transport enterprise probably has to solve the problem of more profitable use of transport when transporting goods from a destination to several settlements. Every schoolchild has encountered logical transfusion problems. It turns out that they can be easily solved using graphs.

The following methods are used in the work: observation, search, selection, analysis.

History of graph theory

The founder of graph theory is considered to be the mathematician Leonhard Euler (1707-1783). The history of this theory can be traced through the correspondence of the great scientist. Here is a translation of the Latin text, which is taken from Euler’s letter to the Italian mathematician and engineer Marinoni, sent from St. Petersburg on March 13, 1736.

“I was once given a problem about an island located in the city of Königsberg and surrounded by a river with seven bridges across it.

[Appendix Fig.1] The question is whether someone can go around them continuously, passing only once over each bridge. And then I was informed that no one had yet been able to do this, but no one had proven that it was impossible. This question, although trivial, seemed to me, however, worthy of attention in that neither geometry, nor algebra, nor combinatorial art are sufficient to solve it. After much thought, I found an easy rule, based on a completely convincing proof, with the help of which it is possible in all problems of this kind to immediately determine whether such a detour can be made through any number and any number of bridges located or not. The Koenigsberg bridges are located in such a way that they can be represented in the following figure [Appendix Fig.2], in which A denotes an island, and B, C and D - parts of the continent separated from each other by river branches

Regarding the method he discovered to solve problems of this kind, Euler wrote:

“This solution, by its nature, apparently has little to do with mathematics, and I do not understand why one should expect this solution from a mathematician rather than from any other person, for this decision is supported by reasoning alone, and there is no need to involve to find this solution, any laws inherent in mathematics. So, I do not know how it turns out that questions that have very little to do with mathematics are more likely to be solved by mathematicians than by others."

So is it possible to get around the Königsberg bridges by passing only once over each of these bridges? To find the answer, let's continue Euler's letter to Marinoni:

"The question is to determine whether it is possible to bypass all these seven bridges, passing through each only once, or not. My rule leads to the following solution to this question. First of all, you need to look at how many areas there are, separated by water - such , which have no other passage from one to another, except through a bridge. In this example, there are four such sections - A, B, C, D. Next, you need to distinguish whether the number of bridges leading to these individual sections is even or odd. So, in our case, five bridges lead to section A, and three bridges each to the rest, i.e. The number of bridges leading to individual sections is odd, and this alone is enough to solve the problem. Once this is determined, we apply the following rule : if the number of bridges leading to each separate section were even, then the detour in question would be possible, and at the same time it would be possible to start this detour from any section.If, however, two of these numbers were if they were odd, because only one cannot be odd, then even then the transition could be completed, as prescribed, but only the beginning of the detour must certainly be taken from one of those two sections to which an odd number of bridges leads. If, finally, there were more than two sections to which an odd number of bridges lead, then such a movement is generally impossible ... if other, more serious problems could be brought here, this method could be of even greater benefit and should not be neglected." .

Basic definitions and theorems of graph theory

Graph theory is a mathematical discipline created by the efforts of mathematicians, therefore its presentation includes the necessary strict definitions. So, let's proceed to an organized introduction of the basic concepts of this theory.

Definition 1. A graph is a collection of a finite number of points, called the vertices of the graph, and pairwise lines connecting some of these vertices, called the edges or arcs of the graph.

This definition can be formulated differently: a graph is a non-empty set of points (vertices) and segments (edges), both ends of which belong to a given set of points

In what follows, we will denote the vertices of the graph by Latin letters A, B, C, D. Sometimes the graph as a whole will be denoted by one capital letter.

Definition 2. Vertices of a graph that do not belong to any edge are called isolated.

Definition 3. A graph consisting only of isolated vertices is called null - count .

Notation: O "– a graph with vertices that has no edges

Definition 4. A graph in which each pair of vertices is connected by an edge is called complete.

Designation: U" – a graph consisting of n vertices and edges connecting all possible pairs of these vertices. Such a graph can be represented as an n-gon in which all diagonals are drawn

Definition 5. The degree of a vertex is the number of edges to which the vertex belongs.

Definition 6. A graph whose degrees of all k vertices are the same is called a homogeneous degree graph .

Definition 7. The complement of a given graph is a graph consisting of all the edges and their ends that must be added to the original graph to obtain a complete graph.

Definition 8. A graph that can be represented on a plane in such a way that its edges intersect only at the vertices is called planar.

Definition 9. A polygon of a planar graph that does not contain any vertices or edges of the graph is called its face.

The concepts of a planar graph and a graph face are used when solving problems on the “correct” coloring of various maps.

Definition 10. A path A to X is a sequence of edges leading from A to X such that every two adjacent edges have a common vertex, and no edge occurs more than once.

Definition 11. A cycle is a path in which the starting and ending points coincide.

Definition 12. A simple cycle is a cycle that does not pass through any of the vertices of the graph more than once.

Definition 13. Length of the path , laid on a loop , the number of edges of this path is called.

Definition 14. Two vertices A and B in a graph are called connected (disconnected) if there exists (does not exist) a path leading from A to B.

Definition 15. A graph is called connected if every two of its vertices are connected; if the graph contains at least one pair of disconnected vertices, then the graph is called disconnected.

Definition 16. A tree is a connected graph that does not contain cycles.

A three-dimensional model of a tree graph is, for example, a real tree with its intricately branched crown; the river and its tributaries also form a tree, but already flat - on the surface of the earth.

Definition 17. A disconnected graph consisting entirely of trees is called a forest.

Definition 18. A tree in which all n vertices are numbered from 1 to n is called a tree with renumbered vertices.

So, we have examined the basic definitions of graph theory, without which it would be impossible to prove theorems, and, consequently, solve problems.

Problems solved using graphs

Famous problems

Traveling salesman problem

The traveling salesman problem is one of the famous problems in the theory of combinatorics. It was put forward in 1934, and the best mathematicians broke their teeth on it.

The problem statement is as follows.
A traveling salesman (wandering merchant) must leave the first city, visit cities 2,1,3..n once in an unknown order and return to the first city. The distances between cities are known. In what order should one go around the cities so that the closed path (tour) of a traveling salesman is the shortest?

Method for solving the traveling salesman problem

Greedy algorithm “go to the nearest (which you have not yet entered) city.”
This algorithm is called “greedy” because in the last steps you have to pay severely for greed.
Consider for example the network in the figure [Appendix Fig.3], representing a narrow rhombus. Let a traveling salesman start from city 1. The “go to the nearest city” algorithm will take him to city 2, then 3, then 4; at the last step you will have to pay for your greed, returning along the long diagonal of the diamond. The result will be not the shortest, but the longest tour.

Problem about the Königsberg bridges.

The problem is formulated as follows.
The city of Koenigsberg is located on the banks of the Pregel River and two islands. The different parts of the city were connected by seven bridges. On Sundays, townspeople took walks around the city. Question: is it possible to take a walk in such a way that, when you leave the house, you return back by walking exactly once over each bridge?
Bridges across the Pregel River are located as in the picture[Appendix Fig.1].

Consider the graph corresponding to the bridge diagram [Appendix Fig. 2].

To answer the question of the problem, it is enough to find out whether the graph is Eulerian. (An even number of bridges must extend from at least one vertex). You can’t walk around the city and cross all the bridges once and come back.

Several interesting tasks

1. "Routes".

Problem 1

As you remember, the hunter for dead souls Chichikov visited famous landowners once each. He visited them in the following order: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Colonel Koshkarev. A diagram was found on which Chichikov sketched the relative positions of the estates and the country roads connecting them. Determine which estate belongs to whom, if Chichikov did not drive any of the roads more than once [Appendix Fig. 4].

Solution:

The road map shows that Chichikov began his journey from estate E, and ended with estate O. We note that only two roads lead to estates B and C, so Chichikov had to travel along these roads. Let's mark them with a bold line. Sections of the route passing through A have been identified: AC and AB. Chichikov did not travel on the roads AE, AK and AM. Let's cross them out. Let us mark with a bold line ED; Let's cross out DK. Let's cross out MO and MN; Let's mark with a bold line MF; cross out FO; Let's mark FH, NK and KO with a bold line. Let's find the only possible route under this condition. And we get: estate E - belongs to Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Appendix Fig.5].

Problem 2

The figure shows a map of the area [Appendix Fig. 6].

You can only move in the direction of the arrows. You can visit each point no more than once. In how many ways can you get from point 1 to point 9? Which route is the shortest and which is the longest.

Solution:

We sequentially “stratify” the circuit into a tree, starting from vertex 1 [Appendix Fig.7]. Let's get a tree. The number of possible ways to get from 1 to 9 is equal to the number of “hanging” vertices of the tree (there are 14 of them). Obviously the shortest path is 1-5-9; the longest is 1-2-3-6-5-7-8-9.

2 "Groups, dating"

Problem 1

The participants of the music festival, having met, exchanged envelopes with addresses. Prove that:

a) an even number of envelopes were handed over;

b) the number of participants who exchanged envelopes an odd number of times is even.

Solution: Let the festival participants be A 1, A 2, A 3. . . , And n are the vertices of the graph, and the edges connect pairs of vertices representing the guys exchanging envelopes [Appendix Fig.8]

Solution:

a) the degree of each vertex A i shows the number of envelopes that participant A i gave to his friends. The total number of transmitted envelopes N is equal to the sum of the degrees of all vertices of the graph N = degree. A 1 + step. A 2 + + . . . + step. A n -1 + degree. And n, N =2p, where p is the number of edges of the graph, i.e. N – even. Consequently, an even number of envelopes were handed over;

b) in the equality N = degree. A 1 + step. A 2 + + . . . + step. A n -1 + degree. And n the sum of odd terms must be even, and this can only be if the number of odd terms is even. This means that the number of participants who exchanged envelopes an odd number of times is even.

Problem 2

One day Andrei, Boris, Volodya, Dasha and Galya agreed to go to the cinema in the evening. They decided to coordinate the choice of cinema and show over the phone. It was also decided that if it was not possible to contact someone by phone, then the trip to the cinema would be cancelled. In the evening, not everyone gathered at the cinema, and therefore the movie visit was cancelled. The next day they began to find out who called whom. It turned out that Andrey called Boris and Volodya, Volodya called Boris and Dasha, Boris called Andrey and Dasha, Dasha called Andrey and Volodya, and Galya called Andrey, Volodya and Boris. Who couldn't get on the phone and therefore didn't come to the meeting?

Solution:

Let's draw five dots and label them with the letters A, B, C, D, D. These are the first letters of the names. Let's connect the dots that correspond to the names of the guys who called.

[Appendix Fig.9]

From the picture it is clear that each of the guys - Andrey, Boris and Volodya - telephoned everyone else. That's why these guys came to the cinema. But Galya and Dasha were unable to get on the phone with each other (points G and E are not connected by a line segment) and therefore, in accordance with the agreement, did not come to the cinema.

Application of graphs in various areas of people's lives

In addition to the examples given, graphs are widely used in construction, electrical engineering, management, logistics, geography, mechanical engineering, sociology, programming, automation of technological processes and production, psychology, and advertising. So, from all of the above, the practical value of graph theory irrefutably follows, the proof of which was the goal of this study.

In any field of science and technology you encounter graphs. Graphs are wonderful mathematical objects with which you can solve mathematical, economic and logical problems, various puzzles and simplify the conditions of problems in physics, chemistry, electronics, and automation. Many mathematical facts can be conveniently formulated in the language of graphs. Graph theory is part of many sciences. Graph theory is one of the most beautiful and visual mathematical theories. Recently, graph theory is finding more and more applications in applied issues. Even computational chemistry has emerged - a relatively young field of chemistry based on the application of graph theory.

Molecular graphs, used in stereochemistry and structural topology, chemistry of clusters, polymers, etc., are undirected graphs displaying the structure of molecules [Appendix Fig. 10]. The vertices and edges of these graphs correspond to the corresponding atoms and chemical bonds between them.

Molecular graphs and trees: [Appendix Fig. 10] a, b - multigraphs, respectively. ethylene and formaldehyde; they say pentane isomers (trees 4, 5 are isomorphic to tree 2).

In the stereochemistry of organisms the most. Molecular trees are often used - the main trees of molecular graphs, which contain only all the vertices corresponding to the C atoms. Compilation of sets of mol. trees and the establishment of their isomorphism make it possible to determine that they say. structures and find the total number of isomers of alkanes, alkenes and alkynes

Protein networks

Protein networks are groups of physically interacting proteins that function in a cell together and in a coordinated manner, controlling interconnected processes occurring in the body [attachment fig. eleven].

Hierarchical system graph called a tree. A distinctive feature of a tree is that there is only one path between any two of its vertices. The tree does not contain cycles or loops.

Typically, a tree representing a hierarchical system has one main vertex, which is called the root of the tree. Each vertex of the tree (except the root) has only one ancestor - the object designated by it is included in one top-level class. Any vertex of a tree can generate several descendants - vertices corresponding to classes of the lower level.

For each pair of tree vertices, there is a unique path connecting them. This property is used when finding all the ancestors, for example, in the male line, of any person whose pedigree is represented in the form of a family tree, which is a “tree” in the sense of graph theory.

Example of my family tree [Appendix Fig. 12].

One more example. The picture shows the biblical family tree [Appendix Fig. 13].

Problem solving

1.Transport task. Let there be a base in the city of Krasnodar with raw materials that need to be distributed to the cities of Krymsk, Temryuk, Slavyansk-on-Kuban and Timashevsk in one trip, spending as little time and fuel as possible and returning back to Krasnodar.

Solution:

First, let's make a graph of all possible travel routes [Appendix Fig.14], taking into account the real roads between these settlements and the distance between them. To solve this problem, we need to create another graph, a tree-like [Appendix Fig.15].

For the convenience of the solution, we designate the cities with numbers: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

The result is 24 solutions, but we only need the shortest paths. Of all the solutions, only two are satisfactory; this is 350 km.

Similarly, it is possible and, I think, necessary to calculate real transportation from one locality to another.

Logical problem involving transfusion. The bucket contains 8 liters of water, and there are two pans with a capacity of 5 and 3 liters. you need to pour 4 liters of water into a five-liter pan and leave 4 liters in the bucket, i.e. pour the water equally into the bucket and a large pan.

Solution:

The situation at any moment can be described by three numbers [Appendix Fig. 16].

As a result, we get two solutions: one in 7 moves, the other in 8 moves.

Conclusion

So, in order to learn how to solve problems, you need to understand what they are, how they are structured, what components they consist of, what are the tools with which problems are solved.

Solving practical problems using graph theory, it became clear that in every step, in every stage of their solution, it is necessary to apply creativity.

From the very beginning, at the first stage, it lies in the fact that you need to be able to analyze and encode the condition of the problem. The second stage is a schematic notation, which consists of a geometric representation of the graphs, and at this stage the element of creativity is very important because it is far from easy to find correspondences between the elements of the condition and the corresponding elements of the graph.

While solving a transport problem or a task of drawing up a family tree, I came to the conclusion that the graph method is certainly interesting, beautiful and visual.

I became convinced that graphs are widely used in economics, management, and technology. Graph theory is also used in programming. This was not discussed in this work, but I think it’s only a matter of time.

This scientific work examines mathematical graphs, their areas of application, and solves several problems using graphs. Knowledge of the basics of graph theory is necessary in various areas related to production and business management (for example, network construction schedule, mail delivery schedules). In addition, while working on a scientific paper, I mastered working on a computer using the WORD text editor. Thus, the objectives of the scientific work have been completed.

So, from all of the above, the practical value of graph theory irrefutably follows, the proof of which was the goal of this work.

Literature

Berge K. Graph theory and its applications. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Introduction to finite mathematics. -M.: IIL, 1963.

Ore O. Graphs and their application. -M.: Mir, 1965.

Harari F. Graph theory. -M.: Mir, 1973.

Zykov A.A. Finite graph theory. -Novosibirsk: Science, 1969.

Berezina L.Yu. Graphs and their application. -M.: Education, 1979. -144 p.

"Soros Educational Journal" No. 11 1996 (article "Flat graphs");

Gardner M. "Mathematical leisure", M. "World", 1972 (chapter 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Old entertaining problems”, M. “Science”, 1988 (part 2, section 8; appendix 4);

Application

Rice. 6

Rice. 7

Rice. 8

application

Application

Rice. 14

application

Application

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

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

and so on. 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).

Bibliography

Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Quantitative correlations of “structure properties” of alkanes. Additive calculation schemes. Tver, 1999. 96 p.
Chemical applications of topology and graph theory / Ed. R. King. M.: Mir, 1987. 560 p.
Application of graph theory in chemistry / Ed. N.S. Zefirov and S.I. Kuchanova. Novo-Sibirsk: Nauka, 1988. 306 p.
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.
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.
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.
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"

Graph theory. Chemical applications of topology and graph theory Application of graphs in various areas of human life

Bibliographic link

Methods for calculating topological indices

Protein networks

Bibliographic link

Password recovery