Graph theory history of origin. History of the emergence and development of graph theory. Graph theory and the most important modern applied problems

GRAPHS

Many problems come down to considering a set of objects, the essential properties of which are described by the connections between them. For example, looking at a road map, one may only be interested in whether there is a connection between certain settlements, ignoring the configuration and quality of roads, distances and other details. When studying electrical circuits, the nature of the connections of its various components - resistors, capacitors, sources, etc. may come to the fore. Organic molecules form structures whose characteristic properties are connections between atoms. Of interest may be various connections and relationships between people, events, states and, in general, between any objects.

In such cases, it is convenient to depict the objects under consideration as points, and the connections between them as lines of arbitrary configuration. Such a formalized image is called a graph (from the Greek grajw - I write).

Rice. 4.1 .

The first work on graphs was published by twenty-year-old Leonhard Euler in 1736, while he was working at the Russian Academy of Sciences. It contained a solution to the problem of the Königsberg bridges (Fig. 4.1a): is it possible to take a walk in such a way that, leaving any place in the city, you can return to it by walking exactly once over each bridge? It is clear that according to the conditions of the problem, it does not matter how the path passes through parts of the land a, b, c, d, on which the city of Koenigsberg (now Kaliningrad) is located, so they can be represented as vertices. And since the connections between these parts are carried out only through seven bridges, each of them is represented by an edge connecting the corresponding vertices. As a result, we obtain the graph shown in Fig. 4.1b. Euler gave a negative answer to the question posed. Moreover, he proved that such a route exists only for a graph such that each of its vertices is connected to an even number of edges.

Graph theory received its next impetus almost 100 years later with the development of research in electrical networks, crystallography, organic chemistry and other sciences. Along with numerous puzzles and graph games, important practical problems were considered, many of which required sophisticated mathematical techniques. Already in the middle of the last century, Kirchhoff used graphs to analyze electrical circuits, and Cayley explored an important class of graphs for identifying and listing isomers of saturated hydrocarbons. However, graph theory as a mathematical discipline was formed only in the mid-thirties of the last century thanks to the work of many researchers, the greatest merit among whom belongs to D. Koenig. Significant contributions to graph theory were made by Soviet scientists L. S. Pontryagin, A. A. Zykov, V. G. Vising and others.

Without even noticing it, we encounter graphs all the time. For example, a graph is a diagram of subway lines. The dots on it represent stations, and the lines represent train routes. By researching our ancestry and tracing it back to our ancestors, we build a family tree. And this tree is a graph.

Graphs serve as a convenient means of describing relationships between objects. For example, by considering a graph depicting a network of roads between populated areas, you can determine the route from point A to point B. If there are several such routes, you would like to choose the optimal one in a certain sense, for example the shortest or the safest. To solve the selection problem, it is necessary to carry out certain calculations on graphs. When solving such problems, it is convenient to use algebraic techniques, and the very concept of a graph needs to be formalized.

Graph theory has a powerful tool for solving applied problems from a wide variety of fields of science and technology. This includes, for example, the analysis and synthesis of circuits and systems, the design of communication channels and the study of information transfer processes, the construction of contact circuits and the study of finite state machines, network planning and control, operations research, the selection of optimal routes and flows in networks, the study of random processes and many other tasks. Graph theory is closely related to such branches of discrete mathematics as set theory, matrix theory, mathematical logic and probability theory.

Currently, graph theory covers a lot of material, but when presenting it we will limit ourselves to only part of it and, omitting numerous theorems, we will consider only a few basic concepts.

Leonard Euler is considered the founder of graph theory. In 1736, in one of his letters, he formulated and proposed a solution to the problem of the seven Königsberg bridges, which later became one of the classical problems of graph theory.

The first problems in graph theory were related to solving mathematical recreational problems and puzzles. Here is a retelling of an excerpt from Euler’s letter dated March 13, 1736: “I was given a problem about an island located in the city of Königsberg and surrounded by a river with 7 bridges across it. 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 in any way or not.” The Königsberg bridges can be schematically depicted as follows:

Euler's rule:

1. In a graph that does not have vertices of odd degrees, there is a traversal of all edges (and each edge is traversed exactly once) starting at any vertex of the graph.

2. In a graph that has two and only two vertices with odd degrees, there is a traversal that starts at one vertex with odd degree and ends at the other.

3. In a graph that has more than two vertices with odd degrees, such a traversal does not exist.

There is another type of problem related to traveling along graphs. We are talking about problems in which it is necessary to find a path passing through all vertices, and no more than once through each. A cycle that passes through each vertex once and only once is called a Hamiltonian line (after William Rowan Hamilton, the famous Irish mathematician of the last century who was the first to study such lines). Unfortunately, a general criterion has not yet been found with the help of which one could decide whether a given graph is Hamiltonian, and if so, then find all Hamiltonian lines on it.

