亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

問(wèn)題的提出

一筆畫問(wèn)題是柯尼斯堡問(wèn)題經(jīng)抽象化后的推廣，是圖遍歷問(wèn)題的一種。在柯尼斯堡問(wèn)題中，如果將橋所連接的地區(qū)視為點(diǎn)，將每座橋視為一條邊，那么問(wèn)題將變成：對(duì)于一個(gè)有著四個(gè)頂點(diǎn)和七條邊的連通圖G(S,E){\displaystyle G(S,E)}，能否找到一個(gè)恰好包含了所有的邊，并且沒(méi)有重復(fù)的路徑。歐拉將這個(gè)問(wèn)題推廣為：對(duì)于一個(gè)給定的連通圖，怎樣判斷是否存在著一個(gè)恰好包含了所有的邊，并且沒(méi)有重復(fù)的路徑？這就是一筆畫問(wèn)題。用圖論的術(shù)語(yǔ)來(lái)說(shuō)，就是判斷這個(gè)圖是否是一個(gè)能夠遍歷完所有的邊而沒(méi)有重復(fù)。這樣的圖現(xiàn)稱為歐拉圖。這時(shí)遍歷的路徑稱作歐拉路徑（一個(gè)環(huán)或者一條鏈），如果路徑閉合（一個(gè)圈），則稱為歐拉回路。

一筆畫問(wèn)題的推廣是多筆畫問(wèn)題，即對(duì)于不能一筆畫的圖，探討最少能用多少筆來(lái)畫成。

一筆畫定理

對(duì)于一筆畫問(wèn)題，有兩個(gè)判斷的準(zhǔn)則，它們都由歐拉提出并證明。

定理一

連通的無(wú)向圖 G{\displaystyle G} 有歐拉路徑的充要條件是：G{\displaystyle G}中奇頂點(diǎn)（連接的邊數(shù)量為奇數(shù)的頂點(diǎn)）的數(shù)目等于0或者2。

連通的無(wú)向圖 G{\displaystyle G} 是歐拉環(huán)（存在歐拉回路）的充要條件是：G{\displaystyle G}中每個(gè)頂點(diǎn)的度都是偶數(shù)。。

證明：

連通無(wú)向圖有歐拉路徑的充要條件也可以寫作“圖中奇頂點(diǎn)數(shù)目不多于2個(gè)”，這是因?yàn)槠骓旤c(diǎn)數(shù)目不可能是1個(gè)。實(shí)際上，連通無(wú)向圖中，奇頂點(diǎn)的數(shù)目總是偶數(shù)。

對(duì)于不連通的無(wú)向圖，如果有兩個(gè)互不連通的部分都包含至少一條邊，那么顯然不能一筆畫。只有當(dāng)此圖的邊全都在某一個(gè)連通部分中（即其它的連通部分都是一個(gè)個(gè)孤立的頂點(diǎn)，度數(shù)為0），并滿足連通無(wú)向圖關(guān)于一筆畫的充要條件，而該圖才能一筆畫。也即是說(shuō)，可以一筆畫的（無(wú)向）圖如果不是連通圖，就必定是一個(gè)可以一筆畫的連通圖與若干個(gè)孤立頂點(diǎn)的組合。

除了用頂點(diǎn)的度數(shù)作為判定的充要條件，還可以用圖中邊的特性來(lái)作為歐拉回路存在的判定準(zhǔn)則。連通的無(wú)向圖 G{\displaystyle G}中存在歐拉回路，等價(jià)于圖G{\displaystyle G}所有的邊可以劃分為若干個(gè)環(huán)的不交并。具體來(lái)說(shuō)，等價(jià)于存在一系列的環(huán)C1,C2,? ? -->,Cm{\displaystyle C_{1},C_{2},\cdots ,C_{m}}，使得圖G{\displaystyle G}里的每一條邊都恰好屬于某一個(gè)環(huán)。

定理二

