通信网理论基础3章1节etudiant

1、第三章通信网结构3.1. 图论基础3.1.1. 基本定义基本定义=端集边集V = v1E = e1v2 e2v3 e3vn em 二元关系R : V V R E图当二元关系 R 存在时V 和 E 组成图 G记为G =VE图 G 中的 V 集是任意给定的而 E 集只是 V 集中两个元的关系若 viVvjVvi Rv j则当且仅当 vi R vj时即 vi 对 vj 有某种二元关系如邻接关系时er Eer E才有某个 erE也可以有多个 erE与 vi 和 vj 对应反之一个 er 只能对应于一对端但这两个端可以是同一端er 的每个端称为与 er 相关联的端 er 的两个端称为邻接端v2e2e3v

2、1v3e4e1e2e5v4v5=无向图若 vi 对 vj 有某种关系等价于vj 对 vi 有某种关系vi则称这种图为无向图vj 是无序的即 vi vj = vj vi=有向图若 vi 对 vj 有某种关系vj 对 vi 有某种关系并不意味着则称这种图为有向图如转移关系 关系是有向的vi 可以转移到 vj所以是有向图并不意味着vj 可以转移到vi这种vivj 是有序的即 vijvjiv2e2e3v1v3e4e1e2e5v4v5=空图端集为空集 V当然边集也为空E的图称为空图=孤立点图但端集不空 V 边集为空 E点图在一个图中例端间无关系则称为孤立无端必定无边但无边却不一定无端v2v3v4v1=全

3、联结图任何两端之间都有一条边的图记为 Kn称为全联结图=有限图当集合 V 和 E 都为有限集时所的图称为有限图=无限图反之为无限图当集合 V 和 E 都为无限集时所的图称为无限图=图的几何表示v2v2v2e1e2e2e3e4e3e4v1v1v1e1v3v3v3c. 孤立点图a.无向图图 a 中b. 有向图边 e1 称为自环e1 所关联的两个端为同一端边 e3e4 称为重边e3 和 e4 关联相同的两个端 v2v3图 b 中边 e3 和 e4 不是重边因为它们的方向不同但二者可以合并成为一条无向边e1 为无向边它也可以拆分成两条不同向的有向边任何有限图都可表示为三的几何图形则有限图可以画在二维平

4、面上若两条边的交点不认为是端点一个图画成几何图形时端点的几何位置是任意的 线的长度和形状也是任意的即可以是直线也可以是曲线即图只规定了拓扑特征而不考虑具体的几何特性图的同构有图 G1有变换 f如下图V1 E1和 G2V2 E2V1V2使端集一一对应且保持边的关联则称以上二图同构图对于某些实际问题也还需要考虑几何特性为此可以对端和边赋予某些数值这样的图称为weight图边或端上所赋的值称为权值或权一条边或一个端的权值也不限于一个性质如在电路图中可以用几个权来表示几种端的权值可以是电位边的权值可以是电流而在通信网中端可以是交换局端的权值可以是该局造价交换容量等 容量长度等边可以是信道边的权值可以是

5、信道的造价又如公路网铁路网邮政网给水和排水等等都可以有不同的权值线路等级价格速度=图论在逻辑分析方面的应用图论除了适用于几何图形性质的应用以外还在逻辑分析逻辑推理等方面也有广泛应用如用 n 位 D 寄存器产生 M 序列的状态转移过程就可抽象为图n 位移位寄存器可以产生种状态2n每个状态可以用图的一个端来表示状态的转移可以用有向边来表示M 序列所有状态在一个周期中只出现一次所以需要找出一个环它遍历所有状态令 n313025746图 33有两种可能的环路001253640735746对应于两个 M 序列0 1 0 1 1 1 0 00 1 1 1 0 1 0 0图的运算=图是集合 V 及其关系 E

6、 的综合 VE 即 GVE 所以集合论中的一些概念及术语可以移植过来=子图图 A 的端集和边集分别为图 G 的端集和边集的子集VA VEA E即GVE AVAEA 则图 A 是 G 的子图记为A G例图 A 为 G 的子图v2v2e1e1e2v1v1v3e4e3e4v4G任何图都是自己的子图v4AA G 也包括 AG即=真子图若 A G若 A G但 A G则称 A 为 G 的真子图且 G A则必有 AG=支撑子图特别地当 VAV 时称图 A VEA 是图 GVE 的支撑子图=补图若图 GVE 则图GCVEC称为图 G 的补图其中 EC 是集合 E 的补集E 的全集为全联结图的边集C如全联结图的

