5
e1

e6
v5
d (v1 ) 3, d (v2 ) 1, d (v3 ) 4 d (v4 ) 3, d (v5 ) 0, d (v6 ) 1,
v 2、v6为悬挂点， 2、e5为悬挂边， e v5为孤立点， v v1、v 2、v 4、v6为奇点，5、v3为偶点
v2

v6
e4
v 4
ቤተ መጻሕፍቲ ባይዱ
d (vi )为偶数 ，即 vi 为偶点
充分性： 若无向连通图G=(V,E)中无奇点，则G为欧拉图
d 例： G连通， (vi )为偶数
v1 e1
e8 e7 e5
v6
e6

v2
e2

5 v
e10
e9
e4
v4
v3 e
3
G
任取一点，如 v3， 找一个以 v3为起点的一个简单回路 C1
简单回路 C1： 3 , e3 , v4 , e9 , v 2 , e2 , v3 } {v
iV2
d (v )为偶数
i 1 V i
而V1是奇点的集合, d (vi )(i V1 )均为奇数
只有偶数个奇数相加才能得到偶数
所以 V1中的点，即奇点的个数 为偶数
四、链： 对无向图 G V，E） （
（ 1、链的定义： 在图 G V，E）中，一个点与边的交 错序列 {vi 0 , ei1 , vi1 , ei 2 , vik 2 , eik 1 , vik 1 , eik , vik }, 且eit (vit 1 , vit )(t 1,2, k ), 则称这个点边序列为 连接 vi 0与vik的一条链 , 简记为 {vi 0 , vi1 ,，vik 2 , vik 1 , vik }
{v5 , e4 , v4 , e9 , v2 , e2 , v3 , e3 , v4 , e8 , v1},
链 开链 : 链中的起点与终点不同
闭链 : 链中的起点与终点重合
圈或回路 道路
简单圈 在圈中，所含的边均不相同 初等圈 在圈 中，除起点和终点重合 外，
没有相同的顶点和相同 的边
六、赋权图（网络）
对图G=（V，E），
e的权
若对每一条边e，都有一个实数w(e)与之对应， 则称图G=（V，E）为赋权图 ，或网络 权w(e)通常表示距离、费用、容量等 如公路交通图： Vi表示 城市， i表示公路 e w(ei）表示公路ei的长度
e2
v1
v6
e6 e5

e1
e8

v2
e3

e7
e9

e2
v2
3
5 v
e6
e4
e3
v3
e4
v4
v 3 v 3 e
e2
v1
e1 e3

v2
v 4
存在v2到v4的 一条欧拉道路：
存在 v3到v4的 一条欧拉道路：
任两点之间都不 存在条欧拉道路
{v2 , e1 , v1 , e5 , v4 , e3 , v3 , e2 , v2 , e6 , v5 , e4 , v4 }
2、相邻点和相邻边：
一条边的两个端点称为 相邻点，简称邻点， 端点落在同一个顶点的 边称为相邻边，简称邻 边 e1 1 3、多重边与环： 具有相同端点的边称为 多重边或平行边； e2 两个端点落在同一个顶 点的边称为环。
v1
e3
e6
4、多重图和简单图：
v2

含有多重边的图称为多 重图； 无环也无多重边的图称 为简单图。
对vi V
vi 每出现一次，必关联两 条边 若vi 是C的中间点， 如C： 1 , e1 , v2 , e2 , v3 , vi 1 , ei 1 , vi , ei , vi 1 ,, v1 } {v ，即 vi 为偶点 d (vi )为偶数
vi 若vi 是C的起点，也是C的终点，必关联两条边 vi
v1
vs
4 3 4

4
2
v4
7 2

2
6

v2
2

5 3
v5

vt
1
1

最大 流问 题
v3
v 6
5.1 基本概念
一、图的概念
图 ------由若干个点和连接这些点的某些连 线所组成的图形 代表具 代表事物 体事物 G——一个图 之间的联 vi——图中的点，称为顶点。 系 v3 ,v5 ei——图中的连线，称为边。ek vi , v j v3 e1 e e 6 v5 记V={vi}，E= {ei}, 2 v1 e e 3 e5 G=（V，E） v4 4 v 2 m(G)=|E|——G的边数，简记为m G 简记为n n(G)= |V|——G的顶点数， m=6, n=5

1
4 2
1

v0
1 3

4 4

1

5
4 5
3


5
1
2
1 2

v0
1

1

3

2
2
2

3、选址问题 已知一个地区的交通网络如下图所示，其中点代表 居民小区，边表示公路，问区中心医院应建在哪个 小区，可使离医院最远的小区居民就诊时所走的路 程最近？ v5 即求图的中心
v3
v6
e6 e5
v1 e1
e8 e7

v2
e2

5 v
e10
e9
e4
v4
v3 e
3
e6
v1 e1
e8 e7

v2

e7
v1
e8
v 6
e5
5 v
e10
e4
G
把C3从C 2的v1点处插入 C 2，得一简单回路 C，
G
v4
5 v
G
e4
v4
C： 2 , e10 , v5 , e5 , v6 , e6 , v1, e7 , v5 , e4 , v4 , e8 , v1 , e1 , v 2 } {v
e3
v3 v 6
5 v
e10
e4
G
v4
5 v
G
e4
v4
简单回路 C1： 3 , e3 , v4 , e9 , v 2 , e2 , v3 } {v 简单回路 C 2： 2 , e10 , v5 , e5 , v6 , e6 , v1 , e1 , v2 } {v
简单回路 C3： 1 , e7 , v5 , e4 , v 4 , e8 , v1 } {v
e6
v2

e4
e5
v 4
v3
v3
e4=（ v3， v4） ≠（ v4， v3） e5=（ v4， v3）≠（ v3， v4）
e4=（ v3， v4） v4， v3） =（ e5=（ v3， v4） =（ v4， v3）
二、常用名词： 1、端点和关联边：
若ek vi , v j E , 则称点 vi、v j 是边 ek的端点， 边ek 是点 vi 和v j的关联边
简单链：在链中，所含的边均不相同 初等链：在链 中，所含的顶点、边均 不相同
v1
v6
e6 e5

e1
e8

v2
e2

e7
e9
5 v
e4
v4
e3
v3
{v6 , e5 , v5 , e7 , v1 }
初等 链
不是链
{v6 , e7 , v1 , e8 , v4 }
简单链
连接 v5与v1的一条链
有向图 ——边e=（vi, vj）有方向 vi为始点，vj为终点 图 此时（vi, vj）≠ （vj,vi） 无向图 ——边e=（vi, vj）无方向
此时（vi, vj）= （vj, vi）
e1
有 向 图
e1
e2
v1
e3
e6
v2

e4
e5
v 4
e2
v1
e3
无 向 图
{v3 , e3 , v4 , e2 , v2 , e1 , v1 , e4 , v4 }
欧拉回路：
v1
欧拉图
圈
设G是一个无向连通图，若 存在一个回路，经过 G中的 每一条边一次且仅一次 ，则称这个回路为欧拉 回路

e1
e6 e5

v2
e2
存在欧拉回路：
{v1 , e1 , v2 , e2 , v3 , e3 , v4 , e7 , v2 , e5 , v5 , e4 , v4 , e6 , v1}
记G G C1 V ，E ），E E E1，V 是E 中边的端点 （ 在G 中，以 G 与C1的公共顶点 v2为起点取一个简单回路 C 2
简单回路 C 2： 2 , e10 , v5 , e5 , v6 , e6 , v1 , e1 , v2 } {v
记G G C2 V ，E ），E E E1，V 是E 中边的端点 （
{v1 , e8 , v4 , e9 , v2 , e2 , v3 }为一条道路
初等圈
五、连通图：图G中任意两点之间至少有 一条链相连 .
v1
v6
e6 e5

e1
e8

v2
e2
v1
e3
e1

e7
e9
5 v
e4
v4