【概述】

競賽圖是一定義在有向圖上的概念，圖中每對不同的頂點(diǎn)通過單個(gè)有向邊連接，即每對頂點(diǎn)間都有一條有向邊。

設(shè) D 為 n 階有向簡單圖，若 D 的基圖為 n 階無向完全圖，則 D 為 n 階競賽圖。

簡單來說，競賽圖就是將完全無向圖的無向邊給定了方向。

競賽圖有許多性質(zhì)，比如在哈密頓問題中，對于 n 階競賽圖，當(dāng) n 大于等于 2 時(shí)一定存在哈密頓通路，關(guān)于 n?階競賽圖下構(gòu)造有向圖的哈密頓通路：點(diǎn)擊這里

【蘭道定理】

蘭道定理（Landau’s Theorem）是用來判定競賽圖的定理。

將一個(gè)競賽圖的每一個(gè)點(diǎn)的出度從小到大排序后得到的序列稱為競賽圖的比分序列

那么，蘭道定理的內(nèi)容為：

對于一個(gè)長度為 n 的序列??是合法的比分序列，當(dāng)且僅當(dāng)：，且 k=n 時(shí)，式子必須要取等

關(guān)于蘭道定理的證明：點(diǎn)擊這里

【例題】

• Football Games（HDU-5873）：點(diǎn)擊這里

?

總結(jié)

以上是生活随笔為你收集整理的图论 —— 竞赛图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。