7、补图 Kn 是只有端而无边的图即为孤立点图=并图图 Gc 的端集和边集分别为图 Ga 与 Gb 的端集和边集之并例Vc Ec记为VaVb EbEaGcGaGb称图 Gc 为图 Ga 与 Gb 的并图v4v4e3e3v1v2v1v1v2e1e1e2e1e2v3Gav3Gbv3Gc=交图图 Gc 的端集和边集分别为图 Ga 和 Gb 的端集和边集之交Vc Ec记为例VaVb EbEaGcGaGb称图 Gc 为图 Ga 与 Gb 的交图v4e3v1v2v1v1e1e1e1e2v3Gav3Gbv3Gc=差图从图 Ga中减去Ga和 Gb 的共有边和共有端但保留未去掉的边所关联的端记为GcGaGbGaGa

8、Gb称图 Gc 为图 Ga 与 Gb 的差图例v4e3v1v2v1v2e1e2e1e2v3Gav3Gbv3Gc=环和图从图 GaGb 中去掉 Ga 和 Gb 的共有边Ga Gb记为GcGaGbGaGb=直和Gb若图 Ga空图则 Ga 和 Gb 的并图可记为并称它们为直和GaGbGaGb=直差若 Gb Ga即 Gb 是 Ga 的真子图则 Ga 与 Gb 的差图可记为并称它们为直差GaGbGaGb3.1.2. 图的联结性3.1.2.1.端的度数=记为 d(vi)端的度数与某端相关联的边数无向图例 1d(v1)=3v2e1e2d(v )=42e3v1v3d(v )=33e4e5d(v )=24v4例

9、 2有向图d+(vi)d (vi)d (vi)表示离开 vi 端或从vi 端射出的边数表示进入 vi 端或射入 vi 端的边数d+(vi)d (vi)表示 vi 的度数v2e1e2 vve313e5e4v41d+(v1)d+(v2)2dd (v1)d (v1)d (v2)34(v2)2 (G) mind (vi )图 G 中端的度数最小值端的度数最大值vi V(G) maxd (vi )vi V3.1.2.2.图的度数的性质=图的度数的性质(1) 对于有 n 个端m 条边即 V n , m的图则必有En d (vi ) 2m31i1 nni1d (v ) d (v ) m对于有向图证明iii1

10、因为 每条边都将提供度数 2所以 一定有上式成立(2) 任何图中度数为奇数的端其数目必为偶数个或零个证明将图的端集 V 分为奇度数端集 V1 和偶度数端集 V2VV1V2则有 d (vi ) d (v j ) d (vk ) 2m由(3-1)式vi Vv j V1vk V22m 也是偶数d(vk)d (vk ) 是偶数因为所以 d (v j ) 必为偶数v j V1d (v j ) 是奇数由于 d(vj)V1 中 vj 的个数必为偶数所以3.1.2.3. 图中的链径环=边序列定义vi1ei1vi2有限条边的一种串序排列相邻两边有公共端称为边序列ei2vik viteik eitvik+1 vi

11、t+1lit=称为 vitvit+1 链其中在边序列中某条边可以重复出现某个端可以重复出现例v2e2e1e3e4v3v1e6e5v4v5e1,e3,e5,e4,e3,e6是一个边序列=链定义没有重复边的边序列链中每条边只能出现一次但可以有重复端链通常是指开链链中只有两个端即起点和终端不是同一端其度数为奇数e1,e3,e5,e4,e2是一条从 V1 到 V3 的链如前例v2e2e1v3e3端 V2 在序列中经过两次其中e4v1e6e5v4v5=径path定义径是既无重复边又无重复端的边序列或无重复端的链在径中每条边和每个端都只能出现一次径又是无环的链在一条径中只有起点和终端的度数为 1其余端点的

