I am trying to find SPQR tree of my graph, so I find out that sage can help me. I put my code here https://sagecell.sagemath.org/ (and than in sage programe). Here it is:
H=Graph({"AL":["GR","ME","MK","RS"],"GR":["BG","MK","TR"],"ME":["BA","HR","KO","RS"],"MK":["BG","RS"],"RS":["BA","BG","HR","HU","KO","RO"],"AD":["FR","SP"],"FR":["BE","DE","IT","LU","MC","SP","CH"],"SP":["PT"],"AT":["CZ","DE","HU","IT","LI","SK","SL","CH"],"CZ":["DE","PL","SK"],"DE":["BE","DK","LU","NL","PL","CH"],"HU":["HR","SK","SL","UA"],"IT":["SM","SL","CH","VA"],"LI":["CH"],"SK":["PL","UA"],"SL":["HR"],"BY":["LV","LT","PL","RU","UA"],"LV":["EE","LT","RU"],"LT":["PL","RU"],"PL":["RU","UA"],"RU":["EE","FI","NO","UA"],"UA":["MD","RO"],"BE":["LU","NL"],"BA":["HR"],"BG":["RO","TR"],"RO":["MD"],"FI":["NO","SE"],"NO":["SE"]}
)
H = H.to_undirected()
tree = spqr_tree(H)
plot(tree)
But I got exception and I can't understand, what the problem with my graph and how can I fix it. Log from sage:
ValueError Traceback (most recent call last)
<ipython-input-1-5545fd16ab3f> in <module>
3 )
4 H = H.to_undirected()
----> 5 tree = spqr_tree(H)
6
7 plot(tree)
/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/graphs/connectivity.pyx in sage.graphs.connectivity.spqr_tree (build/cythonized/sage/graphs/connectivity.c:23494)()
2318
2319 if algorithm == "Hopcroft_Tarjan":
-> 2320 tric = TriconnectivitySPQR(G)
2321 return tric.get_spqr_tree()
2322
/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/graphs/connectivity.pyx in sage.graphs.connectivity.TriconnectivitySPQR.__init__ (build/cythonized/sage/graphs/connectivity.c:30717)()
3109 # If graph has a cut vertex
3110 if cut_vertex != -1:
-> 3111 raise ValueError("graph has a cut vertex")
3112
3113 # Identify reversed edges to reflect the palm tree arcs and fronds
ValueError: graph has a cut vertex
An SPQR tree can only be formed for biconnected graphs. These are connected graphs that stay connected even if any node in the graph is deleted. A graph is not biconnected if it has an articulation vertex (also called a cut vertex), a node that, if removed, leaves the graph disconnected.
The error you're getting indicates that your graph has at least one cut vertex, so it's not possible to form the SPQR tree.