G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,1
Chapter 7 Graphs
图 论图 /Graph：
可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便解决具体问题 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,2
7.1 图的概念 /Introduction of Graph
7.2 图的术语 /Graph Terminology
7.3 图的表示与同构 /
Representing Graph and Graph Isomorphism
7.4 连通性 /Connectivity
7.5 欧拉道路与哈密尔顿道路 /
Euler and Hamilton Paths
7.6 最短道路问题 /Shortest Path Problem
7.7 平面图 /Planar Graphs
7.8 图的着色 /Graph Coloring
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,3
7.1 图的概念 /Introduction of Graph
[定义 ]图
Ｖ是一个非空有限集,Ｅ是Ｖ上的一个二元关系,有序对 （ Ｖ,Ｅ ） 称为 有向图 /Directed
Graph。
若将 E中的有序对看成是无序的 （ 即将 e=(a,b)
看成 e={a,b}）,则称 （ Ｖ,Ｅ ） 为 无向图
/Undirected Graph。 有向图和无向图统称为 图
/Graph,记为 G 。
G = （ Ｖ,Ｅ ）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,4
[定义 ]顶点：
Ｖ中的元素称为 顶点,用带标记的点表示，也称为 结点 /Vertices。
[定义 ]边：
在有向图 G中,若 e=（ ａ,ｂ ） ∈ Ｅ,e称为 G的有向边 /directed edge。 用由ａ到ｂ带箭头的线把
ａ和ｂ连起来；
在无向图 G中,若 e=（ ａ,ｂ ） ∈ Ｅ,e称为 G的无向边 /undirected edge 。 a,ｂ间用连线连结,
有向边和无向边统称为 G的 边 /edge。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,5
[定义 ]图的分类对图 G=（ Ｖ,Ｅ ） 。 若对于任意的 （ ａ,ｂ ）
∈ Ｅ,a? b,则称图 G为简单图 /Simple Graph。
对图 G=（ Ｖ,Ｅ ） 。 若允许Ｅ是一个重集,则称图 G为重图 /Multigraph。 其相同的元素称为 重边 。
对图 G=（ Ｖ,Ｅ ） 。 若 G既允许是重图又允许是非简单图,则称图 G为拟图 /Pseudograph。
一般的 G称为 线性图 /Linear Graph。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,6
7.2 图的术语 /Graph Terminology
[定义 ]相邻和关联：
在无向图 G中，若 e=（ａ，ｂ） ∈ Ｅ，则 称 ａ
与 b相邻 /adjacent，或边 e关联 a、ｂ /incident或 联结
a,b/connect。 a,b称为边 e的 端点或结束顶点
/endpoint.
在有向图 G中，若 e=（ａ，ｂ） ∈ Ｅ，即箭头由
ａ到ｂ，称 ａ相邻到ｂ,或 a关联 或 联结 b。 a称为 e
的 起点 /initial vertex,b称为 e的 终点 /terminal or
end vertex。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,7
[定义 ]自回路：
若（ａ，ａ） ∈ Ｅ，（ {ａ，ａ }∈ Ｅ），
称边（ａ，ａ）（ {ａ，ａ }）是 自回路 /loop。
[定义 ]孤立顶点：
若ａ ∈ Ｖ，ａ不与其他顶点相邻，称
ａ为 孤立顶点 /isolated。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,8
[定义 ]顶点的次：
在无向图 G中，与 a相邻的顶点的数目称为 a的次或度 /degree。 记为 deg(a)或 d(a)。
在有向图 G中，以 a为终点的边的条数称为 a的 入次或入度 /in-degree。记为 deg–(a)或 d
–(a)。以 a为起点的边的条数称为 a的 出次或出度 /out-degree。记为 deg+(a)或 d +(a)。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,9
[定理 1 (Handshaking)] 设无向图 G=
（ V,E）有 e条边，则 G中所有顶点的次之和等于 e的两倍。
证明思路：利用数学归纳法。
[定理 2] 无向图中次为奇数的顶点个数恰有偶数个。
证明思路：将图中顶点的次分类，再利用定理 1。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,10
[定理 3] 设有向图 G=（ V,E）有 e条边，
则 G中所有顶点的入次之和等于所有顶点的出次之和，也等于 e。
证明思路：利用数学归纳法。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,11
有向图与无向图的对应：
无向图对应有向图：加上箭头。
有向图对应无向图：去掉箭头。
称为 underlying undirected graph
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,12
一些特殊的简单无向图：
（ 1） Complete Graphs/完全图 Kn
（ 2） Cycles/环图 Cn
（ 3） Wheels/轮图 Wn
（ 4） n-Cubes/n-立方图 Qn
（ 5） Bipartite Graphs/二分图 Kn,m
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,13
[定理 4] 设无向完全图 G有 n个顶点，则
G有 n(n-1)/2条边。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,14
一些特殊的其他图：
（ 1）有向完全图
（ 2）零图
（ 3）平凡图
（ 4） 正则图：若图Ｇ＝（Ｖ，Ｅ）中每个顶点的次均为 n，称此图Ｇ是 n-正则的 /n-
regular。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,15
计算机处理和网络应用特殊图表示：
（ 1） 串行处理 /Serial
linear array network
（ 2） 并行处理 /Parallel
Kn,Star,Cn,Wn
2-dimensional array network
hypercube network
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,16
[定义 ]子图：
Ｇ＝ （ Ｖ,Ｅ ） 是图,若Ｇ ’ ＝ （ Ｖ ’,
Ε ’） 也是图且满足：
(1)Ｖ ’?Ｖ； (2)Ｅ ’?Ｅ；
则称Ｇ ’ 为Ｇ的 子图 /subgraph。
注：
当Ｖ ’ ＝Ｖ时,称Ｇ ’ 为Ｇ的生成子图 。
当Ｅ ’ ≠Ｅ时,或Ｖ ’ ≠Ｖ时称Ｇ ’ 为Ｇ的真子图 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,17
[定义 ]补图：
关于完全图的子图的补图称为此子图的 绝对补图,若子图记为Ｇ，则补图记为 。G
[定义 ]补 图 /complementary graph,
Ｇ＝ （ Ｖ,Ｅ ） 是图,Ｇ ’ ＝ （ Ｖ ’,
Ε ’） 是Ｇ的子图,Ｅ,＝Ｅ－Ｅ ’,Ｖ,
＝ V－ V’或是Ｅ,中边所关联的所有顶点集合,则Ｇ,＝ （ Ｖ,,Ｅ,） 称为 Ｇ ’
关于Ｇ的 相对补图 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,18
a
e
dc
b
e
d
c
b
a
图 A 图 B
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,19
d
b
a
e
c
e
dc
b
图 C 图 D
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,20
a
e
d
c
b
d
b
图 E 图 F
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,21
图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｂ的边［ａ，ｂ］是孤立边图Ｄ是图Ｃ的子图图Ｆ是图Ｄ关于图Ｃ的余图图Ｅ是图Ｃ的补图
（Ａ是完全图,Ｃ是Ａ的子图 )
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,22
说明：
图Ｃ不是Ｅ的补图。（不互为补图）
因为：
Ｅ,＝Ｅ－Ｅ ’
＝ {[b,c],[b,d],[b,e],
[c,d],[c,e],[d,e]}
Ｖ,＝ {b,c,d,e}
而图 C多了顶点 a。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,23
[定义 ]子图：
Ｇ＝ （ Ｖ,Ｅ ） 和Ｇ ’ ＝ （ Ｖ ’,Ε ’）
是两个简单无向图,它们的并图Ｇ?Ｇ ’ 定义为
Ｇ?Ｇ ’ =（ Ｖ ’?Ｖ,Ｅ ’?Ｅ ）
称Ｇ?Ｇ ’ 为 Ｇ 和 Ｇ ’ 的并图 /union ofＧ 和
Ｇ ’,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,24
7.3图的表示与同构 /
Representing Graph and Graph Isomorphism
图 G表示的三种方法：
（ 1）集合表示
（ 2）邻接表（ adjacency list）表示
（ 3）矩阵（ matrix）表示
1、邻接矩阵（ adjacency matrix）表示
2、关联矩阵（ incidence matrix）表示
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,25
[ 定义 ] 邻接矩阵,
设有向图Ｇ＝（Ｖ，Ｅ），Ｖ＝｛Ｖ 1,Ｖ 2,…，
Ｖ n ｝，若用方阵
nnij
aA
)(
EVV
EVV
a
ji
ji
ij
),(0
),(1
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,26
[ 定义 ] 图的同构,
图Ｇ 1 ＝（Ｖ 1,Ｅ 1 ），Ｇ 2 ＝（Ｖ 2,Ｅ 2 ），
如果能建立Ｖ 1 与Ｖ 2 间的一一对应，在此对应下，Ｅ 1 与Ｅ 2 中的边也一一对应，对有向图还保持关联方向的对应，则称图Ｇ 1 与
Ｇ 2 同构，记作Ｇ 1? Ｇ 2 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,27
a
d
c
b
无向图
b' (c )
a' (b)
c' (a )
d'
例：
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,28
从图中不容易直接得出。
可用邻接矩阵，通过某种算法确定两个图是否同构。
上例的邻接矩阵：
0100
0011
1000
1010
0011
1001
0100
0010
i ii
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,29
同构判定算法（用邻接矩阵）
1、根据图确定其邻接矩阵（ I)
2、计算行次：矩阵每行１的个数，（对应于出次） 和列次：（对应于入次）
3、不考虑出现的次序不同，若行次与列次不同，
则必不同构，否则继续
4、同时交换其一矩阵的ｉ行和ｊ行，ｉ列和ｊ列。
若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,30
例,把 (II）的第１行与第４行交换，
第１列与第４列交换，得,
0010
1001
0100
1010
例,(1)的行次 （ ２,１,２,１ ）
列次 （ １,２,１,２ ）
(2)的行次 （ １,１,２,２ ）
列次 （ ２,２,１,１ ）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,31
再把第２行与第４行交换，第２列与第４列交换，就得,
0010
1001
1000
1010
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,32
小 结
1、图的概念与术语
2、一些特殊的图：极端情况、有用情况
2、图的表示：集合、表、矩阵
3、图的关系：图的转换、图的包含、
图的运算、图的同构
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,33
进一步的思考
1、图中内容的进一步组合
2,图的计算机表示与运算处理说明：（ 1）若从（ I)?(II),如何处理？
（ 2）算法的复杂度,n！,NP完全问题。
（对稍多一些顶点的图，难以计算机实现。）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,34
练 习
pp.443 11
pp.454 17,20,27,33
pp.463 43,51
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,1
Chapter 7 Graphs
图 论图 /Graph：
可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便解决具体问题 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,2
7.1 图的概念 /Introduction of Graph
7.2 图的术语 /Graph Terminology
7.3 图的表示与同构 /
Representing Graph and Graph Isomorphism
7.4 连通性 /Connectivity
7.5 欧拉道路与哈密尔顿道路 /
Euler and Hamilton Paths
7.6 最短道路问题 /Shortest Path Problem
7.7 平面图 /Planar Graphs
7.8 图的着色 /Graph Coloring
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,3
7.1 图的概念 /Introduction of Graph
[定义 ]图
Ｖ是一个非空有限集,Ｅ是Ｖ上的一个二元关系,有序对 （ Ｖ,Ｅ ） 称为 有向图 /Directed
Graph。
若将 E中的有序对看成是无序的 （ 即将 e=(a,b)
看成 e={a,b}）,则称 （ Ｖ,Ｅ ） 为 无向图
/Undirected Graph。 有向图和无向图统称为 图
/Graph,记为 G 。
G = （ Ｖ,Ｅ ）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,4
[定义 ]顶点：
Ｖ中的元素称为 顶点,用带标记的点表示，也称为 结点 /Vertices。
[定义 ]边：
在有向图 G中,若 e=（ ａ,ｂ ） ∈ Ｅ,e称为 G的有向边 /directed edge。 用由ａ到ｂ带箭头的线把
ａ和ｂ连起来；
在无向图 G中,若 e=（ ａ,ｂ ） ∈ Ｅ,e称为 G的无向边 /undirected edge 。 a,ｂ间用连线连结,
有向边和无向边统称为 G的 边 /edge。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,5
[定义 ]图的分类对图 G=（ Ｖ,Ｅ ） 。 若对于任意的 （ ａ,ｂ ）
∈ Ｅ,a? b,则称图 G为简单图 /Simple Graph。
对图 G=（ Ｖ,Ｅ ） 。 若允许Ｅ是一个重集,则称图 G为重图 /Multigraph。 其相同的元素称为 重边 。
对图 G=（ Ｖ,Ｅ ） 。 若 G既允许是重图又允许是非简单图,则称图 G为拟图 /Pseudograph。
一般的 G称为 线性图 /Linear Graph。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,6
7.2 图的术语 /Graph Terminology
[定义 ]相邻和关联：
在无向图 G中，若 e=（ａ，ｂ） ∈ Ｅ，则 称 ａ
与 b相邻 /adjacent，或边 e关联 a、ｂ /incident或 联结
a,b/connect。 a,b称为边 e的 端点或结束顶点
/endpoint.
在有向图 G中，若 e=（ａ，ｂ） ∈ Ｅ，即箭头由
ａ到ｂ，称 ａ相邻到ｂ,或 a关联 或 联结 b。 a称为 e
的 起点 /initial vertex,b称为 e的 终点 /terminal or
end vertex。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,7
[定义 ]自回路：
若（ａ，ａ） ∈ Ｅ，（ {ａ，ａ }∈ Ｅ），
称边（ａ，ａ）（ {ａ，ａ }）是 自回路 /loop。
[定义 ]孤立顶点：
若ａ ∈ Ｖ，ａ不与其他顶点相邻，称
ａ为 孤立顶点 /isolated。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,8
[定义 ]顶点的次：
在无向图 G中，与 a相邻的顶点的数目称为 a的次或度 /degree。 记为 deg(a)或 d(a)。
在有向图 G中，以 a为终点的边的条数称为 a的 入次或入度 /in-degree。记为 deg–(a)或 d
–(a)。以 a为起点的边的条数称为 a的 出次或出度 /out-degree。记为 deg+(a)或 d +(a)。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,9
[定理 1 (Handshaking)] 设无向图 G=
（ V,E）有 e条边，则 G中所有顶点的次之和等于 e的两倍。
证明思路：利用数学归纳法。
[定理 2] 无向图中次为奇数的顶点个数恰有偶数个。
证明思路：将图中顶点的次分类，再利用定理 1。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,10
[定理 3] 设有向图 G=（ V,E）有 e条边，
则 G中所有顶点的入次之和等于所有顶点的出次之和，也等于 e。
证明思路：利用数学归纳法。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,11
有向图与无向图的对应：
无向图对应有向图：加上箭头。
有向图对应无向图：去掉箭头。
称为 underlying undirected graph
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,12
一些特殊的简单无向图：
（ 1） Complete Graphs/完全图 Kn
（ 2） Cycles/环图 Cn
（ 3） Wheels/轮图 Wn
（ 4） n-Cubes/n-立方图 Qn
（ 5） Bipartite Graphs/二分图 Kn,m
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,13
[定理 4] 设无向完全图 G有 n个顶点，则
G有 n(n-1)/2条边。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,14
一些特殊的其他图：
（ 1）有向完全图
（ 2）零图
（ 3）平凡图
（ 4） 正则图：若图Ｇ＝（Ｖ，Ｅ）中每个顶点的次均为 n，称此图Ｇ是 n-正则的 /n-
regular。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,15
计算机处理和网络应用特殊图表示：
（ 1） 串行处理 /Serial
linear array network
（ 2） 并行处理 /Parallel
Kn,Star,Cn,Wn
2-dimensional array network
hypercube network
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,16
[定义 ]子图：
Ｇ＝ （ Ｖ,Ｅ ） 是图,若Ｇ ’ ＝ （ Ｖ ’,
Ε ’） 也是图且满足：
(1)Ｖ ’?Ｖ； (2)Ｅ ’?Ｅ；
则称Ｇ ’ 为Ｇ的 子图 /subgraph。
注：
当Ｖ ’ ＝Ｖ时,称Ｇ ’ 为Ｇ的生成子图 。
当Ｅ ’ ≠Ｅ时,或Ｖ ’ ≠Ｖ时称Ｇ ’ 为Ｇ的真子图 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,17
[定义 ]补图：
关于完全图的子图的补图称为此子图的 绝对补图,若子图记为Ｇ，则补图记为 。G
[定义 ]补 图 /complementary graph,
Ｇ＝ （ Ｖ,Ｅ ） 是图,Ｇ ’ ＝ （ Ｖ ’,
Ε ’） 是Ｇ的子图,Ｅ,＝Ｅ－Ｅ ’,Ｖ,
＝ V－ V’或是Ｅ,中边所关联的所有顶点集合,则Ｇ,＝ （ Ｖ,,Ｅ,） 称为 Ｇ ’
关于Ｇ的 相对补图 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,18
a
e
dc
b
e
d
c
b
a
图 A 图 B
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,19
d
b
a
e
c
e
dc
b
图 C 图 D
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,20
a
e
d
c
b
d
b
图 E 图 F
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,21
图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｂ的边［ａ，ｂ］是孤立边图Ｄ是图Ｃ的子图图Ｆ是图Ｄ关于图Ｃ的余图图Ｅ是图Ｃ的补图
（Ａ是完全图,Ｃ是Ａ的子图 )
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,22
说明：
图Ｃ不是Ｅ的补图。（不互为补图）
因为：
Ｅ,＝Ｅ－Ｅ ’
＝ {[b,c],[b,d],[b,e],
[c,d],[c,e],[d,e]}
Ｖ,＝ {b,c,d,e}
而图 C多了顶点 a。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,23
[定义 ]子图：
Ｇ＝ （ Ｖ,Ｅ ） 和Ｇ ’ ＝ （ Ｖ ’,Ε ’）
是两个简单无向图,它们的并图Ｇ?Ｇ ’ 定义为
Ｇ?Ｇ ’ =（ Ｖ ’?Ｖ,Ｅ ’?Ｅ ）
称Ｇ?Ｇ ’ 为 Ｇ 和 Ｇ ’ 的并图 /union ofＧ 和
Ｇ ’,
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,24
7.3图的表示与同构 /
Representing Graph and Graph Isomorphism
图 G表示的三种方法：
（ 1）集合表示
（ 2）邻接表（ adjacency list）表示
（ 3）矩阵（ matrix）表示
1、邻接矩阵（ adjacency matrix）表示
2、关联矩阵（ incidence matrix）表示
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,25
[ 定义 ] 邻接矩阵,
设有向图Ｇ＝（Ｖ，Ｅ），Ｖ＝｛Ｖ 1,Ｖ 2,…，
Ｖ n ｝，若用方阵
nnij
aA
)(
EVV
EVV
a
ji
ji
ij
),(0
),(1
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,26
[ 定义 ] 图的同构,
图Ｇ 1 ＝（Ｖ 1,Ｅ 1 ），Ｇ 2 ＝（Ｖ 2,Ｅ 2 ），
如果能建立Ｖ 1 与Ｖ 2 间的一一对应，在此对应下，Ｅ 1 与Ｅ 2 中的边也一一对应，对有向图还保持关联方向的对应，则称图Ｇ 1 与
Ｇ 2 同构，记作Ｇ 1? Ｇ 2 。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,27
a
d
c
b
无向图
b' (c )
a' (b)
c' (a )
d'
例：
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,28
从图中不容易直接得出。
可用邻接矩阵，通过某种算法确定两个图是否同构。
上例的邻接矩阵：
0100
0011
1000
1010
0011
1001
0100
0010
i ii
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,29
同构判定算法（用邻接矩阵）
1、根据图确定其邻接矩阵（ I)
2、计算行次：矩阵每行１的个数，（对应于出次） 和列次：（对应于入次）
3、不考虑出现的次序不同，若行次与列次不同，
则必不同构，否则继续
4、同时交换其一矩阵的ｉ行和ｊ行，ｉ列和ｊ列。
若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,30
例,把 (II）的第１行与第４行交换，
第１列与第４列交换，得,
0010
1001
0100
1010
例,(1)的行次 （ ２,１,２,１ ）
列次 （ １,２,１,２ ）
(2)的行次 （ １,１,２,２ ）
列次 （ ２,２,１,１ ）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,31
再把第２行与第４行交换，第２列与第４列交换，就得,
0010
1001
1000
1010
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,32
小 结
1、图的概念与术语
2、一些特殊的图：极端情况、有用情况
2、图的表示：集合、表、矩阵
3、图的关系：图的转换、图的包含、
图的运算、图的同构
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,33
进一步的思考
1、图中内容的进一步组合
2,图的计算机表示与运算处理说明：（ 1）若从（ I)?(II),如何处理？
（ 2）算法的复杂度,n！,NP完全问题。
（对稍多一些顶点的图，难以计算机实现。）
G r a p h s / 图论
7/31/2009 11:30 AM Deren Chen,Zhejiang Univ,34
练 习
pp.443 11
pp.454 17,20,27,33
pp.463 43,51
