3
v6 3 0 3 0 3 0
v1 v2 v3 v4 v5 v6
矩阵表示 A 邻接矩阵 B 关联矩阵
子图
子生 图成
子 图
顶点数p 边数q
环
重 合
端点
简单图
G=(V,E)
边e=[u,v] 多重边
平行边
含
点的次
0 1 奇数 偶数
孤悬 奇 偶 立挂 点 点 点点
多重图 点边关系 各种链的概念
欧拉图与中国邮路问题
e5 V1
e1 V2
V5 e6 e7
e4 V4
e3
e2
V3
例2 某单位储存八种化学药品，其中某些 药品是不能存放在同一个库房里的。为了反映
这个情况可以用点V1,V2,……V8分别代表这八 种药品，若药品Vi和药品Vj是不能存放在同 一个库房的，则在Vi和Vj之间连一条线。

V• 2 • V1
•· V8
bi j
wi j 0
(vi , v j ) E (vi , v j ) E
例6.4 下图所表示的图可以构造权矩阵B如下:
v1 4
v2
36
72
v6 4
3
3
v3
5
2
v5
v4
v1 0 4 0 6 4 3 v2 4 0 2 7 0 0
B
v3
0
2
0
5
0
3
v4 6 7 5 0 2 0
v5
4
0
0
2
0
e6
e7
e8
点称作偶点，次为1的点称为悬挂点，
次为0的点称作孤立点。
v4
v5
图的次: 一个图的次等于各点的次之和。
定理1 任何图中，顶点次数之和等于所有边数的2倍。
证明：由于每条边必与两个顶点关联，在计算点的次时，每条边 均被计算了两次，所以顶点次数的总和等于边数的2倍。
定理2 任何图中，次为奇数的顶点必为偶数个。
V1 V2和E1 E2称G1是G2的一个子图。 v2
v3
若有 V1＝V2，E1 E2 ，则称G1是G2的一
e5
个部分图(支撑子图)。
e4
v1 e2 e4 e3
e6
e7
e8
v2
v3 v2
e5
v3 v4
v5
（G图）
e6
e8
e6
e7
e8
v4
(a)
v5
v4
(b)
v5
网络（赋权图）
赋权图）:权可以代表距离、费用、通过能力(容量)等等。 无向网络:端点无序的赋权图称为. 有向网络:端点有序的赋权图称为。
{v0 , e1 , v1 ,, ek , vk }
起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链，称这样的图为连通图，否则 称图不连通。
e1
e2
e4 v1e3
v2
v3
e5
e6
e7
e8
v4
v5
子图，部分图(支撑子图)
e1
图G1={V1、E1}和图G2={V2，E2}如果有
e2
e4 v1e3
欧拉图
哥尼斯堡七桥问题
哥尼斯堡（现名加里宁格勒）是欧洲一个城市， Pregei河把该城分成两部分，河中有两个小岛，十八世纪 时，河两边及小岛之间共有七座桥，当时人们提出这样 的问题：有没有办法从某处（如A）出发，经过各桥一次 且仅一次最后回到原地呢？
哥尼斯堡七桥问题
a
C
d
b
a
c
d
b (b)
定义1. 在连通无向图G中,若存在经过每条边恰好一次的一个
证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：
d(v) d(v) d(v) 2m
vV1
vV2
vV
2m为偶数，且偶点的次之和 d(v) 也为偶数，所以 d(v) 必为偶
数，即奇数点的个数必为偶数vV。2
vV1
链，圈，连通图
图中某些点和边的交替序列，若其 中各边互不相同，且对任意vi,t-1和 vit均相邻称为链。用μ表示：
e1
若有边e可表示为e=[vi,vj]，称vi和vj
是边e的端点，反之称边e为点vi或vj 的关联边。若点vi、vj与同一条边关
v2
e2
e4 v1e3
v3
e5
联，称点vi和vj相邻；若边ei和ej具 有公共的端点，称边ei和ej相邻。
e6
e7
e8
v4
v5
环, 多重边, 简单图
e1
如果边e的两个端点相重，称该边为 环。如右图中边e1为环。如果两个点 v2 之间多于一条，称为多重边，如右图
第一节 图的基本概念与模型
近代图论的历史可追溯到18世纪的七桥问题—穿过 Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不 可能存在这样的路线。
Königsberg桥对应的图
一、图基本概念
例1、有甲、乙、丙、丁、戊五个球队， 它们之间比赛的情况也可以用图表示出来。
v1 4
v2
36
v6 4
3 2
v5
72 3
5
v4
v1 v2 v3 v4 v5 v6
v3
v1 0 1 0 1 1 1
v2 1 0 1 1 0 0
A66
v3 v4
0 1
1 1
0 1
1 0
0 1
1 0
v5
1
0
0
1
0
1
v6 1 0 1 0 1 0
2. 权矩阵
对于赋权图G=(V,E), 其中边 (vi , v j )有权 wi j , 构造矩阵B=(bij) nn 其中：
②
15
9
7 ④ 14
⑤
①
10
6
19
20
⑥
③
25
图的矩阵描述： 邻接矩阵、关联矩阵、权矩阵等。
1. 邻接矩阵 对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵
A=(aij) nn，其中
1
aij
0
当
且
仅
档v
i
与v
之
j
间
有
关
联
边
时
其它
图的基本概念与模型
例6.2 下图所表示的图可以构造邻接矩阵A如下
图的表示方法：
G {V , E}
运筹学中研究的图具有下列特征:
强调点与点之间的关联关系，不讲究图的比例大 小与形状； 每条边上赋有一个权； 建立网络模型，求最大值或最小值。
下图可以提出很多极值问题
2 1
7 2
4
6
8
6
3
7
3
3
1
6
1
3
6
4
5
6 7
二、关于图的另外一些名称和术语：
端点,关联边,相邻
•V3 • V4
• V5
• V6 • V7
一般地，当用图论研究一个实际问题时， 常以顶点（Vertex）表示要研究的对象，以 它们之间的连线，表示某种关系，这种连线 称为边（Edge），目的是为了解决某个极值 问题。图中的点用v表示，边用e表示。对每 条边可用它所连接的点表示， 记作：e1=[v1,v1]; e2=[v1,v2];
e2
e4 v1e3
v3
e5
中的e4和e5，对无环、无多重边的图
e6
e7
e8
称作简单图。
v4
v5
次，奇点，偶点，孤立点
e1
与某一个点vi相关联的边的数目称为
e2
e4 v1e3
点vi的次（也叫做度），记作d(vi)。 v2
v3
右图中d(v1)＝４,d(v3)=5,d(v5)=1。次
e5
为奇数的点称作奇点，次为偶数的