OR3 5
（2）次：以点u为端点的边的条数，叫做点u的次。 悬挂点：次为1的点叫做悬挂点； 孤立点：次为0的点叫做孤立点； 奇点：次为奇数则称奇点； 偶点：次为偶数则称偶点。 基本定理： 1、图G=(V,E)中，所有点的次之和是边数的两倍，即

d (v) 2q
vV
2、任一图中，奇点的个数为偶数。
OR3 10
避圈法的基本步骤P259
第一步：令i＝1，E0＝空集。 第二步：选一条边ei∈E﹨Ei-1,使ei是使 （V, Ei-1∪｛e｝）不含圈的所有边e（e ∈E﹨Ei-1）中权最小的边。令Ei＝Ei-1 ∪ ｛ei｝,如果这样的边不存在，则T=(V, Ei-1) 是最小树。 第三步：把i换成i＋1，转入第2步。
OR3
6
（3）链：点边交替序列称为链； 圈：首尾相连的链称为圈； 初等链：链中各点均不同的链； 初等圈：圈中各点均不同的圈； 简单链：链中边均不同的链； 简单圈：圈中边均不同的圈。 （4）连通图：任意两点之间至少有一条链的图。 连通分图：对不连通的图，每一连通的部分称为一个连通 分图。 支撑子图：对G=(V,E)，若G’=(V’,E’)，使V’＝V， E’包含于 E，则G’是G的一个支撑子图。 赋权图：在图中，如果每一条边（弧）都被赋予一个权值 wij，则称图G为赋权图。 （5）路：在有向图中，如果链上每条弧的箭线方向与链行 进方向相同，则称之为路。 回路：首尾相接的路称回路
OR3 7
6.2 树与最小生成树
1、树的概念与性质 树：无圈的连通图称为树。 定理： 定量3：设图G=（V,E)是一个树，p(G) ≥2,则G中 至少有两个悬挂点。 定量4：图G=（V,E)是一个树的充要条件是G不 含圈，且恰有p－1条边。 定量5：图G=（V,E)是一个树的充要条件是G是 连通图，并且q(G)= p(G) -1. 定量6：图G=（V,E)是一个树的充要条件是任意 两个顶点之间恰好有一条链。

OR3 11
6.3 最短路问题
最短路：赋权有向图D=（V，A）中，从始点到终点的 权值最小的路称为最短路。
引例:
单行线交通网：v1到v8使总费用最小的旅行路线。 最短路问题的一般描述： 2(v1=w ,6） ，P是vs 对D=（V，A），a=（vi，vj），w（V a） ij 到vt的路，定义路P的权是P中所有弧的权的和，记 为w（P），则最短路问题为：
9
OR3
3、最小支撑树 最小支撑树：当一个连通图的所有边都被赋权， 则取不同边构成的支撑树具有不同的总权数， 其中总权数最小的支撑树称为最小支撑树。 求最小支撑树的方法： 破圈法：在连通图中任取一个圈，去掉一条 权数最大的边，在余下的图中重复上述步骤， 直至无圈为止。 避圈法：将连通图所有边按权数从小到大排 序，每次从未选的边中选一条权数最小的边， 并使之与已选的边不能构成圈，直至得到最小 支撑树。

OR3 8


2、图的支撑树 支撑树：设T=(V,E’)是图G=(V,E)的支撑子图， 如果T是一个树，则称T为G的支撑树。 定理7：图G有支撑树的充要条件是图G是连 通的。 求支撑树的方法： 破圈法：即任取一个圈，从圈中去掉一条 边，对余下的图重复这个步骤，直至图中不含 圈为止。 避圈法：在图中每次任取一条边，与已经 取得的任何一些边不够成圈，重复这个过程， 直到不能进行为止。
OR3
13
Dijkstra算法的基本步骤：
1:给vs以P标号, P(vs)=0,其余各点均给T标 号,T(vi)=+∞ 2:若vj 点为刚得到P 标号的点,考虑这样的点vj, (vi,vj) ∈E,且 vj为T标号. 3:对vj的T标号进行如下更改: T (v j ) min T (v j ), P(vi ) wij
w( P0 ) min w( P)
P
路P0的权称为从vs到vt的距离，记为：d（ vs，vt ）
OR3 12
最短路算法

Dijkstra算法 ：有向图 ，wij≥0 一般结论：
vs ,..., vi ,..., v j vs ,..., vi
v s 到vi的最短路
济南
青岛
郑州
徐州
连云港
南京
上海
武汉
OR3
2
球队比赛图
五个球队比赛,比过的两个队之间用连线 相连，还没有比赛的队之间没有连线
v5
v1
v4
v2
OR3
v3
3
6.1 图的基本概念
图是由点和线构成的。点代表所研究的对象，线表示对 象间的关系。 1、图的分类：无向图，有向图 无向图：由点和边所组成的图。表示为G=(V,E). 有向图：由点和弧所组成的图。表示为D=(V,A) 点的集合用V表示，V={vi} 2、图上的基本概念： （1） 边：图中不带箭头的连线叫做边(edge)，边的集合记 为E= { ej } ，一条边可以用两点[ vi,vj ]表示,ej= [ vi,vj ]. 弧：图中带箭头的连线叫做弧(arc),弧的集合记为A， A= { ak },一条弧也是用两点表示，ak= [ vi,vj ],弧有方向： vi为始点，vj为终点
第六章 图与网络分析
引论 : 哥尼斯堡七桥问题
A A B C B D E c B
OR3 1
C
D
A D
铁路交通图
此图是我国北京,上海等十个 城市间的交通图,反映了这 十个城市间的铁路分布情况. 点表示城市,点间的连线表示 两个城市间的铁路线. 诸如此类问题还有电话线分 布图或煤气管道分布图等.
北京
天津

OR3 4

例1. v1 e5 v4
e1
e2
e3
v2
e4 v1
v3
a8
v5
a1
a3 a2
a4 a6 a9
a10
a7 v6
e7
e6
v3
v2
a5Βιβλιοθήκη v4v7环：两端点相同的边。 多重边：若两点之间有多于一条边，则称这些边为多 重边。 简单图：无环、无多重边的图。 e7 多重图：无环，但允许有多重边的图。
v s 到v j的最短路
Dijkstra算法基本思想: 采用标号法: P标号和T标号
P标号：已确定出最短路的节点(永久性标号)。 T标号：未确定出最短路的节点，但表示其距离的上限(试探性标号)。 算法的每一步都把某一点的T标号改为P标号直至改完为止. Si：P标号节点的集合。