- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
e1 13 , e2 12 , e3 12 ,
e4 23 , e5 33
v1 e2 v2
e1 e3
v3
e4
e5
5
关于点与边的术语
邻接(点)：图 G 中，如果 e E (G) ，G (e) uv ，
31
定义 5.4.2[2]：设 G 是一个图, H G . 如果 u V H 当且仅当 u 是 E H 中某条边的一个端 点 , 则 称 H 是 G 的 由 EH 导 出 的 子 图 , 记 为
G E H 。 【有顶点必有边关联】
边导出子图
【点导出子图：取其两端点必取其边】 说白了，图G的边导出子图就是G的一些边和 这些边的端点所构成的子图。 边导出子图中不会有孤立点，也不会是零图； 但是点导出子图却可以含有孤立点，甚至是一 个零图。
23
图的奇点个数必为偶数
由定理5.3.1可得出如下的推论：
推论5.3.1： 任何一个图的奇点个数必为偶数。
假设图中奇点个数为奇数，则它们的度数之和 为奇数，偶点的度数之和当然是偶数，这样所 有顶点的度数之和为奇数。与定理5.3.1矛盾。 此推论可以用来解决许多实际问题，如“握手 问题”：任何一群人中，与奇数个人握过手的 人必为偶数个。
15
图同构的定义
定义 5.2.1：设 G 和 H 是两个图. 如果存在两个双射：
:V G V H （顶点集之间的双射）,
: E G E H （边集之间的双射）,
使得（在 下）对应边的端点是（在 下）对应的： 当且仅当H e u ，
H 2 既不是点导出子图，也不是 G 的边导出子图；
H 3 是 G 的边导出子图 H 3 G[{e1 , e2 , e3 , e4 }]， 但不是点
导出子图。
35
导出子图例子（2）
下图中，取 E {e1 , e2 , e3 , e4 }，则 E E {e5 , e6 }，试 画出边导出子图 G[ E E]，以及真子图 G E 。
24
§5.4 子图及图 的运算
25
子图
定义 5.4.1：设 G 和 H 是两个图. 如果V H V G 且
E H E G , 则称 H 是 G 的子图, G 是 H 的母图, 记
为H G。
如果 H G , 且 H G , 则称 H 是 G 的真子图, 记为 H G。
32
边导出子图的例子
G
e1 v1 e4 e
H3
2
v1 e1 v3 e4 e2 v4 e3 v2
e6 v4 e5 e3 v3 v2
显然， H 3 G[{e1 , e2 , e3 , e4 }]
H 3 G[{v1 , v2 , v3 , v4 }]
33
关于导出子图
G 的点或边导出子图必是 G 的子图，但 G 的子图却 不一定是 G 的点或边导出子图。 G V G V V , V V G , V V 删去顶点同时也删去其关联边。 不一定有 G E G E E , E E G , E E 删去了边，却会留下顶点，有G E E G E 。
关于图的术语
G 图 G 的阶： 的顶点数， V (G) |，称为 G 的阶。 |
G( p, q) 表示有 p 个顶点， q 条边的图。 用 p(G ) 和 q(G) 分别表示图 G 的顶点数和边
数。
如果图G 的V (G) 和 E (G)都是有限集，称G 为 有限图，否则称为无限图。
7
G
H1
H2
H3
上面各图： G 为母图， H 1 ， H 3 和 H 2 均为 G 的真子 图。 H 3 是生成子图。
27
几个约定
从图中删去一个顶点，必须同时删去所有与该顶 点关联的边； 从图中删去一条边，则只要删去其两个端点之间 的连线，而保留这两个端点。 V V (G) ， G V 表示 G 中删去V 中的顶点后所 得的子图； E E (G)， G E 表示 G 中删去 E 中的边后所得 的子图。
18
§5.3顶点的度
19
顶点的度
定义 5.3.1： G 是一个图, V G , G 中与 关联的边 设 的数目称为 在 G 中的度数, 简称 的度, 记为 dG 或 d 。
注意，顶点 v 上的一条环相当于两条边。
20
图的几种顶点
在一个图中： 度为奇数的点称为奇点； 度为偶数的点称为偶点； 度为1的点称为悬挂点； 度为0的点称为孤立点。
如果 H G , 且 V H V G , 则称 H 是 G 的生成子 图。即包含了全部顶点的子图。
26
子图的例子
v1 e4 e 2 e6 v4 e5 e3 v3 v2 e1 e1 v3 e3 v1 e2 v2 v4 e6 v3 v2 v3 e1 v1 e4 e2 v4 e3 v2
22
顶点的度数之和是边数的两倍
定理 5.3.1：对任何一个图 G( p, q) ，有
d 2q
i 1 i
p
即一个图的所有顶点的度数之和为偶数。 此定理很容易证明，因为在计算顶点的度时，每一条 边都被计算了两次，也只被计算了两次。
思考： p 阶完全图 K p 的边数呢？
E ( K p ) p( p 1) / 2
21
正则图
将一个图的各顶点度数中的最大值和最小值分别记 为 G 和 (G) 。 一个简单图中， 如果 G (G) k , 则称 G 为 k -正则 图。 正则图中各顶点的度都为 k 。 显然， p 阶完全图 K p 必是一个 ( p 1) -正则图，但反 之不然。
G： 5 eu5来自u1e1 u2v1
H：
≌
v4
a1 v2
a3 a5 a2 v5
v3
e4
u4 e3
e2
u3
a4
17
图的等价类
显然，同构关系是一个等价关系。 所以可以将所有的p阶图的集合按图的同构关系 划分成等价类。 例如，3阶图的等价类有如下四种：
无标记图：在每个等价类中任选一个图，去掉 顶点和边的名称，作为该类的代表。这种图成 为无标记图。上面这四个图就是无标记图。
下面给出了完全图K3，K4和K5：
3阶完全图K3
4阶完全图K4
5阶完全图K5
9
二分图
定义 5.1.4： 如果图 G 的顶点集V G 能分成两个不相交 的非空子集V1 和V2 , 使得 G 的每条边的两个端点分别 在V1和V2 中, 则称 G 为二分图. 记为 G V ,V2 .
若图 G 中含有环, 则 G 不是二分图, 若 G 是二分图, 则V G 的二划分子集V1 和V2 可 能不唯一. 若二分图 G V1 ,V2 中V1 的每个顶点与V2 的每个 顶点都邻接, 则称 G 为完全二分图, 记为 K m ,n , 其中 V1 m , V2 n .
§5.2图的同构 (一)
14
图的同构
图描述客观对象间的关系，几何形状不是重要的。 同一个图的图形不是唯一的，其差异可以是很大。 比如，下面的三个图在图形上是完全不相同的：
G a b H b a c d d c a b c d K
但是我们不难看出这三个图描述的是四个对象 之间的相同关系，实质上是同一个图。 它们也就是同构的图。
10
二分图的例子
下面是图G及其二分图：
a2 a1 b1 b2
V1: a1
b1
c1
d1
d2
d1 G c2
c1
V2 : a2
b2
c2
d2
G的二分图
11
补图
定义 5.1.5：如果简单图 G 和简单图 H 满足： （1）V H V G ； （顶点集相等） （2）对 u, V , u , u E H , 当且仅当
30
点导出子图的例子
例如：
G
v1
e4 e 2 e6 v4 e5 e3 v3 v2 e1
H1
v1
e1 v3
e3
e2 v2
H2
v1 e1 v3 e2 v2
H1 G[{v1 , v2 , v3 }]， 但是 H 2 G[{v1 , v2 , v3 }]， 因为缺了
关联 v2 , v3 的边 e3 。
则称 G 和 H 是同构的。记为 G H , 有时可省略。
特别地, 如果V G V H , E G E H , 且G H , 则称 G 和 H 是相等的, 记为 G = H 。
16
图同构的例子
对于下图，令 ui i , ei ai ,1 i 5, 则 和 是 满足定义 5.2.1 的两个双射, 故 G H 。
（ 3 ） 是 E 到 u u, V 的 映 射 , 称 为 关 联 函 数 .
u u , u, V 。
通常用V G 、E G 、G 分别表示图 G 的顶点集、边集 和关联函数.
4
图的例子
设 G V , E , , 其中，
V 1 ,2 ,3 ， E e1 , e2 , e3 , e4 , e5 ，
定义 5.4.2[1]：设 G 是一个图, H G 。 如 果 e E H ， 当 且 仅 当 存 在 u, V H , 使 得
G e u , 则称 H 是 G 的由点V H 导出的子图，记
为 G V H 。