12、度数均为 2如前例e1,e3,e5是 V1 到 V4 的之间的一条径v2e2e1v3e3e4v1e6e5v4v5=环ring定义例起点和终点为同一端的链即闭链=圈circle定义顶点不相同的环即闭径=对于有向图的链径环可有相仿的定义只是在其边序列中相邻两边对共有端而言前面的边必须是射入边后面的边必须是射出端3.1.2.4.联结图=定义图内任何两个端之间都有径否则称为非联结图这类图称为联结图=非联结图非联结图总可以分成几个部分部分是指原图的一个子图此子图是一个最大联结图最大联结子图是联结图但若再加上一个属于原图的任何一个其他元素例就失去联结性成为非联结图v4e4G2e5G1e1v5v6G3v9e

13、6evve2v2313ve78e7v8此图为非联结图由三个部分 G1G2 和 G3 组成即GG1G2G3G1G2 和 G3 都是最大联结子图若将 G1 中去掉一条边 e1则它们是图 G 的一个子图但它不是图 G 的一个部分所以它不是最大的=简单联结图无自环无重边的联结图今后主要研究这种图=全联结图 Kn定义任何两端都有边的无向图称为全联结图一个无重边无自环的全联结图的边数 m 和端数 n 之间有固定关系 n n(n 1)m C 22n2 因为任取两端都有一条边各端的度数均为d(vi)=n-1全联结图是联结性最好的图例n5 的全联结图=正则图定义所有端的度数都相等的联结图称为正则图d(vi)=常

14、数i1,2,nn 为图的端数或者(G) =(G) (G) (G)正则图的联结性最均匀在要求确定的联结性时正则图是边数最少的图无重边无自环的全联结图是正则图正则图不一定是全联结图例d(vi)=2n5d(vi)=3n6n=图定义各端度数均为偶数的图图论的创始人称为图图可以是联结图也可以是非联结图如果是非联结图则其各部分必均为联结的图在联结的图中一定可以找到一个包含所有边的环反之结的联结如果在图中存在一个包含所有边的环图则此图必为联所以两个例v2图的充分必要条件是存在一个包含所有边的闭链图的环和仍是图v2v1v3v1v3v1v3v4图可能有几个子图是 图的环和仍是原图的v4一个非图这些图图的特点能从

15、一点出发经过不重复边回到源端点出发点=M 图图中只有两个度数为奇数的端这种图称为 M 图定义在 M 图中除两个端外其余所有各端的度数均为偶数M 图可以是联结图也可以是非联结图对于非联结的 M 图其只有一个部分是 M 图图其余各部分均为联结 M 图的充要条件是存在一个包含所有边的链图去掉任一边就成为 M 图实际上任一例而 M 图在度数为奇数的两个端之间加一条边即成为图v2e1e2v1v3e5e4e3v4这是一个 M 图存在一条包含所有边的链e1e2e3e4e5如又如e5e3e4e1e2其起点与终点一定是度数为奇数的两个端点由于不存在包含所有边的环所以不是图=图H 图图中至少存在一个包含所有端的环

16、定义这种图称为这样的环称为 H 图的充要条件是例图环简称为 H 图存在一个包含所有端的环v2e2e1e7v1e6e3e5vv4e45这是一个 H 图其中的e1e2e3e4图e5如下 4环为前面的图 3.3 是一个有向的其中的环71020613134020为6或45025757363.1.3. 树=树是图论中一个重要的概念许多理论结果都是从树出发的3.1.3.1.定义=定义任何两端间有且仅有一条径的图称为树树又多种定义方法它们都是等价的树是有 n 个端 树是最小联结图n-1 条边的联结图=树是一种图其任何两端间都有径 其任何两端间仅有一条径3.1.3.2. 树的性质树的性质=树是最大的无环联结图

17、因为任何两端间有径所以一定是联结图因为任何两端间只有一条径所以一定无环只要增加任何一条边图中就会出现一个环且仅出现一个环所以是最大的无环图=树是最小联结图树中去掉任一边就成为非联结图所以是最小的联结图丧失了联结性=若树有 m 条边及 n 个端则有 m=n-1=除单点树外树至少有两个端的度数为 1即树至少有两个悬挂点证明对于有 n 个端m 条边的图来说有n d (vi ) 2mi1有m = n-1又对于树n d (vi ) 2(n 1) 2n 2对于树就有i1这意味着如果每个端的度数都为 2 的话则n d (vi ) 2ni1所以有两个端的度数必须为 1个端的度数大于 2 的话个端的度数为 1如

