Ch3

Posted on

Ch3

1*

是k-边连通图，是的 条边的集合，则 。

根据边割集的性质，去掉条边后仍然是连通图，即

此时在删去一条边后连通分支的数量最多加一，即

2

给出一个连通图G以及k个顶点的集合，使得。

星图

3*

是简单图， ， 则有 。

只有两种情况：

  1. 此时G是完全图，显然有

  2. 假设，则假设删去个顶点后图失去连通性，因为，所以对于剩下 的三个顶点都至少与一个顶点相邻，即是连通的，矛盾！同理可证明更小 的时候也无法分割。

    若移出某个度数为的顶点的所有相邻顶点，则可以导致其不连通，所以

7*

任给三个非负整数，都存在简单图 ，满足。

该题证明存在行即可。

  • 时，完全图满足条件

  • 时，取两个完全图，并分别记做，，取 中 个顶点(记为),中 个顶点(记为)

    中每个顶点向中的顶点连接一条边，使得一共有条边，且中每个顶点都有边被连接。此时图满足条件

13*

证明定理3.4

(定理边版本)给定图G中的两个顶点,中两两无公共边的 轨道的最大 数量等于最小 边割集的边数，即：

这里仿照 点版本的证明，使用归纳假设法，对边的条数作归纳。

令，因为是的子图有：

由归纳假设得：

因为得边割集加上必为的边割集：

如果上述的两个不等式都成立，则命题对多一条边的图也成立

此时假设两个等式都成立，注意第二个不等式的取等条件， 是 的边割集，但不是

的边割集，是 G 的边割集，这说明 必有一条过 的路。

移出所有 后，整个图被分成 和两部分然后对 和 分别进行收缩操作(这里以收缩 V

为例，在边 上的点不会被收缩)。

对于收缩以后图的边连通度(因为是收缩图，所以最小边割集数不会减小;由的最小性知不会增加)，

再利用归纳假设(注意这里收缩图可以通过细分顶点和加边操作得到原图)，可以得出收缩图的边连通度不变。