離散復習公開課一等獎課件省賽課獲獎課件

第三部分離散數(shù)學第1頁設(shè)A

是集合，由A所有子集為元素組成集合稱為A冪集，記作P(A).

1.冪集(powerset)例：

B={1,2}，則P(B)={,{1},{2},{1,2}}第2頁由兩個元素x和y（允許x=y）按一定次序排列成二元組，叫做一種有序?qū)?或序偶.記作<x，y>，其中x稱為它第一種元素，y稱為它第二個元素。2.有序?qū)τ行驅(qū)π再|(zhì)：若xy,則<x，y><y，x>兩個有序?qū)?lt;x，y>和<u，v>相等當且僅當x=u，y=v第3頁3.笛卡兒積設(shè)A，B為集合，用A中元素作為第一元素，B中元素作為第二元素組成有序?qū)?，所有這樣有序?qū)M成集合，叫做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二元關(guān)系設(shè)A，B為集合，則AB任何子集都定義了一種從A到B二元關(guān)系，簡稱關(guān)系，記為R.即RA×B若<x，y>

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

R，記作xRy.尤其地當A=B時，關(guān)系R稱作A上二元關(guān)系.

RA×A第6頁5.關(guān)系表達辦法P1329設(shè)A={1，2，4，6}，有A上關(guān)系

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

A}解:R={<4,4>,<4,2>,<4,1>,<6,1>,<6,6>,<2,2>,<2,1>,<1,1>}用列舉法表達R；給出關(guān)系R關(guān)系矩陣和關(guān)系圖，判斷R性質(zhì).第7頁1426R是自反，不是對稱，是傳遞.第8頁6.逆關(guān)系

設(shè)R為X到Y(jié)二元關(guān)系，假如將R中每一有序正確元素次序交換，所得到集合稱為R逆關(guān)系，簡稱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.復合關(guān)系定義設(shè)A,B,C為集合，且R是從A到B一種關(guān)系，S是從B到C一種關(guān)系，即R為A×B子集，S為B×C子集，則由R和S決定了從A到C一種關(guān)系,記作，其中={<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頁自反關(guān)系，對稱關(guān)系，傳遞關(guān)系設(shè)R為A上關(guān)系，假如對每個x

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

則稱關(guān)系R是自反.對于任意x，y

A，若當xRy時，就有yRx，即當<x,y>R時，就有<y,x>R，則稱關(guān)系R是對稱.對于任意x，y，z

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

<y,z>R時，就有<x,z>R，則稱關(guān)系R是傳遞.

第12頁例7-10設(shè)A={1,2,3},討論下列關(guān)系性質(zhì)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設(shè)A={1,2,3,4},R={<x,y>|x整除y},判斷其性質(zhì)解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>中，與結(jié)點v(v∈V)關(guān)聯(lián)邊數(shù)目(若邊是環(huán)，數(shù)目為2)，稱為結(jié)點v度數(shù)，記作deg(v).在有向圖D=<V,E>中，以結(jié)點v為起點邊條數(shù)稱為v出度；以v為終點邊條數(shù)稱為v入度;結(jié)點出度和入度之和就是該結(jié)點度數(shù).

結(jié)點度數(shù)第16頁圖連通性定義

若無向圖G是平凡圖或G中任何兩個結(jié)點之間都有一條通路，則稱G為連通圖，不然稱G是非連通圖或分離圖。

(a)連通圖

(b)分離圖(c)連通圖

第17頁定義

對有向圖D=<V,E>，有

(1)強連通圖:D中任何一對結(jié)點u,v，不但從u到v有一條通路，并且從v到u也有一條通路.(2)單向連通圖:D中任何一對結(jié)點u,v，或者從u到v有一條通路，或者從v到u有一條通路.(3)弱連通圖:D中略去邊方向，將它當作無向圖后，圖是連通.定理一種有向圖D是強連通，當且僅當圖D中有一個回路，它最少包括每個結(jié)點一次.

第18頁強連通圖強連通圖單向連通圖弱連通圖單向連通圖弱連通圖第19頁一、鄰接矩陣設(shè)G＝<V，E>是一種簡單圖，它有n個結(jié)點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頁二、關(guān)聯(lián)矩陣給定無向圖G＝<V，E>，V＝

v1，…，vn

，E＝

e1，…，em，令mij為結(jié)點vi與ej關(guān)聯(lián)次數(shù)，則稱矩陣