Graphs of road networks and algorithms for working with them. Mathematical model

Statement. If there is a route for two vertices connecting them, then there must be a minimal route connecting these vertices. Let's denote the length of this route asd(v,w).

Definition. the valued(v,w) (finite or infinite) will be called distance between vertices v, w . This distance satisfies the axioms of the metric:

1) d(v,w) 0, andd(v,w) = 0 if and only ifv=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Definition. diameter of a connected graph is the maximum possible distance between two of its vertices.

Definition. Center A graph is a vertex such that maximum distance between it and any other peak is the smallest of all possible; this distance is called radius graph.

Example 82.

For graph G shown in fig. 3.16, find the radius, diameter and centers.

Rice. 3.16. Count for example 82

Decision.

To determine the centers, radius, diameter of the graph G, find the matrix D(g) distances between graph vertices, elements dij which will be the distances between the vertices v i and vj. For this we use graphical representation graph. Note that the matrix D(g) symmetrical about the main diagonal.

Using the resulting matrix for each graph vertex G define the largest removal from the expression: for i,j = 1, 2, …, 5. As a result, we get: r(v1) = 3,r(v2) = 2,r(v3) = 2,r(v4) = 2,r(v5) = 3. The minimum of the obtained numbers is the radius of the graph G, the maximum is the diameter of the graph G. Means, R(G) = 2 and D(G) = 3, the centers are the vertices v 2 ,v 3 ,v 4.

Computing distances and determining paths in a graph is one of the most obvious and practical problems that arise in graph theory. Let us introduce some necessary definitions.

Eccentricity vertices of the graph - the distance to the vertex that is the most distant from it. For a graph for which it is not defined the weight its edges, the distance is defined as the number of edges.

Radius graph is the minimum eccentricity of the vertices, and diameter the graph is the maximum eccentricity of the vertices.

Centre graph form vertices whose eccentricity equal to the radius. The graph center can consist of one, several or all graph vertices.

Peripheral the vertices have an eccentricity equal to the diameter.

A simple chain with length equal to the diameter of the graph is called diametrical .

Theorem 12.1.In a connected graph, the diameter is at most the rank of its adjacency matrix.

Theorem 12.2.(Jordan) Every tree has a center consisting of one or two adjacent vertices.

Theorem 12.3.If the diameter of the tree is even, then the tree has a single center, and all diametrical chains pass through it; if the diameter is odd, then there are two centers and all diametrical chains contain an edge connecting them.

Obviously practical value the center of the graph. If, for example, we are talking about a road graph with vertices-cities, then in the mathematical center it is advisable to place administrative center, warehouses, etc. The same approach can be applied to a weighted graph, where the distances are the weights of the edges. As a weight, you can take the Euclidean distance, time or cost of movement between points.

Example 12.5. Find the radius, diameter and center of the graph shown in fig. 12.1.

Decision. In this problem, it is convenient to use distance matrix S. The element of this square symmetric matrix equal to the distance between top i and top j. For the graph shown in Fig. 12.1, the distance matrix has next view:

Let's calculate the eccentricity of each vertex. This value can be defined as the maximum element of the corresponding column of the distance matrix (or row, since the matrix S symmetrical). We get

Graph Radius r is the minimum eccentricity of the vertices. AT this case r= 2. Vertices No. 2, No. 4, and No. 5 have such an eccentricity. These vertices form the center of the graph. Graph diameter d is the maximum eccentricity of the vertices. In this case d= 3. Vertices No. 1 and No. 3 have such an eccentricity; this is the periphery of the graph. In the studied graph, the vertices turned out to be either central or peripheral. There are other vertices in graphs of higher order.

The eccentricities of the vertices of a small graph can be easily calculated by direct calculation from the figure. However, the graph is not always defined by its drawing. In addition, the graph may have big size. Therefore, another way of solving the previous problem is needed. The following theorem is known.

Theorem 12.4. Let be the adjacency matrix of the graph G without loops and , where . Then it is equal to the number of routes of length k from vertex to vertex .

Solving problems of graph theory using various transformations of the adjacency matrix is called algebraic method .

Example 12.6. Find the distance matrix of the graph shown in fig. 12.1, by the algebraic method.

Decision. The adjacency matrix of this graph is:

