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

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

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