精品文档---下载后可任意编辑习题三：证明： 是连通图 G 的割边当且仅当 V(G)可划分为两个子集 V1 和 V2，使对任意及, G 中的路必含 .证明：充分性: 是 的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对，因为 中的不连通，而在 中 与 连通，所以 在每一条路上， 中的必含 。必要性：取，由假设 中所有路均含有边 ，从而在中不存在从与到 的路，这表明 不连通，所以 e 是割边。3.设 G 是阶大于 2 的连通图，证明下列命题等价：（1） G 是块（2） G 无环且任意一个点和任意一条边都位于同一个圈上；（3） G 无环且任意三个不同点都位于同一条路上。： 是块，任取 的一点 ，一边 ，在 边插入一点 ，使得 成为两条边，由此得到新图，显然的是阶数大于 3 的块，由定理， 中的 u,v 位于同一个圈上，于是中 u 与边 都位于同一个圈上。 ：无环，且任意一点和任意一条边都位于同一个圈上，任取 的点 u，边 e，若 在 上，则三个不同点位于同一个闭路，即位于同一条路，如 不在 上，由定理， 的两点在同一个闭路上，在 边插入一个点 v，由此得到新图，显然的是阶数大于 3 的块，则两条边的三个不同点在同一条路上。 ：连通，若 不是块，则 中存在着割点 ，划分为不同的子集块,,,无环，，点 在每一条的路上，则与已知矛盾， 是块。7.证明：若 v 是简单图 G 的一个割点，则 v 不是补图 的割点。证 明 ：是 单 图的 割 点 ， 则有 两 个 连 通 分 支 。 现 任 取, 假如不在的同一分支中，令 是与处于不同分支的点，那么，与 在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若 是 的割点，则 不是补图的割点。12.对图 3——20 给出的图 G1 和 G2，求其连通度和边连通度，给出相应的最小点割和最小边割。解： 最小点割 {6,8} 最小边割{（6,5），（8,5）} 最小点割{6,7,8,9,10} 最小边割{（2,7）…（1,6）}13.设 H 是连通图 G 的子图，举例说明：有可能 k(H)> k(G).解：精品文档---下载后可任意编辑通常.整 个 图 为 ， 割 点 左 边 的 图 为 的 的 子 图 ， ， 则.eH
