计算机问题求解-论题3-10 图的连通度 2018年11月13日
计算机问题求解 – 论题3-10 - 图的连通度 2018年11月13日
“连通并不都是一样的 问题1： 你能否解释一下它们的“连通” 怎么不一样？ 割点、割边与回路
“连通”并不都是一样的 割点、割边与回路
问题2 衡量连通的牢度”的指 标是什么？
指标1：minimum vertex-cut By a vertex-cut in a graph G,we mean a set U of vertices of G such that G-U is disconnected.A vertex-cut of minimum cardinality in G is called a minimum vertex- cut. 问题3： 你应该了解割点是什么？围 绕割点，有哪些有趣的现象
指标1：minimum vertex-cut By a vertex-cut in a graph G, we mean a set U of vertices of G such that G - U is disconnected. A vertex-cut of minimum cardinality in G is called a minimum vertexcut. 问题3： 你应该了解割点是什么？围 绕割点，有哪些有趣的现象
围绕割点的若千结论 Theorem 5.1 Let y be a vertex incident with a bridge in a connected graph G.Then v is a cut-vertex of G if and only if degv≥2. Theorem 5.3 Let v be a cut-vertex in a conected graph G and let u and w be vertices in distinct components of G-v. Then v lies on every u-w path in G. Theorem 5.5 Let G be a nontrivial connected graph and let u EV(G).Ifv is a vertex that is farthest from u in G,then v is not a cut-vertex of G
围绕割点的若干结论