4. Counts 4.1. The origin of the graphs

Many tasks are reduced to the consideration of a set of objects, the essential properties of which are described by the relations between them. For example, looking at a road map, you can only be interested in whether there is a connection between some localities, distracting from the configuration and quality of roads, distances and other details. When studying electrical circuits, the nature of the compounds of its various components — resistors, capacitors, sources, etc. — can act to the fore. Organic molecules form structures whose characteristic properties are bonds between atoms. Different connections and relations between people, events, states and in general between any objects can be of interest.

In such cases it is convenient to depict the objects in question as points, and the relations between them as lines of arbitrary configuration. Such a formalized image is called a graph (from the Greek  - I write).

but. b

Fig. 4.1 .

The first work on the graphs was published by a twenty-year-old Leonard Euler in 1736, when he worked in the Russian Academy of Sciences. It contained a solution to the problem of the Koenigsberg bridges (Fig. 4.1a): is it possible to make a walk in such a way that, after leaving any place in the city, to return to it, passing exactly once on each bridge? It is clear that, according to the condition of the problem, it does not matter how it goes along parts of the land a, b, c, d on which the city of Königsberg is located (now Kaliningrad), so they can be represented as vertices. And since the connections between these parts are made 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. Moreover, he proved that such a route exists only for such a graph, each of the vertices of which is associated with an even number of edges.

The next impulse was the theory of graphs almost 100 years later with the development of research on electrical networks, crystallography, organic chemistry and other sciences. Along with numerous puzzles and graph games, important practical problems were considered, many of which required subtle mathematical methods. Already in the middle of the last century, Kirchhoff applied graphs to analyze electrical circuits, while Cayley investigated an important class of graphs to identify and list 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 of which belongs to D. Koenig. Soviet scientists L. S. Pontryagin, A. A. Zykov, V. G. Vizing, and others contributed significantly to the theory of graphs.

With graphs, without even noticing, we face constantly. For example, a graph is a metro line pattern. The dots on it are stations, and the lines are the train routes. Investigating our ancestry and elevating it to our ancestors, we are building a family tree. And this tree is a graph.

Graphs are a convenient means of describing the connections between objects. For example, considering a graph depicting a network of roads between settlements, it is possible to determine the route from point A to point B. If there are several such routes, I would like to choose the optimal one in a certain sense, for example, the shortest or safest. To solve the problem of choice, it is necessary to perform certain calculations on graphs. When solving such problems, it is convenient to use algebraic techniques, and the very concept of a graph must be formalized.

Graph theory has a powerful apparatus for solving applied problems from various fields of science and technology. These include, 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 diagrams and the study of finite automata, network planning and control, research of operations, the choice of optimal routes and flows in networks, the study of random processes other tasks. Graph theory is closely related to such sections of discrete mathematics as set theory, matrix theory, mathematical logic, and probability theory.

At present, graph theory covers a large amount of material, but in presenting it we will restrict ourselves to only a part of it and, omitting numerous theorems, consider only some basic concepts.