In other words, if you traverse the graph, you must repeatedly pass through some edges.
To commemorate Euler, a loop containing all nodes and edges of G in a graph is called Euler path, and a path containing all nodes and edges of G is called Euler path.
In other words, if the Euler path is closed, it becomes an Euler path.
Pay attention to the concept of loop: the length from v i to v i is not zero and there is no path with repeated edges.
Therefore, the seven bridges in Connaugsburg mentioned above are not Euler paths.
The prerequisite for the existence of Euler path in graph G is:
Regarding whether there is an Euler path in the graph, two concepts need to be explained first:
Due to the nature of Euler path: each edge can only pass once, so for each node, at least 2n edges are needed to connect the node (n = 0, 1, 2, ... n). When n = 0, G contains only one node V, so the path (V) is called the Euler path of G.
That is to say, the necessary and sufficient condition for the existence of Euler paths in graph G is that every node in G is an even node.
Suppose there is an Euler path in graph G, then the starting point and ending point of the loop are the same node, including one edge and one edge, so the nodes are even, and so on, each node is 2n (n = 0, 1, 2, ... n).
Strip edge.
The necessary and sufficient conditions for the existence of Euler paths in graph G are somewhat similar to those of Euler paths in graph G:
If the number of odd nodes is 0, there is an Euler path in graph G, and Euler path is also a kind of Euler path.
Connecting two odd nodes indicates that this is an Euler path (V 1, V2, V3, V4, V5, V6, V3, V 1).
Euler path (v 1, v 2, v 3, v 4, v 5, v 6, v 3) has two odd nodes at its starting point and ending point.
This concludes the introduction of Euler path and Euler path. Thank you!