18、果有一个或则会有命题得证3.1.3.3.举例例=根树=星树=线树3.1.3.4.主树主树=覆盖联结图 G 所有端的树T称为 G 的主树定义亦称支撑树在联结图 G 中若树 T图 G且 T 包含了 G 的所有端点=则称 T 是 G 的主树=性质只有联结有主树有主树的图必为联结图 一个联结图可以有多个主树图 G 本身已是树的情况除外例联结图至少有一棵主树=图 G 的一棵主树可以是根树e1v2e1e2e7e4e2v1 e5v5ee6v37e3v4e4图 G 的另一棵主树是星树e3v2e4e6e7e1e2v1 e5v5ee67v3e3v4e4图 G 的另一棵主树是线树e1v2e2e3e4e1e2v1 e

19、5v5ee6v37e3v4e4=树枝对于某个图 G定义其主树上的边称为树枝非树枝的边称为连枝主树就是树枝集连枝的边集称为连枝集或树补不同的主树有不同的连枝集=图的阶联结图 G 的主树 T 的树枝数称为图 G 的阶记为若图 G 有 n 个端(G)= | T | = n-1则它的阶数是(G) T n 1| X |代表集合 X 中的元素数图的阶表示主树的大小取决于图 G 中的端数=图的空度定义联结图 G 的连枝集的连枝数称为图 G 的空度记为 若图 G 有 m 条边和 n 个端时则其空度 为(G) = | G T | =m-n+1(G) G T m n 1 + = m显然有图的空度表示主树覆盖该图的

20、程度 越小覆盖程度就越高= 0 表示图 G 就是树主树 T 覆盖了全图图的空度还反映出图 G 的联结程度主林 越大则连枝数越多图的联结性就越好= 0 表示最低联结性即图 G 是最小联结图=定义对于一个非联结图 G它可分成 k 个部分即 k 个最大联结图每个部分至少有一棵主树一共有 k 棵主树它们的集称为主林其余边所形成的集称为主林和也不是唯一的(G)=n-k非联结图 G 的阶可定义为主林的边数(G) n k的边数(G) = m-n-k非联结图 G 的空度可定义为(G) m n k若 k=1则成为联结图但 和 却是确定的主树或主林可以有多个3.1.3.5.小结=以上对树的都是从无向图出发的可以去

21、掉边上的方向而得到无向图对于有向图仍用上述定义此时联结两端的有向径可能不一定存在3.1.4. 割与环=在在图的联结性时常用树的概念破坏图的联结性时常用割的概念割3.1.4.1.=cut割是图的某些子集若图 G 是联结的割去掉这则去掉这集就使图的部分数增加集就成为非联结图割分为割端集和割边集两种割端和割端集3.1.4.2.割端和割端集=割端若 v 是图 G 的一个端去掉 v 及与之相关联的边后则称 v 是 G 的割端使图 G 的部分数增加割端对于图的联结性来说是一个重要的端例割端=不可分图没有割端的图即去掉图中任一个端及其相关联的边图的部分数不变例这样的图称为不可分图若原图是联结的则去掉任一端及

22、其相关联的边后仍是联结的=割端集如果去掉几个端后图的部分数增加例则这些端的集称为割端集v4vv25v1v3v6此图的割端集有v4,v2,v3,v2,v4,v3,v4,v1,v4其中v4 就是割端最小割端集在一个图的割端集中割端集至少存在一个端数最少的割集称为最小v4就是最小割端集上例中3.1.4.3. 图的联结度=图的联结度在图 G 中定义其最小割端集中的端数称为图的联结度= min|X|用X表示割端集图的联结度表示要破坏图的联结度的难度联结大联结性越好联结性越不易被破坏它是从端点的角度来看网的联结性的它对网的可靠性有直接影响即网络节点对网络可靠性的影响割边集和割集3.1.4.4.=割边集和割

23、集割边联结图 G 中某条边被去掉后则此边称为割边图G 变为非联结图割边集设 S 是联结图 G 的某个边子集若在 G 中去掉 S就使G 成为非联结图则称 S 是 G 的割边集割集最小割边集例若 S 的任何真子集都不是割边集则称 S 为最小割边集或割集v2e1e2v1 e5v5ee6v37e3v4e4e1,e4,e6,e7是一个割边集但不是割集它的真子集e1,e4,e6也是割边集Qe1,e4,e6e1,e5,e6e2,e3e2,e5,e6,e7都是割集最小割集在图 G 的若干割集中边数最少的割集称为最小割集例中e2,e3是最小割集之一图的结合度3.1.4.5.=图的结合度图的最小割集的边数称为图的

