圖論習(xí)題ppt課件_第1頁
圖論習(xí)題ppt課件_第2頁
圖論習(xí)題ppt課件_第3頁
圖論習(xí)題ppt課件_第4頁
圖論習(xí)題ppt課件_第5頁
已閱讀5頁，還剩15頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

1、1,圖論習(xí)題課一,2,第一章 圖,3,第一章 圖,47.證明：連通圖若有兩條最長軌，則二最長軌有公共頂點。 hints：設(shè)兩最長軌無公共頂點，由于連通性，找出一條更長軌，得出矛盾。 講解下更長軌的構(gòu)造。,4,第一章 圖,典型錯誤：求的是從 到其它所有點價格總和最小 hints：Dijkstra算法,5,第一章 圖,59.船工把狼、羊、菜運(yùn)過河，每次只能運(yùn)走一宗，為了安全，不能狼與羊、羊與菜在無人看管時在一起，如何運(yùn)送最為省時。 hints：岸上不可能出現(xiàn) 狼羊菜、羊菜、狼羊；他們的余：人、人狼、人菜 也不會出現(xiàn) 從“人狼羊菜”到“空”的最短路。,6,第二章 樹,1.至少兩個頂?shù)臉淦渥铋L軌的起止

2、頂皆是葉，試證明之。 hints：,7,第二章 樹,8,第二章 樹,5.證明：樹有一個中心或者兩個中心，但有兩個中心時，此二中心是鄰頂。 證明：結(jié)論對于樹K1，K2顯然成立。 下證，對于任何一個其它的樹T，與除去T的所有度為1的頂點得到的樹T 有同樣的中心。 因為T有限，經(jīng)過有限步后，得到樹K1或K2。 且K1，K2的中心即為T的中心。 得證。,9,第三章 平面圖,10,第三章 平面圖,5.對偶圖的概念。自對偶圖：平面圖G與其對偶圖同構(gòu)。證明：,11,第三章 平面圖,12,第三章 平面圖,13,第三章 平面圖,14,第四章 匹配理論及其應(yīng)用,15,第四章 匹配理論及其應(yīng)用,2.樹上是否可能有兩個不同的完備匹配？為什么？ 解：不可能。,16,第五章 著色理論,1.求n頂輪的邊色數(shù) hints：n-1,17,第五章 著色理論,18,第五章 著色理論,19,第五章 著色理論,8. 4名老師4個班級上課問題。 計算，一天應(yīng)分幾節(jié)課？

溫馨提示

  • 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)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論