We will fill in the distance matrix by considering the degrees of the adjacency matrix. Adjacency matrix units show pairs of vertices that have a distance of one between them (that is, they are connected by a single edge).

The diagonal elements of the distance matrix are zeros. Multiply the adjacency matrix by itself:

According to the theorem between vertices 2 and 3, 1 and 4, etc. there are some routes of length 2 (because the degree of the matrix is two). The number of routes is not used here, the very fact of the existence of a route and its length are important, which is indicated by a non-zero element of the degree of the matrix, which does not coincide with the element noted when calculating a route of lesser length. We put 2 in the empty elements of the distance matrix and get next approximation:

The distance between vertices 1 and 3 remains unknown. We will multiply the adjacency matrix on itself until the matrix non-null element will not appear . Then the corresponding element of the distance matrix equal to the degree adjacency matrices: . At the next step, we get

hence, , and finally

The resulting matrix coincides with the distance matrix S(12.2) found by direct calculations from the figure.

Let G(V,X) be a pseudograph and let vertices v and w (v¹w) of this graph be connected by a route. Then there necessarily exists a minimal route connecting these vertices. Denote the length of this route d(v, w). We also set d(v, v) =0 for any vertex vнV; d(v, w) = ¥ if there is no route between v and w.

The value d(v,w) defined in this way for any vertices v and w of the graph G(V, X) is called the distance between v and w.

The number of distances in a graph with n vertices is equal to the number of combinations C n 2 .

Let the graph G(V,X) be connected. Let us define the following concepts for it:

Graph diameter: d(G) = maxd(v, w).

Eccentricity (maximum offset) of the vertex: r(v) = maxd(v, w);

Graph Radius: r(G) = min r(v);

Graph center: any vertex vОV such that r(v) = r(G).

The diameter of the graph, the eccentricities of the vertices, the radius of the graph, and the centers of the graph are called the metric characteristics of the graph.

Example. To find metric specifications the graph given by the diagram:

Let us find all distances, taking into account that d(v, w) = d(w, v).

The number of distances in the given graph С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Graph diameter d(G) =3.

Vertex eccentricities: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Graph radius r(G) = 2.

Graph centers v 2 , v 3 , v 4 .

3. Minimum routes in loaded graphs

A graph G(V, X) is called loaded if on the set of edges of the graph there is a function called a weight function that associates with each edge x нX of the graph some number l(x). The value l(x) is called the arc length.

The quantity l(x) can be given different meaning: transportation costs, travel time, distance between points, gasoline consumption, etc.

The sum of the lengths of the edges included in the route is called the length of the route.

Note that if for all x н X l(x) = 1, then the graph can be considered as unloaded.

A route in the graph G(V, X) from vertex v to vertex w (v¹w) is called minimal if it has the minimum length among all routes in graph G(V, X) from vertex v to vertex w.

We restrict ourselves to graphs for which l(x)>0.

When searching for the minimum route in a loaded graph with l(x)>0

we use the same statement as for an unloaded graph, namely:

any minimal route is a simple path.

Consider now the problem of finding the minimum route in a loaded graph.

Let the graph G(V,X) be loaded, the number of vertices n ³ 2, it is necessary to construct a minimal route from v 1 to v n .

Let's give an algorithm.

Step 1. Assign index a(v i) to each vertex: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Color the vertex v 1 and set v = v 1 .

Step 2. For each uncolored vertex v j change the index according to the rule:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Color the vertex for which a(v j) is the smallest.. also color the edge leading to the selected node. this step vertex v j . Put v = v j .

Step 3. If v = v j , finish the procedure since the shortest route from v 1 to v n . if v ¹ v n , then go to step 2.

Comment. Step 2 is impossible if all a(v j)= ¥. In this case, the vertex v n is unreachable.

Let us apply the above algorithm to the graph given by the diagram. Let's find in it the shortest route from v 1 to v 6 .

Step 1. Color the vertex v 1 . Assign indices to the vertices: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. We set v 1 = v.

a(v 2) = min(¥, 0+4) = 4,

a(v 3) = min(¥, 0+7) = 7,

