给定任何连通图和无向图G(V,E)，显示，在v中总是存在一个顶点G，其从图中的移除不影响G的连通性，即，在每对顶点之间存在一条路径。
显示一个O(|E|+|V|)时间算法来找到这样的顶点。
所以我开始想办法解决这个问题我想一个好的方法是使用广度优先搜索（bfs）。然后你就可以移除最高层的顶点了由于bfs是由层完成的，从最高层删除一个顶点不应该断开其他顶点与图形的连接。
我走对了吗我要怎么证明？
最佳答案
设G为连通的无向图。
因为G是连接的，所以考虑M的生成树此生成树G至少有一个顶点的阶数为1（叶顶点）因此，通过从[cc]中删除这样一个特定顶点，我们仍然有一个连通图，也就是说，在每个顶点对之间存在一条路径。
关于algorithm - 关于连通性的图论，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40060825/