【正文】 想 從任一點出發(fā)按下法來描畫一條邊不重復(fù)的跡，使在每一步中未描畫的子圖的割邊僅當(dāng)沒有別的邊可選擇時才被描畫。 (2) 對一般圖，其解法為：添加重復(fù)邊以使 G成為歐拉圖 G*， 并使添加的重復(fù)邊的邊權(quán)之和為最小，再求 G*的歐拉回路。 問題 ： 郵遞員從郵局出發(fā)，遞送郵件，然后返回郵局，要求轄區(qū)每條街至少走一遍且走過的總路程最短，應(yīng)如何選擇路線？ 圖論模型： 在一個連通的具有非負權(quán)的賦權(quán)圖 G中找一條包含每條邊（允許重復(fù)）且邊權(quán)之和最小的閉途徑 .稱之為 最優(yōu)環(huán)游 。 布魯因序列 . 000 100 010 001 101 110 011 111 a b c d e f g j k l m n i p q h 弧 a = (0000) b = (0001) c = (0010) d = (0101) e = (1010) f = (0100) g = (1001) h = (0011) i = (0110) j = (1101) k = (1011) l = (0111) m = (1111) n = (1110) p = (1100) q = (1000) (abcdefghijklmnpq……) = (0000101001101111……) 歐拉閉跡和相應(yīng)的 德 布魯因序列 S. 例 下圖為 k = 4 (τ=24=16) 的 德 (2) H有 2k條弧，若以每一條由點（ b1,b2,…, bk1）到點（b2,b3,…, bk）的弧 a代表一個 k元組（ b1,b2,…, bk），便可得2k個不同的 k元組。 說明： (1) H 的每一點 v，有 d+(v) = d (v) = 2，且是連通的從而 H是歐拉有向圖 , 稱為 德 對點 v = (b1,b2,… ,bk1) ， 用兩條弧分別將 v聯(lián)到點 v1 = (b2,b3,…b k1,0) 和 v2.= (b2,b3,…, bk1,1), 得有向邊 〈 v, v1〉 和 〈 v, v2〉 。 0 1 1 0 1 1 0 0 德 布魯因序列 S. 例 1 設(shè) k =3， 則 τ= 23= 8， 這 8個不同的 3部分序列為 : （ 000） (001) (010) (101) (011) (111) (110) (100) 相應(yīng)的德 布魯因（ De， Bruijn） 序列 : 指對于固定的正整數(shù) k的具有最大 τ的一個（ 0,1）周期序列 S ，它使得 S 的k部分序列 S1,S2,… ,Sτ 均不相同。如果鼓輪沿順時針方向旋轉(zhuǎn)一段，讀數(shù)將是（ 1001）。絕緣段給出信號 0（沒有電流），導(dǎo)通段給出信號 1（有電流）。 高效率計算機鼓輪的設(shè)計 計算機中旋轉(zhuǎn)鼓輪的位置是借助于鼓輪表面上的一系列電觸點所產(chǎn)生的二元信號來識別的。 （ 3） D的弧集可劃分為有向圈。 定理 3 下列陳述對于一個連通有向圖 D是等價的： （ 1） D是歐拉有向圖。 綜上 ,推論結(jié)論成立 . 由以上討論我們還有： 1. 圖 G 有歐拉跡 G 能 “一筆畫” G 連通且 G 中奇點數(shù)不超過 2 2. 若奇點數(shù)為 0, 則一筆畫與起點無關(guān) 。在 u和 v間添加新邊 e 得圖 G + e, 則 G + e 沒有奇點。顯然， C + e是一條 Euler閉跡 ,則由已證結(jié)論， C + e有零個奇點 ,從而 C,即 G有兩個奇點。 證明 定理 1表明： G有 Euler閉 跡當(dāng)且僅當(dāng) G有 零 個奇點。繼續(xù)這個過程，我們可以構(gòu)成一條含有 G的所有邊的閉跡；從而 G是歐拉圖。若 G僅由 Z1組成，則 G顯然是歐拉圖。當(dāng)該過程終止于空圖 Gn時，我們就得到了將 G的邊分成若干圈的一個劃分。移去 Z的各條邊產(chǎn)生一個生成子圖 G1， 其中每個點的度仍然是偶數(shù)。 C中任一個給定的點在 C中每出現(xiàn)一次恰關(guān)聯(lián)兩條邊，因為 G的每條邊在 C中僅出現(xiàn)一次，所以該點的度應(yīng)為該點在 C中出現(xiàn)的次數(shù)乘以 2, 是一個偶數(shù)。 (3) G的邊集能劃分為圈。 （ a） （ f） （ e） （ d） （ c） （ b） 例 1 定理 1 下列陳述對于一個連通圖 G是等價的： (1) G是歐拉圖。 上圖中，（ a） ,（ f） 是歐拉圖；（ b） , (d) 有歐拉跡但不是歐拉圖 。經(jīng)過 G的每條邊的 (閉 )跡被稱為 Euler(閉 )跡 ，存在 Euler閉跡 的圖稱為 歐拉圖 ,簡稱 E 圖。第四章 歐拉圖與哈密爾頓圖 167。 歐拉圖 定義 1 設(shè) G 是無孤立點的圖。 Euler閉跡又稱為Euler環(huán)游。（ c） 和（ e） 無歐拉跡。 (2) G的每個點的度是偶數(shù)。 令 C是 G中的一條歐拉閉跡。 證明 (1) (2) 因為 G連通非平凡，故每個點的度至少是 2，所以 G含有一個圈 Z (見習(xí)題 1,12)。若 G1沒有邊，則（ 3）已經(jīng)成立；否則，重復(fù)應(yīng)用這種論證于 G1， 產(chǎn)生一個圖 G2， 其中所有的點的度仍然是偶數(shù)，等等。 (2) (3): (3) (1) : 令 Z1是這個劃分的一個圈。否則，有另外一個圈 Z2與 Z1有一個公共點 v， 從 v開始并且由 Z1和 Z2相連組成的通道是含有這兩個圈中各條邊的一條閉跡。 推論 連通圖 G 有 Euler跡當(dāng)且僅當(dāng) G最多有兩個奇點。 若連通圖 G有 Euler非閉跡 C,并設(shè)點 u和 v分別是 C的起點和終點 .記在 C中添加一條連接 u和 v的新邊 e后所得到的圖為 C + e。 反之，設(shè) G是恰有兩個奇點 u 和 v 的連通圖。由已證結(jié)論 , G + e有 Euler閉跡 , 從而 G 有 Euler跡。 若奇點 數(shù)為 2, 則一筆畫的起點與終點均為奇點 . 3. 在有向圖（即每條邊均為有向邊的圖，其系統(tǒng)討論將在第九章進行）中有類似結(jié)論 . 有向圖 D中，以一點 u為起點的?。从邢蜻叄┑臄?shù)目稱為 u的出度，記為 dD+(u)； 以一點 u為終點的弧的數(shù)目稱為 u的入度，記為 dD (u)。 （ 2） D的每個點的入度等于出度。 例 歐拉有向圖 : 167。這個表面分為 m段，每段由絕緣體或?qū)w材料組成。 0 0 1 0 0 1 0 觸點 例如， 圖中，鼓輪的位置由四個觸點給出讀數(shù)（0010）。 1. S的周期 : S中對任何正整數(shù) n,具有 an+ τ = an的最小的正整數(shù) τ. 問題 為提高效率 ,我們期望鼓輪每旋轉(zhuǎn)一周 (m段 )讀出的由 k位組成的 m個數(shù)應(yīng)是 互不相同 的 . 進一步 ,對故定的 k,最大的 m應(yīng)是多少 ?如何構(gòu)造這樣的鼓輪 ? 涉及該問題的數(shù)學(xué)模型的幾個概念 : 設(shè) S = (a1,a2,…, a n ,…) 為（ 0,1）無限序列 . 2. S的 k部分序列 S1, S2, … : 是由 S中相繼 k個元素組成的 k元組作為元素組成的序列 , 即 S1=(a1, a2,… ,ak), S2=(a2, a3,… ,ak+1), … 3. 德 易知 , 不同的 k 元 (0,1) 序列 Si 恰有 2k 個，即 τ=2k 上問題的數(shù)學(xué)模型 : 對于固定的 k，求德 布魯因序列是 S = (0001011100010111……) 把這個序列的前 8位排成一個圓圈，與所求的鼓輪相對應(yīng)，就得到下圖的鼓輪設(shè)計。 布魯因序列的構(gòu)造 : 步驟 1 構(gòu)造一個有向圖 H: 它的點是 2k1個不同的有序 (k1)元組。當(dāng)然，上述的點 v = (b1,b2,… ,bk1) 也有兩條由點 u1和 u2的指向 v的邊聯(lián)接，其中 u1 = (0,b1,b2,… ,bk2) ，u2 = (1,b1,b2,…, bk2) 。 布魯因圖 。 步驟 2 求 H的歐拉有向閉跡 , 由此得 k部分序列 S1,S2,… ,Sτ 和相應(yīng)的德 布魯因圖 , 相應(yīng)的歐拉有向閉跡及相應(yīng)的德 布魯因序列 該例有 16個解，其中的一些為 (abcdkijefjhlmnpq……) = (0000101101001111……) (abcdkipghlmjefq……) = (0000101100111101……) (abcfgijedklmnpq……) = (0000100110101111……) (abhijklmnpgcdefq……) = (0000110111100101……) (abhijedklmnpgcfq……) = (0000110101111001……) (abhijefgcdklmnpq……) = (0000110100101111……) (abhipgcdklmnjefq……) = (0000110010111101……) 167。 對該問題 (1) 若圖 G是一個歐拉圖，則找出 G的歐拉回路即可。 (3) 對恰有兩個度數(shù)為奇的點的圖 G， 可證：需要重復(fù)的邊正好是從一個奇度點到另一個奇度點的最短路上的邊，即問題為歐拉問題與最短路問題的綜合。 Euler圖中確定 Euler環(huán)游的 Fleury算法 Fleury算法 1. 任意選取一個頂點 v0，置 w0= v0。 3. 當(dāng)?shù)?2步不能再執(zhí)行時，算法停止。 例： 某博物館的一層布置如下圖，其中邊代表走廊，結(jié)點e是入口，結(jié)點 g是禮品店，通過 g我們可以離開博物館。 a f e d c b i h g j 解： 圖中只有兩個奇度頂點 e和 g,因此存在起點為 e,終點為 g的歐拉跡。 ( ) ( ) ?iiG e G???? 所以 Fleury算法時間復(fù)雜性是： O(n2m), 是好算法。任意添一些邊得到一個歐拉多重圖 (b)。 (c)中每一個圈中重復(fù)邊的數(shù)目均不大于圈長的一半 .從而，由 (c)中每條歐拉閉跡對應(yīng)原圖一條閉通道，它含有所有的邊且具有最短的長度。 哈密 爾 頓圖 經(jīng)過圖中每個點僅一次的路（圈）稱為的 Hamilton路 (圈 )，存在 Hamilton圈的圖稱為 哈密爾頓圖 ，簡稱 H圖 。 只有哈密爾頓路，但不是哈密爾頓圖 哈密爾頓圖 無哈密爾頓路 例如 證明 設(shè) C 是 G 中一條 哈密爾頓圈。由點不重復(fù)的圈的特性知任意刪去 C 中 | S | 個 點，最多將 C 分為 | S | “段 ” ，即