a(v 4) = min(¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

We color the vertex v 4 and the edge (v 1 , v 4 ).

Step 3. Since the vertex v 6 is not colored, we perform step 2, setting v = v 4 .

a(v 2) = min(4, 3+¥) = 4,

a(v 3) = min(7, 3+¥) = 7,

a(v 5) = min(¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

We color the vertex v 2 and the edge (v 1 , v 2 ).

Step 3. Since the vertex v 6 is not colored, we perform step 2, setting v = v 2 .

a(v 3) = min(7, 4+3) = 7,

a(v 5) = min(6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

We color the vertex v 5 and the edge (v 4 , v 5 ).

Step 3. Since the vertex v 6 is not colored, we perform step 2, setting v = v 5 .

a(v 3) = min(7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

We color the vertex v 3 and the edge (v 1 , v 3 ).

Step 3. Since the vertex v 6 is not colored, we perform step 2, setting v = v 3 .

a(v 6) = min(8, 7+2) = 8.

We color the vertex v 6 and the edge (v 5 , v 6 ).

Since the vertex v 6 is colored, we stop the work. We got the minimum route v 1 v 4 v 5 v 6 , the length of which is equal to 8 .

Note that in this case this is not the only minimal route for vertices v 1 and v 6, because in the algorithm it was possible to color instead of the edge (v 4 , v 5 ) the edge (v 2 , v 5 ), then we would get another route of the same length.

4. Tasks on trees

A graph is called acyclic if there are no cycles.

A graph without cycles is called a forest.

A tree is a connected acyclic graph.

Computing distances and determining paths in a graph is one of the most obvious and practical problems that arise in graph theory. Let us introduce some necessary definitions.

Radius graph is the minimum eccentricity of the vertices, and diameter the graph is the maximum eccentricity of the vertices.

Centre The graph is formed by vertices whose eccentricity is equal to the radius. The graph center can consist of one, several or all graph vertices.

Peripheral the vertices have an eccentricity equal to the diameter.

A simple chain with length equal to the diameter of the graph is called diametrical .

Theorem 12.1.In a connected graph, the diameter is at most the rank of its adjacency matrix.

Theorem 12.2.(Jordan) Every tree has a center consisting of one or two adjacent vertices.

The practical significance of the center of the graph is obvious. If, for example, we are talking about a graph of roads with vertices-cities, then it is advisable to place the administrative center, warehouses, etc. in the mathematical center. The same approach can be applied to a weighted graph, where the distances are the weights of the edges. As a weight, you can take the Euclidean distance, time or cost of movement between points.

Example 12.5. Find the radius, diameter and center of the graph shown in fig. 12.1.

Decision. In this problem, it is convenient to use distance matrix S. The element of this square symmetric matrix is equal to the distance between the vertex i and top j. For the graph shown in Fig. 12.1, the distance matrix has the following form:

. (12.2)

Let's calculate the eccentricity of each vertex. This value can be defined as the maximum element of the corresponding column of the distance matrix (or row, since the matrix S symmetrical). We get

№

Graph Radius r is the minimum eccentricity of the vertices. In this case r= 2. Vertices No. 2, No. 4, and No. 5 have such an eccentricity. These vertices form the center of the graph. Graph diameter d is the maximum eccentricity of the vertices. In this case d= 3. Vertices No. 1 and No. 3 have such an eccentricity; this is the periphery of the graph. In the studied graph, the vertices turned out to be either central or peripheral. There are other vertices in graphs of higher order.

The eccentricities of the vertices of a small graph can be easily calculated by direct calculation from the drawing. However, the graph is not always defined by its drawing. In addition, the graph may be large. Therefore, another way of solving the previous problem is needed. The following theorem is known.

Theorem 12.4. Let be the adjacency matrix of the graph G without loops and , where . Then it is equal to the number of routes of length k from vertex to vertex .

Solving problems of graph theory using various transformations of the adjacency matrix is called algebraic method .

Example 12.6. Find the distance matrix of the graph shown in fig. 12.1, by the algebraic method.

Decision. The adjacency matrix of this graph is:

The diagonal elements of the distance matrix are zeros. Multiply the adjacency matrix by itself:

The distance between vertices 1 and 3 remains unknown. We will multiply the adjacency matrix on itself until the matrix non-null element will not appear . Then the corresponding element of the distance matrix is equal to the degree of the adjacency matrix: . At the next step, we get