第十四章 图的基本概念
二、基本要求
深刻理解图论中的基本概念及其它们之间 的相互关系 记住图论中的主要定理并能灵活地应用它 们证明相关定理或命题 应用握手定理及树的性质解无向图、无向 树 会求最小生成树、最优树及最佳前缀码 会用邻接矩阵求有向图中的通路、回路数
第十四章 图的基本概念
本章的主要内容
图及相关的诸多概念
例:
(1)
(2)
(3)
(4)
(5)
(6)
(1)-(6)都是(1)的子图, (2)-(6) 为真子图, (1)-(5)为生成子图。
例 :画出K4的所有非同构的生成子图
八、补图
定义14.9 设G=<V,E>为n阶无向简单图,以V为结 点集,以所有使G成为完全图Kn的添加边 组成的集合为边集的图,称为G的补图, 记作 G . 若G G , 则称G是自补图.
(5)奇度结点与偶度结点
2.图论基本定理——握手定理 定理14.1 设 G=<V,E> 为 任 意 无 向 图 , V={v1,v2,…,vn}, n |E|=m, 则 d (vi ) 2m
i 1
证
G中每条边(包括环)均有两个端点,所 以在计算G中各结点度数之和时,每条边 均提供2度,当然m条边共提供2m度.
(3)若 n阶无向简单图是自补图,则G与其补 图的边数相同,设它们的边数为m,由握手定 理知 n ( n 1)
2 2m
即n(n-1)=4m,因而n为4的倍数,即n=4k 或n-1为4的倍数,即n=4k+1(k为正整数)。
14.2 通路与回路
一、通路与回路的定义
定义14.11 给定图G=<V,E>(无向或有向的), G中结点与边的交替序列 = v0e1v1e2…elvl,vi1, vi是ei的端点.
例 下图中G=(V,E)与G=(V,E)同构 吗?
G
G'
G'中4个3度结点中的每一个均与另外两个3度结 点相邻,而G中每个3度结点只与另外1个3度结点 相邻。
练习:3个结点可构成几个不同构的简单无向图?
例:无向图G的各个结点的度数都是3,且结点 数n与边数m有关系m=2n-3。在同构意义下G是 唯一的吗? 解:由握手定理得 2m=3n,又因为m=2n-3 所以m=9,n=6。在同构意义下不唯一。
练习:
下列哪些序列可构成无向简单图?
(1)1,1,2,2,3 (2)1,1,2,2,2 (3)0,1,3,3,3 (4)1,3,4,4,5 (5)1,1,1,2,3 (6)3,3,3,3 答案: (2)(5)(6)
四、图的同构
定义14.5
设G1=<V1,E1>, G2=<V2,E2>为两个无向图(两 个有向图),若存在双射函数f:V1V2, 对于 vi,vjV1, (vi,vj)E1 ( <vi,vj>E1 ) 当 且 仅 当 (f(vi),f(vj))E2(<f(vi),f(vj)>E2),并且, (vi,vj) (<vi,vj>)与 (f(vi),f(vj))(<f(vi),f(vj)>)的重数 相同,则称G1与G2是同构的,记作G1G2.
例:
(1)
(2)
(3)
(4)
(5)
(1)为完全图K5 , (2),(3)互为补图(自补图), (4),(5)互为补图。
练习:
(1)给出所有非同构的无向4阶自补图;
(2)给出所有非同构的无向5阶自补图; (3)证明:若n阶无向简单图是自补图, 则n=4k或n=4k+1(k为正整数)。
(1)
(2)
I (v) {e | e E (G) e与v关联}
② vV(D) (D为有向图)
v的后继元集
D ( v ) {u | u V ( D )
v, u E ( D ) u v} v的先驱元集
D ( v ) {u | u V ( D )
u, v E ( D ) u v}
通路与回路 图的连通性
图的矩阵表示
14.1
图
一、无向图与有向图的定义 1. 无向图的定义
定义14.1 无向图G = <V,E>, 其中
(1)V 为结点集,元素称为结点(顶 点)。 (2)E为VV的多重集,其元素称Fra bibliotek无向 边,简称边。
设
V={v1, v2, E={(v1,v1), (v2,v3), (v2,v5), (v4,v5)} ,则 …,v5}, (v1,v2), (v2,v3), (v1,v5),
六、正则图
定义14.7
n阶k正则图——==k 的无向简单图 性质:边数
nk m (由握手定理得) 2
例:证明:若有n个人,每个人恰有3个 朋友,则n必为偶数。
证明:
用n个结点代表n个人,两个朋友对应的 结点连边,则得到一个3正则图,跟据 握手定理,所有结点的度数之和3n为偶 数,因而n必为偶数。
v的邻域 N D ( v ) D ( v ) D ( v )
v的闭邻域 N D ( v ) N D ( v ) {v}
(8)基图
二、多重图与简单图
定义14.3 (1)无向图中的平行边及重数
(2)有向图中的平行边及重数(注意方向性)
(3)多重图(含平行边)
(4)简单图(不含平行边与环)
定理:设非负整数列d=(d1,d2,…,dn),则d 是可图化的当且仅当 例:
d
i 1
n
i
0(mod2)
(2, 4, 6, 8, 10),(1, 3, 3, 3, 4) 是可图化的, 后者又是可简单图化的, 而(2, 2, 3, 4, 5),(3, 3, 3, 4) 都不是可简单 图化的,后者也不是可图化的
例:判断以下哪些图是同构的。
a b (1) e
d
c (3)
(2)
v4 v5 v1 v2 (4)
a
e
c
v1 v2 v3
(6) v4
v6 v5
v3
f (5) b d
上图中,(1)≌(2),(3)≌(4),(5)≌(6)
(3)≌(4):av1, bv2, cv3, dv4 ,ev5 (5)≌(6):av1, bv2, cv3, dv4 ,ev5 ,f v6
第四部分 图论
图论是一个古老的数学分支,它起源于游 戏难题的研究。图论的内容十分丰富,应用得 相当广泛,许多学科,诸如运筹学、信息论、 控制论、网络理论、博弈论、、计算机科学等, 都以图作为工具来解决实际问题和理论问题。 随着计算机科学的发展,图论在以上各学科中 的作用越来越大,同时图论本身也得到了充分 的发展。
七、子图
定义14.8 G=<V,E>, G=<V,E>
(1)GG —— G为G的子图,G为G的母图
(2)若GG且V=V,则称G为G的生成子图
(3)若VV或EE,称G为G的真子图
( 4 ) V ( VV 且 V ) 的 导 出 子 图 , 记 作 G[V] ( 5 ) E ( EE 且 E ) 的 导 出 子 图 , 记 作 G[E]
例:
a
e
d
b
n i 1 i
c
d ( v ) d ( a ) d ( b) d ( c ) d ( d ) d ( e )
4 2 1 0 1 8 2m ( m 4)
定理14.2
设 D=<V,E> 为 任 意 有 向 图 , V={v1,v2,…,vn}, |E|=m, 则
32 24+2x
得 x 4, 阶数n 4+4+3=11.
推论 任何图(无向的或有向的)中,奇度结 点的个数是偶数。 证 设G=<V,E>为任意图,令
V1={v | vVd(v)为奇数}
V2={v | vVd(v)为偶数} 则V1V2=V, V1V2=,由握手定理可知
2m d (v) d (v) d (v)
v V v 1 V v 2 V
由于2m, d (v)均为偶数,所以
v 2 V
vV1
(v ) d 为偶数,
但因为V1中结点度数为奇数,所以|V1|必为偶数.
例:
某一次聚会的成员到会后相互握手。证明与 奇数个人握手的人数一定是偶数。
证明: 用结点表示到会的成员,握手两人对应的结 点用边相连,则得到一个无向图,本题可归 结为说明一个图中有偶数个奇数度结点,根 据握手定理的推论知结论成立。
G = <V,E>为一无 向图,用右图表示
2.有向图的定义 定义14.2 有向图D=<V,E>, 只需注意E是VV的 多重子集。
3.关于无向图和有向图诸多定义或表示 (1)图① 可用G泛指图(无向的或有向的) ② V(G), E(G), V(D), E(D) (2)n阶零图与平凡图 (3)用ek表示无向边或有向边 (4)结点与边的关联关系 ③ n阶图
在讨论关系时,我们曾经引进过图
的一些概念。在那里,图只是作为表达
集合上二元关系的一种工具。本部分将 对图的基本概念、基本性质、各种特殊
图及其判别方法进行较为详细的讨论。
一、本部分主要内容 图的基本概念:图、通路和回路、图的连通 性、图的矩阵表示 图的可行遍性:欧拉图、哈密顿图
树:无向树及其性质、生成树与最小生成树、 根树及其应用 平面图及图的着色:平面图、欧拉公式、平 面图的判断、对偶图、着色
三、结点的度数及握手定理
1.结点的度数(度)
定义14.4及衍生的概念
(1)设G=<V,E>为无向图, vV, d(v):v的度
(2)设D=<V,E>为有向图, vV,