提问人：Ftyupl 提问时间：10/21/2023 最后编辑：Ftyupl 更新时间：10/21/2023 访问量：52
从连接图中删除顶点以获取连接子图
Remove a vertex from a connected graph to obtain a connected subgraph
问：
我的印象是，如果我采用一个简单的连接图，那么我可以（前提是它的顶点数大于或等于 2）删除一个顶点并获得一个连接的子图。
这并不适用于所有顶点，有些顶点我无法删除。
例如
我无法在不失去连接的情况下删除 E，但我可以删除 A、B、C 或 D。
但总有一个我可以排除。你有办法证明这个结果吗？
答：
1赞
Dave
10/21/2023
#1
设 G 是任何连接图。则 G 至少有一个生成树。设 T 是 G 的任何生成树。设 v 是 T 的任何叶子。如果我们删除 v，则 T \ {v} 是连接的，并且是 G \ {v} 的子图，因此 G \ {v} 是连接的。
这使用的众所周知的结果：
- 每个连接图至少有 1 个生成树
- 从 n 顶点树中删除叶子会生成 （n-1） 顶点树
1赞
subasri_
10/21/2023
#2
您所指的概念可以与 的概念相关，也称为 。Articulation PointCut Vertex
如果连接的组件中存在一个顶点，当该顶点被移除时，该顶点将断开，即分解为两个或多个组件v
某些条件可以使节点符合衔接点的条件。因此，如果图形被标识为没有此类顶点，则即使删除任何顶点，图形仍将保持为单个连接的组件
有关详细信息，请参阅此处
上一个：根据公式计算参考编号
评论