Graph theory

Count with six peaks and seven edges

Graph theory is a section of discrete mathematics that studies the properties of graphs . In a general sense, a graph is represented as a set of vertices (nodes) connected by edges . In a strict definition, a graph is a pair of sets $G=(V,E)$ ${\ displaystyle G = (V, E)}$ $G = (V, E)$ where $V$ ${\ displaystyle V}$ $V$ there is a subset of any countable set , and $E$ ${\ displaystyle E}$ $E$ - subset $V\times V$ ${\ displaystyle V \ times V}$ $V \ times V$ .

Graph theory is used, for example, in geographic information systems (GIS). Existing or newly designed houses, structures, quarters, etc. are considered as peaks, and the roads connecting them, utility networks, power lines , etc. - as ribs. The use of various calculations performed on such a graph allows, for example, finding the shortest bypass route or the nearest grocery store, planning the optimal route.

Graph theory contains a large number of unsolved problems and not yet proven hypotheses.

Content

1 History of graph theory
2 Terminology of graph theory
3 Image of graphs on a plane
4 Some problems of graph theory
5 Application of graph theory
6 See also
7 notes
8 Literature
9 References

Graph theory history

The founder of graph theory is considered Leonard Euler . In 1736, in one of his letters, he formulated and proposed a solution to the problem of seven Konigsberg bridges , which later became one of the classical problems of graph theory. The term "earl" was first coined by Sylvester, James Joseph in 1878 in his article in Nature .

Graph Theory Terminology

The terminology of graph theory is still not strictly defined. In particular, the monograph by Goodman, Khidniemi, 1981 says: “In the programmer world there is no consensus on which of the two terms is“ graph “or“ network “. We chose the term “network”, as it seems to be more common in applied fields. ” A similar situation with the terms " peak / point ".

Types of graphs:

non-oriented ( non- graph)

oriented (digraph)

Image graphs on the plane

When depicting graphs in figures, the following notation is most often used: the vertices of the graph are represented by dots or, when specifying the meaning of the vertex, by rectangles, ovals, etc., where the meaning of the vertex is revealed inside the figure (graphs of flowcharts of algorithms ). If there is an edge between the vertices, then the corresponding points (figures) are connected by a line or an arc. In the case of a directed graph, the arcs are replaced by arrows, they clearly indicate the direction of the edge. Sometimes explanatory inscriptions are placed next to the edge, revealing the meaning of the edge, for example, in the transition graphs of finite automata . Distinguish between planar and non-planar graphs. A planar graph is a graph that can be depicted in a figure (plane) without intersecting edges (the simplest is a triangle or a pair of connected vertices), otherwise the graph is not planar. In the event that the graph does not contain cycles (containing at least one path of a single traversal of edges and vertices with a return to the original vertex), it is usually called a "tree" . Important types of trees in graph theory are binary trees, where each vertex has one incoming edge and exactly two outgoing edges, or is the final one - without outgoing edges and contains one root vertex into which there is no incoming edge.

The image of the graph itself should not be confused with the graph (abstract structure), since more than one graphical representation can be associated with one graph. The image is intended only to show which pairs of vertices are connected by edges and which are not. In practice, it is often difficult to answer the question whether two images are models of the same graph or not (in other words, whether the graphs corresponding to the images are isomorphic ). Depending on the task, some images can give a more visual picture than others.

Some problems of graph theory

The problem of the seven Konigsberg bridges is one of the first results in graph theory, published by Euler in 1736 .
The problem of four colors - was formulated in 1852 , but non-classical proof was obtained only in 1976 (4 colors are enough for a map on a sphere (plane)).
The salesman problem is one of the most well - known NP-complete problems.
The click problem is another NP-complete problem.
Finding the minimum tightening (spanning) tree .
Isomorphism of graphs - is it possible by renumbering the vertices of one graph to get another.
Graph planarity - is it possible to depict a graph on a plane without intersecting edges (or with a minimum number of layers, which is used when tracing interconnects of elements of printed circuit boards or microcircuits).

Graph theory also includes a number of mathematical problems that have not been solved to date .

Application of graph theory

In chemistry (to describe structures, paths of complex reactions ^[1] , the phase rule can also be interpreted as a problem in graph theory); computer chemistry is a relatively young field of chemistry, based on the application of graph theory. Graph theory is the mathematical basis of chemoinformatics . Graph theory allows you to accurately determine the number of theoretically possible isomers of hydrocarbons and other organic compounds.
In computer science and programming ( graph-diagram of the algorithm , automata ) ^[2]
In communication and transport systems. In particular, for routing data on the Internet .
In economics ^[3]
In logistics
In circuitry (the topology of interconnections of elements on a printed circuit board or microcircuit is a graph or a hypergraph ) ^[4] .

