离散数学及应用 课件 第5章 图的基本概念

DiscreteMathematics鄢小虎

离散数学2图论部分第5章图的基本概念第6章特殊的图第7章树3第5章图的基本概念5.1无向图及有向图5.2通路,回路和图的连通性5.3图的矩阵表示5.4最短路径,关键路径和着色45.1无向图及有向图无向图与有向图顶点的度数握手定理简单图完全图子图补图55.1无向图及有向图有向图相关的基本概念6无向图

多重集合:元素可以重复出现的集合无序积:A

B={{x,y}|x

A

y

B}注意：为了方便起见，本书将{x,y}记为(x,y)

7无向图

定义无向图G=<V,E>,其中(1)顶点集V是非空有穷集合,

其元素称为顶点(2)边集E为V

V的多重子集，其元素称为无向边，简称边.例如,G=<V,E>,其中V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}8有向图定义有向图D=<V,E>,其中(1)顶点集V是非空有穷集合,

其元素称为顶点(2)边集E为V

V的多重子集，其元素称为有向边，简称边.D的基图:用无向边代替有向边如D=<V,E>,其中

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<c,b>,<d,c>,<c,d>}图的数学定义与图形表示,在同构意义下一一对应9无向图与有向图n阶图:n个顶点的图零图:E=

，没有一条边平凡图:1阶零图，只有1个顶点，没有边10顶点和边的关联与相邻定义设e=(u,v)是无向图G=<V,E>的一条边,称u,v为e的端点,e与u

(

v)关联.若u

v,则称e与u

(

v)的关联次数为1;若u=v,则称e为环,此时称e与u

的关联次数为2;若w不是e端点,则称e与w

的关联次数为0.无边关联的顶点称作孤立点.

定义无向图中，若存在一条边e以顶点u,v为端点,则称u,v相邻;若e,e

至少有一个公共端点,则称e,e

相邻.（图5-1(a)）对有向图有类似定义.设e=

u,v

是有向图的一条边,又称u是e的始点,v是e的终点,u邻接到v,v邻接于u.（图5-1(b)）11顶点的度数

设G=<V,E>为无向图,v

V,

v的度数(度)

d(v):v作为边的端点次数之和

悬挂顶点:度数为1的顶点

悬挂边:与悬挂顶点关联的边

G的最大度

(G)=max{d(v)|v

V}

G的最小度

(G)=min{d(v)|v

V}例如d(v5)=3,d(v2)=4,d(v1)=4,

(G)=4,

(G)=1,

v4是悬挂顶点,e7是悬挂边,e1是环12顶点的度数(续)

设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)=max{d+(v)|v

V}

最小出度

+(D)=min{d+(v)|v

V}

最大入度

(D)=max{d

(v)|v

V}最小入度

(D)=min{d

(v)|v

V}

最大度

(D)=max{d(v)|v

V}

最小度

(D)=min{d(v)|v

V}13例例d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,抢答：c,d的入度、出度和度？

+(D)=4,

+(D)=0,

(D)=3,

(D)=1,

(D)=5,

(D)=3.

14图的度数列

设无向图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)如右图出度列:4,0,2,1

入度列:1,3,1,2度数列:5,3,3,315图论基本定理——握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.推论

任意无向图和有向图的奇度顶点个数必为偶数.（顶点的总度数为偶数）16握手定理的应用例1(3,5,3,4),(2,3,4,6,8)能成为图的度数列吗?解不可能.奇度顶点个数为奇数.抢答：课本第137页，习题5.1中能否构成无向图17握手定理的应用课堂练习：课本第137页，习题5.2，5.3，5.5-(1),(2)18多重图与简单图

定义

(1)在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点,则称这些边为有向平行边,简称平行边,平行边的条数称为重数.(3)含平行边的图称为多重图.(4)既无平行边也无环的图称为简单图.例：图5-2为简单图19实例e5和e6是平行边重数为2不是简单图e2和e3是平行边,重数为2e6和e7不是平行边(方向)不是简单图20完全图

n阶无向完全图Kn:每个顶点都与其余顶点相邻的n阶无向简单图.简单性质:边数m=n(n-1)/2,

=

=n-1n阶有向完全图:每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质:边数m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-1

K53阶有向完全图21子图定义设G=<V,E>,G

=<V

,E

>是两个图(1)若V

V且E

E,

则称G

为G的子图,G为G

的

母图,记作G

G（图是自身的子图）(2)若G

G且V

=V，则称G

为G的生成子图(3)若V

V或E

E，称G

为G的真子图(4)设V

V且V,

以V

为顶点集,以两端点都在

V

中的所有边为边集的G的子图称作V

