G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,1
7.1 图的概念 /Introduction of Graph
7.2 图的术语 /Graph Terminology
7.3 图的表示与同构 /
Representing Graph and Graph Isomorphism
7.4 连通性 /Connectivity
7.5 欧拉道路与哈密尔顿道路 /
Euler and Hamilton Paths
7.6 最短道路问题 /Shortest Path Problem
7.7 平面图 /Planar Graphs
7.8 图的着色 /Graph Coloring
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,2
7.4 连通性 /Connectivity
[定义 ]道路 /path：
当Ｇ中相邻边的序列 （ Ｖ 0,Ｖ 1）,
（ Ｖ 1,Ｖ 2）,…（ Ｖ k-1,Ｖ k） 称为一条 道路 （ 通路 ） 。 此道路的长度为ｋ 。 也可以以 （ Ｖ 0,Ｖ 1,…,Ｖ k） 表示道路,Ｖ 0为起点,Ｖ k为终点 。
当 Ｖ 0=Ｖ k时,该道路称为 回路 /circuit。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,3
[定义 ]简单道路 /Simple Path：
一条道路中没有两条边是相同的,称此道路为 简单道路 。 当其是回路时,称为 简单回路 /Simple Circuit。
[定义 ]基本道路 /Element Path：
一条道路中,除了起点和终点可以相同,没有其他相同顶点出现,称此道路为 基本道路 。 当其是回路时,称为 基本回路 /Element Circuit。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,4
e3
e5
e2
e1
d
c
b
a
e4
（ｅ 5，ｅ 1,ｅ 2,ｅ 3，ｅ 4）是简单道路，
不是基本道路，因为（ｃ，ａ，ｂ，ｃ，ｄ，
ｂ）中ｂ，ｃ均出现了两次。但（ c,d,b，
c）是基本道路。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,5
[定义 ]连通性 /connectivity：
设Ｇ＝（Ｖ，Ｅ）,（Ｖ 0，Ｖ 1,…,
Ｖ k） 是 G中的一条道路，则称Ｖ 0到Ｖ k连通
/connective或 可达 /。
说明：对无向图而言，若Ｖ 0到Ｖ k可达，则
Ｖ k到Ｖ 0也可达。对有向图而言则未必。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,6
[定理 1]
任意一个连通无向图的 任两个不同顶点都存在一条简单道路 。
[定义 ]无向图的连通性：
若Ｇ＝（Ｖ，Ｅ）中任两个不同顶点都连通，则称此无向图是 连通的
/connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,7
[定义 ]连通分图 /connected components：
图Ｇ可分为几个不相连通的子图,每一子图本身都是连通的 。 称这几个子图为Ｇ
的连通分图 。
[定义 ]无向图的连通性：
若Ｇ＝（Ｖ，Ｅ）中任两个顶点都连通，则称此无向图是 连通的 /connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,8
[定义 ]有向图的连通性：
(1)弱连通：
若Ｇ＝ （ Ｖ,Ｅ ） 对应的无向图是连通图,则称Ｇ为 弱连通 /weakly connected。
(2） 强连通：
若Ｇ＝ （ Ｖ,Ｅ ） 中任两点间都有路,
即对ａ与ｂ,ａ到ｂ可达,ｂ到ａ可达,称
Ｇ为 强连通 /strongly connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,9
连通无向图
:
弱连通
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,10
强连通
:
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,11
例：用图描述一台自动售货机,只用５分,１０
分二种硬币,满１５分后压按钮,选择一块巧克力,钱多了不找还 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,12
顶点：ａ：０ 分边,５：投５分
ｂ：５分 １０：投１０分
ｃ：１０分 ｐ：压按扭动作
ｄ,≥ １５分表示已投入钱的状态 表示一种动作自动售货机：有向加权图描绘得很清楚
（ 1）钱数不够，压按扭，不起作用
（ 2）钱数够了，压按扭，给过糖果回到０分状态
（ 3）钱超过１５分，再加钱白加
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,13
用邻接矩阵讨论图Ｇ的连通性质：
在邻接矩阵中,若ａ ij＝１,表明Ｖ i到Ｖ j有一条边,即Ｖ i到Ｖ j可达；若ａ ij＝０不说明Ｖ i到Ｖ j
没有道路,若通过其他点中转,也有可能连通 。 作邻接矩阵的普通矩阵乘法：
Ｂ＝Ａ
2
＝Ａ·Ａ＝
nnij
b
)(
ｂ ij ＝?
n
k
kjik
aa
1
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,14
ｂ ij的值表示Ｖ i到Ｖ j路长为２的道路条数,一般地,就有：
[定理 2]
Ａ m的元素ｍ ij表示Ｖ i到Ｖ j长度为ｍ的道路条数 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,15
[定理 3]：
ｎ个顶点的图Ｇ中,如果Ｖ i到Ｖ j
（ Ｖ i≠ Ｖ j） 有道路,则其最短的道路长度 ≤ ｎ－１ 。
[定理 4]：ｎ个顶点的图Ｇ中,A是 G的 邻接矩阵 。 Ｖ i,Ｖ j 是 G的顶点,
B=A+A2+…+An-1
则Ｖ i到Ｖ j（ Ｖ i≠ Ｖ j） 连通当且仅当 b ij
非零 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,16
定义：ｎ个顶点的图Ｇ中,A是 G的 邻接矩阵 。
B=A+A2+…+An-1 +An
称为 G的可达性矩阵 。
有向图的连通性 （ n?1）,
（ １ ） B中元素全为１?Ｇ强连通
（ 2） Ａ ∨ Ａ T的可达性矩阵元素全为１?
Ｇ是弱连通的 。
无向图的连通性 （ n?1）,
B中元素全为１?Ｇ连通
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,17
7.5 Euler and Hamilton Path
Konigsberg(哥尼斯堡 )七桥问题问题：能否从河岸或小岛出发,通过每一座桥,
而且仅仅通过一次回到原地 。
A
C
B
D
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,18
Euler(欧拉 )1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：
[定义 ]欧拉道路（回路）：
Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简单道路为 欧拉道路 /Euler Path/E道路 。
包含Ｅ中所有边的简单回路为 欧拉回路
/Euler Circuit/E回路
。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,19
[定理 1]（ 欧拉定理 ）,
没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是：
(1)图是连通的；
(2)图中奇次顶点个数是０个或 2个 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,20
证明：
必要性：
若存在欧拉道路,且没有０次顶点,则每个顶点都有边关联,而边又全在欧拉道路上,故所有顶点都连通 。
除了起点,终点外,欧拉道路每经过一个顶点,
使顶点的次增加２,故只有起点和终点才可能成为奇次顶点,而一个奇次顶点是不可能的,当无奇次顶点时,是欧拉回路 。
充分性：
若 (1）,(2)成立,构造欧拉道路,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,21
若图Ｇ存在奇次顶点,任取一个作为起点,若不存在,则任取一个顶点作为起点 。
若此图有ｎ条边,总次为２ｎ 。 每进入或离开一个顶点,让此顶点的次减１,由于除了两个 （ 或没有 ） 奇次顶点外,其余顶点次为偶数,只要进得去,一定出得来,直至进入另一个奇次顶点 （ 或起点 ） 作为终点 。 这样构造的是简单道路,如果经过所有的边,即得到一条欧拉道路 。
不然，记走过的简单道路为ｐ 1，ｐ 1上顶点集
Ｖ 1，边集Ｅ 1，Ｇ 1＝（Ｖ 1，Ｅ 1）是Ｇ的子图。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,22
若Ｇ 2＝ （ Ｖ 2,Ｅ 2） 是Ｇ 1的关于Ｇ的余图,Ｅ
2＝Ｅ－Ｅ 1,但Ｖ 1∩ Ｖ 2≠ φ,否则Ｇ不连通,设
Ｃ ∈ Ｖ 1∩ Ｖ 2,从Ｃ出发,用上面方法作Ｇ 2的简单回路ｐ 2 回到Ｃ,这能做到 。
因为作好ｐ 1后,留下顶点的次都是偶次 。 若
ｐ 1∪ ｐ 2经过所有边,则欧拉道路是ｐ 1走到Ｃ时,
先把ｐ 2走完,最后走完ｐ 1的余下道路 。
若ｐ 1∪ ｐ 2仍未经过所有边,将ｐ 1∪ ｐ 2视为
ｐ 1重复上述过程,由于Ｅ边有限,故存在欧拉道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,23
例 1：
A
B
C
D
E
F
G
H
I
J
（ 1）顶点的次,A(3),B(2),C(4),D(2),E(6),F(2),
G(6),H(2),I(4),J(3）。其中奇次顶点 A,J
（ 2）从 A出发，走一条道路
（ A,C,E,A,B,C,D,E,G,J）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,24
（ 3） Ｇ 1＝ （ Ｖ 1,Ｅ 1）
Ｖ 1 ＝ {A,B,C,D,E,G,J}
Ｅ 1 ＝ {（ A,B）,（ B,C）,（ A,C）,（ C，
D）,（ C,E）,（ D,E）,（ E,G）,（ G,J） }
Ｇ 2＝（Ｖ 2，Ｅ 2）
Ｅ 2 ＝ {（ E,F），（ F,G），（ E,J），
（ G,H），（ G,I），（ I,J），（ H,I） }
Ｖ 2 ＝ {E,F,G,H,I,J}
E∈ （ Ｖ 1?Ｖ 2）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,25
（ 4） 从 E出发回到 E的回路 （ E,F,G,I,J,E）,
加入到 P1中
Ｐ 1? ＝ （ A,C,E,F,G,I,J,E,A,B,C，
D,G,J）
（ 5） 还有未经过的边,重复上述过程,从 G出发,
（ G,H,I,G）,再加入即得欧拉道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,26
说明：
哥尼斯堡七桥问题,由于四个顶点都是齐次的,不可能有欧拉道路 。
应用与推广：
（ 1） 一笔画问题；
（ 2） 如果齐次顶点个数为 2K个,此问题是 K
笔画问题 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,27
例
８个顶点均为
3次，至少要
４笔。
定理 2（有向图的欧拉定理）：
不含次为０的孤立顶点的有向图具有欧拉道路的充要条件是：
(1）弱连通；
(2) 除了可能有２个顶点，一个入次比出次大１，
一个出次比入次大１，其余顶点出次等于入次。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,28
中国邮递员问题
(欧拉道路的应用 )(加权图 )
问题,
邮递员从邮局出发,走遍投递区域的所有街道,送完邮件后回到邮局,怎样使所走的路线全程最短,
若街道图 （ 街道的交叉口为顶点 ） 存在欧拉道路,显然此路是全程最短,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,29
Hamilton(哈密顿 )道路问题：
１８５９年发明的一种游戏 。
在一个实心的正十二面体,20个顶点标上世界著名大城市的名字,要求游戏者从某一城市出发,遍历各城市一次,最后回到原地 。
这就是,绕行世界,问题 。 即 找一条经过所有顶点 （ 城市 ） 的基本道路 （ 回路 ） 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,30
[定义 ]哈密顿道路 /回路：
Ｇ＝ （ Ｖ,Ｅ ）,G中经过Ｖ中所有顶点的基本道路称为 哈密顿道路 /Hamilton
Path,简称 Ｈ道路 。
Ｇ＝ （ Ｖ,Ｅ ）,G中经过Ｖ中所有顶点的基本回路称为 哈密顿回路 /Hamilton
Circuit,简称 Ｈ回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,31
A
B
图Ａ 每个顶点都是奇次的，不存在欧拉道路，但有Ｈ道路。 图Ｂ存在欧拉道路，不存在Ｈ道路。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,32
[定理 3]：设Ｇ＝（Ｖ，Ｅ）是ｎ个顶点的简单图，
如果任何一对顶点的次之和 ≥ｎ－１，则Ｇ中一定有Ｈ道路。
证明：
1,Ｇ一定连通,否则Ｇ分为二个不连通的分图
Ｇ 1,Ｇ 2,其中Ｇ 1有ｎ 1个顶点,Ｇ 2有ｎ 2个顶点,
Ｇ 1中每个顶点次 ≤ ｎ 1－１,Ｇ 2中每个顶点次 ≤ ｎ
2－１,从Ｇ 1中取一个顶点,Ｇ 2中取一个顶点,这一对顶点之和 ≤ ｎ 1－１＋ｎ 2－１＝ｎ 1＋ｎ 2－２
＝ｎ－２＜ｎ－１,与定理的假设矛盾 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,33
2,用逐步递推构造法证明Ｇ中存在Ｈ道路：
(1)任取一条边 （ Ｖ 1,Ｖ 2）,是含２个顶点的基本道路 。
(2)如果已有ｐ个顶点的基本道路
（ Ｖ 1,Ｖ 2,…,Ｖ p）,（ ｐ ≤ ｎ－１ ）
必能构造ｐ＋１个顶点的基本道路 。
ａ ） 如果在Ｖ－ ｛ Ｖ 1,Ｖ 2,…Ｖ p｝ 中存在与Ｖ 1
或Ｖ p相邻的顶点,则基本道路自然可以扩充一个顶点 。
ｂ ） 如果Ｖ 1,Ｖ p仅与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中顶点相邻,则 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 必可适当排列,
形成回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,34
如果Ｖ 1与Ｖ p相邻,显然成了环 。 不然,由于Ｖ 1，
Ｖ p仅与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中顶点相邻,Ｖ 1,Ｖ p
的次 ≤ ｐ－１ 。 不妨设Ｖ 1的次为ｋ ≤ ｐ－１,分别记相邻顶点为Ｖ i1,Ｖ i2,…,Ｖ ik,它们前面的顶点
（ 指在基本道路 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中的序 ）
为,Ｖ p必与中某顶点相邻,否则Ｖ p的次 ≤ ｐ－１－ｋ,Ｖ 1与Ｖ
p的次之和 ≤ ｋ＋ｐ－１－ｋ＝ｐ－１＜ｎ－１,与任一对顶点次之和 ≥ ｎ－１矛盾 。
不妨Ｖ p与Ｖ j-1相邻,Ｖ 1与Ｖ j相邻 。 将Ｖ 1与
Ｖ j连起来,Ｖ p与Ｖ j-1连起来,并将Ｖ j-1到 Ｖ j的边去掉,就形成一个环,如下图所示 。
111,,,21 kiii VVV?111,,,21 kiii VVV?
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,35
V x
V k
V k -1
V j
V j- 1
V 1 V 2 V j- 2
V p
又由Ｇ的连通性,总可在Ｖ－ ｛ Ｖ 1,Ｖ 2,…，
Ｖ p｝ 中找到一个点Ｖ x,与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝
中某一顶相邻,不妨与Ｖ k相邻,Ｖ k≠ Ｖ 1,Ｖ k≠
Ｖ p,连上Ｖ x与Ｖ k的边,去掉Ｖ k-1到Ｖ k的边,可以从Ｖ k-1为起点,一直走到Ｖ k,再到Ｖ x,这是一条ｐ＋１个顶点的基本道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,36
如果ｐ＋１＜ｎ,仍继续扩充基本道路内的顶点,直至达到ｎ 。
注意,
此定理条件显然不是必要条件,如ｎ ≥ ６的ｎ
边形,二个顶点次之和＝４,
４＜ｎ－１,而ｎ边形显然有Ｈ道路 。
[定理 4]：
Ｇ＝ （ Ｖ,Ｅ ） 是ｎ ≥ ３的简单图,若任何一对顶点的次之和 ≥ ｎ,则Ｇ必有哈密顿回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,37
由于定理 4条件也必满足定理 3条件,存在Ｈ道路,可类似于定理一的方法找到一条回路 。
[定理 5]：
有向完全图一定存在Ｈ道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,38
小 结
1、图中顶点的连通性 /可达性
2、图的连通性有向图、无向图
3,E图：简单道路 +所有边
4,H图：基本道路 +所有顶点
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,39
进一步的思考
1,图的连通性的计算机表示与实现
2,E图 /H图的应用
3,E图 /H图的判定
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,40
要判别一个图不存在Ｈ道路,Ｈ回路,也不是很容易的,只能对无向图给出一些必要条件：
（ 1） Ｈ道路存在必要条件：
１ ） 连通
２ ） 至多只能有二个顶点的次＜２,其余顶点的次 ≥ ２ 。
b
c
d
a
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,41
（ 2） Ｈ回路存在必要条件：
对Ｖ的任一非空真子集Ｓ,Ｇ－Ｓ的连通分图个数 ≤ |Ｓ |。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,42
A
A2
B
B
A1
B
A
A
B
B
B
A
B
解：取Ｓ＝ ｛ A1,A2 ｝
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,43
G－Ｓ存在 3个分图根据 H道路存在的必要条件之二,
可知,H道路不存在 。
A
A2
B
B
A1
B
A
A
B
B
B
A
B
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,44
应用问题之一：
Knight’s tour
应用问题之二：
Gray Code
应用问题之三：
Tower of Hanoi
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,45
练 习
pp.473 1,2,12,31
pp.486 36,37,65
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,46
7.6 最短道路问题
Shortest Path Problem
加权图 /Weighted graph
G = （ V,E,f ）,f:E?R+
G满足简单连通无向
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,47
Example:
Weighted Graphs Modeling an Airline
System For SF,LS,DL,DV,CG,BT,NY
Cities,
Mileage
Flight Times
Fares
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,48
Example:
Weighted Graphs Modeling a Computer
Network For SF,LS,DL,DV,CG,BT,
NY Cities,
Distance
Response Time
Lease Rate(per month)
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,49
a到 b的道路及其长度,
道路中所有边的函数值之和。
a到 b的 最短道路 /shortest path：
所有 a到 b的道路中长度最短的一条。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,50
a到 b的道路及其长度,
道路中所有边的函数值之和。
求 G中任意两个顶点 a到 b的 最短道路的方法：
Dijkstra’s 算法
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,51
应用问题,旅行商问题 （ TSP）
Traveling Salesman Problem
问题：从某地出发，恰好一次经过ｎ个城市回到原地，寻找最短的道路。
实质：无向简单加权图，寻找最短Ｈ回路的问题。
说明：
（ 1） 不一定存在,若无向图是完全图则存在 。
（ 2） 图是 连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的 H回路问题,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,52
无向加权完全图的 最近邻域算法 /Approximation：
１,从任一顶点出发,记为Ｖ 1,找一个与Ｖ 1最近的顶点Ｖ 2,（ Ｖ 1,Ｖ 2） 为两个顶点的基本道路 。
２,若找出有ｐ个顶点的基本道路
（ Ｖ 1,Ｖ 2,…,Ｖ p）,ｐ＜ｎ,在道路外找一个离Ｖ p最近的顶点,记为Ｖ p+1,将其加入则得到具有 P+1个顶点的基本道路 。
３,若ｐ＋１＝ｎ,转４,否则转２ 。
４,闭合Ｈ回路：即增加一条边 （ Ｖ n,Ｖ 1）,
则 （ Ｖ 1,Ｖ 2,…,Ｖ n,Ｖ 1） 为一条近似的最短回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,53
说明：
(1)找最近一个顶点不唯一时,按序取 。
(2) 不一定是最短Ｈ回路,
例：
下 图是加权无向完全图,从 a点出发,用最近邻域法求最短Ｈ回路,并与实际的最短 H
回路做比较 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,54
d
a
c
e
a
b
14
d
a
a
11
d
a
a
13 8
d
a
a
12
d
a
a
9
d
a
a
10
d
a
a5
d
a
a
6
d
a
a
7
d
a
a
d
d
a
a
7
d
a
a
14
d
a
a
8
d
a
a
6
d
a
a
5
d
a
a
c
d
a
a
b
d
a
a
a
d
a
a
e
d
a
a
最近邻域法所求为,（ ａ,ｃ,ｅ,ｄ,ｂ,ａ ）
总长为７＋６＋８＋５＋１４＝４０
最短回路,（ ａ,ｃ,ｅ,ｂ,ｄ,ａ ）
总长为７＋６＋９＋５＋１０＝３７ 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,55
(2)以关联 ei的两个顶点 v1,v2分别作为起点，用最近邻域法求最短 H回路。
(3)再比较这两条回路的长度，以确定最短的一条。
如上例,
（ ｂ,ｄ ） 边长为５,最短 。
以ｂ为起点,（ ｂ,ｄ,ｅ,ｃ,ａ,ｂ ）
总长为４０
以ｄ作起点,（ ｄ,ｂ,ｅ,ｃ,ａ,ｄ ）
总长为３７
改进,
(1)找一条最短的边 ei。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,56
设Ｇ＝ （ Ｖ,Ｅ,Ｗ ） 是ｎ个顶点的完全无向图,满足三角不等式ｗ （ ｉ,ｊ ） ＋ｗ （ ｊ,ｋ ）
≥ ｗ （ ｉ,ｋ ）,ｄ 0是最短Ｈ回路Ｄ 0的长度,ｄ
是最近邻域法得到的Ｈ回路Ｄ的长度,则,
2
1][ l o g
2
1
2
0
n
d
d
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,57
练 习
pp.499 17,26
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,1
7.1 图的概念 /Introduction of Graph
7.2 图的术语 /Graph Terminology
7.3 图的表示与同构 /
Representing Graph and Graph Isomorphism
7.4 连通性 /Connectivity
7.5 欧拉道路与哈密尔顿道路 /
Euler and Hamilton Paths
7.6 最短道路问题 /Shortest Path Problem
7.7 平面图 /Planar Graphs
7.8 图的着色 /Graph Coloring
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,2
7.4 连通性 /Connectivity
[定义 ]道路 /path：
当Ｇ中相邻边的序列 （ Ｖ 0,Ｖ 1）,
（ Ｖ 1,Ｖ 2）,…（ Ｖ k-1,Ｖ k） 称为一条 道路 （ 通路 ） 。 此道路的长度为ｋ 。 也可以以 （ Ｖ 0,Ｖ 1,…,Ｖ k） 表示道路,Ｖ 0为起点,Ｖ k为终点 。
当 Ｖ 0=Ｖ k时,该道路称为 回路 /circuit。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,3
[定义 ]简单道路 /Simple Path：
一条道路中没有两条边是相同的,称此道路为 简单道路 。 当其是回路时,称为 简单回路 /Simple Circuit。
[定义 ]基本道路 /Element Path：
一条道路中,除了起点和终点可以相同,没有其他相同顶点出现,称此道路为 基本道路 。 当其是回路时,称为 基本回路 /Element Circuit。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,4
e3
e5
e2
e1
d
c
b
a
e4
（ｅ 5，ｅ 1,ｅ 2,ｅ 3，ｅ 4）是简单道路，
不是基本道路，因为（ｃ，ａ，ｂ，ｃ，ｄ，
ｂ）中ｂ，ｃ均出现了两次。但（ c,d,b，
c）是基本道路。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,5
[定义 ]连通性 /connectivity：
设Ｇ＝（Ｖ，Ｅ）,（Ｖ 0，Ｖ 1,…,
Ｖ k） 是 G中的一条道路，则称Ｖ 0到Ｖ k连通
/connective或 可达 /。
说明：对无向图而言，若Ｖ 0到Ｖ k可达，则
Ｖ k到Ｖ 0也可达。对有向图而言则未必。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,6
[定理 1]
任意一个连通无向图的 任两个不同顶点都存在一条简单道路 。
[定义 ]无向图的连通性：
若Ｇ＝（Ｖ，Ｅ）中任两个不同顶点都连通，则称此无向图是 连通的
/connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,7
[定义 ]连通分图 /connected components：
图Ｇ可分为几个不相连通的子图,每一子图本身都是连通的 。 称这几个子图为Ｇ
的连通分图 。
[定义 ]无向图的连通性：
若Ｇ＝（Ｖ，Ｅ）中任两个顶点都连通，则称此无向图是 连通的 /connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,8
[定义 ]有向图的连通性：
(1)弱连通：
若Ｇ＝ （ Ｖ,Ｅ ） 对应的无向图是连通图,则称Ｇ为 弱连通 /weakly connected。
(2） 强连通：
若Ｇ＝ （ Ｖ,Ｅ ） 中任两点间都有路,
即对ａ与ｂ,ａ到ｂ可达,ｂ到ａ可达,称
Ｇ为 强连通 /strongly connected。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,9
连通无向图
:
弱连通
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,10
强连通
:
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,11
例：用图描述一台自动售货机,只用５分,１０
分二种硬币,满１５分后压按钮,选择一块巧克力,钱多了不找还 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,12
顶点：ａ：０ 分边,５：投５分
ｂ：５分 １０：投１０分
ｃ：１０分 ｐ：压按扭动作
ｄ,≥ １５分表示已投入钱的状态 表示一种动作自动售货机：有向加权图描绘得很清楚
（ 1）钱数不够，压按扭，不起作用
（ 2）钱数够了，压按扭，给过糖果回到０分状态
（ 3）钱超过１５分，再加钱白加
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,13
用邻接矩阵讨论图Ｇ的连通性质：
在邻接矩阵中,若ａ ij＝１,表明Ｖ i到Ｖ j有一条边,即Ｖ i到Ｖ j可达；若ａ ij＝０不说明Ｖ i到Ｖ j
没有道路,若通过其他点中转,也有可能连通 。 作邻接矩阵的普通矩阵乘法：
Ｂ＝Ａ
2
＝Ａ·Ａ＝
nnij
b
)(
ｂ ij ＝?
n
k
kjik
aa
1
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,14
ｂ ij的值表示Ｖ i到Ｖ j路长为２的道路条数,一般地,就有：
[定理 2]
Ａ m的元素ｍ ij表示Ｖ i到Ｖ j长度为ｍ的道路条数 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,15
[定理 3]：
ｎ个顶点的图Ｇ中,如果Ｖ i到Ｖ j
（ Ｖ i≠ Ｖ j） 有道路,则其最短的道路长度 ≤ ｎ－１ 。
[定理 4]：ｎ个顶点的图Ｇ中,A是 G的 邻接矩阵 。 Ｖ i,Ｖ j 是 G的顶点,
B=A+A2+…+An-1
则Ｖ i到Ｖ j（ Ｖ i≠ Ｖ j） 连通当且仅当 b ij
非零 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,16
定义：ｎ个顶点的图Ｇ中,A是 G的 邻接矩阵 。
B=A+A2+…+An-1 +An
称为 G的可达性矩阵 。
有向图的连通性 （ n?1）,
（ １ ） B中元素全为１?Ｇ强连通
（ 2） Ａ ∨ Ａ T的可达性矩阵元素全为１?
Ｇ是弱连通的 。
无向图的连通性 （ n?1）,
B中元素全为１?Ｇ连通
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,17
7.5 Euler and Hamilton Path
Konigsberg(哥尼斯堡 )七桥问题问题：能否从河岸或小岛出发,通过每一座桥,
而且仅仅通过一次回到原地 。
A
C
B
D
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,18
Euler(欧拉 )1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：
[定义 ]欧拉道路（回路）：
Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简单道路为 欧拉道路 /Euler Path/E道路 。
包含Ｅ中所有边的简单回路为 欧拉回路
/Euler Circuit/E回路
。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,19
[定理 1]（ 欧拉定理 ）,
没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是：
(1)图是连通的；
(2)图中奇次顶点个数是０个或 2个 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,20
证明：
必要性：
若存在欧拉道路,且没有０次顶点,则每个顶点都有边关联,而边又全在欧拉道路上,故所有顶点都连通 。
除了起点,终点外,欧拉道路每经过一个顶点,
使顶点的次增加２,故只有起点和终点才可能成为奇次顶点,而一个奇次顶点是不可能的,当无奇次顶点时,是欧拉回路 。
充分性：
若 (1）,(2)成立,构造欧拉道路,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,21
若图Ｇ存在奇次顶点,任取一个作为起点,若不存在,则任取一个顶点作为起点 。
若此图有ｎ条边,总次为２ｎ 。 每进入或离开一个顶点,让此顶点的次减１,由于除了两个 （ 或没有 ） 奇次顶点外,其余顶点次为偶数,只要进得去,一定出得来,直至进入另一个奇次顶点 （ 或起点 ） 作为终点 。 这样构造的是简单道路,如果经过所有的边,即得到一条欧拉道路 。
不然，记走过的简单道路为ｐ 1，ｐ 1上顶点集
Ｖ 1，边集Ｅ 1，Ｇ 1＝（Ｖ 1，Ｅ 1）是Ｇ的子图。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,22
若Ｇ 2＝ （ Ｖ 2,Ｅ 2） 是Ｇ 1的关于Ｇ的余图,Ｅ
2＝Ｅ－Ｅ 1,但Ｖ 1∩ Ｖ 2≠ φ,否则Ｇ不连通,设
Ｃ ∈ Ｖ 1∩ Ｖ 2,从Ｃ出发,用上面方法作Ｇ 2的简单回路ｐ 2 回到Ｃ,这能做到 。
因为作好ｐ 1后,留下顶点的次都是偶次 。 若
ｐ 1∪ ｐ 2经过所有边,则欧拉道路是ｐ 1走到Ｃ时,
先把ｐ 2走完,最后走完ｐ 1的余下道路 。
若ｐ 1∪ ｐ 2仍未经过所有边,将ｐ 1∪ ｐ 2视为
ｐ 1重复上述过程,由于Ｅ边有限,故存在欧拉道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,23
例 1：
A
B
C
D
E
F
G
H
I
J
（ 1）顶点的次,A(3),B(2),C(4),D(2),E(6),F(2),
G(6),H(2),I(4),J(3）。其中奇次顶点 A,J
（ 2）从 A出发，走一条道路
（ A,C,E,A,B,C,D,E,G,J）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,24
（ 3） Ｇ 1＝ （ Ｖ 1,Ｅ 1）
Ｖ 1 ＝ {A,B,C,D,E,G,J}
Ｅ 1 ＝ {（ A,B）,（ B,C）,（ A,C）,（ C，
D）,（ C,E）,（ D,E）,（ E,G）,（ G,J） }
Ｇ 2＝（Ｖ 2，Ｅ 2）
Ｅ 2 ＝ {（ E,F），（ F,G），（ E,J），
（ G,H），（ G,I），（ I,J），（ H,I） }
Ｖ 2 ＝ {E,F,G,H,I,J}
E∈ （ Ｖ 1?Ｖ 2）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,25
（ 4） 从 E出发回到 E的回路 （ E,F,G,I,J,E）,
加入到 P1中
Ｐ 1? ＝ （ A,C,E,F,G,I,J,E,A,B,C，
D,G,J）
（ 5） 还有未经过的边,重复上述过程,从 G出发,
（ G,H,I,G）,再加入即得欧拉道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,26
说明：
哥尼斯堡七桥问题,由于四个顶点都是齐次的,不可能有欧拉道路 。
应用与推广：
（ 1） 一笔画问题；
（ 2） 如果齐次顶点个数为 2K个,此问题是 K
笔画问题 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,27
例
８个顶点均为
3次，至少要
４笔。
定理 2（有向图的欧拉定理）：
不含次为０的孤立顶点的有向图具有欧拉道路的充要条件是：
(1）弱连通；
(2) 除了可能有２个顶点，一个入次比出次大１，
一个出次比入次大１，其余顶点出次等于入次。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,28
中国邮递员问题
(欧拉道路的应用 )(加权图 )
问题,
邮递员从邮局出发,走遍投递区域的所有街道,送完邮件后回到邮局,怎样使所走的路线全程最短,
若街道图 （ 街道的交叉口为顶点 ） 存在欧拉道路,显然此路是全程最短,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,29
Hamilton(哈密顿 )道路问题：
１８５９年发明的一种游戏 。
在一个实心的正十二面体,20个顶点标上世界著名大城市的名字,要求游戏者从某一城市出发,遍历各城市一次,最后回到原地 。
这就是,绕行世界,问题 。 即 找一条经过所有顶点 （ 城市 ） 的基本道路 （ 回路 ） 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,30
[定义 ]哈密顿道路 /回路：
Ｇ＝ （ Ｖ,Ｅ ）,G中经过Ｖ中所有顶点的基本道路称为 哈密顿道路 /Hamilton
Path,简称 Ｈ道路 。
Ｇ＝ （ Ｖ,Ｅ ）,G中经过Ｖ中所有顶点的基本回路称为 哈密顿回路 /Hamilton
Circuit,简称 Ｈ回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,31
A
B
图Ａ 每个顶点都是奇次的，不存在欧拉道路，但有Ｈ道路。 图Ｂ存在欧拉道路，不存在Ｈ道路。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,32
[定理 3]：设Ｇ＝（Ｖ，Ｅ）是ｎ个顶点的简单图，
如果任何一对顶点的次之和 ≥ｎ－１，则Ｇ中一定有Ｈ道路。
证明：
1,Ｇ一定连通,否则Ｇ分为二个不连通的分图
Ｇ 1,Ｇ 2,其中Ｇ 1有ｎ 1个顶点,Ｇ 2有ｎ 2个顶点,
Ｇ 1中每个顶点次 ≤ ｎ 1－１,Ｇ 2中每个顶点次 ≤ ｎ
2－１,从Ｇ 1中取一个顶点,Ｇ 2中取一个顶点,这一对顶点之和 ≤ ｎ 1－１＋ｎ 2－１＝ｎ 1＋ｎ 2－２
＝ｎ－２＜ｎ－１,与定理的假设矛盾 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,33
2,用逐步递推构造法证明Ｇ中存在Ｈ道路：
(1)任取一条边 （ Ｖ 1,Ｖ 2）,是含２个顶点的基本道路 。
(2)如果已有ｐ个顶点的基本道路
（ Ｖ 1,Ｖ 2,…,Ｖ p）,（ ｐ ≤ ｎ－１ ）
必能构造ｐ＋１个顶点的基本道路 。
ａ ） 如果在Ｖ－ ｛ Ｖ 1,Ｖ 2,…Ｖ p｝ 中存在与Ｖ 1
或Ｖ p相邻的顶点,则基本道路自然可以扩充一个顶点 。
ｂ ） 如果Ｖ 1,Ｖ p仅与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中顶点相邻,则 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 必可适当排列,
形成回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,34
如果Ｖ 1与Ｖ p相邻,显然成了环 。 不然,由于Ｖ 1，
Ｖ p仅与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中顶点相邻,Ｖ 1,Ｖ p
的次 ≤ ｐ－１ 。 不妨设Ｖ 1的次为ｋ ≤ ｐ－１,分别记相邻顶点为Ｖ i1,Ｖ i2,…,Ｖ ik,它们前面的顶点
（ 指在基本道路 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝ 中的序 ）
为,Ｖ p必与中某顶点相邻,否则Ｖ p的次 ≤ ｐ－１－ｋ,Ｖ 1与Ｖ
p的次之和 ≤ ｋ＋ｐ－１－ｋ＝ｐ－１＜ｎ－１,与任一对顶点次之和 ≥ ｎ－１矛盾 。
不妨Ｖ p与Ｖ j-1相邻,Ｖ 1与Ｖ j相邻 。 将Ｖ 1与
Ｖ j连起来,Ｖ p与Ｖ j-1连起来,并将Ｖ j-1到 Ｖ j的边去掉,就形成一个环,如下图所示 。
111,,,21 kiii VVV?111,,,21 kiii VVV?
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,35
V x
V k
V k -1
V j
V j- 1
V 1 V 2 V j- 2
V p
又由Ｇ的连通性,总可在Ｖ－ ｛ Ｖ 1,Ｖ 2,…，
Ｖ p｝ 中找到一个点Ｖ x,与 ｛ Ｖ 1,Ｖ 2,…,Ｖ p｝
中某一顶相邻,不妨与Ｖ k相邻,Ｖ k≠ Ｖ 1,Ｖ k≠
Ｖ p,连上Ｖ x与Ｖ k的边,去掉Ｖ k-1到Ｖ k的边,可以从Ｖ k-1为起点,一直走到Ｖ k,再到Ｖ x,这是一条ｐ＋１个顶点的基本道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,36
如果ｐ＋１＜ｎ,仍继续扩充基本道路内的顶点,直至达到ｎ 。
注意,
此定理条件显然不是必要条件,如ｎ ≥ ６的ｎ
边形,二个顶点次之和＝４,
４＜ｎ－１,而ｎ边形显然有Ｈ道路 。
[定理 4]：
Ｇ＝ （ Ｖ,Ｅ ） 是ｎ ≥ ３的简单图,若任何一对顶点的次之和 ≥ ｎ,则Ｇ必有哈密顿回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,37
由于定理 4条件也必满足定理 3条件,存在Ｈ道路,可类似于定理一的方法找到一条回路 。
[定理 5]：
有向完全图一定存在Ｈ道路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,38
小 结
1、图中顶点的连通性 /可达性
2、图的连通性有向图、无向图
3,E图：简单道路 +所有边
4,H图：基本道路 +所有顶点
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,39
进一步的思考
1,图的连通性的计算机表示与实现
2,E图 /H图的应用
3,E图 /H图的判定
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,40
要判别一个图不存在Ｈ道路,Ｈ回路,也不是很容易的,只能对无向图给出一些必要条件：
（ 1） Ｈ道路存在必要条件：
１ ） 连通
２ ） 至多只能有二个顶点的次＜２,其余顶点的次 ≥ ２ 。
b
c
d
a
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,41
（ 2） Ｈ回路存在必要条件：
对Ｖ的任一非空真子集Ｓ,Ｇ－Ｓ的连通分图个数 ≤ |Ｓ |。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,42
A
A2
B
B
A1
B
A
A
B
B
B
A
B
解：取Ｓ＝ ｛ A1,A2 ｝
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,43
G－Ｓ存在 3个分图根据 H道路存在的必要条件之二,
可知,H道路不存在 。
A
A2
B
B
A1
B
A
A
B
B
B
A
B
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,44
应用问题之一：
Knight’s tour
应用问题之二：
Gray Code
应用问题之三：
Tower of Hanoi
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,45
练 习
pp.473 1,2,12,31
pp.486 36,37,65
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,46
7.6 最短道路问题
Shortest Path Problem
加权图 /Weighted graph
G = （ V,E,f ）,f:E?R+
G满足简单连通无向
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,47
Example:
Weighted Graphs Modeling an Airline
System For SF,LS,DL,DV,CG,BT,NY
Cities,
Mileage
Flight Times
Fares
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,48
Example:
Weighted Graphs Modeling a Computer
Network For SF,LS,DL,DV,CG,BT,
NY Cities,
Distance
Response Time
Lease Rate(per month)
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,49
a到 b的道路及其长度,
道路中所有边的函数值之和。
a到 b的 最短道路 /shortest path：
所有 a到 b的道路中长度最短的一条。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,50
a到 b的道路及其长度,
道路中所有边的函数值之和。
求 G中任意两个顶点 a到 b的 最短道路的方法：
Dijkstra’s 算法
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,51
应用问题,旅行商问题 （ TSP）
Traveling Salesman Problem
问题：从某地出发，恰好一次经过ｎ个城市回到原地，寻找最短的道路。
实质：无向简单加权图，寻找最短Ｈ回路的问题。
说明：
（ 1） 不一定存在,若无向图是完全图则存在 。
（ 2） 图是 连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的 H回路问题,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,52
无向加权完全图的 最近邻域算法 /Approximation：
１,从任一顶点出发,记为Ｖ 1,找一个与Ｖ 1最近的顶点Ｖ 2,（ Ｖ 1,Ｖ 2） 为两个顶点的基本道路 。
２,若找出有ｐ个顶点的基本道路
（ Ｖ 1,Ｖ 2,…,Ｖ p）,ｐ＜ｎ,在道路外找一个离Ｖ p最近的顶点,记为Ｖ p+1,将其加入则得到具有 P+1个顶点的基本道路 。
３,若ｐ＋１＝ｎ,转４,否则转２ 。
４,闭合Ｈ回路：即增加一条边 （ Ｖ n,Ｖ 1）,
则 （ Ｖ 1,Ｖ 2,…,Ｖ n,Ｖ 1） 为一条近似的最短回路 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,53
说明：
(1)找最近一个顶点不唯一时,按序取 。
(2) 不一定是最短Ｈ回路,
例：
下 图是加权无向完全图,从 a点出发,用最近邻域法求最短Ｈ回路,并与实际的最短 H
回路做比较 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,54
d
a
c
e
a
b
14
d
a
a
11
d
a
a
13 8
d
a
a
12
d
a
a
9
d
a
a
10
d
a
a5
d
a
a
6
d
a
a
7
d
a
a
d
d
a
a
7
d
a
a
14
d
a
a
8
d
a
a
6
d
a
a
5
d
a
a
c
d
a
a
b
d
a
a
a
d
a
a
e
d
a
a
最近邻域法所求为,（ ａ,ｃ,ｅ,ｄ,ｂ,ａ ）
总长为７＋６＋８＋５＋１４＝４０
最短回路,（ ａ,ｃ,ｅ,ｂ,ｄ,ａ ）
总长为７＋６＋９＋５＋１０＝３７ 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,55
(2)以关联 ei的两个顶点 v1,v2分别作为起点，用最近邻域法求最短 H回路。
(3)再比较这两条回路的长度，以确定最短的一条。
如上例,
（ ｂ,ｄ ） 边长为５,最短 。
以ｂ为起点,（ ｂ,ｄ,ｅ,ｃ,ａ,ｂ ）
总长为４０
以ｄ作起点,（ ｄ,ｂ,ｅ,ｃ,ａ,ｄ ）
总长为３７
改进,
(1)找一条最短的边 ei。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,56
设Ｇ＝ （ Ｖ,Ｅ,Ｗ ） 是ｎ个顶点的完全无向图,满足三角不等式ｗ （ ｉ,ｊ ） ＋ｗ （ ｊ,ｋ ）
≥ ｗ （ ｉ,ｋ ）,ｄ 0是最短Ｈ回路Ｄ 0的长度,ｄ
是最近邻域法得到的Ｈ回路Ｄ的长度,则,
2
1][ l o g
2
1
2
0
n
d
d
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,57
练 习
pp.499 17,26
