离散复习公开课一等奖课件省赛课获奖课件

第三部分离散数学第1页设A

是集合，由A所有子集为元素组成集合称为A幂集，记作P(A).

1.幂集(powerset)例：

B={1,2}，则P(B)={,{1},{2},{1,2}}第2页由两个元素x和y（允许x=y）按一定次序排列成二元组，叫做一种有序对,或序偶.记作<x，y>，其中x称为它第一种元素，y称为它第二个元素。2.有序对有序对性质：若xy,则<x，y><y，x>两个有序对<x，y>和<u，v>相等当且仅当x=u，y=v第3页3.笛卡儿积设A，B为集合，用A中元素作为第一元素，B中元素作为第二元素组成有序对，所有这样有序对组成集合，叫做A和B笛卡儿积，记作A

B.即A

B={<x，y>

x

A且y

B}.

第4页例7-3若A={1,2}，B={a,b,c}，求A

B，

B

A，AA，BB.A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}；B

A

={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}；AA={<1,1>,<1,2>,<2,1>,<2,2>}；B

B={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>，<c,a>,<c,b>,<c,c>}；第5页4.从A到B二元关系设A，B为集合，则AB任何子集都定义了一种从A到B二元关系，简称关系，记为R.即RA×B若<x，y>

R，记作xRy；若<x，y>

R，记作xRy.尤其地当A=B时，关系R称作A上二元关系.

RA×A第6页5.关系表达办法P1329设A={1，2，4，6}，有A上关系

R={<x，y>|x/y

A}解:R={<4,4>,<4,2>,<4,1>,<6,1>,<6,6>,<2,2>,<2,1>,<1,1>}用列举法表达R；给出关系R关系矩阵和关系图，判断R性质.第7页1426R是自反，不是对称，是传递.第8页6.逆关系

设R为X到Y二元关系，假如将R中每一有序正确元素次序交换，所得到集合称为R逆关系，简称R逆，记作R-1，即R-1={<x，y>|<y，x>

R}例A={1,2,3},R={<1,2>,<2,3>,<3,1>}R-1={<2,1>,<3,2>,<1,3>}第9页7.复合关系定义设A,B,C为集合，且R是从A到B一种关系，S是从B到C一种关系，即R为A×B子集，S为B×C子集，则由R和S决定了从A到C一种关系,记作，其中={<x,z>|存在y∈B,使得<x,y>

R,且<y,z>

S}第10页例令R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>

},第11页自反关系，对称关系，传递关系设R为A上关系，假如对每个x

A，都有xRx，即<x,x>R,

则称关系R是自反.对于任意x，y

A，若当xRy时，就有yRx，即当<x,y>R时，就有<y,x>R，则称关系R是对称.对于任意x，y，z

A，若当xRy，且yRz时，就有xRz，即当<x,y>R，且

<y,z>R时，就有<x,z>R，则称关系R是传递.

第12页例7-10设A={1,2,3},讨论下列关系性质R1={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>}是自反,不是对称,不是传递R2={<1,1>,<1,2>,<2,1>}不是自反,是对称,不是传递R3={<1,3>,<3,2>,<1,2>}不是自反,不是对称,是传递R4={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>}是自反,是对称,不是传递R5={<1,1>,<2,2>}不是自反,是对称,是传递R6={<1,1>,<2,2>,<3,3>,<1,2>}是自反,不是对称,是传递第13页例7-11设A={1,2,3,4},R={<x,y>|x整除y},判断其性质解R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,3>,<1,4>,<2,4>}是自反不是对称是传递第14页无向图：每条边均为无向边图称为无向图。记为G=<V,E>无向图v1v4v3v2v5有向图：每条边均为有向边图称为有向图。记为D=<V,E>(b)有向图v1v4v3v2第15页定义在无向图G=<V,E>中，与结点v(v∈V)关联边数目(若边是环，数目为2)，称为结点v度数，记作deg(v).在有向图D=<V,E>中，以结点v为起点边条数称为v出度；以v为终点边条数称为v入度;结点出度和入度之和就是该结点度数.

结点度数第16页图连通性定义

若无向图G是平凡图或G中任何两个结点之间都有一条通路，则称G为连通图，不然称G是非连通图或分离图。

(a)连通图

(b)分离图(c)连通图

第17页定义

对有向图D=<V,E>，有

(1)强连通图:D中任何一对结点u,v，不但从u到v有一条通路，并且从v到u也有一条通路.(2)单向连通图:D中任何一对结点u,v，或者从u到v有一条通路，或者从v到u有一条通路.(3)弱连通图:D中略去边方向，将它当作无向图后，图是连通.定理一种有向图D是强连通，当且仅当图D中有一个回路，它最少包括每个结点一次.

第18页强连通图强连通图单向连通图弱连通图单向连通图弱连通图第19页一、邻接矩阵设G＝<V，E>是一种简单图，它有n个结点V＝

v1，v2,…，vn.矩阵A(G)＝(aij)n称为图G邻接矩阵，其中显然，A(G)是n阶矩阵.

图矩阵表达

第20页deg(v1)=4，deg(v2)=2，deg(v3)=3，deg(v4)=3，deg(v5)=2v1v4v3v2v5第21页v1v3v2v4v1出度为1，入度为2；v2出度为2，入度为2；v3出度为3，入度为1；v4出度为1，入度为2；deg(v1)=3，deg(v2)=4，deg(v3)=4，deg(v4)=3

第22页二、关联矩阵给定无向图G＝<V，E>，V＝

v1，…，vn

，E＝

e1，…，em，令mij为结点vi与ej关联次数，则称矩阵