图论 第四章 割集

第四章 割 集
4.1 割集与断集
我们定义连通图G的顶点数减1为图G的秩，记作 R(G)，即R(G)=p-1 如果G有k个连通分支，则R(G)=p-k
定义4.1.1 设S E(G),如果
1.R(G-S)=p-2
2.对S S,R(G-S)=p-1 则称边集S为图G的的一个割集(cut set)。
割集是指一个边集S，在G中去掉S的所有边后G变 为具有两个分支的分离图，但是去掉S中的部分边时 图仍然是连通的。
0Gi ,1 Gi Gi ,Gi
下构成域 F 0,1上的一个q维向量空间。
5.2 圈 空 间
定义5.2.1 设T是连通G的一棵生成树，由T的树枝和一条 连枝构成的圈，称为图G关于生成树T的基本圈。
设图G为连通（p,q）图，那么G的任一生成树T的树 枝数和关于T的连枝数均为p和q-p+1。
由q-p+1条连枝构成的q-p+1个基本圈，称为G关于生 成树的基本圈组，记作Cf。由于一个图G的生成树不是唯 一的，因而一个图的基本圈组也不是唯一的。
定理5.2.1 图G 关于生成树的基本圈
C1, C2 , , Cq p1 是线性无关的。
定理5.2.2 连通图G的任一环路均可表示成 若干个基本圈的环和。
定理5.2.3 连通（p,q）图G的所有环路和空图 的集合构成一个q-p+1维空间，记作 (G)称为圈 空间。
定理5.2.4 连通（p,q）图G的圈空间中元素的 个数为2 q-p+1。
Leabharlann Baidu
5.3 割集空间
定义5.3.1 设S是图G的一个割集，T是一棵生 成树，如果S中恰好含有T的一树枝，则称S为 G的关于生成树T的基本割集。 P-1个基本割集称为图G的基本割集组。
定理5.3.1 设T是图G的一棵生成树，T的连枝 e`包含在由树枝e确定的基本割集中的充要树枝 e包含在由连枝e`确定的基本圈中。
c1u1 c2u2 cnun 0 成立 ，则称u1,u2, un 线性相关，否则称为线性无关。
其中ci F,i 1, 2, , n, 则称 V 为 u1,u2, un 的线性组合。
设S是一个n维向量组，如果S中任一向量都可表示成 向量u1,u2, un 的线性组合，则称u1,u2, un是S是的 生成元素组。又若u1,u2, un线性无关，则称u1,u2, un 是一个线性无关极大组。
结论：1. p阶连通图G关于生成树T的基本割集组是G的 割集空间的一组基底，割集空间维数为p-1。 2. 图G的全部断集的个数为2p-1-1，空集不是断集。
推断：求一个图的全部断集，首先选取一棵生成树，然后 找到对应的基本割集，求所有可能基本割集的环合。
定理5.3.5 p阶连通图恰有p-1个线性无关的关联集。
定理5.3.2 设S1，S2，…，Sp-1是连通（p,q） 图G的基本割集，那么它们是线性无关的。
定理5.3.3 图G的任一断集均可表示成若干基 本割集的环和。 对任意一个断集我们规定0·S=φ，1·S=S
定理5.3.4 图G的所有断集和空图的集合 作成向 量空间 (G)的一个子空间，称为G的割集空间。
(2)T e包含G的一个唯一的割集
定理4.1.2 连通图G的一个割集至少包含生成的一个 树枝。
4.2 关联图
定义4.2.1 设v是图G的一个顶点，与v关联的所有边 的集合，称为顶点v 的关联集，记作S（v）.
2
d a
7
i k
1 b
c e
3
fg
j
9
5
h
6
l
8
4
2
割点、割集、
断集？
a
c
7
3 k
1
8
b
5
h
6
l
9 4
引理4.2.1 设V1，V2 ， V3 ， V4是图G 的顶点集合的 非空子集，其中任何两个的交均为空集，则：
E(V1 V2 V3 V4 ) E(V1 V3 ) (V1 V4 ) E(V2 V3) (V2 V4 )
引理4.2.2 设V1和V2 是图G 顶点集合的非空子集，则：
• 线性空间R的一个线性无关极大组叫做空 间的基底，基底中所含的向量的个数叫 做空间的维数。
命题5.1.1图G中所有不同的子图的个 数是2q(包括图G中空图 )。
设G1,G2,…,GN（N=2q）是图G的全部子图， 则有下面的定理。
定题5.1.1集合 G1,G2, ,GN在环和运算与
数乘运算：
E(V1 V1) E(V2 V2 ) E(V11 V22 V21 V12 )
E(V3 V3 )
其中
V11 V1 V2 V12 V1 V2 V21 V2 V1
V22 V1 V2 V3 V11 V22
定理4.2.1 图G 的任一断集均可表示成若干个关联集的环 和。
推论4.2.1 图G 中任一顶点的关联集等于其余顶点关联集 的环和。
第五章 圈空间与割集空间
5.1 图的向量空间
定义5.1.1 n个只取0或1的数a1, a2, …, an,按一定次序 排成一行，再用括号括起来写成（a1, a2, …, an ） 叫做一个n维向量，其中a1, a2, …, an 叫做分量。
定义5.1.2 设 u1,u2, un 为n个向量，如果存在n个不全 为零的数， c1, c1, c1 F,i 1, 2, n, 使等式
2
a
c
b
1
d
e
4
3
g f
5
1 2
1
d
e 3
f
g
5
2
a
4
e
3
g
5
2
a
c
b
2
1
d
e
4
3
2
a
1 f
e
4
3
g
g f
5
a b
1
4
3
d
5
2
a
b
5
1
d
4
3
f
5
1
3 2
a
b
c
d
e
f
4
5
1
7
6
c 2
3
1
h
l
10
V1
i
9
8 V1
4
e
5
V1
6
7
g
2 3
1
4
5
10
8
6
7 9
• 定义4.1.2 图G中端点分别属于V1
P阶连通图G有p-1个关联集，然后求出它们 所有可能的环合，即可求出G的全部断集。
和集(Vse1g的)。所有边的集合称为G的断
• E(V1×V2)表示一个端点在V1中， 另一个端点在V2中的所有边的集 合。
2
V1 a 1
b V2
c
3
e
f
d
g
5
h
4
2
V1 a
b
1
c
e
f
d
3
V1
g
5
h
4
V1
V1
V1
V1
V1
定理4.1.1 设T是连通图G的一棵生成树，并且e是任 一树枝，则：
（1）连枝集中不包含G的割集。