预习检查 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
指标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是什么?
关于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