当前位置：文档之家 › 图论第二章作业

图论第二章作业

  • 格式：docx
  • 大小：16.96 KB
  • 文档页数：2

5、生成树：包含了图中所有节点，且是不含回路的连通图。树枝数（m-1）与
余树边（n-m+1）之和等于边数n，由n-m+1条余数弦形成n-m+1个基本回路。

9、基本关联矩阵的特征表示：矩阵内每行的非零元素表示与相应节点关联的分
支，1表示流出该节点的分支，-1为流入节点的分支。矩阵每列仅有-1和1组成，
分别对应该边的终点和始点，列中仅含有一个非零元素的对应边，即为与该参考
点相连的分支。
与生成树的关系：连通图G的基本关联矩阵B的一个大子阵是非奇异的充要条
件为与这个大子阵的列相应的边，组成G的一棵生成树。

10、基本回路矩阵的每行对应一个独立回路，一个连通图（m，n）的基本回路
数为（n-m+1），互异回路数为（2^n-m+1）。

11、基本割集矩阵表示出了生成树的基本割集，基本割集矩阵S的一个大子阵是
非奇异的充要条件是这个大子阵的列对应于图的某生成树的树枝。

14、试述破圈法、加边法、收缩法求最小生成树的思路与步骤，并比较其优缺
点和使用条件。
破圈法：
一、思路
在一个连通图中，逐次去掉一些边，以破除图中所有回路，则剩下的不含回路的
连通图就是图的一棵生成树。如需选择最小树，每次去掉的边应是被破回路中权
最大者；如需选最大树，则逐次去掉的边应是被破回路中权最小者；若每次去掉
的是任意的一条边，则最后得到一棵任意树。
二、步骤
(1) 画网路图，将点、边编号，标出风向。
(2) 确定图的余树弦数(即独立回路数)
(3) 将分支按权大小排序。
(4) 从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立
回路。若被破坏的回路中，有一条以上高阻分支，应重选；
(5) 重复(4)，直到移去n－m＋1条余树弦，剩余的分支即组成最小风阻树Tmin；
三、优缺点
该法简单、易懂
四、使用条件
适于不太复杂的图
加边法：
一、思路
在图中任取一条边 ，找一条不与 构成回路的边 相连，然后再找一条不与 构成
回路的边 相连，如此继续，直到此过程不能进行，这时所得的图就是一棵生成
树，若加入的边总是权小的边，可得一最小树；若加入的边总是权大的边，则得
最大树；如任意加边，则得一任意树。
二、步骤
(1) 将图去边留点；
(2) 将分支按权排序；
(3) 加边，即按一定顺序将边加到图中原位置。选最大树时，按权从大到小依次
将边加入；选最小树时，按权从小到大依次将边加入。每加入一条边都要判断是
否构成回路，若新加入的边与已有边构成回路，则这条边就是余树弦，将它取走，
计入余树弦集合；若新加入的边与已加入的边未构成回路，说明它是树枝，计入
树枝集合；
(4) 重复(3)，将所有边都加过后，取走n－m＋1条余树弦，剩余的(m—1)条边，
即构成一棵生成树。
三、优缺点
该法方便易行，简单易懂。
四、使用条件
可以手工解算，也可以计算机解算。
收缩法：
一、思路及步骤
(1) 绘网路图，将节点、分支编号，并标出风向；
(2) 计算生成树枝数和独立回路数，并将边按权大小排序；
(3) 从权最小的分支起，由始点向终点收缩(始点与最小权分支被收缩)，将此分
支号授于所有与其始点连接的分支，如某分支号重复出现，则消去此分支号；
(4) 如收缩边始末点合一，即构成一个回路。此始末点合一的分支，即为余树弦，
将其计入余树弦集；
(5) 如未形成回路，则依次收缩权较小的分支；
(6) 重复(5)，直到最后一个节点。收缩过程中始末点合一的分支即为余树弦，去
掉余树弦后剩余的子图即为最小生成树。收缩过程中形成的回路，即为相应的独
立回路。
如需选择最大树，应从最大权分支开始，依次收缩高权分支即可。对任意连通图，
如其顶点为m，则需收缩(m－1)次。
二、优缺点
此法较复杂，不适于手算
三、使用条件
适用于较为额复杂的网络图，适用于电脑解算。

合集下载

图论第二次作业

图论第二次作业

