Tashkent university of information technologies named after muhammad al-khorazmi, ministry of information technology and communication development of the republic of uzbekistan

Theorem #2

• 
  Theorem 2. If in a connected graph two vertices are odd and all the others are even, then this graph contains an Euler open circuit.
  

Unicursal lines

• 
  Any line that can be drawn, passing through the given areas exactly once, is called unicursal.
  
• 
  With regard to Euler graphs, to draw a unicursal line means to go along all the edges of the graph one time without lifting the pencil from the paper. For example, the following sequence is a closed unicursal line
  

.

Note: An open unicursal line always starts at an odd vertex and ends at another odd vertex.
If we start traversing a semi-Euler graph from an even vertex, then a unicursal line, neither closed nor open, cannot be constructed.
Euler graphs are sometimes called unicursal.
Theorem #3
Theorem 3. If a connected graph G contains 2k odd vertices, then it contains k open Euler paths that in the aggregate contain all the edges of the graph G exactly once.
Example: the graph in Figure contains four odd vertices, therefore, k = 2. When drawing it, the pencil will have to be torn off the paper once. If we start from top 1, we get two unicursal lines: 1,3,4,2,1,2,4 and 2,3.

Theorem #4
Theorem 4. In any connected graph, one can construct a closed route passing through each edge exactly twice.
Note: From Theorem 4 it follows that any graph can be depicted without lifting the pencil from the paper and passing along each edge no more than two times.
For example, the graph shown in Fig. 12, can be depicted as a sequence of vertices as follows: 1,2,4,2,1,3,2,3,4, whence it follows that the pencil passed twice only along the edge {2,3}.

The traveling salesman
A traveling salesman (in French: commisvoyageur) is a traveling representative of a large trading company, offering customers goods according to samples, catalogs, price lists.
The traveling salesman (traveling merchant) problem has two essentially different formulations. In the first, the question is posed as follows: “A traveling salesman wants to visit n certain cities; how should he move in order to enter each of them at least once, having completed the path of the smallest total length? " According to this formulation, a traveling salesman can visit certain cities more than once.
According to the second formulation, "he must visit each point exactly once and is interested in spending as little time as possible on the trip." In what follows, we will use the second formulation.
Euler graphs. It is well known that the formation of graph theory is related to the problem of Königsberg bridges. L. Euler proved in 1736 that this problem has no solution. He also found an answer to the following question, which is considered quite general in graph theory: under what conditions will a connected graph have a cycle that passes through all edges only once? A chain that passes through each edge of a graph only once is called an Euler chain. A graph with a closed Euler chain (that is, an Euler cycle) is called an Euler graph. If a non-closed Euler chain is found in a graph, then such a graph is called a semi-Eulerian graph. It is possible to search for a directed Euler path in directed graphs. A path that passes through each arc only once is called an oriented Euler path. An oriented graph containing an oriented Euler path is called an oriented Euler graph
Now we present Flory's algorithm for constructing an Euler chain in a given Euler graph with the number of edges equal to n. According to this algorithm, the edges of the graph are numbered from l to n according to the order of occurrence in the Euler cycle. It is proved that operation according to Flory's algorithm is always a finite process for the Euler graph, and this process always ends with the removal of all edges from the graph, that is, the creation of an Euler chain. It should also be noted that in the process of using the Fleury algorithm, since there are many options for choosing edges, in such situations, the application of the algorithm is limited to finding one of the existing Euler cycles. It is clear that by repeating the Flory algorithm (in this case, the edge selection process should not be repeated exactly as in the previous applications) all the Euler cycles that exist in the graph can be found.
We determine one of the Euler cycles for the given graph using the Flory algorithm. Let the first point be the point 1 in the graph. It is possible to move form 1 in two third directions: along (1;2) edge or along (1;4) edge. For example, we move along the edge (1;2) and move to a point with 2 characters. Now the movement can be continued in 3 directions: either along the (2;3) edge, or along the (2;4) edge, or along the (2;5) edge. Let's say that we move along the edge (2;3) and move to a 3-digit point. Continuing in this way, we form one of the possible Euler cycles, for example, the following cycle: ((1,2), (2,3), (3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5), (5,8), (8,7), (7,5), (5,2), (2 ,4 ), (4,1)). Example 1. Let's look at the graph shown in figure 1. First of all, we check the condition that this graph is an Euler graph, i.e., the conditions of Theorem 1 are fulfilled.
nV = 4 INF = 999 def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) for k in range(nV): for i in range (nV): for j in range(nV): distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) print_solution(distance) def print_solution(distance): for i in range(nV): for j in range(nV): if(distance[i][j] == INF): print("INF", end=" ") else: print (distance[i][j], end=" ") print(" ") G = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF ], [INF, INF, 2, 0]] floyd_warshall(G)
General information about routes and chains. Let there be an undirected graph G = (V,U) with set of vertices V = {v1;v2,...,vm} and tuple of edges U — {u1,u2,...,un}. A finite or infinite sequence of vertices and edges in this graph G in the form (…,vi,ui,vi2,ui2,vi3,..) where both adjacent edges have a common edge is called a route. A route can also be specified as a sequence of its vertices (...,vj1,vj2,...) or as a sequence of edges (...,uj1,uj2,...) If the route has no vertices before any vertex , this vertex is called the initial vertex of the route, and if there are no vertices belonging to the route after this vertex, it is called the last vertex of the route. If the initial vertex of the route is vp and the last vertex is vq, then it is is called a connected route or a route with edges vp and vq.
The triangle corresponding to two adjacent edges in the route is called an internal vertex or an intermediate vertex. Since edges and vertices can be repeated in a route, the inner end of a route can simultaneously be its start and/or end end, and vice versa, the start and/or end end of a route can be its inner end. it is also possible. Naturally, a route: - may not have a start point or an end point (such a route is called a two-way infinite route); - may have a start point and no end point or, on the contrary, may have an end point and no start point (one-way infinite route); - can consist of a single edge (non-trivial route); -may not have any edges (zero route or trivial route). The length of a route is the number of edges in it. A route consisting of different edges is called a chain.