图论第9单元.pptVIP

七、有向路与有向圈 在有向图中，路和有向路的长不存在紧密关系。 例如在下图中，其路可以任意长，但有向路的长不大于1。 有向路长的某些信息可由其色数c 得到。 定理 有向图中存在长为c -1的有向路。 定理 设D=(V, E) 是有向图。 (1) 若D中存在子图H使得对任意的v ∈V(H)均有d +(v)0 (或d －(v)0)，则D中存在有向圈。 (2) 若D连通，且对任意的v∈V(D)均有d +(v)=1(或d －(v)=1)，则D中存在唯一有向圈。 定理 设D=(V, E) 是有向图。D中存在有向欧拉回路，当且仅当D连通且每个点的出度和入度相等； 有向图D中存在有向欧拉迹，当且仅当D连通且除了两个点外，每个点的出度和入度相等。而这两个点中，一个点的入度比出度大1，另一个点出度比入度大1. 在各种比赛中，循环比赛是常见形式，即队与队之间都要进行比赛。 循环比赛的结果可以用所谓的“竞赛图”来表示。u队战胜了v队，则由点u向v画一条有向边。 完全图的定向图称为竞赛图。 定理 每个竞赛图均存在有向Hamilton路。 八、生成树的计数 在第二章中我们学习了生成树棵数的递推公式： 这里我们介绍关联矩阵计数法。 定理 设M是无环n阶连通有向图D的关联矩阵，n≥2，则M的秩为n－1。 定理 设M是具有w个连通分支的n阶无环有向图D的关联矩阵，则M的秩为n－w。 设M是n阶连通无环有向图D的关联矩阵。因M中每一列恰有两个非零元，一个为+1，一个为－1，故在M中任取一行，比如第i行，将M中其余各行加到第i 行，可以使得第i行全为0。 又因为M是秩为n－1，这说明任意的n－1行作为行向量是线性无关的。 因此在M中任意删去一行，比如点v对应的行，可得一个秩为n－1的矩阵M*，我们称M*为D的对应于参考点v的基本关联矩阵，简称基本关联矩阵。 假定方阵A为一个n×m矩阵的子矩阵，且A的阶数为min{m, n}，则称A为主子阵，主子阵的行列式称为主行列式。 定理 设A是n阶无环有向连通图D的基本关联矩阵M*的任一主子阵，DA是以A的列对应的边作为边集的图的生成子图，则A非奇异的充要条件是DA是D的生成树。 证明 若DA是D的生成树，则DA连通，从而DA的关联矩阵的秩为n－1 。 因此DA的基本关联矩阵的秩为n－1，而A正是DA的基本关联矩阵，所以A非奇异 。 反过来，因D连通，所以M*的行数不超过其列数，这表明A是n－1阶方阵，所以DA是有n个点， n－1条边的图。 若DA不连通，则M(DA)的秩小于n－1，而A是M(DA)的子矩阵，所以A的秩小于n－1，因此A是奇异矩阵，矛盾！ 因此DA连通，又有n个点， n－1条边，所以DA是D的生成树。 该定理表明，可利用基本关联矩阵来计算一个有向图的生成树的个数： (1) 写出D的关联矩阵，进一步写出基本关联矩阵，记住参考点； (2) 找出基本关联矩阵的非奇异主子阵，对每个这样的主子阵，画出相应的生成树。 一个有m条边的n阶无环有向连通图D的基本关联矩阵有 个主子阵，若其中有k个是奇异的，则D的生成树的个数为 例 设有向图D如图所示。 1 2 3 4 a b c d e 若以4为参考点，则D的基本关联矩阵为 M*的主子阵个数为 其中有两个奇异主子矩阵： 所以生成树的个数为：10－2＝8. 其中两棵生成树及其对应M*的主子矩阵为 1 2 3 4 a b e d 1 2 3 4 a b 矩阵树定理 设无环连通图G的顶点集合为V={v1, v2,…,vn}，A=(aij)是G的推广的邻接矩阵，C=(cij)是n阶方阵，其中： 则G的生成树棵数为C的任意一个余子式的值。 例 图G 知图所示。求τ(G)。 v1 v4 v2 v3 解 记C删去第i 行及第i 列后所得到的矩阵为Ci，则 则 例 图G如图所示，求τ(G)，并给出G的所有生成树。 解 . v1 e1 e2 e3 v2 v3 e4 所以 因为 这5棵生成树如下： e1 e2 e1 e3 e1 e4 e2 e3 e2 e4 解 显然 例 求τ(Kn)。 所以 Thank you! * * * * * * * * * * * 定义 一个有向图是一个称为点集的非空集合V(D) 和一个称为边集的集合E