Notes

↑ G.S. Yablonsky, V.I. Bykov, A.N. Gorban, Kinetic models of catalytic reactions , Novosibirsk: Nauka (Sib. Branch), 1983.- 255 p.
↑ Evstigneev V.A. Application of graph theory in programming. - M., Science , 1985. - Circulation of 20,000 copies. - 352 c.
↑ Eremenko A. O. Using graph theory to solve problems in economics // Progressive technologies and economics in mechanical engineering: proceedings of the VII All-Russian Scientific and Practical Conference for Students and Young Students, Yurga, April 7-9, 2016: in 2 t. - Tomsk: TPU Publishing House. - 2016 .-- T. 2 . - S. 279-281 .
↑ Kureichik V.M., Glushan V.M., Scherbakov L.I. Combinatorial hardware models and algorithms in CAD. M .: Radio and communications, 1990.216 s.

Literature

Distel R. Graph Theory Per. from English - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - 336 p. ISBN 5-86134-101-X .
Diestel R. Graph Theory, Electronic Edition . - NY: Springer-Verlag, 2005 .-- S. 422.
Basaker R., Saati T. Finite graphs and networks. M .: Nauka, 1974.368c.
Belov V.V., Vorobev E.M., Shatalov V.E. Graph theory. - M .: Higher. School, 1976 .-- S. 392.
Berge K. Graph theory and its applications. M .: IL, 1962.320c.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on graph theory. M .: Nauka, 1990.384s. (Vol. 2, rev. M .: URSS, 2009.392 s.)
Zykov A.A. Fundamentals of graph theory . - M .: "University Book" , 2004. - S. 664. - ISBN 5-9502-0057-8 . (M .: Nauka, 1987.383c.)
Chemical applications of topology and graph theory. Ed. R. King. Per. from English M .: Mir, 1987.
Kirsanov M.N. Counts in Maple. M .: Fizmatlit, 2007.168 p. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/en/library/books/Kirsanov2007ru.pdf
Christofides N. Graph Theory. Algorithmic approach. M .: Mir, 1978. 429c.
Kormen T.Kh. et al. Part VI. Algorithms for working with graphs // Algorithms: construction and analysis = Introduction to Algorithms. - 2nd ed. - M .: Williams , 2006 .-- S. 1296. - ISBN 0-07-013151-1 .
Ore O. Graph Theory . - 2nd ed. - M .: Nauka , 1980 .-- S. 336.
Saliy V.N. Bogomolov A.M. Algebraic foundations of the theory of discrete systems . - M .: Physical and mathematical literature, 1997. - ISBN 5-02-015033-9 .
Swami M., Thulasiraman K. Graphs, networks and algorithms. M: Mir, 1984.
Tutt W. Graph Theory. Per. from English M.: Mir, 1988.442 s.
Wilson R. Introduction to Graph Theory. Per from English. M .: Mir, 1977.208s.
Harari F. Graph Theory . - M .: Mir , 1973. (Ed. 3, M .: KomKniga, 2006 .-- 296 p.)
Harari F., Palmer E. Enumeration of Counts . - World , 1977.
Sergey Melnikov. Sim and Cram under the "electron microscope" // Science and Life . - 1996. - Vol. 3 . - S. 144-145 . The article is about the game on the Count Sim, invented by Gustav Simmons.

Links

WikiGrapp - Explanatory Dictionary of Graph Theory
Algorithms and short descriptions of C ++ programs
Discrete mathematics, algorithms, applets, graph visualization
Graphs in chemistry
Intelligent Graph Visualizer (automatic placement on the plane, search for the shortest path, search for the center, etc.)
Graph Theory Software
Visual Graph : a program that provides the user with a wide range of tools and methods for visualizing and finding information in graphs

[1] G.S. Yablonsky, V.I. Bykov, A.N. Gorban, Kinetic models of catalytic reactions , Novosibirsk: Nauka (Sib. Branch), 1983.- 255 p.

[2] Evstigneev V.A. Application of graph theory in programming. - M., Science , 1985. - Circulation of 20,000 copies. - 352 c.

[3] Eremenko A. O. Using graph theory to solve problems in economics // Progressive technologies and economics in mechanical engineering: proceedings of the VII All-Russian Scientific and Practical Conference for Students and Young Students, Yurga, April 7-9, 2016: in 2 t. - Tomsk: TPU Publishing House. - 2016 .-- T. 2 . - S. 279-281 .

[4] Kureichik V.M., Glushan V.M., Scherbakov L.I. Combinatorial hardware models and algorithms in CAD. M .: Radio and communications, 1990.216 s.