Formulated in the mid-19th century. The four color problem also looks like an entertaining problem, but attempts to solve it have led to some graph studies that have theoretical and applied significance. The four-color problem is formulated as follows: “Can an area of ​​any flat map be colored with four colors so that any two adjacent areas are colored with different colors?” The hypothesis that the answer is affirmative was formulated in the mid-19th century. In 1890, a weaker statement was proven, namely that any flat map can be colored in five colors. By associating any planar map with its dual planar graph, we obtain an equivalent formulation of the problem in terms of graphs: Is it true that the chromatic number of any planar graph is less than or equal to four? Numerous attempts to solve the problem influenced the development of a number of areas of graph theory. In 1976, a positive solution to the problem using a computer was announced.

Another old topological problem that has been particularly resistant to solution for a long time and has haunted the minds of puzzle lovers is known as the “electricity, gas and water supply problem.” In 1917, Henry E. Dudeney gave it this formulation. Gas, electricity and water must be installed in each of the three houses shown in the figure.

Graph theory. 1

The history of the emergence of graph theory. 1

Euler's rule. 1

Literature

1. Belov Graph Theory, Moscow, "Science", 1968.

2. New pedagogical and information technologies E.S. Polat , Moscow, "Akademia" 1999

3. Kuznetsov O.P., Adelson-Velsky G.M. Discrete mathematics for the engineer. – M.: Energoatomizdat, 1988.

4. Cook D., Baze G. Computer mathematics. – M.: Science, 1990.

5. Nefedov V.N., Osipova V.A. Discrete mathematics course. – M.: MAI Publishing House, 1992.

6. Ore O. Graph theory. – M.: Science, 1980.

7. Ismagilov R.S., Kalinkin A.V. Materials for practical lessons in the course: Discrete Mathematics

Graph theory- chapter discrete mathematics, studying properties graphs . In a general sense, a graph is represented as a set of vertices (nodes) connected by edges. In a strict definition, such a pair of sets is called a graph. G=(V,E), where V is a subset of any countable set, and E is a subset of V×V.

History of graph theory
Leonard Euler is considered the founder of graph theory. In 1736, in one of his letters, he formulated and proposed a solution to the problem of the seven Königsberg bridges, which later became one of the classical problems of graph theory.
The first problems in graph theory were related to solving mathematical recreational problems and puzzles. Here is a retelling of an excerpt from Euler’s letter dated March 13, 1736: “I was given a problem about an island located in the city of Königsberg and surrounded by a river with 7 bridges across it. 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 in any way or not.” The Königsberg bridges can be schematically depicted as follows:
Euler's rule:

1. In a graph that does not have vertices of odd degrees, there is a traversal of all edges (and each edge is traversed exactly once) starting at any vertex of the graph.
2. In a graph that has two and only two vertices with odd degrees, there is a traversal that starts at one vertex with odd degree and ends at the other.
3. In a graph that has more than two vertices with odd degrees, such a traversal does not exist.

2016 academic year Year

1. Introduction

2. History of the emergence of graph theory

3. Basic concepts of graph theory

4. Basic theorems of graph theory

5. Methods of representing graphs in a computer

6. Review of graph theory problems

7. Conclusion

8. References

Introduction

Recently, research in areas traditionally related to discrete mathematics has become increasingly prominent. Along with such classical sections of mathematics as mathematical analysis and differential equations, sections on mathematical logic, algebra, combinatorics and graph theory have appeared in the curricula of the specialty “Applied Mathematics” and many other specialties. The reasons for this are not difficult to understand by simply identifying the range of problems solved on the basis of this mathematical apparatus.

The history of the emergence of graph theory.

1. Problem about the Königsberg bridges. In Fig. 1 shows a schematic plan of the central part of the city of Koenigsberg (now Kaliningrad), including two banks of the Pergola River, two islands in it and seven connecting bridges. The task is to go around all four parts of the land, crossing each bridge once, and return to the starting point. This problem was solved (it was shown that there was no solution) by Euler in 1736.

rice. 1

2. The problem of three houses and three wells. There are three houses and three wells, somehow located on a plane. Draw a path from each house to each well so that the paths do not intersect (Fig. 2). This problem was solved (it was shown that there is no solution) by Kuratovsky in 1930.

rice. 2

3. The four color problem. A division of a plane into non-overlapping areas is called a map. Areas on a map are called adjacent if they have a common border. The task is to color the map in such a way that no two adjacent areas are painted with the same color (Fig. 3). Since the end of the century before last, the hypothesis has been known that four colors are enough for this. In 1976, Appel and Heiken published a solution to the four-color problem, which was based on a computer search. The solution to this problem “programmatically” was a precedent that gave rise to a heated debate, which is by no means over. The essence of the published solution is to try a large but finite number (about 2000) types of potential counterexamples to the four-color theorem and show that not a single case is a counterexample. This search was completed by the program in about a thousand hours of supercomputer operation. It is impossible to check the resulting solution “manually” - the scope of enumeration goes far beyond human capabilities. Many mathematicians raise the question: can such a “program proof” be considered a valid proof? After all, there may be errors in the program... Methods for formally proving the correctness of programs are not applicable to programs of such complexity as the one being discussed. Testing cannot guarantee the absence of errors and in this case is generally impossible. Thus, we can only rely on the programming skills of the authors and believe that they did everything right.

