歐拉圖與哈密爾頓圖

Euler圖

定義

• 經(jīng)過G的每條邊的跡被稱為歐拉跡

  • 跡的邊，每個邊只出現(xiàn)一次，但是點不一定，可以多次

• 能夠閉合的跡被稱為閉跡

• 存在歐拉閉跡的圖稱為歐拉圖
• 歐拉閉跡又稱為歐拉回路

歐拉圖等價性質

• 圖G的每個點的度都是偶數(shù)

  • 證明：令C為G中的一條歐拉回路，G中任一個給定的點在C中每出現(xiàn)一次恰好關聯(lián)兩條邊，因為G的每條邊在C僅出現(xiàn)一次，所以該點的度為該店在C中出現(xiàn)的次數(shù)的兩倍，是偶數(shù)

  • 推論：連通圖G有歐拉跡當且僅當G最多有兩個奇點

    • 證明：顯然，G有歐拉閉跡時當且僅有0個奇點。而若G有歐拉非閉跡，并設點u和v分別是C的奇點和終點，記在C中添加一條連接u和v的邊e后所得到的圖為C+e，顯然，C+e是一條歐拉閉跡，則由已知結論可知，C+e有0個奇點，所以C有兩個奇點。反之，設G是恰有兩個奇點u和v的連通圖，在u和v之間添加新邊e得圖G+e，則G+e沒有奇點，由已知結論，G+e有歐拉閉跡，所以G有歐拉跡，綜上，結論成立

• 圖G的邊集能劃分為邊不重的圈的并

  • 由上一個性質來證明該性質，當G的邊數(shù)為1時，G只能是自環(huán)，結論顯然成立。假設G的邊數(shù)大于1，從任意一點出發(fā)，尋找一條通路直到某一個頂點再次遇到，假設為v，則v到v的通路構成一個圈。從G中移除得到的圈，則得到的每個連通分支是一個滿足條件，邊數(shù)較少的圈。
  • 可以想象，一個大圈，被擰巴成那種麻花，成了幾個小圈

一筆畫

• 多少筆畫完取決于有多少對奇點

• 若G有2k個奇度頂點，則存在k條邊不重的跡Q1,Q2...Qk使得E(G)=E(Q1)∪E(Q2)∪...∪E(Qk)

  • 證明：只就連通圖進行證明，對2k個奇點，兩兩配對且不相鄰，添加k條新的邊，從而G‘變成了歐拉圖，G’存在歐拉回路C，在C中刪除剛才新加的邊，得k個邊不重的跡Qi，從而得證

一些性質(例題)

• 若G是非平凡的歐拉圖，則G的每個塊也是歐拉圖

  • 證明：設B是G的任意一個塊，C是G的一個歐拉回路，從B的某一點v出發(fā)，沿著C前進，由塊的定義知，歐拉回路C只有經(jīng)過G的割點才能離開B，也只有經(jīng)過同一割點才能回到B中，我們將C中不屬于B的那些邊去掉，得到一個回路，該回路經(jīng)過了B的每條邊，因此，該回路是B的歐拉回路，所以B是歐拉圖。

• 若G和H是歐拉圖，則GxH是歐拉圖

  • 首先GxH是積圖的意思，(x,y)，新圖中相連必須一個坐標相等，另外一個相連
  • 證明要從（度數(shù)偶數(shù)，連通圖來入手）

  • 度數(shù)偶數(shù)：對于任意u∈V(G)，v∈V(H)，必有

    • 如此便能得到積圖度數(shù)為偶數(shù)

  • 其次，GxH必為連通圖，對任意頂點(u1,v1)∈V(GxH)，(u2,v2)∈V(GxH)，它們之間必存在一條通路，由于G是歐拉圖，則G必為連通圖，因此，在G中存在一條連接u1和u2的路(u1,x1,x2,...xp,u2)，同理在H中存在一條連接v1和v2的路(v1,y1,y2,...,yq,v2)，所以GxH中存在一條連接(u1,v1)和(u2,v2)的路(u1,v1)(x1,v1)...(xp,v1)(u2,v1)(u2,y1)(u2,y2)...(u2,yq)(u2,v2)

  • 綜上，GxH是每個頂點度數(shù)為偶數(shù)的連通圖，所以GxH是歐拉圖

