当前位置：文档之家 › 14-L.03 图的关联矩阵及生成树数目

14-L.03 图的关联矩阵及生成树数目

  • 格式：pdf
  • 大小：376.33 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

离散数学中的生成树与生成树计数

离散数学中的生成树与生成树计数

离散数学是计算机科学中的重要学科，其中生成树是一个重要的概念。

在图论中，生成树是一棵树，它包含了图中的所有顶点，并且是由图边组成的无环连通子图。

生成树在图论中有着重要的应用，特别是在计算机网络、运筹学和电路设计等领域。

生成树的概念与基础就是组成它的边是有限的，并且连接图中的所有顶点，但没有形成圈回到起点。

生成树通常是用来描述一个系统的最小连接方式。

生成树可以应用于计算机网络的设计中，用于构建最小生成树算法，以便在网络中选择最小的数据传输路径。

此外，在运筹学中，生成树被用于求解最小生成树问题，即为一个加权图找到一棵包含所有顶点的生成树，使得树中边的权重之和最小。

在离散数学中，生成树计数是一个重要的研究分支。

生成树计数是指对给定图，计算其生成树的数目。

生成树计数的问题可以通过使用基于图论和组合数学的算法来解决。

通常，生成树计数的问题与相应图的特性和性质密切相关。

对于一个简单图来说，如果图中任意两点之间至少有一条边，那么该图一定存在生成树。

对于有 n 个顶点的连通图来说，它的生成树数量可以通过Cayley公式计算得到。

Cayley公式表明，一个有 n 个标号的顶点的完全图的生成树数量等于 n^(n-2)。

而对于非完全图，生成树的计数问题则较为困难。

在处理非完全图的生成树计数问题时，可以使用基于递归和动态规划的算法来解决。

一个常见的方法是使用Kirchhoff矩阵树定理，它将生成树计数的问题转化为计算矩阵的行列式的问题。

Kirchhoff矩阵树定理提供了一种计算给定图的生成树数目的有效算法，通过计算图的基尔霍夫矢量的一个特征值，可以得到图的生成树的数目。

另一个常见的方法是使用Prufer编码，它是一个用于描述无环连通图的序列。

通过Prufer编码，我们可以将计算生成树的问题转化为计数树的问题。

通过对无向图进行Prufer编码，我们可以计算出生成树的数目，并且可以根据生成树的数目来确定该无向图的种类和特征。

树与图的生成树

树与图的生成树

