为方便起见，常将无序对{a,b}记为(a,b)
定义1.1 一个无向图是一个有序的二元组<V,E>，
记为G，其中
（1）Ｖ≠称为结点集，元素称为结点或顶点；
第 （2）Ｅ称为边集，它是无序积V&V的多重子集，
七 其元素称为无向边，简称为边。
章
图
常把无向图记为G=<V,E>
论
12/22/2019 9:31 PM
5
离 例1、G1=<V,E>
散 数
V＝{v0, v1, v2,v3}
学 E＝{(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2，v3)}
v0
v3
v1
第
七
章
v2
图
论
12/22/2019 9:31 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
平行边
章
简单图
多重图
（ 图
论
不含平行边也不含环） 12/22/2019 9:31 PM7Βιβλιοθήκη 离 散 数 学旧金山
丹佛
洛杉矶
第 七 章
图
论
12/22/2019 9:31 PM
底特律
芝加哥
纽约 华盛顿
散 数
解： K4的所有非同构的生成子图如下图所示。
学
第 七 章
图
论
12/22/2019 9:31 PM
33
离
二、路与回路
散
数 定义2.1 设Ｇ为无向标定图，G中结点与边 学 的 交 替 序 列 =vi0ej1vi1ej2…ejlvil 称 为 vi0 到
vil的路。vi0，vil分别称为的始点和终点， 中边的条数称为它的长度。
怎样定义有向图的同构？
第 七 章
图
论
12/22/2019 9:31 PM
28
离
散 例7、
数 学
a
d
第 七 章
图
论
12/22/2019 9:31 PM
b

c
c' (a)
a' (b) d' (d)
b' (c)
29
离
散
数
学
1
2
6
10
7
9 8
2
5
3
第
3
4
七 章
彼得松图(petersen)
图
论
12/22/2019 9:31 PM
离
散 数 学
一个具n有=410个顶点，每 个结点m的=度45 都为6的图，
v1
有多少顶结条点边度？之和为810
e5
e1
e3 e4
v2 e2
v3
v4
定理1.1 设G=<V，E>为无向图， |V(G)|= n， |E(G)|=m，则
n
握手定理 deg(vi) 2m
第
i 1
即使出现多重边和环，这
W（G）=2
39
离 设G=<V,E>为无向图
散 数
(1)设eE，用G-e表示从G中去掉边e，称为删
c
d
G″´
d
G″
27
离 定义1.8 设G1=<V1,E1>,G2= <V2,E2>为两个无向
散 数
图，若存在一一映射
学
g： V1 V2
对于vi,vjV1，
(vi,vj)E1 当且仅当 (g(vi),g(vj))E2,
并且(vi,vj)与(g(vi),g(vj))的重数相同，
则称G1与G2是同构的，记作G1 G2
华盛顿
11
离
散 数
e0
学
v1
v5
v3
孤立点
标定图
非标定图
e1 e3
v2
在无向图G=<V,E>中，若ek= （vi，vj） ∈Ｅ，则称vi，vj 为
e2 边ek的端点,
e4
ek与vi或ek与vj是彼此关联的；
(v3e，5 v4) v4
关联次数 邻接点、邻接边
第 七 章
图
论
12/22/2019 9:31 PM
七 章
边，构成一个无向重图，问题化为图论中简单道路
的问题。
图
论
12/22/2019 9:31 PM
3
离 一、图的基本概念
散 数 学
旧金山
丹佛
洛杉矶
第 七 章
图
论
12/22/2019 9:31 PM
底特律
芝加哥
纽约 华盛顿
4
离
散 设A、B是两个集合，称
数
学
A&B={{a,b}|aA, bB}
为A与B的无序积。
35
有向图中，路、回路等概念与无向图类似
离
散
b
数
学
e1
e4
a
e2
d
e5 e3
c
（ｅ ，ｅ ，ｅ ，ｅ ，ｅ ）是迹，不是通路，因
5
1
2
3
4
第 为（ｃ，ａ，ｂ，ｃ，ｄ，ｂ）中ｂ，ｃ均出现了
七 章
两次。（c，d，b，c）是圈。
图
论
12/22/2019 9:31 PM
36
离
散
数 学
定理2.1 在n阶图中，若从结点vi到vj（vivj） 存在一条路，则从vi到vj存在长度不大于n-1的路。
a e
b c 图G d
a
b e
c d
图 G3
23
离 散 数 学
k4
G
第 七 章
图
论
12/22/2019 9:31 PM
G
24
离 定义1.6 设G=<V,E>，G’= <V’,E’>为两个图，
散 数
若V’ V且E’ E，则称Ｇ’为Ｇ的子图，G为
学 G’的母图，记作Ｇ’Ｇ；
又若V’V或E’ E，则称Ｇ’为Ｇ的真子图。
第
任意一个连通无向图的任两个不同结
七 点都存在一条通路。
章
图
论
12/22/2019 9:31 PM
38
离
非连通图Ｇ可分为几个不相连通的子图，
散 每一子图本身都是连通的。称这几个子图为
数 学
Ｇ的连通分支,G的连通分支数记为W（G）。
k4
B A
第
七
W（G）=1
章
图
论
12/22/2019 9:31 PM
viV1
viV2
偶数
e1 v1
偶数 v2
偶数
第 七 章
e3
e2
e4
因此|V2 |为偶数
图
v3
v4
论
12/22/2019 9:31 PM
18
离 例4、已知无向图G中结点数n与边数m相等，2度
散 数 学
结点与3度结点各2个，其余结点的度数均为1，试 求G的边数m。
解：由握手定理
n
2m deg(vi) =22+ 32+ 1(n-4)
推论 在n阶图中，若从结点vi到vj（vivj）存在一 条路，则从vi到vj存在长度小于n的通路。
第 七 章
图
论
12/22/2019 9:31 PM
37
离
散 数
定义2.2
设无向图Ｇ＝<Ｖ，Ｅ>， u,vＶ，若
学 u,v之间存在路，则称u,v是连通的，记作uv 。
定义2.3 设无向图Ｇ是平凡图或G中任何两个结 点都是连通的，则称G为连通图，否则称G为非连 通图或分离图。
1
5
6
10 7 8
9
4
30
离 散 数 学

第 七 章
图
论
12/22/2019 9:31 PM
31
离 散 数 学
两个图同构必有： （1）结点数相同；
但不是充分条件
（满足这三个条件的两图 不一定同构）
第 （2）边数相同；
七
章 （3）度数列相同
图
论
12/22/2019 9:31 PM
32
离 例8、 画出K4的所有非同构的生成子图。
v3
章 图
degv+3 (v1)=3
degv+4(v2)= deg+(v4)=1 dve2g+(v3)=0
论 ddeegg-1((2vv/2112/))2==019dd9e:3eg1gP(M-v(4v)2=)=2ddeegg-((vv42))==1deg(dve3g)=-(3v3)=2
14
离 散 数
学
定义1.5 设Ｇ＝<Ｖ，Ｅ>为n阶无向简单图， 以V为结点集，以所有使G成为完全图Kn的添加 边组成的集合为边集的图，称为Ｇ的相对于完 全图的补图，记作 G
第
七
章
图
k4
G
论
12/22/2019 9:31 PM
G
22
离
图 K5 a
散
数
学
b
e
c
d
a
b
e
第
七
c
d
章
图 G1
图
论
12/22/2019 9:31 PM