24、结合度= min|Y|用表示Y割集图的结合度表示图的连通程度它是从边的角度来看网的联结性的也对网的可靠性有直接影响即网络的边对网络可靠性的影响结论3.1.4.6. 2mn n m图 GVE则 d (v) 2m n mind (v) 2mn证明vVvV要破坏图 G 的联结性其含义是至少应破坏 或至少应破坏个端点条边但需破坏的端数不会多于边数二者都不会多于图中各端最小的度数三者都不会多于 2mn若去掉割集 S 后变成G对任意图包括联结图和非联结图则有(G) (G) (G) (G S ) 1GS其含义是树枝从图中去掉割集对应到树上相当于去掉一个3.1.4.7. 基本割集与基本环=基本割集与基本环为列

25、举联结图的所有割集基本割集需要建立基本割集和基本环的概念设 T 是联结图 G 的一棵主树取一条树枝与某些连枝一定能一个割集称之为基本割集基本割集只有一条树枝若图 G 有 n 个端则其主树有 n-1 条树枝G 有 n-1 个基本割集从基本割集出发利用环和可求出图 G 的所有割集基本割集举例s1e1s4e2 s2Ge6e3e5s3e4如上图 G取主树 T = e1, e3, e4, e6则连枝集为e2, e5于是可等到基本割集如下与 e1 对应与 e2 对应与 e4 对应与 e6 对应S1=e1, e5 S2=e2, e3 S3=e4, e5 S4=e6, e2, e5这四个基本割集与四条树枝一一

26、对应所以它们是线性独立的以它们作基 用环和运算可以生成一个子空间到24 C1 C 2 C C 个元44每个元或为割集或为割集的并即当两个基本割集有公共连枝时其环和是另一个割集而当两个基本割集无公共连枝时其环和是二者的并集注割集的并是割边集但不是割集共有 4 个基本割集其含义是1C4由其中 2 个可生成个2C4343由其中由其中个可生成个C44个可生成个C割边集4图 G 的全部割集都包含在这些割边集中除四个基本割集外还有*S5 = S1S2 = S1S2 = e1, e2, e3, e5S6 = S1S3 = S1 S7 = S1S4 = S1*S8 = S2S3 = S2S3 - S1 S4

27、- S1S3 = e1, e4S4 = e1, e2, e6S3 = e2, e3, e4, e5S9 = S2S4 = e3, e5, e6S10 = S3S4 = e2, e4, e6*S11 = S1S2S3 = S6S2 = S6S2 = e1, e2, e3, e4S12 = S1S2S4 = S5S4 = e1, e3, e6*S13 = S1S3S4 = S6S4 = S6S4 = e1, e2, e4, e5, e6S14 = S2S3S4 = S8S4 = e3, e4, e6*S15 = S1S2S3S4 = S6S9 = S6S9 = e1, e3, e4, e5, e6

28、最终S3而标会发现这 15 个割边集中有 10 个是割集S1S2S4S6*S7S9S10S12S14号的都不是割集如S5 的子集e1, e5是割集所以 S5 不是割集基本环取一条连枝可与某些树枝闭径或环这种仅由一条连枝的环称为联结图的基本环基本环的数目等于连枝数共有 m- (n-1)个2m-n+1-1 个元的子空间以及环的并用环和运算可其中包括环基本环举例如前例e1e2Ge3ee56e4取主树 Te1, e3, e4, e6则连枝集为e2, e5基本环有两个与 e2 对应C1 C2 e2, e3, e6 e5e1, e6, e4与 e5 对应利用环和可以形成 26-5+1-13 个元的子空间其

29、中两个是基本环C1C2C3e1, e2, e3, e4, e5另一个是C3 C1 C2 e1 , e2 , e3 , e4 , e5 3.1.4.8. 环与割是对偶的关系=环与割是对偶的关系3.1.5. 平面性和对偶性图的平面性可以不讲=定义G若图画在平面上时除端点外任何两条边可以没有其他交点则称 G 为平面图公式或称 G 具有平面性=设一个联结的平面图有m 条边n 个端把平面分成 S 个区域包括开区域即 S 是指图中所有的环及外空间的个数公式Smn2则有著名的证明用数学归纳法当 S=1 时的开区域全平面只有一个区域即只有一个包括无限远点不存在环这就是树的情况m=n-1公式成立下面来证明当 S