的导出子图，记作G[V

](5)设E

E且E,

以E

为边集,以E

中边关联的所有顶点为顶点集的G的子图称作E

的导出子图,记作G[E

]导出子图实例

22GDG[{v1,v2}]G[{e1,e3,e4}]D[{e1,e3}]D[{v1,v2}]23补图定义设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.实例：课本图5-424课堂练习课本第138页，习题5.9DiscreteMathematics鄢小虎

离散数学课前复习函数：特殊(?)的二元关系,B上A的计算图论概念：有向图、无向图、顶点、边定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.275.2通路、回路、图的连通性

简单通(回)路,初级通(回)路,复杂通(回)路无向图的连通性

无向连通图,连通分支有向连通图

弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)28通路与回路

定义给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列

=v0e1v1e2…elvl，(1)若

i(1

i

l),vi

1,vi是ei的端点(对于有向图,要求vi

1是始点,vi是终点),则称

为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称

为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).通路与回路实例2930无向图的连通性设无向图G=<V,E>u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={<u,v>|u,v

V且u

v}是V上的等价关系连通图：任意两点都连通的图.平凡图是连通图.连通分支:V关于连通关系R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图

p(G)=1例31有向图的连通性

设有向图D=<V,E>u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通):基图为无向连通图D单向连通:

u,v

V，u可达v

或v可达u

D强连通:

u,v

V，u与v相互可达强连通

单向连通

弱连通32课程回顾握手定理：所有顶点度数之和等于边数的2通路和回路：回路为起点和终点相等的通路连通图：任意两点都连通的图连通图G的连通分支个数记作p(G)=k例如：p(G)=333有向图的连通性(续)

例

强连通单向连通弱连通定理(强连通判别法)

D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)

D单向连通当且仅当D中存在经过每个顶点至少一次的通路34课堂练习课本139页，习题5.25

355.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵36无向图的关联矩阵定义设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij为顶点vi与边ej的关联次数，称(mij)n

m为G的关联矩阵，记为M(G).顶点边环该如何表示？37无向图的关联矩阵性质(1)每一列恰好有两个1或一个2行元素和为度数所有元素和为边的2倍38有向图的关联矩阵定义设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

则称(mij)n

m为D的关联矩阵，记为M(D).有向图的关联矩阵(续)性质(1)每一列恰好有一个1和一个-1(2)第i行1的个数等于d+(vi),-1的个数等于d-(vi)(3)1的总个数等于-1的总个数,且都等于m(4)平行边对应的列相同39例

M(D)=

顶点边40定义设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()m

n为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵

行元素之和等于出度列元素之和等于入度有向图的邻接矩阵实例41顶点顶点42有向图的可达矩阵

定义设D=<V,E>为有向图,V={v1,v2,…,vn},令

称(pij)n

n为D的可达矩阵,记作P(D),简记为P.性质:

P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.43有向图的可达矩阵实例例顶点顶点44课堂练习写出下列有向图的关联矩阵、邻接矩阵、可达矩阵45关联矩阵DiscreteMathematics鄢小虎

离散数学475.4

最短路径,关键路径与着色带权图最短路径与Dijkstra算法关键路径着色问题最短路径我们日常生活中经常用到最短路径，例如：坐地铁从深圳北站去宝安机场，怎么走最短？最短路径最短（最快、最便宜）航空路线？50最短路径带权图G=<V,E,w>,其中w:ER.

e

E,w(e)称作e的权.e=(vi,vj),记w(e)=wij.若vi,vj不相邻,记wij=.通路L的权:L的所有边的权之和,记作w(L).u和v之间的最短路径:u和v之间权最小的通路.例

L1=v0v1v3v5,w(L1)=1+7+2=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.51标号法(E.W.Dijkstra,1959)设带权图G=<V,E,w>,其中

e

E,w(e)0.设V={v1,v2,,vn},求v1到其余各顶点的最短路径1.令l1

0,p1

,lj

+

,pj

,j=2,3,

,n,P={v1},T=V-{v1},k

1,t

1./

表示空2.对所有的vj

T且(vk,vj)

E

令l

min{lj,lk+wkj},

若l=lk+wkj,则令lj

l,pj

vk.3.求li=min{lj|vj

Tt}.

令P

P

{vi},T

T-{vi},k

i.4.令t

t+1,

若t<n,则转2.视频讲解：/video/BV1Ut41197ae52Dijkstra标号法实例例

求v0到v5的最短路径t

v0

v1

v2

v3

v4

v5

1(0,

)*(+

,

)(+

,

)(+

,

)(+

,

)(+

,

)2(1,v0)*(4,v0)(+

,

)(+

,

)(+

,

)3