记为G，其中
（1）Ｖ≠称为结点集，元素称为结点或顶点；
第 七 章
（2）Ｅ称为边集，它是无序积 V&V 的多重子集，
其元素称为无向边，简称为边。 常把无向图记为G=<V,E>
1/17/2019 1:11 PM 5
图 论
离 散 数 学
例1、G1=<V,E> V＝{v0, v1, v2,v3} E＝{(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2，v3)}
|E(D)|=m，则
deg
第 七 章
n
(vi ) m
n i
i 1
deg
i 1
n
(vi ) m
图 论
deg(v ) 2m
第 七 章
deg(v ) 2m
i i 1
n
即使出现多重边和环，这 个式子仍然成立
图 论
1/17/2019 1:11 PM
16
离 散 数 学
n=4 m=5 结点入度之和为5 结点出度之和为5 e5
v1 e1
v4
e3
e4
e2
v3
v2
定理1.2 设D=<V，E>为有向图， |V(D)|= n，
13
离 散 数 学
定义1.3 在图G=<Ｖ，Ｅ>中，与结点v（vV）关联的 边数称为结点v的度数，简称度，记为deg(v)。 (结点上的环关联次数为2)
设D=<Ｖ，Ｅ>为有向图，以结点v（vV）作为始 点的边数称为v的出度，记作deg+(v)；以v作为终 点的边数称为v的入度，记作deg-(v) 称deg+(v)+deg-(v)为v的度数，记作deg(v)
1 2 4 3
14
离 散 数 学
有向图中，所有结点的入度之和等于所有结点的出 度之和。
最大度 在无向图G中， 令△(G)=max{deg(v)|vV(G)} (G)=min{deg(v)|vV(G)} 最小度
第 七 章
类似可定义有向图的最大出度和最小出度、最大入 度和最小入度。
图 论
1/17/2019 1:11 PM
多重图
7
（不含平行边也不含环） 1/17/2019 1:11 PM
离 散 数 学
底特律 旧金山 纽约 芝加哥 华盛顿 洛杉矶
丹佛
第 七 章
图 论
1/17/2019 1:11 PM
8
离 散 数 学
定义1.2 一个有向图是一个有序的二元组<V,E>，记 为D，其中 （1）Ｖ同无向图； （2）Ｅ称为边集，它是笛卡尔积V×V的多重子集， 其元素称为有向边，简称为边。 v0 D=<V,E> V＝{v0, v1, v2}， E＝{<v0,v1>, <v1,v0>, <v1，v2>}
v1 e1 v2 e2 e4 e5 v1 e1 e4 v4 e3
e3
e2
v3
第 七 章
e5
v2 v v + + + deg 3 (v1)=3 deg 4 (v2)= deg (v4)=1 deg+(v3)=0 图 deg(v deg(v )=deg(v 论 deg -1/17/2019 -(v 2 -(v )=2 4)=2 3)=3 PM-(v (v1)=deg(v )=1:11 deg )=deg )=1 deg
e5 (v3，v4)
关联次数
邻接点、邻接边
图 论
1/17/2019 1:11 PM
12
离 散 数 学
在有向图D=<V,E>中，若ek=<vi，vj> ∈Ｅ，则称vi 为ek 的起点， vj 为ek的终点 ；并称vi邻接到vj ， vj 邻接于vi 。
v1
v2
v3
第 七 章
v4
图 论
1/17/2019 1:11 PM
v0 v3
第 七 章
v1 v2
图 论
1/17/2019 1:11 PM
G1
6
离 散 数 学
例2 、 G2=<V,E> V＝{v0, v1, v2,v3} E＝{(v0,v3),(v1,v3),(v1,v3),(v2，v3),(v0,v0)}
环 v0 v1
第 七 章
G 简单图
v3
v2 G2
平行边
图 论
第七章
图 论
离 散 数 学
图论的起源
Konigsberg(哥尼斯堡)七桥问题
A
C
D
B
第 七 章
问题：能否从河岸或小岛出发，不重复地经过所 有的桥回到原地。
图 论
1/17/2019 1:11 PM
2
离 散 数 学
Euler (欧拉) 1736年对这个问题给出了否定的回答。
A
C
D
B
第 七 章
图 论
Euler将河岸和小岛作为图的结点，七座桥为 边，构成一个无向重图，问题化为图论中简单道路 的问题。
空图 ——V(G)=
丹佛 洛杉矶
图 论
1/17/2019 1:11 PM
11
标定图
离 散 数 学
e0
非标定图
e1
e3
v1
v5 v3
在无向图G=<V,E>中，若ek= v2 （vi，vj） ∈Ｅ，则称vi，vj 为 e2 边ek的端点,
e4
ek与vi或ek与vj是彼此关联的；
v4
孤立点
第 七 章
平行边
1/17/2019 1:11 PM 10
有时用G泛指图（有向的或无向的）
离 散 数 学
|V(G)|表示G的结点数
|E(G)|表示G的边数
有限图—— |V(G)|和 |E(G)|均有限
n阶图——|V(G)|=n
零图—— E(G)=
旧金山 平凡图——1阶零图
第 七 章
底特律 纽约 芝加哥 华盛顿
1/17/2019 1:11 PM 3
离 散 数 学
一、图的基本概念
底特律 旧金山 纽约 芝加哥 华盛顿 洛杉矶
丹佛
第 七 章
图 论
1/17/2019 1:11 PM
4
离 散 数 学
设A、B是两个集合，称
A&B={{a,b}|aA, bB} 为A与B的无序积。 为方便起见，常将无序对{a,b}记为(a,b) 定义 1.1 一个无向图是一个有序的二元组 <V,E> ，
v1
第 七 章
v2
D
1/17/2019 1:11 PM 9
图 论
离 散 数 学
例3、 D=<V,E>, 其中 V={v1，v2 ，v3 ，v4 } E={<v1,v1>,<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>, <v3,v4>,<v2,v1>}
v1 v2
第 七 章
v3
v4
图 论
15
离 散 数 学
对图的所有顶点的度求和时，得出了什么？
n=4 一个具有 10个顶点，每
顶点度之和为10 结点度之和为 8
个结点的度都为 6的图， m=4 m=5 e5 有多少条边？
v3
v1
ቤተ መጻሕፍቲ ባይዱ
e1
e3
v2 e2
e4 v4
定理1.1 设G=<V，E>为无向图， |V(G)|= n， |E(G)|=m，则 握手定理