如何使用 Sage 找到 SPQR 树？

Question

我试图找到我的图表的 SPQR 树，所以我发现 sage 可以帮助我。我把我的代码放在这里 https://sagecell.sagemath.org/ （而不是在圣人程序中）。这是：

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)

但是我遇到了异常，我不明白我的图表有什么问题，我该如何解决。来自 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

Answer 1

只能为双连通图形成SPQR树。这些是连接的图，即使图中的任何节点被删除也保持连接。如果图具有 连接顶点 （也称为 切割顶点 )，一个节点，如果删除该节点，会使图形断开连接。

您收到的错误表明您的图形至少有一个切割顶点，因此无法形成 SPQR 树。

如何使用 Sage 找到 SPQR 树？

How can I find an SPQR tree using Sage?

python

graph

sage