计算机问题求解一论题3-10 图的连通度 2022年11月16日
计算机问题求解 – 论题3-10 - 图的连通度 2022年11月16日
观察和衡衡量图连通特性的关键 问题1： 你能否解释一下它们的“连通” 怎么不一样？ 割点、割边与回路
观察和衡量图连通特性的关键 割点、割边与回路
围绕割点的若干结论 Theorem 5.1 Let v 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. Corollary 5.2 Let G be a connected graph of order 3 or more.If G contains a bridge,then G contains a cut-vertex. Theorem 5.3 Let v be a cut-vertex in a connected graph G and let u and w be vertices in distinct components of G-v.Then y lies on every u-w path in G. Corollary 5.4 A vertex v of a connected graph G is a cut-vertex of G if and only if there exist vertices u and w distinct from v such that v lies on every u-w path of G. Theorem 5.5 Let G be a nontrivial connected graph and let ueV(G).Ifv is a vertex that is farthest from u in G,then v is not a cut-vertex of G
围绕割点的若干结论
问题2 衡量连通的牢度”的指 标是什么？
指标1：minimum vertex-cut By a vertex-cut in a graph G,we mean a (strict) subset 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
指标1：minimum vertex-cut By a vertex-cut in a graph 𝐺 , we mean a (strict) subset 𝑈 of vertices of 𝐺 such that 𝐺 − 𝑈 is disconnected. 𝐴 vertex-cut of minimum cardinality in 𝐺 is called a minimum vertex-cut