离散数学之树和生成树的笔记(上)

离散数学之树和生成树的笔记:

1.树的基本定义与性质

2.生成树的定义与性质

3.基本回路系统

4.基本割集系统

设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的:

(1)G是树

(2)G中任意两个顶点之间唯一唯一的路径。

(3)G是连通的,且n=m-1(n是边数,m是顶点数)

(4)中无回路,且n=m-1

(5)G是连通的且任何边均为桥

(6)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有唯一的一个含新边的圈。

握手定理说的是度数之和等于两倍的边数,在这里等于两倍的(m-1)

生成树指的是在无向图G中产生的是树的生成子图(生成子图只允许删去边,不允许删去顶点)。而如果有T是G的生成子图,则把仍然留在T中的边叫做T的树枝,已经被删去不在T的边被称作弦。T的所有弦的导出子图(只保留这些边)被称作余树。

余树虽然是树,但并不一定真的是树。

唯有图G是联通的(充分必要条件),这个图G才有生成树。

基本回路(或基本圈),就是生成树的任意一条弦+若干个(所有)树枝所得到的回路(显然是回路,这个可以由树的性质“G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有唯一的一个含新边的圈。”得出)。显然不同的弦对应了不同的基本回路,把所有基本回路作为元素构成的集合成为G对应生成树T的基本回路系统,m-n+1被成为圈秩(就是基本回路系统中元素的个数)。

基本割集与基本回路基本上差不多。唯一不同的就是基本割集是任意一条树枝+若干个弦构成的一个集合。对于这个集合的要求比较苛刻一些,不能像基本回路那样随便取任意一个弦就万事大吉了,而是需要进行一定的甄别。因为这里我们要获得的是一个割集。显然我们要的是一个边割集。n-1是割集秩

在这里复习一个边割集的概念:边割集就是说去掉这些边之后图的连通分支数会加一。

求基本割集可以用“切”法。就是先选一个树枝,然后从这个树枝出发,找弦,穿过去,如果还有弦再传过去,但是得要能够在不穿过树枝的情况下穿到外面去才行。

以下面这个为例:(图片来自《离散数学》(高等教育出版社))

e1可以经由e7、e8,在不穿过其它树枝的情况下穿出去。因此e7、e8被保留了,但是没办法找到其它能够穿出去的路径满足这个要求。比方说如果e1穿过了e6,那么根本穿不过去,因为e4、e5都是树枝。所以S={e1,e7,e8}是一个基本割集。

那e2有两条路径,分别是e2e7e8, e2,e10,e11,所以S={e2,e7,e8,e10,e11}也是一个基本割集。

同理还可以得出其它4个基本割集。

留下评论

电子邮件地址不会被公开。 必填项已用*标注