※ 引述《jvvbn0601 (part2)》之铭言： : For an undirected graph G=(V, E) and a vertex v in V, let G\v denote the : subgraph of G obtained by removing v and all the edges incident to v from G. If G is : connected, then G\v can be connected or disconnected. Prove that for any connected graph G, : we can always find a vertex v in G such that G\v is connected. : 目前我的想法是1)没有回圈:视为树，leaf必定是non-cut : 2)有回圈:有回圈的话，degree不是最大的应该都可以是non-cut? : 请问一下，我的观念是否有错? : 还有如何用数学归纳法证明呢? 有 cycle 也不见得可以从 cycle 拔，例如三个点组成三角形，下面连另外两 个点，变成 "A" 的形状，中间的两个点一拔就断了。 我的做法不使用数学归纳法，参考一下。很久没做题目了，希望没错。 先在图中任取一点 v0，然後对所有其他点，计算到达 v0 的最短路径，直接 相连的邻居就是 1，邻居的邻居为 2，以此类推。全部算完之後，随便挑一个离 v0 最远的 v，把它拔掉即可。v0 必然仍然和所有的点连通，若有一点 v' 因为 拔掉 v 而不再和 v0 相连，那麽 v 必然在 v0 到 v' 的所有路径上，包括最短 路径，这与 v 是离 v0 最远的点矛盾，因此 v0 和所有的点连通。任两点也可 经过 v0 互相连通，因此整个图仍为连通。 -- Just because you deserve this doesn't mean they're gonna give it to you. Sometimes you gotta take what's yours. ── Kenny Ray Carter --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 174.21.233.189