论文标题
构建最小的3连接图
Constructing minimally 3-connected graphs
论文作者
论文摘要
如果删除任何边缘的3个连接性，则$ 3 $连接的图是最小的3连接。我们提出了一种基于（DAWES，JCTB 40，159-168，1986）的结果来构建最小3连接图的算法：使用两个操作：在非粘性顶点之间添加边缘并拆分顶点。为了测试3兼容性的顶点和边缘，取决于图表的周期，我们开发了一种从$ g $的周期中获得$ g'$的周期的方法，其中$ g'$由上面的两个操作中的一个从$ g $中获得。我们使用McKay的同构检查器Nauty生成的证书消除异构。该算法连续构建具有$ n $ vertices的非同形微型3连接图和$ M $边缘，来自非iSomorphic微型3连接图，带有$ n-1 $ n-1 $顶点和$ M-2 $ edges，$ m-M-2 $ edges，$ n-1 $ n-1 $ n-1 $ n-1 $ vertices和$ m-3 $ edges and $ m-3 $ edges and $ n $ edges and $ n $ n33 $ ncy and $ n33。
A $3$-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. In order to test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G'$ from the cycles of $G$, where $G'$ is obtained from $G$ by one of the two operations above. We eliminate isomorphs using certificates generated by McKay's isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with $n$ vertices and $m$ edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges.