9
二维数组AdjUnion[AdjNum][4]：边的信息
1) 二维数组中的每个元素的4个分量分别为标志F、每条边 的起点i、终点j、权值w。
F 0 i 0 j 1 w 28
2) 标志位初始值为0，表示边没有加入到生成树中，初始 时边的集合为空集。 3) 标志位的修改，当查找到权值最小的边，并且这条边的 2个顶点不在同一个连通分量上，则修改对应的标志位 为1，如果在同一个连通分量上，则这条边要舍去，对 应的标志位设为-1。
1) 输出这条边;
2) 将标志位置为1;
3) 在VerUnion数组中将以顶点j所在的连通分量的每 个顶点为下标的元素值设为VerUnion[i];
3. 重复执行1、2步，直至最小生成树中的边数为VerNum-1
11
AdjUnion F
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
14 16 10
0
14
1
16
5
25 24
6
18 22 12
2
5
25
6
2
12
4
3
4
22
3
在Prim算法运算过程当中，需要知道哪些 信息？1.V集合内各顶点距离U内权值最小 的边的权值；2. V集合内各顶点距离U内 哪个顶点最近(权值最小)。
17
采用邻接矩阵来存储图。为了实现上述思想，必须定义 2个 辅助数组： lowcost[ ]: 存放顶点集合V(生成树外)内的各顶点到顶点集合 U(生成树顶点集合)内的权值最小的边的权值。
j=0; int count=0; while(count<VerNum-1) { int min=MAX; for(k=0;k<AdjNum;k++) //找到权值最小的边AdjUnion[j]; (1) if(AdjUnion[k][0]==0 && AdjUnion[k][3]<min) { min=AdjUnion[k][3]; j=k;}

14-L.03 图的关联矩阵及生成树数目

14-L.03 图的关联矩阵及生成树数目

− 例.
v1 ⎡ 1 1 1 0 0 0 0 ⎤
v2 ⎢⎢−1 0
0
−1
0
−1
0
⎥ ⎥
v3 v4
⎢ ⎢ ⎢
0 0
−1 0 0 −1
1 0
1 −1
0 1
0⎥
0
⎥ ⎥
v5
⎢ ⎢
0
v6 ⎢ 0
0 0
0 0
0 0
0 0
0 1⎥ 0 −1⎥⎥
v7 ⎢⎣ 0 0 0 0 0 0 0 ⎥⎦
a1 a2 a3 a4 a5 a6 a7
k1a1p + k2a2p +… + kl alp = 0， 1≤ p ≤ m 注意到 kj≠0 (1≤ j ≤ l)，而 B 中每列只含一个+1元和一个‐1元，其它都是0元。 欲使上式成立，a1p , a2p , … alp 中必须同含一个+1和一个‐1元，或只含0元。例 如，假如其中只含一个+1元 at,p，1≤t≤l，则有：
∑ det(AB) = AjBj
( j)
其中，Aj 是从 A 中取第 j1, j2 …jm (1≤ j1 ≤ j2 ≤ … ≤ jm ≤n ) 列组成的行列式， Bj 是 从 B 中取第 j1, j2 …jm 行组成的行列式，∑ 是对所有满足 1 ≤ j1 ≤ j2 ≤ … ≤ jm ≤n 的排列( j1, j2 , …, jm ) 求和。
k1V1+ k2V2+… + kn‐1Vn‐1 = 0 不妨设 kj≠0 (1≤ j ≤ l ≤ n‐1 )，ks=0 (l <s≤ n‐1), 则有：
k1V1+ k2V2+… + klVl = 0 若设 Vj =(aj1, aj2, …, ajm)，(m=|A|, 1≤ j ≤ l)，考察 m 维向量 k1V1+ k2V2+… + klVl 的第 p 维分量

算法合集之《生成树的计数及其应用》

算法合集之《生成树的计数及其应用》

算法合集之《生成树的计数及其应用》生成树是图论中的一个重要概念，指的是一个连通图中的一个子图，它包含图中的所有顶点，并且是一个树结构，即没有回路。

生成树可以应用于许多实际问题中，如网络设计、电路设计等。

生成树的计数是指给定一个图，计算其中生成树的个数。

本文将介绍生成树的计数方法及其应用。

生成树个数的计数方法主要有两种：基于度数矩阵的方法和基于邻接矩阵的方法。

基于度数矩阵的方法是通过度数矩阵计算生成树的个数。

度数矩阵是一个n*n的矩阵，其中第i行第j列的元素表示顶点i的度数。

对于一个连通图，它的度数矩阵满足以下性质：矩阵中每个元素都是对称的，对角线上的元素为顶点的度数，非对角线上的元素为-1、生成树的个数可以通过计算度数矩阵的行列式的值来获得。

基于邻接矩阵的方法是通过邻接矩阵计算生成树的个数。

邻接矩阵是一个n*n的矩阵，其中第i行第j列的元素表示顶点i和顶点j之间是否存在一条边。

对于一个连通图，它的邻接矩阵满足以下性质：矩阵中每个元素都是对称的，对角线上的元素为0，非对角线上的元素为1、生成树的个数可以通过计算邻接矩阵的专门构造的拉普拉斯矩阵的行列式的值来获得。

生成树的计数方法在实际应用中有着广泛的应用。

以下是两个典型的应用案例。

1.网络设计：在网络设计中，生成树可以用来表示一个网络的拓扑结构。

生成树的计数可以帮助设计师在设计网络时选择最佳的拓扑结构，以提高网络的可靠性和性能。

例如，在构建一个数据中心的网络时，生成树的计数可以帮助设计师选择恰当的网络拓扑结构，使得数据中心能够快速传输数据，并且故障时能够保持高可用性。

2.电路设计：在电路设计中，生成树可以用来表示电路中的连接关系。

生成树的计数可以帮助设计师评估电路的性能，并且选择合适的电路结构以优化电路的功耗和响应速度。

例如，在设计一个数字电路时，生成树的计数可以帮助设计师选择合适的连接方式，以最小化电路中的延迟和功耗。

综上所述，生成树的计数及其应用是一个复杂而重要的问题。

关联矩阵和树的关系

关联矩阵和树的关系

关联矩阵和树的关系
关联矩阵与树的关系主要体现在以下几个方面：
1. 关联矩阵与树的数量关系：对于一个给定的图，其关联矩阵的转置矩阵的行列式值等于该图的树的数量。

这一关系在计算图的树的数量时非常有用，可以大大简化计算过程。

2. 关联矩阵与树的生成：一个图的关联矩阵的子矩阵对应于该图的一棵生成树。

具体来说，如果一个图的关联矩阵的子矩阵非退化，那么该子矩阵对应于该图的一棵生成树。

这一关系使得我们可以通过检查关联矩阵的子矩阵来判断一个图是否包含特定的生成树。

3. 关联矩阵与欧拉图：通过关联矩阵的谱理论，可以研究欧拉图。

如果一个图的关联矩阵的主对角线上的元素均为偶数，那么该图是一个欧拉图。

这一关系有助于我们判断一个图是否是欧拉图，并进一步研究欧拉图的性质和结构。

综上所述，关联矩阵与树之间存在密切的关系，这些关系有助于我们更好地理解图的结构和性质，以及利用关联矩阵进行图论问题的求解。

图论生成树的概念与性质PPT课件

图论生成树的概念与性质PPT课件
充分性 如果Am的列对应的边作成G的一棵生成树，因树是连通的，所以，它对应的 基本关联矩阵Am非奇异。
该定理给出了求连通图G的所有生成树的方法：
(1) 写出G的关联矩阵，进一步写出基本关联矩阵，记住参考点；
8
第8页/共32页
(2) 找出基本关联矩阵的非奇异主子阵，对每个这样的主子阵，画出相 应的生成树。
第19页/共32页
n 2 1
C
1
n 1
0 1
于是由矩阵树定理：
0
1
n 2
n 1 1 1 n 1 (Kn e) 1 1 1 1
1 1 1 1
n 1 1 1 n 2
n 1 1
1 1 n 1 1
1 0
1 n 1 1 1 1 n 1 1 0
1 1 n 1 1 1 1 n 1 0
1 1
例6 求下图G的回路空间的一个基底和它的全部元素。
25
第25页/共32页
a
f
cd
g
e
b
h
G
解：取G的一棵生成树T为：
a
d
g
b T
G对于生成树T的基本回路为：
C1 ,b, d, g, h C4 d, f , g
26
第26页/共32页
图形为：
a c
b
利用破圈法，显然也可以求出任意图的一个生成森林。
3
第3页/共32页
推论 若G是(n, m)连通图，则m≧n-1 连通图G的生成树一般不唯一！
(二)、生成树的计数
1、凯莱递推计数法 凯莱(Cayley 1821—1895): 剑桥大学数学教授，著名代数学家，发表
论文数仅次于Erdos ,Euler, Cauchy. 著名成果是1854年定义了抽象群，并 且得到著名定理：任意一个群都和一个变换群同构。同时，他也是一名出 色的律师，作律师14年期间，发表200多篇数学论文，著名定理也是在该 期间发表的。

矩阵图 关联图ppt课件

印锡时刮刀刮不干净的问题有；刮刀未拧紧；刮刀压 力设置不合理；板子厚度设置不合理；ＧＡＰ值设置 太大；ＰＣＢ ＣＬＡＭＰ表面太脏；顶针支撑不良 ；锡膏黏度太大；刮刀磨损严重；刮刀刀片柔性不够 ；ＰＣＢ板表面不平或有异物
清洗装置清洗钢网不干净的问题有；清洗速度和行程 不对；清洁纸被卡住卷不动；酒精喷管孔被堵住；真 空泵真空吸力太小；清洁纸支撑塑料片磨损严重，接 触不到钢网；清洁机构汽缸上升不到位
ppt课件完整
手段 目的
手段
目的 手段
手段 目結的果
手段 目的
手段
ห้องสมุดไป่ตู้
目的 手段
目的 手段
基本目的
目的 手段
目的 手段
手段 目的
手段 目的
手段
手段
關聯圖中目的和手段的關系
23
3、2关联图实例
下面的圖3.1事例是某一個早上棒球隊用關聯圖分析在地區競賽上輸給A隊的 原因的事例.通過關聯圖一層一層找出原因,最后找出了其主要原因(圖中的3個 网狀框) 明确此主要原因和問題點的強烈的因果關系的路徑(圖中用粗線表示的地方).
聯圖. 探索問題的原因時, 從很多的原因中挑出主要的主要原因, 但是明确問題
的构造時, 對結果性的現象以及可預測到的結果性現象, 或是關于某制品特性的
主要原因是如何等情況時弄清問題的全貌. 手段
目的
手段
(3).展開達到目的的手段 如右圖所示把為了達到 “目的”而采 用必要的手段重新作為目的來考慮. 依 此類推達到 “基本目的的手段” .
纏在一起時利用圖(關聯圖)明确相互之間的關系,探索問題的原因或明确問題
的构造展開達到目標的手段的方法. 原因
(1).探索問題的原因 引起問題的“原因”, 引起此 “原因”的“原因”, 在進一步

图的关联矩阵

图的关联矩阵的研究摘要利用矩阵的形式来对图进行表示，不仅在理论方面便于用代数知识对图进行研究，而且也便于计算机对图进行处理，在图论的应用中具有极其重要的意义，图的关联矩阵是用来表示的图中结点与边的关系，本文首先对图的定义及分类进行描述，再对图中的结点和边的一些性质进行描述，同时对数域和线性空间的定义进行叙述。

其次我们对有向图和无向图中的关联矩阵进行描述，通过举例，让我们更加直观的理解关联矩阵。

接下来我们结合线性代数的知识，简明地证明了具有n个顶点无向图G的关联矩阵的秩为n-1，接下来我们引入了积和式的定义，然后证明了一类连通图的积和式的计值关键词:图完全图数域线性空间关联矩阵积和式Research on the Incidence Matrix of GraphsABSTRACTUsing the form of matrix to represent the graph, not only in theory to facilitate the use of algebra knowledge to study the map, but also to facilitate the computer to deal with the map, in the application of graph theory has a very important significance, the graph is associated with the matrix In this paper, we first describe the definition and classification of graphs, and then describe the various properties of nodes and edges in the graph, and describe the definition of logarithmic domain and linear space. Secondly, we describe the associative matrices in directed graphs and undirected graphs. By way of example, let us understand the associative matrices more intuitively. Then we combine the knowledge of linear algebra to prove the rank of n-1 with the correlation matrix of n vertex undirected graphs G，T hen we introduce the definition ofpermanent, and then prove that a class of connected graphs of the product and the type of valueKey words：Graph Complete graph Number field Linear space Incidence matrix permanent;目录第1章绪论 ............................................................................................................. ..1第2章图的关联矩阵 (5)2.1 关联矩阵的定义 (5)2.1. 关联矩阵的举例及其简单应用 (6)第3章第4章致谢 (16)参考文献 (17)第1章绪论定义1.1 一个图是由点集V={v i}和V中元素的无序对的一个集合E={e k}所构成的二元组，将其记为G=(V,E),V中的元素v i叫做顶点，E中的元素e k叫做边。

以IEEE14、30、39节点为例应用计算机形成关联矩阵


同理，利用Q和B的关系可以得到割-支关联矩 阵Q。
2、IEEE30节点
1 4 6 11 12 14 16 15 17 10 9 29 27 2 5 7 8
24
22
30
25
26
IEEE30节点系统图
30个节点，41条支路
2、IEEE30节点系统各线路数据
含有变压器的支路中变压器的变比
高等电力网络分析
题目
以IEEE14、30、39节点为例应用计算机形成关联 矩阵，用matlab编程，结果存到excel中
电力系统中IEEE节点：是为了验证某一个计算方法行不行 而设立的节点
1、IEEE14节点
14个节点，20条支路
IEEE14节点系统图
1、IEEE14节点程序设 计
对于含有变压器的支路， 节点电流的正负规则不变， 以支路首端为参考，则末 端为负的变比。
设计思路：将IEEE14节点系统的数据存入到data中，定义14*20的零矩阵，以 支路号为循环变量并作为A的列元素，取出data中该支路号对应的首端节点数 并作为A的行元素，令A矩阵对应的位置为1；同理取出data中该支路号对应的 末端节点数并作为A的行元素，令A矩阵对应的位置为-1。遵循节点电流流出 为正，流入为负的规则。
将各线路数据输入到excel表格中， 便于程序的调用
2、IEEE30节点程序设计
编程思路与IEEE14节点系统类似。 区别之处在于：调用的excel数据库不同；定义的关联矩阵A 维数不同。
2、IEEE30节点A矩阵结果
剩下的结果略
3、IEEE39节点系统图
未查到相关数据，思路与前面的一样
1、利用已知的A矩阵计算B矩阵
利用A与B的关系式：

杨忠道定理

杨忠道定理杨忠道定理是由中国数学家杨忠道提出的一个重要的数学定理，它在数学领域具有广泛的应用价值。

本文将围绕杨忠道定理展开，介绍其定义、性质和应用。

杨忠道定理，又称为杨氏矩阵树定理，是图论中的一个重要定理。

它是由杨忠道于1963年提出的，用于计算图的生成树的个数。

该定理的核心思想是利用矩阵的行列式性质，将图的邻接矩阵转化为关联矩阵，从而求解生成树的个数。

我们来介绍一下图的邻接矩阵和关联矩阵。

在图论中，邻接矩阵是用矩阵来表示图的结构的一种方式。

对于一个n个顶点的图，邻接矩阵是一个n×n的矩阵，其中第i行第j列的元素表示顶点i和顶点j之间是否存在一条边。

如果存在边，则为1；否则为0。

关联矩阵则是将图的边和顶点之间的关系都表示在矩阵中，是一个n×m的矩阵，其中n为顶点数，m为边数。

杨忠道定理的关键是通过计算邻接矩阵的代数余子式来求解生成树的个数。

具体来说，对于一个n个顶点的图，将其邻接矩阵的第i 行第i列元素替换为该顶点的度数，其他元素不变。

然后计算该矩阵的任意一个n-1阶代数余子式，即去掉其中任意一行和一列后，剩下的元素所构成的(n-1)×(n-1)矩阵的行列式。

最后，将所有的代数余子式相加，即可得到生成树的个数。

杨忠道定理具有以下几个重要性质。

首先，生成树的个数与图的度数有关，即与邻接矩阵的对角元素有关。

其次，生成树的个数与图的连通性有关，只有连通图才存在生成树。

此外，杨忠道定理还可以用于计算图的割集（图中去掉某个边后，图分为两个不连通的部分）的个数和割点（图中去掉某个顶点后，图分为两个不连通的部分）的个数。

杨忠道定理在实际应用中有着广泛的用途。

首先，它可以用于计算网络中的最小生成树，从而优化网络的通信效率。

其次，它可以用于计算电路中的回路个数，从而帮助设计师评估电路的稳定性。

此外，杨忠道定理还可以应用于社交网络中的信息传播研究，帮助分析信息在网络中的传播路径和速度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
故 r(B) ≥ n‐1 又由[定理1]，r(B)<n 所以 r(B)=n‐1
• 定义. 基本关联矩阵 − 有向连通图 G=(V, A)，V=(v1,v2,..,vn)，|A|=m，从 G 的关联矩阵 Bn×m 中去掉 与结点 vk∈V 对应的一行，得到一个 (n‐1)×m 的矩阵 Bk，称为对应于结点 vk 的基本关联矩阵。
• 算法：求有向连通图所有生成树的清单。
− 设有向连通图 G =(V, A)，n=|V|，m=|A|，并设
A = {a1, a2 , …, am}。 对基本关联矩阵 Bk = (bij) (n‐1)×m 令 Bke = (bije)(n‐1)×m
其中 bije =bij ⋅ aj (标记为整数系数 ⋅ 结点标志符)，则 det(Bke ⋅ BkT)
− 例.
v1 ⎡ 1 1 1 0 0 0 0 ⎤
v2 ⎢⎢−1 0
0
−1
0
−1
0
⎥ ⎥
v3 v4
⎢ ⎢ ⎢
0 0
−1 0 0 −1
1 0
1 −1
0 1
0⎥
0
⎥ ⎥
v5
⎢ ⎢
0
v6 ⎢ 0
0 0
0 0
0 0
0 0
0 1⎥ 0 −1⎥⎥
v7 ⎢⎣ 0 0 0 0 0 0 0 ⎥⎦
a1 a2 a3 a4 a5 a6 a7
编号规则： (1) 分层结构以 vk 为根，连接上下层的弧可以是向上弧或向下弧； (2) 共有 l 层。第 i 层的结点编号为 vi1~ vibi，根为第0层，bi 为第 i 层结点
数； (3) 结点数目为 n = 1+ b1 + b2 + … + bl ； (4) 除 vk 外的任一结点 vij 都有唯一的上紧邻关联弧，记为aij ，i=1 .. l ，j = 1 ..
给出所有生成树的清单。
− 上例中： 取 B4
则
⎛ 1 1 1 0 0 0⎞
B4
=
⎜ ⎜⎜⎝
−1 0
0 −1
0 0
1 −1
1 0
0 1
⎟ ⎟⎠⎟
因此
⎛ a1
B4e
=
⎜ ⎜⎜⎝
−a1 0
a2 0 −a2
a3 0 0
0
a4 −a4
0 a5 0
0⎞
0 a6
⎟ ⎟⎠⎟
B4e ⋅ B4T
=
⎛ ⎜ ⎜⎜⎝
a1
+ a2 + a3 −a1 −a2
下一单元内容提示 − 二叉树的性质 − Huffman树
− 例：有向图 G 及其关联矩阵如下。
取 B4 则
⎛ 1 1 1 0 0 0⎞
B4
=
⎜ ⎜
−1
0
0
1
1
0
⎟ ⎟
⎜⎝ 0 −1 0 −1 0 1 ⎟⎠
⎛ 3 −1 −1⎞
B4
⋅ B4T
=
⎜ ⎜⎜⎝
−1 −1
3 −1
−1 3
⎟ ⎟⎟⎠
因此图 G 的生成树的数目是：det(B4⋅B4T) = 16
• 讨论：无向连通图的生成树数目。 − 为无向连通图的每一条边任意定义一个方向，得到一个有向连通图并应用[定 理6]，得到的生成树数目就是相应的无向连通图的生成树数目。
离散数学基础
2017-11-19
• 单元内容提示 − 图的关联矩阵 − 比内‐柯西定理 − 图的生成树的数目
• 定义. 有向图的关联矩阵 − 对有向图 G=(V, A)，n=|V|，设 V={v1, v2, …, vn}，A={a1, a2, …, am}，构造矩阵 B=(bij)n×m，其中
称 B 是图 G 的关联矩阵。
−a1 a1 + a4 + a5
−a4
a2
−a2 −a4 + a4 +
a6
⎞ ⎟ ⎟⎠⎟
作行列式展开得到全部 16 棵生成树的清单： det(B4e ⋅ B4T ) = a1a2a3 + a1a2a5 + a1a2a6 + a1a3a4 + a1a3a6 + a1a4a5 + a1a4a6 + a1a5a6 + a2a3a4 + a2a3a5 + a2a4a5 + a2a4a6 + a2a5a6 + a3a4a5 + a3a4a6 + a3a5a6
− ① 若 C 不经过 vk，则从 B 生成 Bk 时从 D 中划去的是全0 (不在 D1 中) 的行向量，lk = l，D1k=D1，即D1k每列都含+1和‐1。故D1k不满秩，或r(D1k) < l
− ② 若 C 经过 vk，则从 B 生成 Bk 时从 D 中划去了 D1 中的一行，此时 lk = l‐1，即 D1k 中最多有 l‐1 个非 0 行向量，故 r(D1k) ≤ l‐1 ，或 r(D1k) < l 。
• 定理3. − 若 Bk 是有向连通图 G=(V, A) 的基本关联矩阵，C= {a1, a2, …, al}（ai∈A, i=1…l, l≤m =|A|）构成 G 中的弱连通回路，则 C 的各边对应的 Bk 的各列向量线性 相关。 − 证明：设关联矩阵 B 和 Bk 中与 C 各边对应的列向量分别构成矩阵 Dn×l 、 Dk (n−1)×l 。由于 C 最多经过 l 个结点，故 D 中最多有 l 个非0行向量。经过 适当重排行序后得到 D 和相应的 Dk 形如：
• 例：
⎛2 1⎞
A
=
⎛ ⎜ ⎝
1 −1
2 3
1⎞
1
⎟, ⎠
B
=
⎜ ⎜⎜⎝
0 1
11 ⎟⎟⎟⎠
1 221 1 121 2101
det(AB) = −1
⋅ 30
+
1
= 13
• 定理6. − 设有向连通图 G =(V, A)，n=|V|， Bk 是 G 的一个基本关联矩阵 ，则 G 的 生成树的数目为 det(Bk ⋅ BkT) − 证明：由 Binet‐Cauchy 定理有：
∑ ∑ det(Bk ⋅ BkT ) = BjBTj = B2j
( j)
( j)
其中，其中 Bj 为 Bk 的某一个 (n‐1) 阶子式。由[定理 4]，当且仅当 Bj 各列 对应的弧构成一棵生成树时， Bj ≠0；又由[定理 2]，此时 Bj2=1。而 ( j ) 是在 图 G 中任取 n‐1 条边的所有可能性。
− 关联矩阵的特征 » 每列有两个非零元 +1、‐1； » 孤立点对应的行是0向量； » 非连通图的结点和弧经适当排列，可得到对角分块的关联矩阵。
⎛ ⎜
P1
⎜0
0 %
0
⎞ ⎟
0⎟
⎜⎝ 0
0
Pk
⎟ ⎠
• 定理1. − 有向图 G =(V, A) 的关联矩阵 B 的秩 r(B)<|V|。 − 证明：B 的 |V| 个行向量之和为0，故 r(B)<|V| 。
bi (5) 弧的数目为 n‐1。 按照上述编号规则给原图 G 的顶点和边重新编号，则其关联矩阵对应于这 棵生成树的列向量部分构成所示矩阵：
去掉第1行，得到定理所述的子式为上三角型，其行列式的值非0。
• 定理5. (Binet‐Cauchy) − 已知矩阵 A =(aij)m×n，B =(bij)n×m ，且 m≤n，则：
− 综上，总有 r(D1k) < l，即 D1k 中的列向量线性相关，故 Dk 中的列向量也线性 相关，定理得证。
− 定理揭示了图的回路与基本关联矩阵之间的内在联系。
• 定理4. − 有向连通图 G=(V, A)，n=|V|，其基本关联矩阵 Bk 的任一 (n‐1) 阶子式非零的 充要条件是：该子式各列对应的图 G 的弧构成 G 的一棵生成树。 ⇒ 必要性：若此 n‐1 条弧中存在弱连通回路，则该回路对应于 Bk 中相应的列 向量线性相关，此 n‐1 条弧对应于 Bk 中相应的列向量也线性相关，由 [定理 3] 该 (n‐1) 阶子式为零，矛盾。 ⇐ 充分性：编号法。将该子式各列对应的弧构成的生成树画成以 vk 为根的一 棵树如图。
• 定理2’. − 有向连通图 G=(V,A) 的关联矩阵 B 的秩 r(B)=n‐1，n=|V|。 − 证明：先证明 r(B) ≥ n‐1。反证：若 r(B)<n‐1，则在 B中有 n‐1个行向量线性相 关，不妨设此线性相关向量组为 V1, V2, … , Vn‐1。即存在不全为0的 ki， 1≤ i ≤ n‐1，使得：
k1⋅0+ k2⋅0+…+ kt‐1⋅0+kt⋅1+kt+1⋅0+…+kl⋅0 = 0 得到 kt = 0，1≤t≤l，矛盾。 对 (V1,V2,..,Vl)T 作适当列交换，得：
其中 A1 式每列同含+1和‐1。故原关联矩阵 B 经过上述列交换可得分块矩阵 如图所示，其中 l≤n‐1。此时 G 非连通，矛盾。
k1a1p + k2a2p +… + kl alp = 0， 1≤ p ≤ m 注意到 kj≠0 (1≤ j ≤ l)，而 B 中每列只含一个+1元和一个‐1元，其它都是0元。 欲使上式成立，a1p , a2p , … alp 中必须同含一个+1和一个‐1元，或只含0元。例 如，假如其中只含一个+1元 at,p，1≤t≤l，则有：
k1V1+ k2V2+… + kn‐1Vn‐1 = 0 不妨设 kj≠0 (1≤ j ≤ l ≤ n‐1 )，ks=0 (l <s≤ n‐1), 则有：
k1V1+ k2V2+… + klVl = 0 若设 Vj =(aj1, aj2, …, ajm)，(m=|A|, 1≤ j ≤ l)，考察 m 维向量 k1V1+ k2V2+… + klVl 的第 p 维分量