如果連通無(wú)向圖 G{\displaystyle G} 有 2k{\displaystyle 2k} 個(gè)奇頂點(diǎn)，那么它可以用 k{\displaystyle k} 筆畫成，并且至少要用 k{\displaystyle k} 筆畫成。

證明：將這 2k{\displaystyle 2k} 個(gè)奇頂點(diǎn)分成 k{\displaystyle k} 對(duì)后分別連起，則得到一個(gè)無(wú)奇頂點(diǎn)的連通圖。由上知這個(gè)圖是一個(gè)環(huán)，因此去掉新加的邊后至多成為 k{\displaystyle k} 條歐拉路徑，因此必然可以用 k{\displaystyle k} 筆畫成。但是假設(shè)全圖可以分為 q{\displaystyle q} 條歐拉路徑，則由定理一知，每條鏈中只有不多于兩個(gè)奇頂點(diǎn)，于是 2q≥ ≥ -->2k{\displaystyle 2q\geq 2k}。因此必定要 k{\displaystyle k} 筆畫成。

有向圖的一筆畫

對(duì)有向圖來(lái)說(shuō)，一筆畫不僅指遍歷所有邊，而且要遵循正確的方向。嚴(yán)謹(jǐn)?shù)卣f(shuō)，一個(gè)連通有向圖G{\displaystyle G}有歐拉路徑，指存在一個(gè)頂點(diǎn)，從它出發(fā)，沿著有向邊的方向，可以不重復(fù)地遍歷圖中所有的邊。有向圖的歐拉回路則是指可以從某一頂點(diǎn)開(kāi)始，沿有向邊的方向不重復(fù)地遍歷所有邊，然后回到原來(lái)出發(fā)的頂點(diǎn)。用類似于定理一中證明的思路，可以得到有向圖一筆畫的判定準(zhǔn)則：

一個(gè)連通的有向圖可以表示為一條從頂點(diǎn)u{\displaystyle u}到v{\displaystyle v}的（不閉合的）歐拉路徑的充要條件是：u{\displaystyle u}的出度（從這個(gè)頂點(diǎn)發(fā)出的有向邊的數(shù)量）比入度（指向這個(gè)頂點(diǎn)的有向邊的數(shù)量）多1，v{\displaystyle v}的出度比入度少1，而其它頂點(diǎn)的出度和入度都相等。

一個(gè)連通的有向圖是歐拉環(huán)（存在歐拉回路）的充要條件是以下兩個(gè)之一：

例子

圖一：無(wú)法一筆畫

圖二：盡管按照中文書寫習(xí)慣“串”字不止一筆，但它可以一筆寫成。

七橋問(wèn)題

右圖一是七橋問(wèn)題抽象化后得到的模型，由四個(gè)頂點(diǎn)和七條邊組成。注意到四個(gè)頂點(diǎn)全是奇頂點(diǎn)，由定理一可知無(wú)法一筆畫成。

一個(gè)可以一筆畫的例子

圖二是中文“串”字抽象化后得到的模型。由于只有最上方和最下方的頂點(diǎn)是奇頂點(diǎn)，由定理一知它可以一筆畫成。

一筆畫問(wèn)題與哈密頓問(wèn)題

一筆畫問(wèn)題討論的是能否不重復(fù)地遍歷一個(gè)圖的所有邊，至于其中有否頂點(diǎn)的遍歷或重復(fù)經(jīng)過(guò)則沒(méi)有要求。哈密頓問(wèn)題討論的則是頂點(diǎn)的遍歷：能否不重復(fù)地遍歷一個(gè)圖的所有頂點(diǎn)？哈密頓問(wèn)題由哈密頓在1856年首次提出，至今尚未完全解決。

參見(jiàn)

柯尼斯堡七橋問(wèn)題

哈密爾頓問(wèn)題

樹(shù) (圖論)

中國(guó)郵遞員問(wèn)題

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請(qǐng)告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。