图论第二次作业一、 第四章4.3（1）画一个有Euler 闭迹和Hamilton 圈的图；（2）画一个有Euler 闭迹但没有Hamilton 圈的图；（3）画一个有Hamilton 圈但没有Euler 闭迹的图；（4）画一个既没有Euler 闭迹也没有Hamilton 圈的图；解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：4.7 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得)()()()(21m C E C E C E G E ••• 。

证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1 G ，则1G 含圈1C ，在去掉)(11C E G 的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2 G ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G 全为孤立点为止，于是得到)()()()(21m C E C E C E G E 。

4.10 证明：若（1）G 不是二连通图，或者（2）G 是具有二分类),(Y X 的偶图，这里Y X ，则G 是非Hamilton 图。

证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)( v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w )(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。

（2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ，在这里假设Y X ，则有X Y X G w )(，也就是说：对于v(G)的非空顶点集S ，有：S S G w )(成立，则可以得出G 是非Hamilton 图。

第2章 树

第2章 树


推论2.4.1 每一连通图 都包含一生成树。 每一连通图G都包含一生成树 都包含一生成树。 推论
证明：令 T 为G的极小 minimal)连通生成子图 极小( 极小 连通生成子图 （即 T 的任一真子图都不是G的连通生成子图） （由定义知，T 可在保持连通性 保持连通性的前提下，用逐步 保持连通性 从G中去边的办法求出（ ∴所去的边一定在一圈中 边 （即非割边 非割边）（∴每步至少破坏一圈））。 由T的 非割边 定义知，ω(T) = 1 ， ω(T - e) = 2 ∀ e ∈ E(T) 。 即 T 的每边为割边，故由定理2.4知T为树。
2.1.4 G为 林 ⇔ ε = ν - ω。 2.1.5 若林G 恰有2k个奇点 奇点，则G 中存在k条边不重 奇点 的路 1 ,P2 ,..,Pk ,使得E(G) = E(P1 )∪E(P2 )∪ ... ∪E(Pk )。 2.1.6 正整数序列 (d 1 ,d 2 ,...,d ν )是一 棵树的度序 ν 列，当且仅当
定理2.5 设 T 为G的一生成树，e为G中不属于 定理 T的边，则T+e 含唯一的圈。 证明： 若e为环（即1-圈），结论显然成立。 不然，由于T 无圈，T + e 中的每个圈（若存 在的话）都包含e 。又，C为 T + e 的一圈 ⇔ C - e 为T 中连接e的两个端点的路。但， 由定理2.1知，T中恰只有一条这样的路，因 此 T + e中包含唯一的圈。
⇔ 不含圈的图。 树（tree） ⇔ 连通无圈图。 叶 (leave) ⇔ 树中度为1的顶点。 例：六个顶点的树
称边e为图G的割边( cut edge) ⇔ ω(G-e) > ω(G) 。 （或即 ω(G-e) = ω(G) + 1 ） （称边e为图G的非割边 ⇔ ω(G-e) = ω(G) 。）
第二章_图论10111

第二章_图论10111


Graphs - why should we care?
Friendship Network [Moody ’01]
3
社会也是一个网络，它由友情、家庭和职业关系彼此连结。
Graphs - why should we care?
Science co-authorship network [Newman ’01]
v2 v4
v6
23
端点： v4 与v5 是的e45 端点。
关联边：同一个顶点相连 的边，均称为该点的关 联边，如图中的e24 、e34 、 e45均是v4的关联边。
e22 v1 e12 e24 e45 e34 v4 v5 v2
e'13 e13 相邻：一条边的两个顶点， 称为相邻的，如v2与v4， v4与v5等是相邻点，而v2 v3 与v5则不是。
34

定理： 一个图有支撑树的充分必要条件是该图是连通 的。
证明：
必要性：显然。
充分性：如果G连通且有圈，任取一圈去掉一边，得到G
的一个支撑子图；重复上述步骤，直到G不再含圈为止，则 所得的图为树，即支撑子树
35
• 寻找连通图的支撑树
– 破圈法
从整个图开始，逐个把圈去掉
– 避圈法
从任一边开始，把不构成圈的边逐一加上
30
树(tree)
一个无圈的连通图称为树。
31
• 对图G下列陈述是等价的:
1. G是一个树；
2. G不含圈，且 q p 1 ；
3. G是连通图，且 q p 1 ；
4. G的任意两点由唯一的一条链联结。
v1 v2
v3
右图中有6个点，5条边
v5
v4
v6
第二章图论基础

第二章图论基础


2.1 图的基本概念
4、割集——割集的方向
对有向图，若给割集定义一个方向，则称为有向割集。 以表示割集的虚线面为界，可把从割集由内向外穿出的方 向定为割集的正方向，也可把从割集由外向内穿入的方向 定为正方向。 与割集方向相同的边，称为正向边；反之，称为负向
边。
2.1 图的基本概念
4、割集——生成树与割集的关系
一个连通图的生成树是连通这个图的全部节点的边数 最少的集合，而割集则是分割—个图的节点为不相连的二 个节点子集的边数最少的集合，因此，一个图的生成树与 割集间存在着一定的联系。 [定理] 连通图G的一个割集S至少包含图G的生成树的 一条树枝。因为单纯余树弦是不能将图G分成两部分的。
2.1 图的基本概念
若偶对(V，E)是有序的，即由点和有向边组 成的图，称为有向图；若偶对(V，E)是无序的， 称为无向图；既含有向边，又含无向边的图称为 混合图。
2.1 图的基本概念
1、图
v1 e1 e2 v3 e3 e5 e6 v5 e4 e7 v4
v2
图G1是(5，7)图。图G1的边所 联接的两节点所构成的偶对是无序 的，它们是 e1=<v1,v2>,e2=<v1,v4>,e3=<v2, v3>,e4=<v3,v4>,e5=<v2,v5>,e6= <v3,v5>,e7=<v4,v5>。
2.1 图的基本概念
1、图
图中节点的个数称为图的阶，用nv表示。每一对不 同节点间均有一条边相连的简单图称为完全图，图 G2就是一个4阶的完全图。m阶完全图的边数等于 v v e m(m-1)/2。 e v
1 9 1
e1 v2 e3 e5 v3