第二章图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图,其连通的程度 也有高有低。例如,下列三个图都是连通图。对于图G1,删除一条边或一个顶点便可使其 变得不连通;而对于图G2,至少需要删除两条边才能使其不连通,也可以删除一个顶点使 其不连通;对于图G,要破坏其连通性,则至少需要删除三条边或三个顶点 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性 程度。通过研究割边和割点来刻画1连通图的特性:定义连通度和边连通度来度量连通图连 通程度的高低;通过不交路结构和元素的共圈性质来反映图的2连通和k连通性。 §2.1割点和割边 定义211设v∈V(G),如果w(G-v)>w(G),则称v为G的一个割点。 (注:该定义与某些著作中的定义有所不同,主要是在环边的顶点是否算作割点上有区别)。 例如,下图中t,y两点是其割点。 定理211如果点v是简单图G的一个割点,则边集E(G)可划分为两个非空子集E1和E2, 使得G[E1]和G[E2]恰好有一个公共顶点v 证明留作习题。 推论211对连通图G,顶点v是G的割点当且仅当G一v不连通。 定理212设是树T的顶点,则v是T的割点当且仅当d(v)>1 证明:必要性:设v是T的割点,下面用反证法证明d(v)> 若d(v)=0,则T≡K1,显然v不是割点 若d(v)=1,则T-v是有v(T-v)-1条边的无圈图,故是树。从而w(T-v)=1=w(7)。 因此v不是割点 以上均与条件矛盾。 充分性:设d(v)>1,则v至少有两个邻点uw。路uw是T中一条(u,w)路。因T是树, n是T中唯一的(u,w)路,从而w(T-v)>1=w(T)。故v是割点。证毕。1 第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度 也有高有低。例如，下列三个图都是连通图。对于图 G1，删除一条边或一个顶点便可使其 变得不连通；而对于图 G2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使 其不连通；对于图 G3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性 程度。通过研究割边和割点来刻画 1 连通图的特性；定义连通度和边连通度来度量连通图连 通程度的高低；通过不交路结构和元素的共圈性质来反映图的 2 连通和 k 连通性。 §2.1 割点和割边 定义 2.1.1 设v ∈V (G) ，如果 w(G − v) > w(G) ，则称 v 为 G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中 u, v 两点是其割点。 定理 2.1.1 如果点 v 是简单图 G 的一个割点，则边集 E(G)可划分为两个非空子集 E1和 E2 ， 使得 [ ] G E1 和 [ ] G E2 恰好有一个公共顶点 v。 证明留作习题。 推论 2.1.1 对连通图 G，顶点 v 是 G 的割点当且仅当G − v 不连通。 定理 2.1.2 设 v 是树 T 的顶点，则 v 是 T 的割点当且仅当d(v) > 1。 证明：必要性：设 v 是 T 的割点，下面用反证法证明d(v) > 1。 若d(v) = 0 ，则T ≅ K1，显然v 不是割点。 若d(v) = 1，则T − v 是有ν (T − v) −1条边的无圈图，故是树。从而 w(T − v) = 1 = w(T ) 。 因此v 不是割点。 以上均与条件矛盾。 充分性：设d(v) > 1，则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条(u,w) 路。因 T 是树， uvw 是 T 中唯一的(u,w) 路，从而 w(T − v) > 1 = w(T ) 。故v 是割点。证毕。 G1 G2 G3 u v