• G是非平凡的歐拉圖，且v∈V(G)，G的每條以v為起點的跡都能擴展成G的歐拉回路當且僅當G-v為森林

  • 擴展的意思是從跡的終點繼續(xù)走下去，延伸
  • 森林，就是無圈圖

  • 必要性：若不然，G-v包含圈C，考慮G1=G-E(C)的包含頂點v的連通分支H，由于G是歐拉圖，則G的每個頂點度數(shù)為偶數(shù)，圈C的每個頂點度數(shù)為偶數(shù)，所以G1的每個頂點的度數(shù)都是偶數(shù)，從而H是頂點度數(shù)都是偶數(shù)的連通圖，H是歐拉圖。設T為H的歐拉回路，則T可以看做是圖G的以v為起點與終點的一條跡。這里可以證明T與C不相交，且圖G與v關聯(lián)的邊都在T中。假設T與C相交，即有公共邊，則在G-E(C)時就會將其刪掉，則不可能再H中構成回路，所以T與C不相交；同時，圈C是由G-v得到，所以與v相關聯(lián)的邊一定不在圈C上，然后與v關聯(lián)的邊一定出現(xiàn)在v所在的連通分支上，不出現(xiàn)在其他連通分支上，這顯然，所以一定在T中。此時，與v關聯(lián)的邊都在T中，無法繼續(xù)走下去，所以無法擴展，所以矛盾，所以G-v一定不包含圈，所以G-v是森林

    • 一句話：反證，點v除了在圈中，不和剩余部分相連，所以矛盾

  • 充分性：若不然，則設Q=(v,w)是G的一條不能擴展為G的歐拉回路的最長的跡。首先，v=w，即Q是一條閉跡，否則，v和w是G-Q僅有的兩個奇度點，從而，G-Q中存在以w為奇點，v為終點的跡P，因此，跡Q可以通過P繼續(xù)擴展，所以Q必須是閉跡。其次，Q包含與v關聯(lián)的所有邊，否則，Q還可以延長。所以，G-v包含包含G-Q的所有邊，且G-Q的每個頂點的度數(shù)都是偶數(shù)。所以G-Q的非平凡連通分支是歐拉圖，所以存在圈，所以G-v中也存在圈，這和充要條件G-v是森林矛盾，故充分性證閉。

    • 一句話，反證，最長的跡時閉跡，推導出G-v也是度數(shù)為偶數(shù)的圖，存在圈

Fleury算法

• 描畫一條邊不重復的跡，割邊在沒有其他選擇時才會被描畫

• 目的：找歐拉圖的歐拉回路

  • 對于半歐拉圖的歐拉跡也可以，因為它和歐拉圖也就差了一條邊，填上這條邊，就可以用fleury算法尋找歐拉回路，刪掉添的邊，就成了歐拉跡

• 算法過程

  • 每次在當前軌跡的終點選擇邊，從當前可選邊的非割邊中任意選一條邊，然后繼續(xù)走下去，若只有割邊，那就只能選割邊往下走了

中國郵遞員問題

問題描述

• 從某點出發(fā)，每條邊至少走一遍，回到該點，總路程最小
• 不一定是歐拉回路，因為有的路是重復走的，歐拉回路中每條路都是只走一次的

• 該問題的圖論模型：在一個連通的具有非負權的賦權圖G中找一條包含每條邊(允許重復)且邊權之和最小的閉途徑，稱之為最優(yōu)環(huán)游

  • 若圖G是歐拉圖，則直接找出G的歐拉回路即可
  • 若圖G是一般圖，其解法為：添加重復邊使G成為歐拉圖G‘，并使添加的重復邊的邊權之和最小，再求G’的歐拉回路

定理：假定G‘是在圖G中添加一些重復邊得到的歐拉圖，則G’具有最小權值的充要條件是：（1）G的每一條邊最多被添加一次（2）對于G‘的每個圈來說，新添加的邊的總權值不超過該圈總權值的一半