Rice. 3

Basic concepts of graph theory

1) Graph G(V,E) is a collection of two sets – a non-empty set V (set of vertices) and a set E of two-element subsets of the set V (E – set of edges).

2) Oriented is a graph in which is a set of ordered pairs of vertices of the form (x,y), where x is called the beginning, and y is the end of the arc. The arc (x, y) is often written as . They also say that the arc leads from vertex x to vertex y, and vertex y adjacent with vertex x.

3) If an element of the set E can be a pair identical(not distinct) elements of V, then such an element of the set E is called loop, and the graph is called graph with loops(or pseudograph).

4) If E is not a set, but set containing several identical elements, then these elements are called multiple edges, and the graph is called multigraph.

5) If the elements of the set E are not necessarily two-element, but any subsets of the set V, then such elements of the set E are called hyperarcs, and the graph is called hypergraph.

6) If the function is specified F: V → M and/or F: E → M, then the set M called a set notes, and the graph is called marked(or loaded). The set of marks is usually letters or integers. If the function F is injective, that is, different vertices (edges) have different labels, then the graph is called numbered.

7) Subgraph is called the graph G′(V′,E′), where and/or .

a) If V′ = V, then G′ is called core subgraph G.

b) If , then the graph G′ is called own subgraph of graph G.

c) A subgraph G′(V′,E′) is called a regular subgraph of the graph G(V,E) if G′ contains all possible edges of G.

8) Degree (valence) vertices is the number of edges incident to this vertex (the number of vertices adjacent to it).

9) Route in a graph is an alternating sequence of vertices and edges in which any two adjacent elements are incident.

a) If , then the route closed, otherwise open.

b) If all edges are different, then the route is called chain.

c) If all vertices (and therefore edges) are different, then the route is called simple chain.

d) A closed circuit is called cycle.

e) A closed simple circuit is called simple loop.

f) A graph without cycles is called acyclic.

g) For digraphs, the chain is called by, and the cycle is outline.

rice. 4. Routes, chains, cycles

Example

In the graph, the diagram of which is shown in Fig. 4:

1. v 1, v 3, v 1, v 4 – a route, but not a chain;

2. v 1, v 3, v 5, v 2, v 3, v 4 – a chain, but not a simple chain;

3. v 1, v 4, v 3, v 2, v 5 – simple chain;

4. v 1, v 3, v 5, v 2, v 3, v 4, v 1 – a cycle, but not a simple cycle;

5. v 1, v 3, v 4, v 1 – a simple cycle.

10) If a graph has a cycle (not necessarily simple) containing all the edges of the graph once, then such a cycle is called Eulerian cycle.

11) If a graph has a simple cycle containing all the vertices of the graph (once at a time), then such a cycle is called Hamiltonian cycle.

12) tree called a connected graph without cycles.

13) skeleton A tree containing all the vertices of a graph is called.

14) Matching is a set of edges in which no two are adjacent.

15) The matching is called maximum, if no superset of it is independent.

16) Two vertices in a graph connected, if there is a simple chain connecting them.

17) A graph in which all vertices are connected is called coherent.

18) A graph consisting only of isolated vertices is called quite incoherent.

19) Route length the number of edges in it is called (with repetitions).

20) Distance between vertices u and v is called the length of the shortest chain, and the shortest chain itself is called geodetic.

21) Diameter of a graph G is called the length of the longest geodesic.

22) Eccentricity vertex v in a connected graph G(V,E) is the maximum distance from vertex v to other vertices of the graph G.

23) Radius of a graph G is called the smallest of the eccentricities of the vertices.

24) Vertex v is called central, if its eccentricity coincides with the radius of the graph.

25) The set of central vertices is called center graph.

rice. 5 Eccentricities of vertices and centers of graphs (highlighted).

Related information.

Graph theory finds application, for example, in geographic information systems (GIS). Existing or newly designed houses, structures, blocks, etc. are considered as vertices, and the roads, utility networks, power lines, etc. connecting them are considered as edges. The use of various calculations performed on such a graph allows, for example, to find the shortest detour route or the nearest grocery store, or to plan the optimal route.

Graph theory contains a large number of unsolved problems and as yet unproven hypotheses.

History of graph theory

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

Graph theory terminology

Application of graph theory

see also

Notes

Literature

• Distel R. Graph theory Trans. 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. - P. 422.
• Basaker R., Saati T. Finite graphs and networks. M.: Nauka, 1974. 368c.
• Belov V.V., Vorobyov E.M., Shatalov V.E. Graph theory. - M.: Higher. school, 1976. - P. 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. 384 p. (Ed. 2, revised M.: URSS, 2009. 392 p.)