30、 = r 时已知树的边与端的数量关系是所以mn2 = (n-1)n+2公式成立设当 S=r-1 时公式成立因为 r 2 时去掉这环的一条边边数成为 m-图内必有环1区域数也将减少一成为 r-1即 m-1 条边和 n 个端把区域分成 r-1 个依假设此时公式是成立的即r-1= (m-1) n+2S = rmn2整理后得到可见公式成立证毕=平面性的必要条件对于无重边无自环的联结图n 3具有平面性的必要条件是m 3n6这是因为在无重边无自环的条件下要形成一个区域至少要三条边又一条边只能介于两个区域之间即只能计算两次2m 3S( 2m 3S )所以有把公式代入即证但不是充分条件注意此不等式为必要条件因

31、为形成一个区域也可能用了 4 条边或见下例虽然图 1 和图 3 都满足此不等式但图 1 是平面图而图 3 则是非平面图例平面图n m 3n4666图 1非平面图n m 3n51069图 2非平面图n m 3n69612图 3=用图论来分析通信网问题时图的平面性并不很重要因为通信线路在架设或埋设时是可以交叉的但在电路印制板和集成电路等技术中则显得很重要图的对偶性=定义例设有两个边集 E 相同的图 G1 和 G2无自环一一对应若 G1 中的割集G2 中的环二者具有对偶性则 G1 与 G2 互为对偶图=e1e3G2G1e3e5e2e4ee24ee15G1 中的三个割集对应于 G2 中的三个环G1 中

32、的割集 G1 中的割集 G1 中的割集e1,e2,e3 e3,e4,e5 e1,e2,e4,e5G2 中的环G2 中的环G2 中的环e1,e2,e3 e3,e4,e5e1,e2,e4,e5e1G2e3eeeG132ee424e1e5e5反之G1 中的六个环对应于 G2 中的六个割集分别为e1,e2 e2,e3,e4e4,e5e2,e3,e5e1,e3,e4e1,e3,e5二者具有对偶性所以G1 与 G2 互为对偶图=对偶图的存在性平面图的对偶图总是存在的而非平面图不可能有对偶图例平面对偶图的方法如图 G1把平面分成三个区域每个区域内各取一点 v1, v2, v3作为对偶图的三个端e5v v1e

33、2v23ee v1v211e1e3.v e e51e2e2v23e3v3e5e4v3e4e4v4G1G2把分隔两个区域的边用作对偶图中两个端的联结边即在两两端间作连线线使每个连线穿越这两个区域间的一条分界这样就了对偶图 G2对偶图 G2 将平面分成四个区对应于原图的四个端=自对偶定义如果一个图 G 的对偶图就是自己性质则称 G 为自对偶图例自对偶图必为平面图自对偶图的区域数必等于端数自对偶图的端数 n 与边数 m 有确定的关系m2n2n4m6 的自对偶图为e5e5e1e2e2e4e6e6e3e4e1e3G1G23.1.6. 图的矩阵表示=图的几何表示具有直观性图的矩阵表示则适于数值计算和分析图

34、的矩阵表示与几何表示一一对应可存入计算机关联矩阵=关联矩阵是表达全关联阵 A0 定义端与边的关联性的矩阵设图 G 有 n 个端m 条边以每端为一行以每边为一列作 nm 矩阵A0 aij n m1若ej 与vi 关联 若ej 与vi 不关联若ej 是vi的射出边a无向图ij01a 1若e 是v 的射入边有向图ijji若ej 与vi 不关联0例如图n4m5e1v1e4 v4e30011v2 e2v3e5e3e1v1 1e20110e410e51v2 10全关联阵A0 v3 00100v14 nm特点每行中非零元素的个数等于该端的度数d(vi)若行向量是零向量则该端是个孤立端若行向量仅有一个非零元素

35、则它是一个悬挂端对于无自环的图任一边必与且仅与两个端相关联1 和1所以列向量中有且仅有两个非零元素有向图为且和值必为零无向图用模 2 和有向图用算术和所以n 个行向量不是线性无关的而是线性相关的最多只有 n这意味着1 个线性无关的向量在全关联矩阵中有一个行向量是多余的即使去掉后也是可以补上的不会丢失信息所以不用写在矩阵中=关联阵定义从全关联阵中去掉一个行向量后得到的矩阵称为关联阵关联阵已能充分代表一个图去掉的一行所对应的端可作为图的参考端如电路图中的接地点例如前例去掉 v4 端的行向量e1v1 1e2011e3001e4100e5110则关联阵为A v2 1 (n1)mv3 0根据关联阵判断联

