计算机问题求解一论题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 vertexcut. 问题3： 你能据此解释：割点是什么？ Nonseparable graph是什么？ 图的block是什么？