離散數(shù)學(xué)-3-11相容關(guān)系.ppt

《離散數(shù)學(xué)-3-11相容關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-3-11相容關(guān)系.ppt（12頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1,第三章集合與關(guān)系,3-11相容關(guān)系授課人：李朔Email:chn.nj.ls@,2,一．相容關(guān)系,與等價(jià)關(guān)系類似，另一類應(yīng)用非常廣泛的關(guān)系，就是相容關(guān)系。P135定義3-11.1給定集合A上的關(guān)系r，若r是自反的，對(duì)稱的，則稱r是A上的相容關(guān)系。例如：設(shè)A是由下列英文單詞組成的集合。A={cat,teacher,cold,desk,knife,by}。定義關(guān)系：r={?x,y?A且x和y有相同的字母}。易見r是自反，對(duì)稱的。因此r為相容關(guān)系。設(shè)x1=cat,x2=teacher,x3=cold,x4=desk,x5=knife,x6=byr的關(guān)系矩陣如下：,3,一．相容關(guān)系,由于r是對(duì)稱的，因此r的關(guān)系矩陣也是對(duì)稱矩陣，因此，對(duì)相容關(guān)系，其關(guān)系矩陣只需寫出下三角部分即可（簡(jiǎn)化矩陣，P136表3-11.1)。至于關(guān)系圖，因r是自反和對(duì)稱的，故每個(gè)結(jié)點(diǎn)都有環(huán)，且任兩點(diǎn)若有連線，必有雙向線，因此，大家約定。對(duì)相容關(guān)系，在畫圖時(shí)，不畫每個(gè)元素的環(huán)，同時(shí)對(duì)每對(duì)雙向線，只畫出單線，這樣就更加簡(jiǎn)潔直觀，如上例，關(guān)系圖可表示如上右圖.,,,4,二．相容類,P136定義3-11.2設(shè)r是集合A上的相容關(guān)系，若C?A，且對(duì)于C中任兩個(gè)元素a1,a2有a1ra2，則稱C是由相容關(guān)系r產(chǎn)生的相容類。例如上例的相容關(guān)系r可產(chǎn)生相容類。{x1,x2},{x1,x3},{x2,x3},{x6},{x2,x4,x5}。對(duì)于前三個(gè)相容類，都能加入新的元素組成新的相容類，而對(duì)于后兩個(gè)相容類，加入任一新元素，就不再成為相容類，我們稱它們?yōu)樽畲笙嗳蓊?。P137定義3-11.3設(shè)r為集合A上的相容關(guān)系，不能真包含在其它相容類中的相容類。稱作最大相容類，記作Cr。若Cr為A上最大相容類，顯然它是A的子集，對(duì)任何x?Cr，x必與Cr中的所有元素有相容關(guān)系.而在A－Cr中沒有任何元素與Cr中所有元素有相容關(guān)系。,5,二．相容類,在相容關(guān)系圖中，最大完全多邊形的頂點(diǎn)集合，就是最大相容類。所謂完全多邊形，就是其每個(gè)頂點(diǎn)都與其它頂點(diǎn)連接的多邊形，例如一個(gè)三角形是完全多邊形，一個(gè)四邊形再加兩條對(duì)角線就是完全多邊形。此外，在相容關(guān)系圖中，一個(gè)孤立點(diǎn)，以及不是完全多邊形的兩個(gè)結(jié)點(diǎn)的連線，也是最大相容類。,,6,二．相容類,P137例：給定相容關(guān)系圖寫出最大相容類。解：最大相容類為：{x1,x2,x4,x5},{x3,x4,x6},{x4,x5},{x7}:,,7,二．相容類,P137定理3-11.1設(shè)r是有限集A上的相容關(guān)系，c是一個(gè)相容類，那么必存在最大相容類Cr使c?Cr。證明：設(shè)A＝{x1,x2,?,xn}，構(gòu)造相容類序列C0?C1?C2??，其中C0=c且Ci+1=CiU{xj}，其中j滿足xj?Ci且xj與Ci中各元素都相容的最小足標(biāo)。由于?A?=n，故至多經(jīng)n-?c?步，過程將終止，此時(shí)序列中最后一個(gè)相容類，即為所求。由上可見，A中任一元a，可組成相容類{a}，而它必包含在一個(gè)最大相容類Cr中，因此，由最大相容類構(gòu)成一個(gè)集合，則A中每一個(gè)元素至少屬于該集合的一個(gè)成員中，即是說，最大相容類的集合必然構(gòu)成集合A的一個(gè)覆蓋。,8,三．完全覆蓋,P138定義3-11.4在集合A上給定相容關(guān)系r，其最大的相容類集合稱為A的一個(gè)完全覆蓋，記Cr(A)。注意到集合A的覆蓋不是唯一的，因此給定相容關(guān)系r，可以作成不同的相容類集合，它們都是A的覆蓋。但是，給定相容關(guān)系r,只能唯一對(duì)應(yīng)一個(gè)完全覆蓋。如上例：{{x1,x2,x4,x5},{x3,x4,x6},{x4,x5},{x7}}反過來，下面討論由覆蓋如何決定一個(gè)相容關(guān)系。,9,三．完全覆蓋,P138定理3-11.2給定集合A的覆蓋{A1,A2,?,An}。由它確定的關(guān)系：R=A1?A1?A2?A2???An?An是A上相容關(guān)系。證明：因A＝。對(duì)任一x?A，必存在某個(gè)j>0，使x?Aj，故?Aj?Aj，即?R。因此R是自反的。其次，若x,y?A且?R，則有某個(gè)j>0使?Aj?Aj，故?Aj?Aj。即?R。故R是對(duì)稱的。因此R是A上的相容關(guān)系。,,10,三．完全覆蓋,從上述可見，給定集合A上的任一個(gè)覆蓋，必可在A上構(gòu)造對(duì)應(yīng)于此覆蓋的一個(gè)相容關(guān)系。但是不同的覆蓋卻能構(gòu)造相同的相容關(guān)系。例：A＝{1,2,3}集合{{1,2,3},{3,4}}和{{1,2},{2,3},{1,3},{3,4}}都是A的覆蓋，但它們可以產(chǎn)生相同的相容關(guān)系。R＝{,,,,,，,,,,,}但對(duì)完全覆蓋有：定理3-11.3集合A上相容關(guān)系r與完全覆蓋存在一一對(duì)應(yīng)。證明：略,,11,本課小結(jié),相容關(guān)系相容類完全覆蓋,12,作業(yè),P139(6),