支撑树
最小支撑树
【例】今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。
E
I
A 3.5
2
C
2
4
G
5
1S
25
4
5
3
3KLeabharlann B22 F 2 26 J
D
H
最小支撑树问题
G的支撑树，又称生成树、部分树。
(G1)
(G2)
(G)
(G3)
(G4)
最小支撑树问题
图的支撑树的应用举例 【例】 某地新建5处居民点，拟修道 路连接5处，经勘测其道路可铺成如 图所示。为使5处居民点都有道路相 连，问至少要铺几条路？
【解】 该问题实为求图的支撑
树问题，共需铺4条路。 v2
v1
5
v2
1、树 连通且无圈的无向图 判断下面图形哪个是树：
(A)
(B)
(C)
树的性质： 1、树中任两点中有且仅有一条链；
2、树任删去一边则不连通，故树是使图保持连通且具有最 少边数的一种图形。
3、边数 = 顶点数 – 1。
最小支撑树问题
2、图的支撑树
若一个图 G =（V , E）的支撑子
图 T=（V , E´） 构成树，则称 T 为
定义2：无环、无多重边的图称作简单图。
含有多重边的图为多重图。
图的基本概念
2、图的分类
无向图，记作G=(V，E) 图
有向图，记作D=(V，A)
有向图的边 称为弧。
例1：哥尼斯堡桥问题的图为一个无向图。
v5
例2：五个球队的比赛情况，v1 v2
表示v1胜v2。
v1
v
v2
v3
图的基本概念
2、图的分类
定义3：每一对顶点间都有边相连的无向简单图，称为 完全图。有n个顶点的无向完全图记为Kn。
定义4：图G=(V, E)的点集V可分为两个非空子集X、Y， 即X∪Y=V，X∩Y=∅ ，使得E中每条边的两个 端点必有一个端点属于X ，另一个端点属于Y， 则称G为二部图（偶图），有时记作G=(X,Y,E) 。
图的基本概念
e1
e2
v1 e4
e3
v2
v3
3、顶点的次
定义5：以点v为端点的边数叫点v的次
A=(aij)n×n ，其中：
a ij
wi 0
j
（vi，vj）∈E
其他
则称矩阵A为网络G的权矩阵。
图的基本概念
8、图的矩阵表示
定义12：图G=(V, E)，|V|=n，构造一个矩阵 A=(aij)n×n ，其中：
1
a ij
0
（vi，vj）∈E
其他
则称矩阵A为图G的邻接矩阵。
最小支撑树问题
树
e5
e6
e7
e8
（degree），记作deg(v)或d(v)。 v4 图5－1 v5
图5-1中，d(v1)＝４，d(v3)=5，d(v5)=1。 次为奇数的点称作奇点，次为偶数的点称作偶点，
次为0的点称作孤立点。 次为1的点称作悬挂点，连接悬挂点的边为悬挂边。
图的次：各点的次之和。 有向图中顶点的次？
e6可记作： e6 [v2,v4]
v2和v4是边e6的端点，点v2、v4相邻。 e6与e7共用顶点v4，e6与e7相邻，e6和e7为点v4的关联边。
e1
图的基本概念
e2
v1 e4
e3
v2
v3
2、图的分类
e5
e6
e7
e8
环，多重边，简单图
一条边的两个端点相同，称此边为环，e1； v4 图5－1 v5 两个点之间多于一条，称为多重边，e4和e5
V={v1，v2，……，vn}为结点的集合， E={e1，e2，……，em}为边的集合。 点表示研究对象
边表示表示研究对象之间的特定关系
V、E为有限集合，则为有限图，反之无限图。
注意：上面定义的图Ｇ区别于几何学中的图。几何学中，
图中点的位置、线的长度和斜率等都十分重要，而这里 只关心图中有多少点以及哪些点之间有线相连。
定理1：任何图中，顶点次数的总和等于边数的2倍。 定理2： 任何图中，次为奇数的顶点为偶数个。
图的基本概念
4、子图、支撑子图
图G=(V, E)和G’ =(V’ ,E’ )，若V’ V，E‘ E，则称G’ 为G的 子图。特别地，若V =V ‘ 且E ’ E，则称G' 为G的支撑子图。
v5
G2为G1的支撑子图
13 20 19
2
12 14 18 6
5
15 11
16 10 9 3
17 7 8
4
问题：游戏者从任一城市出发，寻找一条可经过每 个城市一次且仅一次，在回到原出发点的路?
欧拉回路：每边经过一次且仅一次的回路
哈密尔顿回路：每个点经过一次且仅一次的回路
图的基本概念
1. 图 定义1：由点和边组成，记作G=(V，E)，其中
v5
v1
v4
v1
v4
v2
v3
G1
v2
v3
G2
图的基本概念
5、赋权图（网络）
图的每条边都有一个表示一定实际含义的权数，称 为赋权图。记作D=(V，A，C)。
v1
5
3
v2
7.5 4
v5
5.5
2
v3 3.5 v4
图的基本概念
6、链与路、圈与回路
无向图： 链 有向图： 路
v5
点边交错的序列 圈 起点=终点的链
3.5 4
5.5
3
v5
2
v1
v3 7.5 v4
v5
v3
v4
最小支撑树问题
3、最小支撑树问题
v1
问题：求网络的支撑树，使其权和最小。v2
5 3.5 4
算法1（避圈法）：把边按权从小到大依次 5.5
点弧交错的序列 回路 起点=终点的路
v5
v1
v4
v1
v4
v2
v3
v2
v3
没有重复点和重复边的链为初等链。初等圈
图的基本概念
7、连通图
定义10：任意两点之间至少存在一条链的图称为连通图， 否则称为不连通图。
例 ： G1为不连通图， G2为连通图
G1
G2
图的基本概念
8、图的矩阵表示
定义11：网络G=(V, E)，边（vi，vj）有权wij，构造矩阵
第五章 图论与网络分析
学习目标
➢ 图的基本概念 ➢ 最小支撑树问题 ➢ 最短路径问题
图的基本概念
图论起源——哥尼斯堡七桥问题
A
A
C
D
C
D
B
B
问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？
结论：每个结点关联的边数均为偶数。
图的基本概念
哈密尔顿回路问题：环球旅行遊戏 1
图的基本概念
端点，相邻，关联边 【例】图5－1， G(V,E)
e1
e2
v1 e4
e3
v2
v3
e5
e6
e7
e8
V{v1,v2,v3,v4,v5} E{e1,e2,e3, ,e8} v4
图5－1
v5
边e=[vi ，vj]，称vi和vj是边e的端点，vi和vj 两点相邻； 边ex和ey有公共端点vi ，称边ex和ey相邻，边ex和ey为点vi 的关联边；