E.Euler（瑞士数学家）
18世纪创始人创立时间问题的提出歌尼斯堡七桥难题
※ 歌尼斯堡七桥难题普莱格尔河结论,不存在这样一种走法。
用 A,B表示两座小岛,C,D表示两岸，
连线 AB表示 A,B之间有一座桥。
问题简化为：
A? B
C
D
在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点七桥问题的 数学模型,
类似的问题：一笔画问题字的一笔画：如“中、日、口、串”等可一笔画而：“田、目”等不能一笔画图的一笔画,可一笔画 不可一笔画图论的应用范围：
1、中国邮路问题：
邮递员如何选择适当的投递路线，使每条街道至少走过一次且所走的总路程最短？
2、最短路问题：
一个乡有 9个自然村，其间道路如下图所示，
要以村为中心 建有线广播网，如要求沿道路架设广播线，应如何架设使所用电线最短 0v
0v
4 1
1
5
2
4
4
31
2
3
55
1
4
2
1
0v
1
2
1
2
3
1 2
已知一个地区的交通网络如下图所示，其中点代表居民小区，边表示公路，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？
结论：把医院建在 v6,可使离医院最远的小区居民就诊时所走的路程最近即求图的中心
3、选址问题
1v
2v
3v
4v
5v
6v
60
30
15
1825
15
20
7v
20
30
例：在一个输油管道网中，
为起点，sv,为终点tv
的总运输量最大？到使从应如何安排，才能管道的最大输油量，问边上的数表示该为中转站（
ts
i
vv
kiv ),,,2,1
最大流问题
4、网络流问题：
旅客流、车流、货物流
1v
2v
3v
4v
5v
6v
2
6
1
7
3
2?tv
2
4
sv
2
15
3
4
4
------由若干个点和连接这些点的某些连线所组成的图形
vi—— 图中的点，称为顶点。
ei—— 图中的连线，称为边。
m(G)=|E|—— G的边数,简记为 m
n(G)= |V|—— G的顶点数,简记为 n
一、图的概念记 V={vi},E= {ei},
G=（ V,E）
图
G—— 一个图代表具体事物 代表事物之间的联系
G
1v
2v
3v
4v
5v
1e
2e
3e4e
5e?
6e
m=6,n=5
jik vve,53,vv?
5.1 基本概念
图有向图无向图
—— 边 e=（ vi,vj）有方向
—— 边 e=（ vi,vj）无方向此时（ vi,vj） = （ vj,vi）
e4=（ v3,v4） =（ v4,v3）e4=（ v3,v4） ≠（ v4,v3）
e5=（ v3,v4） =（ v4,v3）
此时（ vi,vj） ≠ （ vj,vi）
vi为始点,vj为终点
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
有向图无向图
e5=（ v4,v3） ≠（ v3,v4）
二、常用名词：
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
1、端点和关联边：
的关联边和是点边的端点，是边、则称点若
jik
kjijik
vve
evvEvve,,
2、相邻点和相邻边：
边边称为相邻边，简称邻端点落在同一个顶点的相邻点，简称邻点，一条边的两个端点称为
3、多重边与环：
点的边称为环。两个端点落在同一个顶多重边或平行边；具有相同端点的边称为
4、多重图和简单图：
为简单图。无环也无多重边的图称重图；含有多重边的图称为多
4e
5,次,)(
iii vdvv 的次，点为端点的边的条数称为以点
6、悬挂点和悬挂边：
7、孤立点：
8,奇点与偶点,
,3)( 1?vd
边。挂点相联的边称为悬挂的点称为悬挂点，与悬次为 1
为悬挂点，,62 vv 为悬挂边，,52 ee
的点称为孤立点次为 0
为孤立点,5v
点，次为偶数的点称为偶次为奇数的点称为奇点
1v
2v
3v
4v
2e
3e 4e
5e
1e
5v?
6v
6e 为奇点，、、、
6421 vvvv
为偶点,35 vv
4)( 3?vd,1)( 2?vd
,3)( 4?vd,0)( 5?vd,1)( 6?vd
)( ivd 12,G的边数 m=6
mvd i 2)(即定理 1 在图 G=(V,E)中，所有点的次之和是边数 m
的两倍。
证明,由于每条边均与两个顶点关联，
因此在计算顶点的次时每条边都计算了两遍所以顶点次数的总和等于边 数的二倍。
三、次的性质定理 5.2 在任何图 G=(V,E)中,奇点的个数为偶数证明,中奇点和偶点的集合分别是图和设 GVV
21
2121 VVVVV 且则
21
)()()(
Vi
i
Vi
i
Vi
i vdvdvd
（定理 5.1）m2?
是偶点的集合2V? 均为偶数))((,2Vivd i?
为偶数所以?
2
)(
Vi
ivd 为偶数
1
)(
Vi
ivd
是奇点的集合而 1V 均为奇数))((,1Vivd i?
只有偶数个奇数相加才能得到偶数为偶数中的点，即奇点的个数所以 1V
、链的定义：1
的一条链与连接则称这个点边序列为且错序列）中，一个点与边的交，（在图
iki
ititit
ikikikikikiiii
vv
ktvve
vevevevev
EVG
0
1
1122110
),,2,1)(,(
},,,,,,,,,{
},,,,,,,,,,,{ 18433229445 vevevevevev
},,,,{ 17556 vevev
},,,,{ 48176 vevev
简单链：? 中，所含的边均不相同在链?
初等链：?
简单链链四、链：
},,,,{,1210 ikikikii vvvvv,简记为
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
不相同中，所含的顶点、边均在链?
的一条链与连接 15 vv
不是链
），（对无向图 EVG?
初等
开链闭链链中的起点与终点重合链?:
中的起点与终点不同链?:
圈或回路
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
为一个圈},,,,,,,,,,,,{ 5443322948175 vevevevevevev
为一个圈},,,,,,,,{ 544816655 vevevevev
初等圈简单圈 中，所含的边均不相同在圈?
的边没有相同的顶点和相同外，中，除起点和终点重合在圈?
简单圈初等圈道路为一条道路 },,,,,,{ 3229481 vevevev
五、连通图,一条链相连中任意两点之间至少有：图 G
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e?
1v
2v
3v
4v
2e
3e 4e
1e
5v
6e
连通图不连通图六,赋权图（网络 ）
对图 G=（ V,E），
若对每一条边 e，都有一个实数 w(e)与之对应，
e的权则称图 G=（ V,E）为赋权图,或网络权 w(e)通常表示距离、费用、容量等如公路交通图,Vi表示 城市,ei表示公路
w(ei）表示公路 ei的长度如 w(e2） =50：
城市 v2 到城市 v3
的距离是 50公里
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
5.2 欧拉图与中国回路问题欧拉道路：?
道路，则称这条道路为欧拉每一条边一次且仅一次中的存在一条道路，经过是一个无向连通图，若设 GG
开链
},,,,,,,,,,,,{ 4456223345112 vevevevevevev
一条欧拉道路：
的到存在 42 vv 一条欧拉道路：
的到存在 43 vv
},,,,,,,,{ 441122433 vevevevev
1e
2e
3e
4e?
1v 2v
3v
4v
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
1e
3e
2e
1v 2v
3v
4v
存在条欧拉道路任两点之间都不一笔画问题回路，则称这个回路为欧拉每一条边一次且仅一次中的存在一个回路，经过是一个无向连通图，若设 GG
欧拉回路：? 圈
},,,,,,,,,,,,,,{ 164455274332211 vevevevevevevev
存在欧拉回路：
该图特点,均为偶数)(
ivd
该图不存在欧拉回路存在奇点
1v 2v1e
2e
3e
4e
5e?
3v
4v5v
6e
7e
1e
2e
3e
4e 5
e
1v 2v
3v 4v
欧拉图定理 5.3 无向连通图 G为欧拉图的充要条件是 G中无奇点已知 G=（ V,E)为欧拉图，即存在一条欧拉回路 C，
C经过 G的每一条边,由于 G为连通图，
所以 G中的每个点至少在 C中出现一次证明：必要性
Vv i对的中间点，是若 Cv i 条边每出现一次，必关联两 iv
},,,,,,,,,,,{ 111132211 vvevevvevevC iiiii：如为偶数)( ivd? 为偶点，即 iv
的起点，是若 Cv i 的终点，也是 Cv i 必关联两条边 iv
为偶数)( ivd? 为偶点，即 iv
充分性,若无向连通图 G=(V,E)中无奇点，则 G为欧拉图
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
为偶数)( ivd连通，G
G
例,
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
},,,,,,{ 32294331 vevevevC,简单回路
），，（记 EVCGG 1 中边的端点是,EVEEE 1
G
6v
1e
4e
5e
6e
1v 2v
4v5v
7e
8e
10e
G?
},,,,,,,,{ 21166551022 vevevevevC,简单回路
4e
1v
4v5v
7e
8e
G?
},,,,,,{ 18445713 vevevevC,简单回路
，任取一点，如 3v
221 CvCGG 为起点取一个简单回路的公共顶点与中，以在
13 Cv 为起点的一个简单回路找一个以
），，（记 EVCGG 2 中边的端点是,EVEEE 1
312 CvCGG 为起点取一个简单回路的公共顶点与中，以在
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
G
6v
1e
4e
5e
6e
1v 2v
4v5v
7e
8e
10e
G?
2116655102,,,,,,,,vevevevev 184457,,,,,,veveve,,,,{ 9433 evev },,32 ve
4e
1v
4v5v
7e
8e
G?
},,,,,,{ 32294331 vevevevC,简单回路
},,,,,,,,{ 21166551022 vevevevevC,简单回路
},,,,,,{ 18445713 vevevevC,简单回路
，，得一简单回路点处插入的从把 CCvCC 2123
，即得所求欧拉回路：点处插入的从再把 121 CvCC
},,,,,,,,{ 2116655102 vevevevevC,184457,,,,,,veveve
1e
2e
3e4e
5e
6e
1v
2v? 3v
4v
5v
7e
例：判断下图是否为欧拉图，若是，求出欧拉回路
:1C
3455473,,,,,,vevevev
164332211,,,,,,,,{ vevevevev
定理 5.3 无向连通图 G为欧拉图的充要条件 是 G中无奇点
:欧拉回路
1643,,,,veve,,,,,{ 32211 vevev
4e
5e
3v
4v
5v
7e
:2C
345547,,,,,veveve
定理 5.3 无向连通图 G为欧拉图的充要条件是 G中无奇点推论 无向连通图 G有欧拉道路的充要条件是 G中恰有两个奇点
),,( ji vveG?上增加一条边在的奇点，是证明：充分性：设 Gvv ji,
，得连通图 G?
中无奇点，则 G? CG 存在欧拉回路所以?
，中的边去掉 eC 为终点的欧拉道路为起点即得以 ji vv,
LvvG ji 为终点的欧拉道路为起点有一条以必要性：设,
),,( ji vveG?上增加一条边在
CGLe 的一条欧拉回路中得加到把边?为欧拉图，即 G?
Gvvd,)( 为偶数为奇数)(),(,ji vdvd中，在 G
一笔画问题：
1、一个连通图的顶点都是偶点，没有奇点，则该图可以一笔画出
2、一个连通图的顶点恰有两个奇点，其余均为偶点，
则从任一奇点出发，可以一笔画出该图，而终点则是另一个奇点。
（从任一点出发均可）
3、一个连通图的顶点有两个以上的奇点，则该图不能一笔画出田日中 白回 不连通可一笔画 可一笔画 不可一笔画可一笔画 可一笔画 不可一笔画 不可一笔画二,中国邮路问题提出问题的人：管梅谷教授时间,1962年提出的问题：
一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？
邮路问题的图论描述：
取一无向赋权连通图 G=（ V,E）
E中的每一条边对应一条街道每条边的非负权 l(e)=街道的长度
V中某一个顶点为邮局，其余为街道的交叉点在 G上找一个圈，
该圈过每边至少一次，且圈上所有边的权和最小
1、若 G中的顶点均为偶点,即 G中存在欧拉回路，
则该回路过每条边一次且仅一次，
此回路即为所求的投递路线邮路问题的图论描述：
在无向连通赋权 G =（ V,E）上找一个圈，
该圈过每边至少一次，且圈上所有边的权和最小
2,G中有奇点,不存在欧拉回路投递路线：至少有一街道要重复走一次或多次为邮局为邮路图，其中例：设 1vG
不是欧拉图为奇数 Gvdvd,)(),( 43?
不存在欧拉回路，G?
即不存在每条街道走一次且只走一次的投递路线
14253214563211 vvvvvvvvvvvvvC,路线 12?权和
1232563542412 vvvvvvvvvvvvC,路线 11?权和
12 CC 优于路线路线分析：
），），（，），（，重复走过边：（路线 4132211 vvvvvvC
），），（，重复走过边：（路线 32422 vvvvC
重复边
2?重复边的权和结论：
选择最佳投递路线 =选择重复边的权和最小的路线
3?重复边的权和
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
14253214563211 vvvvvvvvvvvvvC,对路线
），），（，），（，重复边：（ 413221 vvvvvv
1G
为欧拉图,1G 的一条欧拉回路为且 11 GC
1232563542412 vvvvvvvvvvvvC,对路线
），），（，重复边：（ 3242 vvvv
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
2G
为欧拉图，2G 的一条欧拉回路为且 22 GC
欧拉图一条投递路线对应一个条欧拉回路且投递路线为该图的一反之，对邮路图 G，
的一条链到任取奇点 34 vv
3654,,,vvvv如：
对该链上的每一条边增加一条重复边
G?
为欧拉图G? 存在欧拉回路即 G?,
CG 对应一条投递路线即?
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
G
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
投递路线 欧拉图
1454256536321 vvvvvvvvvvvvvC,
结论,对任意一个含奇点的邮路图 G，由于奇点的个数为偶数个，把每两个配成一对，由于 G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线寻找最佳投递路线方法,
在原邮路图上增加一些重复边得一个欧拉图，，
在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线管梅谷 —— 奇偶点图上作业法奇偶点图上作业法,
例：求解右图所示的邮路问题第一步：确定一个初始可行方案方法,检查图 G中是否有奇点无奇点：,找出一条以 v1为起点的欧拉回路,该回路就是最佳投递路线有奇点：
图 G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，
在该条链上的每一条边增加一条重复边，得一个欧拉图 G1,由 G1所确定的欧拉回路即为一个可行方案
v2,v8,v4,v6G中有奇点：
取 v2到 v4的一条链,v2v1v6v7v8v9v4
取 v6到 v8的一条链,v6v1v2v3v4v9v8
)( 1为邮局v
G
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
G1
显然 G1不是最佳方案
G1是欧拉图，
第二步：调整可行方案，
使重复边权和下降重复边权和 =
若图中某条边有两条或多于两条的重复边同时去掉偶数条，
G2
使图中每一条边最多有一条重复边
G2的重复边权和 =
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
步骤 1、
可得到重复边权和较小的欧拉图
4
G2
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
51
21
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35G2是欧拉图，
重复边权和 =21
G2
4
2、使图中每个初等圈重复边的权和不大于该圈权和的一半
9个初等圈
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
G2
4
3
G3是欧拉图，
重复边权和 =17
G3
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
6（ 1） v1v2v5v6v1 16 √
7（ 2） v6v5v8v7v6 14 √
10（ 3） v2v3v4v5v2 24 √
4（ 4） v5v4v9v8v5 16 √
G3的初等圈 权和 重复边权和
13（ 5） v1v2v5v8v7v6v1 24 ×
G4
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
G4
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
7（ 1） v1v2v5v6v1 16 √
4（ 2） v6v5v8v7v6 14 √
4（ 3） v2v3v4v5v2 24 √
8（ 4） v5v4v9v8v5 16 √
G4的初等圈 权和 重复边权和
11（ 5） v1v2v5v8v7v6v1 24
1v
√
（ 6） v2v3v4v9v8v5v2 32 4 √
（ 8） v6v5v4v9v8v7v6
（ 7） v1v2v3v4v5v6v1 28 11 √
22 4 √
（ 9） v1v2v3v4v9v8v7v6v1 36 7 √
G4是最佳方案最佳投递路线：
16785894561254321 vvvvvvvvvvvvvvvvv
奇偶点图上作业法,
第一步：确定一个初始可行方案方法,检查图 G中是否有奇点。
无奇点：,找出一条以 v0为起点的欧拉回路，该回路就是最佳投递路线有奇点：
图 G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边第二步：调整可行方案，使重复边权和下降
1、使图中每一条边最多有一条重复边若图中某条边有两条或多于两条的重复边，
同时去掉偶数条
2、使图中每个初等圈重复边的权和 ≤ 该圈权和的一半若图中某初等圈重复边的权和大于该圈权和的一半去掉圈中的重复边同时将圈中没有重复边的边加上重复边为邮局）线最短（路线行走才能使所行路问邮递员应按怎样的例：设有邮路图如下，
0v
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2?
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2
最佳投递路线,v0v3v0 V4v3v4 v5v3v2v5
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2
v1v2v1 v4v1v0
期末考试论文题目：
请用所学的运筹学方法解决一个你在工作、学习、
生活中所遇到的实际问题。（ 40分）
要求：
1、字数不少于 400字。
2、不能采用课堂、作业、教材上的原题。
（说明：若出现两篇完全相同的论文，每篇各得一半分）
18世纪创始人创立时间问题的提出歌尼斯堡七桥难题
※ 歌尼斯堡七桥难题普莱格尔河结论,不存在这样一种走法。
用 A,B表示两座小岛,C,D表示两岸，
连线 AB表示 A,B之间有一座桥。
问题简化为：
A? B
C
D
在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点七桥问题的 数学模型,
类似的问题：一笔画问题字的一笔画：如“中、日、口、串”等可一笔画而：“田、目”等不能一笔画图的一笔画,可一笔画 不可一笔画图论的应用范围：
1、中国邮路问题：
邮递员如何选择适当的投递路线，使每条街道至少走过一次且所走的总路程最短？
2、最短路问题：
一个乡有 9个自然村，其间道路如下图所示，
要以村为中心 建有线广播网，如要求沿道路架设广播线，应如何架设使所用电线最短 0v
0v
4 1
1
5
2
4
4
31
2
3
55
1
4
2
1
0v
1
2
1
2
3
1 2
已知一个地区的交通网络如下图所示，其中点代表居民小区，边表示公路，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？
结论：把医院建在 v6,可使离医院最远的小区居民就诊时所走的路程最近即求图的中心
3、选址问题
1v
2v
3v
4v
5v
6v
60
30
15
1825
15
20
7v
20
30
例：在一个输油管道网中，
为起点，sv,为终点tv
的总运输量最大？到使从应如何安排，才能管道的最大输油量，问边上的数表示该为中转站（
ts
i
vv
kiv ),,,2,1
最大流问题
4、网络流问题：
旅客流、车流、货物流
1v
2v
3v
4v
5v
6v
2
6
1
7
3
2?tv
2
4
sv
2
15
3
4
4
------由若干个点和连接这些点的某些连线所组成的图形
vi—— 图中的点，称为顶点。
ei—— 图中的连线，称为边。
m(G)=|E|—— G的边数,简记为 m
n(G)= |V|—— G的顶点数,简记为 n
一、图的概念记 V={vi},E= {ei},
G=（ V,E）
图
G—— 一个图代表具体事物 代表事物之间的联系
G
1v
2v
3v
4v
5v
1e
2e
3e4e
5e?
6e
m=6,n=5
jik vve,53,vv?
5.1 基本概念
图有向图无向图
—— 边 e=（ vi,vj）有方向
—— 边 e=（ vi,vj）无方向此时（ vi,vj） = （ vj,vi）
e4=（ v3,v4） =（ v4,v3）e4=（ v3,v4） ≠（ v4,v3）
e5=（ v3,v4） =（ v4,v3）
此时（ vi,vj） ≠ （ vj,vi）
vi为始点,vj为终点
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
有向图无向图
e5=（ v4,v3） ≠（ v3,v4）
二、常用名词：
1v
2v
3v
4v
1e
2e
3e 4e
5e
6e
1、端点和关联边：
的关联边和是点边的端点，是边、则称点若
jik
kjijik
vve
evvEvve,,
2、相邻点和相邻边：
边边称为相邻边，简称邻端点落在同一个顶点的相邻点，简称邻点，一条边的两个端点称为
3、多重边与环：
点的边称为环。两个端点落在同一个顶多重边或平行边；具有相同端点的边称为
4、多重图和简单图：
为简单图。无环也无多重边的图称重图；含有多重边的图称为多
4e
5,次,)(
iii vdvv 的次，点为端点的边的条数称为以点
6、悬挂点和悬挂边：
7、孤立点：
8,奇点与偶点,
,3)( 1?vd
边。挂点相联的边称为悬挂的点称为悬挂点，与悬次为 1
为悬挂点，,62 vv 为悬挂边，,52 ee
的点称为孤立点次为 0
为孤立点,5v
点，次为偶数的点称为偶次为奇数的点称为奇点
1v
2v
3v
4v
2e
3e 4e
5e
1e
5v?
6v
6e 为奇点，、、、
6421 vvvv
为偶点,35 vv
4)( 3?vd,1)( 2?vd
,3)( 4?vd,0)( 5?vd,1)( 6?vd
)( ivd 12,G的边数 m=6
mvd i 2)(即定理 1 在图 G=(V,E)中，所有点的次之和是边数 m
的两倍。
证明,由于每条边均与两个顶点关联，
因此在计算顶点的次时每条边都计算了两遍所以顶点次数的总和等于边 数的二倍。
三、次的性质定理 5.2 在任何图 G=(V,E)中,奇点的个数为偶数证明,中奇点和偶点的集合分别是图和设 GVV
21
2121 VVVVV 且则
21
)()()(
Vi
i
Vi
i
Vi
i vdvdvd
（定理 5.1）m2?
是偶点的集合2V? 均为偶数))((,2Vivd i?
为偶数所以?
2
)(
Vi
ivd 为偶数
1
)(
Vi
ivd
是奇点的集合而 1V 均为奇数))((,1Vivd i?
只有偶数个奇数相加才能得到偶数为偶数中的点，即奇点的个数所以 1V
、链的定义：1
的一条链与连接则称这个点边序列为且错序列）中，一个点与边的交，（在图
iki
ititit
ikikikikikiiii
vv
ktvve
vevevevev
EVG
0
1
1122110
),,2,1)(,(
},,,,,,,,,{
},,,,,,,,,,,{ 18433229445 vevevevevev
},,,,{ 17556 vevev
},,,,{ 48176 vevev
简单链：? 中，所含的边均不相同在链?
初等链：?
简单链链四、链：
},,,,{,1210 ikikikii vvvvv,简记为
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
不相同中，所含的顶点、边均在链?
的一条链与连接 15 vv
不是链
），（对无向图 EVG?
初等
开链闭链链中的起点与终点重合链?:
中的起点与终点不同链?:
圈或回路
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
为一个圈},,,,,,,,,,,,{ 5443322948175 vevevevevevev
为一个圈},,,,,,,,{ 544816655 vevevevev
初等圈简单圈 中，所含的边均不相同在圈?
的边没有相同的顶点和相同外，中，除起点和终点重合在圈?
简单圈初等圈道路为一条道路 },,,,,,{ 3229481 vevevev
五、连通图,一条链相连中任意两点之间至少有：图 G
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e?
1v
2v
3v
4v
2e
3e 4e
1e
5v
6e
连通图不连通图六,赋权图（网络 ）
对图 G=（ V,E），
若对每一条边 e，都有一个实数 w(e)与之对应，
e的权则称图 G=（ V,E）为赋权图,或网络权 w(e)通常表示距离、费用、容量等如公路交通图,Vi表示 城市,ei表示公路
w(ei）表示公路 ei的长度如 w(e2） =50：
城市 v2 到城市 v3
的距离是 50公里
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
5.2 欧拉图与中国回路问题欧拉道路：?
道路，则称这条道路为欧拉每一条边一次且仅一次中的存在一条道路，经过是一个无向连通图，若设 GG
开链
},,,,,,,,,,,,{ 4456223345112 vevevevevevev
一条欧拉道路：
的到存在 42 vv 一条欧拉道路：
的到存在 43 vv
},,,,,,,,{ 441122433 vevevevev
1e
2e
3e
4e?
1v 2v
3v
4v
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
1e
3e
2e
1v 2v
3v
4v
存在条欧拉道路任两点之间都不一笔画问题回路，则称这个回路为欧拉每一条边一次且仅一次中的存在一个回路，经过是一个无向连通图，若设 GG
欧拉回路：? 圈
},,,,,,,,,,,,,,{ 164455274332211 vevevevevevevev
存在欧拉回路：
该图特点,均为偶数)(
ivd
该图不存在欧拉回路存在奇点
1v 2v1e
2e
3e
4e
5e?
3v
4v5v
6e
7e
1e
2e
3e
4e 5
e
1v 2v
3v 4v
欧拉图定理 5.3 无向连通图 G为欧拉图的充要条件是 G中无奇点已知 G=（ V,E)为欧拉图，即存在一条欧拉回路 C，
C经过 G的每一条边,由于 G为连通图，
所以 G中的每个点至少在 C中出现一次证明：必要性
Vv i对的中间点，是若 Cv i 条边每出现一次，必关联两 iv
},,,,,,,,,,,{ 111132211 vvevevvevevC iiiii：如为偶数)( ivd? 为偶点，即 iv
的起点，是若 Cv i 的终点，也是 Cv i 必关联两条边 iv
为偶数)( ivd? 为偶点，即 iv
充分性,若无向连通图 G=(V,E)中无奇点，则 G为欧拉图
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
为偶数)( ivd连通，G
G
例,
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
},,,,,,{ 32294331 vevevevC,简单回路
），，（记 EVCGG 1 中边的端点是,EVEEE 1
G
6v
1e
4e
5e
6e
1v 2v
4v5v
7e
8e
10e
G?
},,,,,,,,{ 21166551022 vevevevevC,简单回路
4e
1v
4v5v
7e
8e
G?
},,,,,,{ 18445713 vevevevC,简单回路
，任取一点，如 3v
221 CvCGG 为起点取一个简单回路的公共顶点与中，以在
13 Cv 为起点的一个简单回路找一个以
），，（记 EVCGG 2 中边的端点是,EVEEE 1
312 CvCGG 为起点取一个简单回路的公共顶点与中，以在
1e
2e
3e
4e
5e
6e
1v 2v
3v
4v5v
6v
7e
8e
9e
10e
G
6v
1e
4e
5e
6e
1v 2v
4v5v
7e
8e
10e
G?
2116655102,,,,,,,,vevevevev 184457,,,,,,veveve,,,,{ 9433 evev },,32 ve
4e
1v
4v5v
7e
8e
G?
},,,,,,{ 32294331 vevevevC,简单回路
},,,,,,,,{ 21166551022 vevevevevC,简单回路
},,,,,,{ 18445713 vevevevC,简单回路
，，得一简单回路点处插入的从把 CCvCC 2123
，即得所求欧拉回路：点处插入的从再把 121 CvCC
},,,,,,,,{ 2116655102 vevevevevC,184457,,,,,,veveve
1e
2e
3e4e
5e
6e
1v
2v? 3v
4v
5v
7e
例：判断下图是否为欧拉图，若是，求出欧拉回路
:1C
3455473,,,,,,vevevev
164332211,,,,,,,,{ vevevevev
定理 5.3 无向连通图 G为欧拉图的充要条件 是 G中无奇点
:欧拉回路
1643,,,,veve,,,,,{ 32211 vevev
4e
5e
3v
4v
5v
7e
:2C
345547,,,,,veveve
定理 5.3 无向连通图 G为欧拉图的充要条件是 G中无奇点推论 无向连通图 G有欧拉道路的充要条件是 G中恰有两个奇点
),,( ji vveG?上增加一条边在的奇点，是证明：充分性：设 Gvv ji,
，得连通图 G?
中无奇点，则 G? CG 存在欧拉回路所以?
，中的边去掉 eC 为终点的欧拉道路为起点即得以 ji vv,
LvvG ji 为终点的欧拉道路为起点有一条以必要性：设,
),,( ji vveG?上增加一条边在
CGLe 的一条欧拉回路中得加到把边?为欧拉图，即 G?
Gvvd,)( 为偶数为奇数)(),(,ji vdvd中，在 G
一笔画问题：
1、一个连通图的顶点都是偶点，没有奇点，则该图可以一笔画出
2、一个连通图的顶点恰有两个奇点，其余均为偶点，
则从任一奇点出发，可以一笔画出该图，而终点则是另一个奇点。
（从任一点出发均可）
3、一个连通图的顶点有两个以上的奇点，则该图不能一笔画出田日中 白回 不连通可一笔画 可一笔画 不可一笔画可一笔画 可一笔画 不可一笔画 不可一笔画二,中国邮路问题提出问题的人：管梅谷教授时间,1962年提出的问题：
一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？
邮路问题的图论描述：
取一无向赋权连通图 G=（ V,E）
E中的每一条边对应一条街道每条边的非负权 l(e)=街道的长度
V中某一个顶点为邮局，其余为街道的交叉点在 G上找一个圈，
该圈过每边至少一次，且圈上所有边的权和最小
1、若 G中的顶点均为偶点,即 G中存在欧拉回路，
则该回路过每条边一次且仅一次，
此回路即为所求的投递路线邮路问题的图论描述：
在无向连通赋权 G =（ V,E）上找一个圈，
该圈过每边至少一次，且圈上所有边的权和最小
2,G中有奇点,不存在欧拉回路投递路线：至少有一街道要重复走一次或多次为邮局为邮路图，其中例：设 1vG
不是欧拉图为奇数 Gvdvd,)(),( 43?
不存在欧拉回路，G?
即不存在每条街道走一次且只走一次的投递路线
14253214563211 vvvvvvvvvvvvvC,路线 12?权和
1232563542412 vvvvvvvvvvvvC,路线 11?权和
12 CC 优于路线路线分析：
），），（，），（，重复走过边：（路线 4132211 vvvvvvC
），），（，重复走过边：（路线 32422 vvvvC
重复边
2?重复边的权和结论：
选择最佳投递路线 =选择重复边的权和最小的路线
3?重复边的权和
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
14253214563211 vvvvvvvvvvvvvC,对路线
），），（，），（，重复边：（ 413221 vvvvvv
1G
为欧拉图,1G 的一条欧拉回路为且 11 GC
1232563542412 vvvvvvvvvvvvC,对路线
），），（，重复边：（ 3242 vvvv
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
2G
为欧拉图，2G 的一条欧拉回路为且 22 GC
欧拉图一条投递路线对应一个条欧拉回路且投递路线为该图的一反之，对邮路图 G，
的一条链到任取奇点 34 vv
3654,,,vvvv如：
对该链上的每一条边增加一条重复边
G?
为欧拉图G? 存在欧拉回路即 G?,
CG 对应一条投递路线即?
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
G
1v 2v 3v
4v 5v 6v
1 1
1
1
111
1
1
投递路线 欧拉图
1454256536321 vvvvvvvvvvvvvC,
结论,对任意一个含奇点的邮路图 G，由于奇点的个数为偶数个，把每两个配成一对，由于 G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线寻找最佳投递路线方法,
在原邮路图上增加一些重复边得一个欧拉图，，
在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线管梅谷 —— 奇偶点图上作业法奇偶点图上作业法,
例：求解右图所示的邮路问题第一步：确定一个初始可行方案方法,检查图 G中是否有奇点无奇点：,找出一条以 v1为起点的欧拉回路,该回路就是最佳投递路线有奇点：
图 G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，
在该条链上的每一条边增加一条重复边，得一个欧拉图 G1,由 G1所确定的欧拉回路即为一个可行方案
v2,v8,v4,v6G中有奇点：
取 v2到 v4的一条链,v2v1v6v7v8v9v4
取 v6到 v8的一条链,v6v1v2v3v4v9v8
)( 1为邮局v
G
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
G1
显然 G1不是最佳方案
G1是欧拉图，
第二步：调整可行方案，
使重复边权和下降重复边权和 =
若图中某条边有两条或多于两条的重复边同时去掉偶数条，
G2
使图中每一条边最多有一条重复边
G2的重复边权和 =
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
步骤 1、
可得到重复边权和较小的欧拉图
4
G2
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
51
21
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35G2是欧拉图，
重复边权和 =21
G2
4
2、使图中每个初等圈重复边的权和不大于该圈权和的一半
9个初等圈
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
G2
4
3
G3是欧拉图，
重复边权和 =17
G3
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
6（ 1） v1v2v5v6v1 16 √
7（ 2） v6v5v8v7v6 14 √
10（ 3） v2v3v4v5v2 24 √
4（ 4） v5v4v9v8v5 16 √
G3的初等圈 权和 重复边权和
13（ 5） v1v2v5v8v7v6v1 24 ×
G4
1v
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
G4
2v
3v
6v
4v?
5v?
2 4
3
4
6
9
5
7v
8v
9v
4
4
35
4
7（ 1） v1v2v5v6v1 16 √
4（ 2） v6v5v8v7v6 14 √
4（ 3） v2v3v4v5v2 24 √
8（ 4） v5v4v9v8v5 16 √
G4的初等圈 权和 重复边权和
11（ 5） v1v2v5v8v7v6v1 24
1v
√
（ 6） v2v3v4v9v8v5v2 32 4 √
（ 8） v6v5v4v9v8v7v6
（ 7） v1v2v3v4v5v6v1 28 11 √
22 4 √
（ 9） v1v2v3v4v9v8v7v6v1 36 7 √
G4是最佳方案最佳投递路线：
16785894561254321 vvvvvvvvvvvvvvvvv
奇偶点图上作业法,
第一步：确定一个初始可行方案方法,检查图 G中是否有奇点。
无奇点：,找出一条以 v0为起点的欧拉回路，该回路就是最佳投递路线有奇点：
图 G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边第二步：调整可行方案，使重复边权和下降
1、使图中每一条边最多有一条重复边若图中某条边有两条或多于两条的重复边，
同时去掉偶数条
2、使图中每个初等圈重复边的权和 ≤ 该圈权和的一半若图中某初等圈重复边的权和大于该圈权和的一半去掉圈中的重复边同时将圈中没有重复边的边加上重复边为邮局）线最短（路线行走才能使所行路问邮递员应按怎样的例：设有邮路图如下，
0v
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2?
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2
最佳投递路线,v0v3v0 V4v3v4 v5v3v2v5
1v
2v
3v
4v? 5v?
2
32 6
15
0
v 4 2 3
1
2
v1v2v1 v4v1v0
期末考试论文题目：
请用所学的运筹学方法解决一个你在工作、学习、
生活中所遇到的实际问题。（ 40分）
要求：
1、字数不少于 400字。
2、不能采用课堂、作业、教材上的原题。
（说明：若出现两篇完全相同的论文，每篇各得一半分）