• 必要性：若G中某條邊在G’中被添加的次數(shù)超過1，則去掉其中兩條重復邊，將得到一個總權值更小，且以G為子圖的歐拉圖。所以每條邊最多被添加一次。假定G‘中存在某個圈使得新添加的邊的總權值大于該圈權值的一半，設該圈為C，那么在G’中，將C上新添加的邊全部去掉，然后將原來的每條邊都添加一次，這樣就能夠得到總權值更小的以G為子圖的歐拉圖，所以（2）需要滿足
• 充分性：要證明，滿足兩個條件的任意兩個圖都有相同的總權值。設Y1與Y2分別表示G1與G2中添加的邊的集合，令Y是Y1和Y2的非公共部分。G[Y]的每個頂點的度數(shù)必為偶數(shù)(可證明，這里不證明)，由此，G[Y]的每個分支都是歐拉圖，可以做圈分解，對于每個圈，其添加的權值都相等(可證明，這里不證明)。由此，可證得G1和G2有相同的權值。（這里兩個可證明而不證明的地方，因為證明內(nèi)容太長，所以就暫時不寫了，考到的可能性比較低）

非歐拉圖求最優(yōu)環(huán)游方法

• 用每條邊最多添加一次的方式去任意添加一些重復邊是圖G稱為一個歐拉多重圖G‘
• 考察G’的圈，若存在圈C，其中重復邊的總權值大于該圈權值的一半，則再圈C上交換重復邊和不重復邊得到一個新的歐拉多重圖。重復這個過程，直到滿足不大于一半
• 用Fleury算法來求G‘的歐拉回路

最優(yōu)環(huán)游例題解決

• 如果一個賦權圖G中只有兩個奇度頂點u和v，設計一個求其最優(yōu)歐拉環(huán)游的算法

  • 在u和v之間求出一條最短路P，在最短路P上，給每條邊添加一條平行邊得到G的歐拉多重圖G’，在歐拉多重圖G‘中用Fleury算法求出一條歐拉回路

E圖與H圖

線圖L(G)

• V(L(G))=E(G)
• (e1,e2)∈E(L(G))當且僅當e1與e2相鄰

• n次迭線圖

  • 線圖的線圖，n-1次迭代

線圖的性質

• 線圖L(G)的頂點數(shù)等于G的邊數(shù)
• 若e=uv是G的邊，則e作為L(G)的頂點，度數(shù)為

• 若G有n個點，m條邊，則線圖L(G)的邊數(shù)為

  • 證明，對于G中任一頂點v，關聯(lián)于該頂點的d(v)條邊在L(G)中產(chǎn)生的邊數(shù)為d(v)(d(v)-1)/2（兩兩相鄰的頂點），求和便是該結果

• 一個圖同構與它的線圖，當且僅當它是圈

• 若圖G1和G2有同構的線圖，則除了一個是K3另一個是K1,3外，G1和G2同構

n次細分圖

- 只將G的每條邊都插入n個2度頂點，迭代n次（符號Sn）

定理：（1）若G是E圖，則L(G)既是E圖又是H圖（2）若G是H圖，則L(G)是H圖

• （1）因為G是E圖，所以每個點的度數(shù)是偶數(shù)，然后線圖的每個點度數(shù)都是偶數(shù)，連通，所以線圖是E圖。沿著歐拉圖的歐拉回路走一圈，就是線圖的H圖
• （2）不會，不管了···

一個圖G是E圖的充要條件是L3(G)為H圖

若G是具有n個點m條邊的非平凡連通圖，且不是一條路，則k≥n-3時，圖Lk(G)是H圖

TSP問題

問題描述：完全圖，恰好遍歷每個點，返回，且最終總路程最短

圖論模型：在賦權完全圖G中求具有最小權的哈密爾頓圈，即最優(yōu)圈

邊交換技術

• 權重小的邊去替換權重大的邊
• 選出的邊是要交叉的
• 得到的結果是近似最優(yōu)解
• 可以通過幾個不同的初始圈開始，通過邊交換技術得到幾個近似的最優(yōu)解，然后選其中最好的

最優(yōu)圈的下界