36、结图对于联结图关联阵的阶是 n1实际上这就是图的阶即主树的边数n1 A 对应一个联结图也可以表示为r(A)由此可知联结图的关联阵中n1n1必存在至少一个非奇异的方阵这个方阵所对应的边集就是一棵主树根据关联阵判断环的存在若关联阵中有一个即其行列式值为零n1n1方阵为奇异的则这方阵所对应的边集中必存在环因为形成环的边所对应的列向量必线性相关从而使行列式值为零例 1前例中取边 e2,e4,e5方阵e2v1 0e4100e5110A v 0 1 1 0A12 11v3 1A1 为非奇异矩阵v1e4v4e2,e4,e5所以树v2 e2v3e5例 2前例中取边 e1,e2, e5方阵e1v1 1e2011

37、e51模2加 1 1 0A210A v22 1v3 0A2 为奇异矩阵所以对应边中有环不是主树e1v2 e2v3v1e5当关联阵的阶小于 n1 时它所对应的图必为非联结图n1n1因为没有一个方阵是非奇异的也就是没有主树根据关联阵计算联结图的主树数目S| AAT |计算联结图的主树数目S 的公式AT例 1是 A 阵的转置如前例由于此法只对有向图是准确的方向所以应在原图上随意加上e1v1e4v4v2 e2v3e5e3 110 10 e1v1 1e201 1e3001e4 100e5 1 1 21 0v 10 1S AAT2 v3 0 1由于本例较为简单可以换树枝数为 4法验证一下13有四个端有五条

38、边C 10 种3可能形成树的情况有5其中有 2 种是三条边形成的环另 8 种是树方阵 AAT 可以从图中直接求得而不必先求关联阵 A其实AAT 是对称矩阵11 3 121AAT 的元是 A 的行向量的内积对角线上的元就是该端的度数其他元为 0 或 1两端之间无边 则内积必为 0 113 两端之间有边则内积必为1因为边对之一端为1另1一端必为割阵=割阵是表达割集与边的关系的矩阵定义具有 n 个端m 条边的联结图具有n1 个基本割集n1m 的矩阵所以割阵是一个它对应于某一棵主树 每行对应一个基本割集每列对应一条边对于有向图割阵元素为基本割集的方向取树枝的方向为正ij( n1)m对于有向图1若ej

39、在基本割集Si内且与割集同向若ej 在基本割集Si内且与割集反向 1qij0若e 不在基本割集S 内ji对于无向图若ej Si若ej Si1qij0例如图S2v2ev11S1ee3e4v3v4e5e6e7S3v5S4以e2,e3,e5,e6为主树有 4 个基本割集S1 S3e1,e2 e4,e5,e7S2 S4e1,e3,e4 e6,e7割阵为2e1s1 1e21000e30100e40 110e50010e60001e70 10 s2 1 Q s3 00 1s4 重排 Q 阵边的次序将树枝放面e2s1 1e3010e5001e6000ee0 11e11000 ss IQ 2 Q 1 ft3

40、s4 InQt nn +1I 是11其中Qt 是阵对应树枝n1m矩阵对应于连枝=由割阵的行向量的环和可以得出全部割集的矩阵因为基本割集的环和可以求出全部割集环阵=环阵是用环与边的关系来表达图的定义联结图的环阵也是针对某一主树的以基本环为行环阵是一个 对于有向图 环阵元素为边为列n +1mm 的矩阵环的方向取连枝的方向B b ij(mn1)m对于有向图1若ej ci若ej ci若ej ci且二者同向且二者反向b 1ij0对于无向图若ej ci1b0ij若e cji例如前例e1c1v1e2v2e3e4c2v3v4e5e6ce37v5取主树e2,e3,e5,e6有三个基本环C1 C2 C3e1,e3,e2 e4,e5,e3 e7,e6,e5环阵为e2c1 1e3 11e50 1e600eee00 B I cB012 ftc3 BtI的树枝Bt 对应是m n +1nm1n1阵其中矩阵I 对应于连