0%

离散数学《图论与代数结构》第12周习题

上次写离散已经是4周之前了…

1.

n个点的图最多有n-2个割点。

构造方法:将n个点连成链,除2个端点外,都是割点。

上界证明

首先删去图中的所有重边和自环,这对割点个数无影响。

引理

对于一个连通图,生成树的叶节点都不是割点。

证明:删去生成树的某一个叶节点,其他点对仍然可以通过树边相连通,因此叶节点不是割点。

主要证明

若G没有边,则每个点都不是割点。

否则,考虑G的某个点数大于1的连通块,任取它的某个生成树,由于点数大于1的树至少有两个度数为1的点,因此G至少有两个点不是割点,因此n-2是割点个数上界。


n个点的图最多有n-1条割边。

构造方法:将n个点连成链,有n-1条边,每条边都是割边。

上界证明:若有条割边,则割边会形成环,这与割边的定义矛盾。

4.

G是2-连通图当且仅当G的任意两节点之间至少有两条不相交的道路。

充分性

因为任意两节点之间至少有2条不相交的道路,所以删去任意一点后,任意两节点之间至少有1条道路,因此即.

必要性

假设u,v之间不存在2条不相交的道路,则删去u,v之间道路的某个公共点,u,v不连通。因此,矛盾。因此原命题成立。