9512.net
甜梦文库
当前位置:首页 >> >>

2019年-31离散数学0601-PPT精选文档_图文

第6章 图

1

第6章 图
? 6.1 图的基本概念 ? 6.2 图的连通性

? 6.3 图的矩阵表示
? 6.4 几种特殊的图

2

6.1 图的基本概念
? 6.1.1 无向图与有向图 ? 6.1.2 顶点的度数与握手定理 ? 6.1.3 简单图、完全图、正则图、圈图、 轮图、方体图 ? 6.1.4 子图、补图 ? 6.1.5 图的同构

3

无序对与多重集合
无序对: 2个元素构成的集合, 记作(a,b) 无序积: A?B={(x,y) | x?A?y?B} 例如 A={a,b,c}, B={1,2} A?B=B?A={(a,1), (b,1), (c,1), (a,2), (b,2), (c,2)} A?A={(a,a), (a,b), (a,c), (b,b), (b,c), (c,c)} B?B={(1,1), (1,2), (2,2)}

多重集合: 元素可以重复出现的集合 重复度: 元素在多重集合中出现的次数 例如 S={a,b,b,c,c,c}, a,b,c 的重复度依次为1,2,3

4

笛卡儿积
定义4.2 设A, B为集合,A与B 的笛卡儿积记作A?B, A?B = { <x,y> | x?A ? y?B }. 例2

A={0, 1}, B={a, b, c} A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} B?A = ? {<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1>}
A = {?}, B = ? P(A) = {?, {?}} P(A)?A = ? P(A)?B = ?

{<?,?>, <{?},?>} ?
5

无向图
定义6.1 无向图G=<V,E>, 其中V??称为顶点集, 其元素称为 顶点或结点; E是V?V的多重子集, 称为边集, 其元素称为 无向边,简称边. 有时用V(G)和E(G)分别表示V和E 例如, G=<V,E>如图所示, 其中V={v1, v2, …,v5} E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}
e1 v1 e3 v5 e7 v4
6

e2 e4 e5

v2 e6

v3

有向图
定义6.2 有向图D=<V,E>, 其中V??称为顶点集, 其元素称为 顶点或结点; E是V?V的多重子集, 称为边集, 其元素称为有 向边,简称边. 有时用V(D)和E(D)分别表示V和E
e1

有限图: V, E都是有穷集合的图 n 阶图: n个顶点的图 零图: E=?的图 平凡图: 1 阶零图

a e4 d e7 c
7

e2

e3
e6

b

e5

顶点和边的关联与相邻
设无向图G=<V,E>, ek=(vi, vj)?E, 称vi, vj为ek的端点, ek与vi ( vj)关联. 若vi = vj, 则称ek为环. 无边关联的顶点称作孤立点. 若vi ? vj, 则称ek与vi ( vj)的关联次数为1;

若vi = vj, 则称ek与vi 的关联次数为2;
若vi不是边e的端点, 则称e与vi 的关联次数为0. 设vi,vj?V, ek,el?E, 若(vi,vj)?E, 则称vi,vj相邻; 若ek,el有一个公共端点, 则称ek,el相邻. 对有向图有类似定义. 设ek=?vi,vj?是有向图的一条边, 又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻接于vi
8

顶点的度数
设G=<V,E>为无向图, v?V, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 e1 悬挂边: 与悬挂顶点关联的边 v1 G的最大度?(G)=max{d(v)| v?V} G的最小度?(G)=min{d(v)| v?V} e
3

e2

v2 e5 v3 e6

v5

e4
e7 v4

例如 d(v5)=3, d(v2)=4, d(v1)=4, ?(G)=4, ?(G)=1, v4是悬挂顶点, e7是悬挂边, e1是环

9

顶点的度数(续)
设D=<V,E>为有向图, v?V, v的出度d+(v): v作为边的始点次数之和 v的入度d?(v): v作为边的终点次数之和 v的度数(度) d(v): v作为边的端点次数之和 d(v)= d+(v)+ d-(v) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) 悬挂顶点, 悬挂边 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, ?+=4, ?+=0, ??=3, ??=1, ?=5, ?=3
e4 d e7 c
10

e1

a
e2 e6

e3
e5

b

握手定理
定理6.1 任何图(无向图和有向图)的所有顶点度数之和都 等于边数的2倍. 证 图中每条边(包括环)均有两个端点, 所以在计算各顶点 度数之和时, 每条边均提供2度, m条边共提供2m度.

