Graph Theory

Graph theory is one of the subsections of mathematics, the main distinguishing feature of which is the geometric method in the study of objects. The founder of it is considered to be the famous mathematician L. Euler.

The application of the theory of graphs to the end of the 19th century was reduced to solving entertaining problems and did not attract significant general attention. Since the 20th century, when the theory of graphs has developed into an independent mathematical discipline, it has found wide application in such fields of science as cybernetics, physics, logistics, programming, biology, electronics, transport and communication systems.

Basic concepts of graph theory

The graph is the basic one. In terminology, one can come across such a concept as a network identical to a graph. The latter is a non-empty number of points, that is, vertices, and segments, that is, edges, both ends of which correspond to a given number of points. The graph theory does not make a definite sense in the values of edges and vertices. For example, cities and the roads connecting them, where the first are the tops of the graph, and the second - the edges. More importance in theory is given to arcs. If the edge has a direction, then it has the name of an arc, if the graph is with oriented edges, it is called the digraph.

In the terminology of the theory, the following concepts also stand out:

A subgraph is a graph, all edges and vertices of which are among vertices and edges.

A connected graph is one that has a chain connecting them for two different vertices.

A weighted connected graph is one whose weight function is given.

A tree is a connected graph without cycles.

The skeleton is a subgraph that is a tree.

When a graph is drawn on the plane, a certain notation is used: the selected vertex corresponds to a point on the simplest surface, and if there is an edge between the vertices, then the corresponding points are joined by a segment. If the graph is oriented, these segments are replaced by arrows.

But do not compare the image of the graph with it, that is, with an abstract structure, because one graph can be given more than one graphical representation. A drawing on the plane is given in order to see which pairs of vertices are joined by edges and which are not.

Among some problems of graph theory, there are:

1. The task of the shortest chain (replacement of equipment, placement of ambulance and telephone stations).
2. The problem of the maximum flow (the ordering of traffic in a dynamic network, the distribution of work, the organization of capacity).
3. The task of coatings and packaging (placement of dispatching points).
4. Coloring in graphs (placement of memory on electronic computers).
5. Communication of networks and graphs (creation of a communication network, analysis of communication networks).

At present, it is impossible to program most of the problems without knowing the theory of graphs. This makes it easier and easier to work with a computer.

Programming uses a lot of structures and universal methods for solving problems, and one of them is graph theory. Its value is difficult to overestimate. The graph theory in programming makes it easy to find information, optimize programs, convert and distribute data. Thanks to the algorithms of the theory, it becomes possible to apply and evaluate them in use for solving specific problems, to modify the algorithm without reducing the degree of mathematical certainty of the final version of the program.

An important property of a control system or model is the set of binary relations in the collection of actions and data units. These structures are the only parts of the programs and the information that they convert. Therefore, graphs are the basis of the construction for the programmer.