• 方法：在G中任意刪掉一點得圖G1，在圖G1中求出一棵最小生成樹T，在v的關連邊中選出兩條權值最小者e1和e2，若C是G的最優(yōu)圈，則W(C)≥W(T)+W(e1)+W(e2)
• 關于那個例題，三角不等式的，還是比較好理解的，通過最小生成樹的歐拉圖來構建H圈那個，ppt上說的是從第三個點開始刪點，這個很不好理解，視頻上說是沿著T1的歐拉圈來構建H圖，是通過每遍歷一個新的點，就加進路徑，這樣例如v1,v2,v3,v4,v5,v6,v1就是H圈，結合三角不等式，一定比最小生成樹的歐拉圈權值要小，即最小生成樹權值的兩倍

度極大的非哈密爾頓圖

概念

• 度極大非H圖

  • 非H圖
  • 度不弱于其他非H圖
  • 度弱是度序列排序后比較第i個大小

• Cm,n圖

  -

  - 可以展開
  

• 有必要說，1≤m<n/2

• 理解其生成規(guī)則：左邊m個孤立點，中間一個Km完全圖，右邊一個Kn-2m的完全圖，中間分別和左右做聯(lián)運算，即每個點都與左右兩邊的點連接

  -

• Cmn的度序列是什么樣的呢

  • (m,...m,(m個),n-m-1...n-m-1(n-2m個),n-1...n-1(m個))
  • 挺好理解的

• Cmn圖不是H圖

  • 如果刪去中間m個頂點，刪去它們，會得到m+1個連通分支，這不符合H圖的性質3，所以其不是H圖

• Cmn圖對于任意兩個不相鄰的頂點，添加一條邊，則會成為H圖

  • 故，Cmn圖是極大的非H圖

• 定理：(Chvatal) 若G是n≥3的非H簡單圖，則G度弱與某個Cmn圖

  • 用度序列判定定理的逆否命題來證明即可
  • Cmn圖族中每個圖都是某個n階非簡單圖的極圖
  • 如果n階簡單圖G度優(yōu)于所有的Cmn圖族，則G一定是H圖

  • 定理的條件是必要條件而非充分條件

    • 比如5階圈C5，度弱于C2,5，但它還是H圖

  • 即：非H圖，一定度弱于Cmn圖族中的某個，度優(yōu)于所有Cmn圖族一定是H圖。

    • 除此之外，別無它意
    • 所以，用該定理來判斷H圖時，寫出G(n)的度序列，再寫出所有的Cmn圖族度序列，如果度優(yōu)于所有，則它是H圖，否則不能判斷

  • 推論：G為n階簡單圖，若n≥3且滿足下面條件，則其一定為H圖

    • 則可以得到非H圖的邊數(shù)上限
    • 滿足邊數(shù)如此的非H圖只有C1,n和C2,5
    • 證明：若不然，由Chvatal定理，G一定度弱于Cm,n，計算Cmn，他是小于等于上面的一串的，所以|E|也小于那一串，和條件中大于那一串矛盾
    • 只是充分條件，非充要