推论 任何图(无向图和有向图)都有偶数个奇度顶点
定理6.2 有向图所有顶点的入度之和等于出度之和等于边数

证 每条边恰好提供1个入度和1个出度

11

图的度数列
设无向图G的顶点集V={v1, v2, …, vn} G的度数列: d(v1), d(v2), …, d(vn) 如右图度数列:4,4,2,1,3 设有向图D的顶点集V={v1, v2, …, vn} D的度数列: d(v1), d(v2), …, d(vn) D的出度列: d+(v1), d+(v2), …, d+(vn) D的入度列: d?(v1), d?(v2), …, d?(vn) 如右图度数列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,2

e1 v1 e3 v5 e7 v4 e2 v2 e5 e6

e4

v3

e1
a e4 d e7 c
12

e2 e6 e3 e5 b

实例
例1 下述2组数能成为无向图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3 解 (1) 不可能. 有奇数个奇数. (2) 能

13

实例
例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 4?3+2?(n-4)?2?10 解得 n?8 例3 已知5阶有向图的度数列和出度列

分别为3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2

14

实例
例4 证明不存在具有奇数个面且每个面都具有奇数条棱的

多面体.
证 用反证法. 假设存在这样的多面体, 作无向图G=<V,E>,

其中 V={v | v为多面体的面}, E={(u,v) | u,v?V ? u与v有公共的棱 ? u?v}. 根据假设, |V|为奇数且?v?V, d(v)为奇数. 这与握手定理的 推论矛盾.

15

