How to check whether the graph is Eulerian, if so, then build an Eulerian cycle?
I know for sure that there is an Eulerian cycle in this graph. I don't understand how to check this and construct it using the adjacency matrix of this graph.
PS you can use ready-made libraries. The task is practical.
nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H')
distances = {
'A': {'B': 2, 'C': 1, 'D': 3, 'E': 9, 'F': 4},
'B': {'C': 4, 'E': 3},
'C': {'D': 8},
'D': {'E': 7},
'E': {'F': 5},
'F': {'C': 2, 'G': 2, 'H': 2},
'G': {'F': 1, 'H': 6},
'H': {'F': 9, 'G': 8}}
unvisited = {node: None for node in nodes}
visited = {}
print(" ")
print("Введите вершину:")
current = input()
currentDistance = 0
unvisited[current] = currentDistance
while True:
for neighbour, distance in distances[current].items():
if neighbour not in unvisited: continue
newDistance = currentDistance + distance
if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
unvisited[neighbour] = newDistance
visited[current] = currentDistance
del unvisited[current]
if not unvisited: break
candidates = [node for node in unvisited.items() if node[1]]
if not candidates: break
current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
print(visited)
matrix = [[0,1,1,1,1,1,0,0], # a
[0,0,1,0,1,0,0,0], # b
[0,0,0,1,0,0,0,0], # c
[0,0,0,0,1,0,0,0], # d
[0,0,0,0,0,1,0,0], # e
[0,0,1,0,0,0,1,1], # f
[0,0,0,0,0,1,0,1], # g
[0,0,0,0,0,1,1,0]] # h
1
1 answers
It seems that this graph does not contain an Euler cycle:
import networkx as nx # pip install networkx
import matplotlib.pyplot as plt
distances = {
'A': {'B': 2, 'C': 1, 'D': 3, 'E': 9, 'F': 4},
'B': {'C': 4, 'E': 3},
'C': {'D': 8},
'D': {'E': 7},
'E': {'F': 5},
'F': {'C': 2, 'G': 2, 'H': 2},
'G': {'F': 1, 'H': 6},
'H': {'F': 9, 'G': 8}}
G = nx.DiGraph()
for k,v in distances.items():
for k2,v2 in v.items():
G.add_edge(k, k2, dist=v2)
In [24]: nx.draw(G, with_labels=True)
In [25]: nx.is_eulerian(G)
Out[25]: False
In [26]: nx.eulerian_circuit(G)
Out[26]: <generator object eulerian_circuit at 0x000000000AD631A8>
In [27]: list(nx.eulerian_circuit(G))
---------------------------------------------------------------------------
NetworkXError Traceback (most recent call last)
<ipython-input-27-d4bc2ec5ddbd> in <module>
----> 1 list(nx.eulerian_circuit(G))
~\Anaconda3\envs\ml\lib\site-packages\networkx\algorithms\euler.py in eulerian_circuit(G, source, keys)
168 """
169 if not is_eulerian(G):
--> 170 raise nx.NetworkXError("G is not Eulerian.")
171 if G.is_directed():
172 G = G.reverse()
NetworkXError: G is not Eulerian.
Example of a simple Euler cycle:
In [30]: G2 = nx.from_edgelist([('A','B'),('B','C'),('C','D'),('D','A')], create_using=nx.DiGraph)
In [31]: list(nx.eulerian_circuit(G2))
Out[31]: [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')]
In [32]: list(nx.eulerian_circuit(G2, 'C'))
Out[32]: [('C', 'D'), ('D', 'A'), ('A', 'B'), ('B', 'C')]
In [33]: nx.draw(G2, with_labels=True)
3
Author: MaxU, 2018-12-11 21:29:46