关于连通性的图论
Graph Theory about connectivity
给定任何连通图和无向图 G(V,E)，证明 G 中始终存在一个顶点 v，从图中移除该顶点不会影响 [=12] 的连通性=]，即每对顶点之间存在路径。
显示一个 O(|E|+|V|) 时间算法来找到这样一个顶点。
所以我开始尝试想出一种算法来解决这个问题。我认为一个好的方法是使用广度优先搜索 (BFS)。然后您就可以删除最高层中的顶点。由于 BFS 是按层完成的，因此从最高层删除一个顶点不应断开其他顶点与图中的连接。
我走在正确的轨道上吗？我将如何证明这一点？
设 G 为连通无向图。
因为G是连通的，考虑G的生成树M。这棵生成树 M 至少有一个顶点的度数为 1（叶顶点）。因此，通过从 G 中删除这样一个特定的顶点，我们仍然有一个连通图，也就是说，每对顶点之间存在一条路径。
关于算法，您可以 运行 DFS 或 BFS 并找到第一个没有子节点的顶点。如果不存在这样的节点，那么你必须有一个循环，然后你可以return任何节点。
关于证明。也许通过感应？您可以证明，如果将具有单边的顶点（叶顶点）添加到任何连通的无向图中，您始终可以将其删除，而不会影响连通性。
给定任何连通图和无向图 G(V,E)，证明 G 中始终存在一个顶点 v，从图中移除该顶点不会影响 [=12] 的连通性=]，即每对顶点之间存在路径。
显示一个 O(|E|+|V|) 时间算法来找到这样一个顶点。
所以我开始尝试想出一种算法来解决这个问题。我认为一个好的方法是使用广度优先搜索 (BFS)。然后您就可以删除最高层中的顶点。由于 BFS 是按层完成的，因此从最高层删除一个顶点不应断开其他顶点与图中的连接。
我走在正确的轨道上吗？我将如何证明这一点？
设 G 为连通无向图。
因为G是连通的，考虑G的生成树M。这棵生成树 M 至少有一个顶点的度数为 1（叶顶点）。因此，通过从 G 中删除这样一个特定的顶点，我们仍然有一个连通图，也就是说，每对顶点之间存在一条路径。
关于算法，您可以 运行 DFS 或 BFS 并找到第一个没有子节点的顶点。如果不存在这样的节点，那么你必须有一个循环，然后你可以return任何节点。
关于证明。也许通过感应？您可以证明，如果将具有单边的顶点（叶顶点）添加到任何连通的无向图中，您始终可以将其删除，而不会影响连通性。