Graph theory is one of the branches of mathematics whose main distinguishing feature is the geometric method in the study of objects. The founder of it is considered to be the famous mathematician L. Euler.
The use of graph theory until the end of the 19th century was reduced to solving entertaining problems and did not attract significant general attention. Starting from the 20th century, when graph theory was formed into an independent mathematical discipline, it 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 base is a graph. 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. Graph theory does not make any sense in the values of edges and vertices. For example, cities and roads connecting them, where the first are the vertices of the graph, and the second are the edges. Greater importance in theory is given to arcs. If an edge has a direction, then it has the name of an arc, if a graph with oriented edges, it is called a digraph.
In the terminology of the theory, the following concepts are also distinguished:
A subgraph is a graph whose all edges and vertices are among the vertices and edges.
A connected graph is one with a chain connecting them for two different vertices.
A weighted connected graph is one with a weight function.
A tree is a connected graph, without cycles.
A skeleton is a subgraph that is a tree.
When plotting a graph on a plane, a certain notation system 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 the abstract structure, because more than one graphic representation can be given to one graph. The 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:
- The task of the shortest chain (replacement of equipment, placement of ambulances and telephone exchanges).
- The problem of maximum flow (streamlining traffic in a dynamic network, work distribution, bandwidth organization).
- The problem of coatings and packaging (placement of control centers).
- Coloring in graphs (memory allocation on electronic computers).
- Communication networks and graphs (creating a communication network, analysis of communication networks).
It is currently impossible to program most tasks without knowledge of graph theory. This facilitates and simplifies work with computers.
Programming uses many structures and universal methods for solving problems, and one of them is graph theory. Its value is difficult to overestimate. 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 use and evaluate them to solve specific problems, modify the algorithm without reducing the degree of mathematical reliability of the final version of the program.
An important property of a control system or model is the combination of binary relations in a set of actions and data units. These structures are the only parts of programs and the information that they transform. Therefore, graphs are the basis of the construction for the programmer.