圖的對集與獨立集_第1頁
圖的對集與獨立集_第2頁
圖的對集與獨立集_第3頁
圖的對集與獨立集_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、CH5 圖的對集與獨立集圖的對集與獨立集 1 二分圖二分圖 例： 人員分配問題，某公司分配個 工人做 件工作。代表人的一組頂點用 表示，代表工作的一組頂點 用表示。 與 相鄰當且僅當工人 能做工作 ，從而 之間(Y 之間)無邊。所得圖稱為二分圖 。nmnxxxX,2112,mYy yyXjyixixjy 一、一、 二分圖定義二分圖定義 定義定義1： 的二分劃 ，即使 的每條邊的兩個端點一個在 中，另一個在 中。則稱 是二分圖， 稱為 的二分劃，記為 。VYXYXGVYX,),(GYX ,G);,(EYXG XYYX ,G返回 結(jié)束例 1v2v3v1u2u3u是二分圖， 123 ,Xv v v1

2、23, ,Yu u u1v2v3v1u2u3u一些等價刻劃圖 是二分圖當且僅當存在頂點集合的二分劃 ，使 為空圖； 當且僅當 不含長為奇數(shù)的回路； 當且僅當 的所有非平凡子圖是二分圖。 GYX,YGXGGG 的一個回路為若 ，則 類似有所以而 ，故 是偶數(shù)。G34,uX uY1uX212,lluX uYkuY122u uEuY121kCu uu uk利用第二個等價刻畫即可。返回 結(jié)束例 3,4K定義定義2 2 二分圖 );,(EYXG 中， ,xX yY 都有( )xyE G，則稱 );,(EYXG 是完全二分圖 。);,(EYXG |,|,Xn Ym,n mK。若也記為 二、二、 簡單性質(zhì)簡單性質(zhì) 是二分圖。 1、若 ，則 不是H-圖。 證證：不妨設(shè) ，則 故 不是H -圖。);,(EYXG |YX XSYX|,|)()(SXYXGwSGw);,(EYXG );,(EYXG 返回 結(jié)束考慮 的邊數(shù)？,n mKnm 2、 3、若 是 正則二分圖，則 。 證證： 。 ) 1(kk|YX |)(YXYkXkGq(, ;),( )( )( )x Xy YGX Y Eq Gd xd y則。);,(EYXG 返回 結(jié)束1xmy3y2y1yn

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論