实例
例5 设9阶无向图的每个顶点的度数为5或6, 证明它至少有 5个6度顶点或者至少有6个5度顶点. 证 讨论所有可能的情况. 设有a个5度顶点和b个6度顶点 (1)a=0, b=9; (2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1 (1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点 方法二 假设b<5, 则a>9-5=4. 由握手定理的推论, a ? 6

16

简单图
定义6.4 在无向图中, 关联同一对顶点的2条或2条以上的 边, 称为平行边, 平行边的条数称为重数 在有向图中, 具有相同始点和终点的2条或2条以上的边称 为有向平行边, 简称平行边, 平行边的条数称为重数 含平行边的图称为多重图 既无平行边也无环的图称为简单图

17

实例
e1
v1 e2 v2 e5 v3 v4 e6 e4 e1 a e2 e3

e3 e4 v5 e7

d
e7

e6
e5 c

b

e5和e6 是平行边 重数为2 不是简单图

e2和e3 是平行边,重数为2 e6和e7 不是平行边 不是简单图
18

完全图与正则图
无向完全图: 每对顶点之间都有一条边的无向简单图. n阶无向完全图记作Kn, 顶点数n, 边数m=n(n-1)/2, ?=?=n-1 有向完全图: 每对顶点之间均有两条方向相反的边的有向简单图. 顶点数n, 边数m=n(n-1), ?+=?+=?-=?-=n-1, ?=?=2(n-1) k-正则图: 每个顶点的度数均为k的无向简单图 顶点数n, 边数m=kn/2

19

实例

K3

K5

3阶有向完全图

2正则图

3正则图 彼得松图

4正则图
20

圈图与轮图
无向圈图Cn=<V,E>, 其中V={v1,v2,…,vn}, E={(v1,v2),(v2,v3), …,(vn-1,vn),(vn,v1)}, n ?3 有向圈图Cn=<V,E>, 其中V={v1,v2,…,vn}, E={<v1,v2>, <v2,v3>,…,<vn-1,vn>,<vn,v1>}, n ?3 轮图Wn:无向圈图Cn-1内放一个顶点, 且与圈图的每个顶点之间 恰有一条边, n ?4

21

方体图
n方体图Qn=<V,E>是2n阶无向简单图, 其中 V={v|v=a1a2…an, ai=0,1, i=1,2,…,n} E={(u,v)| u,v?V?u与v恰好有一位数字不同}.

00 0 1 10

01

100 000 001

101

11

010 011 110 111
22

实例
e1 b a e2 f e6 f e6 b e1 a f

e3
c e4

e5 e e7 d

e5
e7 d

e

e3
c

e5
e7 d

e

(1)

(2)

(3)

(1),(2),(3)是(1)的子图, (2),(3)是真子图, (1)是母图. (1),(3)是(1)的生成子图. (2)是{d,e,f }的导出子图, 也是{e5, e6, e7}导出子图. (3)是{e1, e3, e5, e7}的导出子图
23

子图
定义6.10 设G=<V,E>, G?=<V?,E?>是2个图(同为无向图,或 同为有向图) 若V??V且E??E, 则称G?为G的子图, G为G?的母图, 记作 G??G 若G??G 且V?=V, 则称G?为G的生成子图 若V??V或E??E, 称G?为G的真子图 设V??V且V???, 以V?为顶点集, 以两端点都在V?中的所有 边为边集的G的子图称作V?的导出子图, 记作G[V?] 设E??E且E???, 以E?为边集, 以E?中边关联的所有顶点为 顶点集的G的子图称作E?的导出子图, 记作G[E?]
24

实例
e1 b a e2 f e6 f e6 b e1 a f

e3
c e4

e5 e e7 d

e5
e7 d

e

e3
c

e5
e7 d

e

(1)

(2)

(3)

(1),(2),(3)是(1)的子图, (2),(3)是真子图, (1)是母图. (1),(3)是(1)的生成子图. (2)是{d,e,f }的导出子图, 也是{e5, e6, e7}导出子图. (3)是{e1, e3, e5, e7}的导出子图
25

补图
?定义14.9 设G=<V,E>为n阶无向简单图,以V为顶点集,以 所有使G成为完全图Kn的添加边组成的集合为边集的图, 称为G的补图,记作 G .

26

图的同构
定义6.12 设G1=<V1,E1>, G2=<V2,E2>为两个无向图(有向
图), 若存在双射函数 f: V1?V2, 使得对于任意的vi,vj?V1, (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是同构的,记作G1?G2.

27

实例
1 1 2 3

2 1

3

4

5

6

4

1

6

2
5 3 4

3 2
5

6

28

实例
例6 画出4阶3条边的所有非同构的无向简单图 解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数 为偶数, 有下述3个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.

1,1,1,3

1,1,2,2

0,2,2,2

29

实例
例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图

30

相关概念
8. 邻域与关联集 ① v?V(G) (G为无向图)
v 的邻 N ( v ) ? { 域 u | u ? V ( G ) ? ( u , v ) ? E ( G ) ? u ? v } v 的闭 N ( v ) ? N 邻 ( v ) ? { v } 域

( v ) ? { e | e ? E ( G ) ? e 与 v 关联 } v 的关联集 I
② v?V(D) (D为有向图)
? v 的后继元集 ? ( v )? { u |u ? V ( D ) ? ? v ,u ?? E ( D )? u ? v } D ? v 的先驱元集 ? ( v )? { u |u ? V ( D ) ? ? u ,v ?? E ( D )? u ? v } D ? ? v 的邻域 N ( v ) ? ? ( v ) ? ? ( v ) D D D

v 的闭邻域 N ( v )? N ( v ) ? { v } D D

31

n 阶完全图与竞赛图
? 定义14.6 ? (1) n (n?1) 阶无向完全图——每个顶点与其余顶点均相邻 的无向简单图,记作 Kn. ? 简单性质:边数
n ( n ? 1 ) m ? , ? ? ? ? n ? 1 2 ? (2) n (n?1)阶有向完全图——每对顶点之间均有两条方向 相反的有向边的有向简单图. ? ? ? 简单性质:m ? n ( n ? 1 ), ? ? ? 2 ( n ? 1 ), ? ? ? n ? 1

?
2

?

? (3) n (n?1) 阶竞赛图——基图为Kn的有向简单图. ? 简单性质:边数 n ( n ? 1 )
m ? , ? ? ? ? n ? 1

32

n 阶 k 正则图

(1)

(2)

(3)

? (1)为K5,(2)为3阶有向完全图,(3)为4阶竞赛图.
定义14.7 n 阶k正则图——?=?=k 的无向简单图 简单性质:边数(由握手定理得) nk m ? 2 Kn是 n?1正则图, 彼得松图(见书上图14.3(a) 所示,记住它)
33

实例
例2 画出K4的所有非同构的生成子图

34

补图
?定义14.9 设G=<V,E>为n阶无向简单图,以V为顶点集,以 所有使G成为完全图Kn的添加边组成的集合为边集的图, 称为G的补图,记作 G . ?若G? G (同构) , 则称G是自补图.

35



学霸百科 | 新词新语

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图