图 论（Graph Theory）graph-chapter4-5.pptVIP

第四章 割 集 4.1 割集与断集 定义4.1.2 图G中端点分别属于V1和 的所有边的集合称为G的断集(seg)。 E(V1×V2)表示一个端点在V1中，另一个端点在V2中的所有边的集合。 4.2 关联图 线性空间R的一个线性无关极大组叫做空间的基底，基底中所含的向量的个数叫做空间的维数。 5.2 圈 空 间 5.3 割集空间 * * 定义4.1.1 则称边集S为图G的的一个割集(cut set)。 我们定义连通图G的顶点数减1为图G的秩，记作R(G)，即R(G)=p-1 如果G有k个连通分支，则R(G)=p-k 割集是指一个边集S，在G中去掉S的所有边后G变 为具有两个分支的分离图，但是去掉S中的部分边时图仍然是连通的。 b a d c f e g 1 2 3 4 5 f d e g 1 2 3 5 g g 1 a e 2 4 5 g 3 1 a f e g 2 3 4 5 3 a b 1 2 4 5 d f d 1 2 5 4 b a 3 b a d c f e g 1 2 3 4 5 1 2 3 f 7 1 e d 6 c 5 b 4 a 10 1 2 h 9 i 8 l c 3 4 e 5 6 g 7 V1 10 1 2 9 8 3 4 5 6 7 1 a b 3 4 5 h g d e f c V1 V2 2 1 a b 3 4 5 h g d e f c V1 2 V1 定理4.1.1 设T是连通图G的一棵生成树，并且e是任一树枝，则： （1）连枝集中不包含G的割集。 定理4.1.2 连通图G的一个割集至少包含生成的一个树枝。 定义4.2.1 设v是图G的一个顶点，与v关联的所有边的集合，称为顶点v 的关联集，记作S（v）. 1 a 2 d c b 4 e 3 f g h 5 6 9 i 7 k l 8 j 1 a 2 c b 4 5 6 3 h l 9 7 k 8 割点、割集、断集？ 引理4.2.1 设V1，V2 ， V3 ， V4是图G 的顶点集合的非空子集，其中任何两个的交均为空集，则： 引理4.2.2 设V1和V2 是图G 顶点集合的非空子集，则： 其中 定理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 设 为n个向量，如果存在n个不全为零的数， 使等式 成立 ，则称 线性相关，否则称为线性无关。 其中 则称 为 的线性组合。 设S是一个n维向量组，如果S中任一向量都可表示成向量 的线性组合，则称 是S是的生成元素组。又若 线性无关，则称 是一个线性无关极大组。 命题5.1.1图G中所有不同的子图的个数是2q(包括图G中空图 )。 定题5.1.1集合 在环和运算与数乘运算： 下构成域 上的一个q维向量空间。 设G1,G2,…,GN（N=2q）是图G的全部子图， 则有下面的定理。 定义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的生成树不是唯一的，因而一个图的基本圈组也不是唯一的。