南京大学：《计算机问题求解》课程教学资源（课件讲稿）图中的连通度和距离

计算机问题求解一论题3-10 图的连通度 2016年11月9日

计算机问题求解 – 论题3-10 - 图的连通度 2016年11月9日

预习检查 Whitney theorem then gives us an alternative method for determining the connectivity of a graph G.Not only is K(G) the minimum number of vertices whose removal from G results in a disconnected or trivial graph but K(G)is the maximum positive integer k for which every two vertices y and vin G are connected by k internally disjoint u-v paths in G

预习检查  Whitney theorem then gives us an alternative method for determining the connectivity of a graph G. Not only is K(G) the minimum number of vertices whose removal from G results in a disconnected or trivial graph but K(G) is the maximum positive integer k for which every two vertices u and v in G are connected by k internally disjoint u - v paths in G

“连通并不都是一样的 (c) (d) (a) (b) 问题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： 你能据此解释：割点是什么？ Nonseparable graph;是什么？ 图的block是什么？

指标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： 你能据此解释：割点是什么？ Nonseparable graph是什么？ 图的block是什么？

关于block的几个理解 Theorem 5.7 A graph of order at least 3 is nonseparable if and only if every two vertices lie on a common cycle. x u Uk-1 Uk=U 问题4：从这个定 理及证明中能否 看出，非分离图 在外表上具有什 么共性？

关于block的几个理解 Theorem 5.7 A graph of order at least 3 is nonseparable if and only if every two vertices lie on a common cycle. 问题4：从这个定 理及证明中能否 看出，非分离图 在外表上具有什 么共性？

关于block的几个理解 A maximal nonseparable subgraph of a graph G is called a block of G 极大还是 最大？

关于block的几个理解 A maximal nonseparable subgraph of a graph G is called a block of G. 极大还是 最大？

关于block的几个理解 Theorem 5.8 Let R be the relation defined on the edge set of a nontrivial connected graph G by e R f,where e,f eE(G),if e f or e and f lie on a common cycle of G.Then R is an equivalence relation. 用等价关系来描述边之间的关系，到底有何用意？ Each subgraph of G induced by the edges in an equivalence class is in fact a block of G 问题6：Bock的“极大”特性，是否能够被“等价 类”保证？

关于block的几个理解 Theorem 5.8 Let R be the relation defined on the edge set of a nontrivial connected graph G by e R f, where e, f ∈E(G), if e = f or e and f lie on a common cycle of G. Then R is an equivalence relation. 用等价关系来描述边之间的关系，到底有何用意？ Each subgraph of G induced by the edges in an equivalence class is in fact a block of G. 问题6：Block的“极大”特性，是否能够被“等价 类”保证？

问题7： 两个block的“边界”是什么？ Corollary 5.9 Fvery two distinct blocks B and B in a nontrivial connected graph G have the following properties: (a) The blocks B and B are edge-disjoint. (b)The blocks B and B have at most one vertex in common. (c)If B and B,have a v vertex v in common, then v is a cut-vertex of G

Corollary 5.9 Every two distinct blocks B1 and B2 in a nontrivial connected graph G have the following properties: (a) The blocks B1 and B2 are edge-disjoint. (b) The blocks B1 and B2 have at most one vertex in common. (c) If B1 and B2 have a vertex v in common, then v is a cut-vertex of G

问题8： 从一个k-连通图中删除k个点， 剩下的图是否一定不连通了？ 是否存在一种方法， 使得从一 个k-连通图中删除k个点，剩 下的图是否一定不连通？

从一个k-连通图中删除k个点， 剩下的图是否一定不连通了？ 是否存在一种方法，使得从一 个k-连通图中删除k个点，剩 下的图是否一定不连通？