• 哈密爾頓圖

  定義

  • 經(jīng)過圖G中每個點的路稱為哈密爾頓路，H路
  • 經(jīng)過圖G中每個點的圈稱為哈密爾頓圈，H圈
  • 存在哈密爾頓圈的圖稱為哈密爾頓圖，H圖

  性質

  • 性質1：如果二部圖G是哈密爾頓圖，則它的二部劃分(X,Y)滿足|X|=|Y|

  • 性質2：若G1和G2是H圖，則G1xG2是H圖

    • 證明：G1的H圈為u1u2...upu1，G2的H圈為v1v2...vqv1，分為奇數(shù)和偶數(shù)來討論

    - 奇數(shù)與偶數(shù)的區(qū)別在于遍歷到每個點的順序不一樣，因為要從(u1,v1)點出發(fā)，你需要最終到達(up,v1)或者(u1,vq)才可，不然的話是構不成圈的，而因為奇偶的問題，到這從(u1,v1)到達(up,v1)和(u1,vq)的路線不同，所以需要分類來討論，這里都是偶數(shù)為行，奇數(shù)為列來排列點

    -

  • 性質3（定理）：若G是H圖，則對于V的每個非空真子集S，均有ω(G-S)≤|S|

    • 證明：設C的H圈。對V的任意非空子集S，易知ω(C-S)≤|S|(這是圈嘛)。C是G的生成子圖，生成子圖肯定沒有原圖結構牢靠一些，所以ω(G-s)≤ω(C-S)，所以得證
    • 這只是必要條件，不是充分條件，即H圖都具有這個性質，但是滿足該條件不一定是H圖
    • 彼得森圖不是H圖，但滿足定理
    • 可以用于判斷某圖不是H圖
    • 對這個定理，可以將S設為一點x，則ω(G-x)≤|x|=1，則ω(G-x)=1，則說明哈密爾頓圖沒有割點

  • 性質4：若連通圖不是2-連通的，則G不是H圖

    • 證明：若連通圖不是2-連通的，所以其一定是1連通的，所以存在割點，假設割點為v，所以ω(G-v)=2>|v|=1，所以該圖不是H圖
    • 所以，H簡單圖中一定不存在割點

  • 性質5：若圖G包含H路，則對V(G)的每個真子集S有，ω(G-S)≤|S|+1

    • 證明：這個和性質3很像，證明是一樣的，從一條路上刪去一個點，最多兩個連通分支，刪去k個，則最多有K+1個連通分支

  • 性質6：若圖G是H圖且不是圈，則G至少包含2個度不小與3的頂點

    - 證明：因為連通圖G不是圈，則圖G至少包含一個度數(shù)大于3的頂點，否則圖G是圈。若圖G只包含一個度數(shù)大于等于3的頂點，則其結構必為幾個塊相交于一點，因此該點為割點，所以該圖不是H圖，矛盾，所以得證

  H圖的判定

  • 充分條件1：Dirac定理。對于n≥3的簡單圖G，如果G中有δ(G)≥n/2，那么G是H圖 （充分條件）

    • 證明：反證：若不然，設G是一個滿足定理條件的極大非H簡單圖，顯然G不能是完全圖，否則G是H圖，所以，在G中任意取兩個不相鄰頂點u和v，考慮G+uv，由G的極大性，G+uv是H圖，有與G是非H圖，G+uv的每個H圈必然包含邊uv，所以在G中存在起點為u終點為v的H路P。設P為v1v2...vn，v1=u，vn=v，令S={vi|uvi+1∈E(G)}，T={vj|vjv∈E(G)}，對于S和T，顯然vn不在S∪T中，|S∪T|＜n，同時S∩T=?，否則設vi∈S∩T，由vi∈T可得vnvi∈E，則v1vi+1也∈E，則v1vi+1vivn...v1則為圈，且H圈，所以矛盾，所以S∩T=?，所以d(u)+d(v)=|S|+|T|=|S∪T|<n，這與條件矛盾，所以得證
    • 感覺只要會用就行

  • 充分條件2：Ore定理，對于n≥3的簡單圖G，如果G中任意兩個不相鄰的頂點u與v，有d(u)+d(v)≥n，則G是H圖（充分條件）

    • Ore定理比Dirac更緊
    • 證明與Dirac完全類似
    • 下界不能再變化

  • 充分條件3：若G1和G2是同一個點集V的兩個閉圖，則G=G1∩G2是閉圖

    • 定義：若對d(u)+d(v)≥n的任意一對點和v都是相鄰的，則稱G是閉圖
    • 證明：對任意的w∈V，有dG(w)≤dG1(w)，dG(w)≤dG2(w)，所以由dG(u)+dG(v)≥n可得，dG1(u)+dG1(v)≥n，dG2(u)+dG2(v)≥n，由G1和G2是閉圖，u和v在G1和G2中都鄰接，所以u和v在G1和G2中都相鄰，故u和v在G中也相鄰，從而G是閉圖
    • 閉圖的交一定是閉圖，但是并不一定

    • 閉包

      • 定義：若一個與G有相同點集的閉圖G‘，使G包含于G'，且對異于G‘的任何圖H，若有G包含于H包含于G’，則H不是閉圖，則稱G‘是G的閉包

        • 也就是說，G的閉包是包含G的極小閉圖，擱這扯犢子呢，定義一大堆

        • 閉包的構造方法：將圖中度數(shù)之和至少是圖的頂點個數(shù)的非鄰接頂點對遞歸的連接起來，知道不再由這樣的頂點對存在為止。

          • 即，使得度數(shù)之和≥n的頂點對都成為鄰接的，從而成為閉圖

        • 一個圖的閉包不一定是完全圖

    • 定理：任意圖G的閉包是唯一的

      • 證明：設G1和G2是G的閉包，則顯然由G包含于G1，G包含于G2，可得G包含于G1交G2，由于由閉包定理，G1交G2是閉圖，其包含于G1也包含于G2，如若它比G1G2還小，則G1G2就不能稱之為閉包了，所以它們?nèi)呦嗟?/li>

  • 充分條件4：G是n階簡單圖，u和v是G中不相鄰的頂點，且滿足d(u)+d(v)≥n，則G是H圖的充要條件是，G+uv為H圖

    • 和Ore定理有點像，但是又不完全一樣，忽略了任意的uv
    • 證明：必要性：若G是H圖，則顯然G+uv也是H圖。充分性：設G+uv是H圖，C是一個H圈，如果C不含邊uv，則G中本來就含有H圈，則得證，如果圈C中有uv邊，設C=uvv3v4...vnu，令G1=G+uv，則dG1(u)=dG(u)+1,dG1(v)=dG(v)+1，所以dG1(u)+dG1(v)=dG(u)+dG(v)+2≥n+2，一定存在i(3≤i≤n-1)使得u與vi相鄰，v與vi+1相鄰，若不存在這樣的i，因為v3,v4...,vn-1中有dG1(u)-2個點u相鄰，則v4,v5..vn就有dG1(u)-2個點不能與v相鄰，從而dG1(v)≤(n-1)-(dG1(u)-2)=n+1-dG1(u)，這與dG(u)+dG(v)+2≥n+2矛盾，所以一定存在i(3≤i≤n-1)使得u與vi相鄰，v與vi+1相鄰，從而，G中存在不經(jīng)過uv的H圈C1=uvivi-1...v3vi+1vi+2...vnu，所以G是H圖

  • 充分條件5：Bondy定理，一個簡單圖G是H圖，當且僅當它的閉包是H圖

    • 證明：若G的閉包等于G，結論顯然成立，若G的閉包和G不同，設ei是為了構造G的閉包而依次添加的所有邊，G是H圖當且僅當G+e1是H圖，G+e1是H圖當且僅當G+e1+e2是H圖，如此反復下去，可以得到定理結論

    • 推論：設G是n≥3的簡單圖，若G的閉包是完全圖，則G是H圖

      • 顯然呀，完全圖一定是H圖，閉包是H圖，則一定是H圖

    • 推論：G是n≥3的簡單圖，若G中每個點的度d(v)≥n/2，則G是H圖

      • dirac定理，廢話···

    • 推論：G是n≥3的簡單圖，若G中任何兩個不鄰接的點u和v均有d(u)+d(v)≥n，則G是H圖

      • 就是Ore定理

  • 充分條件6：度序列判定法，設簡單圖G的度序列是(d1,d2...dn)，d1≤...dn，且n≥3，若對任意的k<n/2，或有dk>k，或有dn-k≥n-k，則G是H圖

    • 也就是對于小于n/2的k，滿足兩個條件中的一個就可以
    • 這個太麻煩了，不用證明

    • 例題：若G是度序列(d1,d2,...dn)的非平凡簡單圖，且滿足d1≤d2≤...≤dn，證明：弱不存在小于(n+1)/2的正整數(shù)m，使得：dm<m且dn-m+1<n-m，則G有H路

      • 證明：在G外加一個新點v，把它和G的所有頂點連接得圖G1，G1度序列(d1+1,d2+1,...dn+1,n)，因為不存在····，由度序列判定定理知G1是H圖，所以去掉點v，顯然G有H路

  補充：有割點的圖不一定是非哈密爾頓圖：注意這里是圖，而非簡單圖，若是簡單圖成立，而圖的話，可以是哈密爾頓圖加一個自環(huán)，即為反例