




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、循環(huán)賽的合理排名方法171240542李博文循環(huán)賽是啥?解決此問題,需要如下五條命題命題1:循環(huán)賽構(gòu)成的圖一定是競賽圖命題2:競賽圖必定有哈密頓通路命題3:存在哈密頓通路的有向無環(huán)圖有唯一的拓撲排序命題4:競賽圖合并強連通分量后可以得到有向無環(huán)的競賽圖命題5:競賽圖中任意的強連通分量中的任意兩點在一個環(huán)上命題1:循環(huán)賽構(gòu)成的圖一定是競賽圖命題2:競賽圖必定有哈密頓通路已證明命題3:存在哈密頓通路的有向無環(huán)圖有唯一的拓撲排序引理1:有向無環(huán)圖有且僅有0或1條哈密頓通路證明:若有多條路徑,則必有如下情況:在某條路徑中,u先于v出現(xiàn),而在另一條路徑中,v先于u出現(xiàn),進而可以推出存在環(huán);引理2:若有向
2、無環(huán)圖的拓撲排序中,任意連續(xù)節(jié)點都有邊連接,則此拓撲排序為圖的一條哈密頓通路證明:根據(jù)算法導(dǎo)論引理22.11,有向無環(huán)圖的DFS結(jié)果中不存在back edge,因此任意兩個連續(xù)節(jié)點間的邊都是同一方向的,進而構(gòu)成了哈密頓通路(引理1的證明可見:/questions/32172870/multiple-hamiltonian-paths-and-topological-sorting)命題3:存在哈密頓通路的有向無環(huán)圖有唯一的拓撲排序證明:假設(shè)此結(jié)論錯誤,即存在部分有哈密頓通路的有向無環(huán)圖,該圖有多個拓撲排序。根據(jù)競賽圖的定義,任意兩個節(jié)點間都存在邊,再根據(jù)引理2,該圖有多條哈密頓通路,這與引理1矛盾。故此命題是成立。命題4:競賽圖合并強連通分量后可以得到有向無環(huán)的競賽圖命題5:競賽圖中任意的強連通分量中的任意兩點在一個環(huán)上五條命題證明完畢命題1:循環(huán)賽構(gòu)成的圖一定是競賽圖命題2:競賽圖必定有哈密頓通路命題3:存在哈密頓通路的有向無環(huán)圖有唯一的拓撲排序命題4:競賽圖合并強連通分量后可以得到有向無環(huán)的競賽圖命題5:競賽圖中任意的強連通分量中的任意兩點在一個環(huán)上循環(huán)賽排名步驟1.合并連通分量,找出無法比較名次、并列
溫馨提示
- 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)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 優(yōu)化防止返貧和低收入群體幫扶的實施路徑
- 五年級上冊美術(shù)教學(xué)設(shè)計-13 實物的聯(lián)想-蘇少版
- 備考農(nóng)業(yè)職業(yè)經(jīng)理人考試的升學(xué)規(guī)劃試題及答案
- 園藝師植物營養(yǎng)學(xué)試題及答案
- 2024農(nóng)業(yè)經(jīng)理人考試基礎(chǔ)知識試題及答案
- 備戰(zhàn)技巧2024年福建事業(yè)單位考試試題及答案
- 華大聯(lián)考試題及答案
- 掌握基礎(chǔ)花藝知識做好備考試題及答案
- 共同投資魚塘合同樣本
- 全國承包合同范例
- 病毒性腦膜炎護理
- 高中名著導(dǎo)讀社團課《紅與黑》 課件
- 洗煤廢水處理及回用工藝的設(shè)計計算-畢業(yè)設(shè)計
- 2023年四川省內(nèi)江市中考物理試卷
- 信陽職業(yè)技術(shù)學(xué)院單招《職業(yè)技能測試》參考試題庫(含答案)
- 國旗護衛(wèi)工作總結(jié)
- 人教版五年級數(shù)學(xué)下冊全冊分層作業(yè)設(shè)計含答案
- 冠心病合并糖尿病課件
- 裝卸作業(yè)安全培訓(xùn)課件
- 2022撬裝式承壓設(shè)備系統(tǒng)制造監(jiān)督檢驗技術(shù)導(dǎo)則
- 高考化學(xué)二輪復(fù)習(xí) 題組14 化學(xué)用語練習(xí)(含解析)-人教版高三化學(xué)試題
評論
0/150
提交評論