工學圖論與其應用ch3ch4

樹/3.1樹的基本性質(zhì)樹：無圈的連通圖。森林：無圈圖.舉例：(1)碳氫化合物的分子式都是樹形結(jié)構(gòu)。(2)決策樹：用邏輯關(guān)系做出判決的樹稱為決策樹。(3)數(shù)據(jù)樹：表示數(shù)據(jù)的數(shù)被程序員稱為數(shù)據(jù)樹。Lilzhang@hhu.edu.cn樹的特性定理3.1.1：一個簡單圖T是樹當且僅當T中任意兩個頂點之間有且僅有一條路連接。定理3.1.2：下述論斷等價：(1)圖T是樹；(2)T連通且q(T)=p(T)-1;(3)T無圈且q(T)=p(T)-1;(4)T連通且T的每條邊都是割邊；(5)T無圈且對任意兩個不相鄰的頂點u和v，T+uv有且只有一個圈.定理3.1.4：樹T的每一個非懸掛點都是T的割點.很容易得到第二章第二節(jié)引理2和定理3。Lilzhang@hhu.edu.cn應用（例題）例有10個學生參加一次考試，試題10道。已知沒有2個學生做對的題目是完全相同。證明：在這10道題中可以找到一道題，將這道試題取消后，每2個學生所做對的題目仍然不會完全相同。證明：首先如何構(gòu)造圖論中的圖，對象和關(guān)系分別是什么？Lilzhang@hhu.edu.cn3.2生成樹/spanningtree定義1：如果樹T是連通圖G的生成子圖，那末稱T是G的一棵生成樹（支撐樹）。定義1‘:如果G是一個包含k個成分的分離圖,則相應的k個生成樹所組成的圖稱為生成森林。定理3.2.1

G是連通圖當且僅當G含有生成樹.必要性：逐步移去圖中圈上的邊，直到?jīng)]有圈為止，這樣就能得到G的一棵支撐樹。(破圈法)避圈法：在v(G)中逐次添加E(G)中的邊，要求每次添加之后所得子圖不含圈，一直進行到無法再添邊為止。Lilzhang@hhu.edu.cn定義3：設(shè)T是連通圖G的一棵生成樹,稱為T的余樹.T中的邊稱為樹枝,中的邊稱為G關(guān)于T的弦.(樹枝和弦都是相對于某一棵生成樹而言，不同的生成樹對應不同的樹枝和弦)說明:對連通圖G的任意生成樹T,總有p-1條樹枝和q-p+1條弦。舉例說明。Lilzhang@hhu.edu.cn掌握定理內(nèi)容，定理證明以具體圖舉例說明其意義。并延伸其中的圈的個數(shù)的計算。對保距生成樹不做要求。Lilzhang@hhu.edu.cn怎樣找出所有的生成樹(補充一種方法)初等變換：在一棵生成樹上加一條弦,刪除一條樹枝而生成一棵新的生成樹的變換稱為初等樹變換。樹之間的距離：G中兩棵支撐樹T1和T2間的距離是它們之間不相同邊數(shù)的一半。Lilzhang@hhu.edu.cnLilzhang@hhu.edu.cn性質(zhì)：對于一個秩是r的連通圖G,有如下結(jié)論：G中任何兩棵支撐數(shù)之間的最大距離是Lilzhang@hhu.edu.cn定理:從圖G的任何支撐樹出發(fā)，通過一系列初等樹變換,總能找到G的所有支撐樹.練習：求四邊形帶一條對角線的圖的生成數(shù)的棵樹。Lilzhang@hhu.edu.cn生成樹計算的另一重要方法：Lilzhang@hhu.edu.cn你能根據(jù)現(xiàn)在的理論給出剛才練習題的過程嗎？Lilzhang@hhu.edu.cn3.3最優(yōu)生成樹Lilzhang@hhu.edu.cn3.4樹形圖有向樹：一個有向圖D，如果略去每條弧的方向時所得無向圖是一棵樹，就稱D為有向樹。樹形圖：若一棵有向樹恰有一個頂點的入度為0,其余所有頂點的入度為1,則稱為該有向樹的樹形圖.入度為0的頂點稱為樹形圖的根.入度為1出度為0的頂點稱為樹形圖的樹葉,入度為1出度非零的頂點稱為內(nèi)點,又將內(nèi)點同根點統(tǒng)稱為分支點。由于樹形圖具有一根因而又稱根樹。層樹：在樹形圖中,從根到其余頂點的長度。Lilzhang@hhu.edu.cn二元有序樹有序樹：如果在樹形圖中規(guī)定了每一層上頂點的次序這樣的樹形圖稱為有序樹。m元樹：每個分支點的出度≤m的樹形圖;m元正則樹：每個分支點的出度=m的樹形圖;m元有序正則樹：有序的m元正則樹;m元完全正則樹：所有樹葉的層樹均相同的m元正則樹。當m=2時，我們討論二元有序樹及而元正則有序樹等。Lilzhang@hhu.edu.cn相關(guān)結(jié)果定理3.4.1:在二元正則樹T中,它的分支點數(shù)r和樹葉數(shù)t滿足：r=t-1.定理3.4.2:設(shè)T是二元正則樹,r為T的分支點數(shù),I為各分支點的層數(shù)之和,L為各樹葉的層樹之和,則L=I+2r.Lilzhang@hhu.edu.cnHuffman定理（掌握）帶權(quán)二元樹:每片樹葉權(quán)值為實數(shù)二元樹。最優(yōu)二元樹：權(quán)最小的二元樹。Lilzhang@hhu.edu.cnHuffman定理（掌握如何使用）由Huffman定理可以想到什么？Lilzhang@hhu.edu.cn對應算法過程Lilzhang@hhu.edu.cn舉例例：構(gòu)造帶權(quán)3，4，7，8，10，12的最優(yōu)二元樹。在二進制編碼中的應用：如何用非等長的二進制序列表示相應的字母，使傳遞的信息的二進制位盡可能地少？Lilzhang@hhu.edu.cn需要的概念前綴：Lilzhang@hhu.edu.cn舉例例：在通訊中已知子母A,B,C,D,E,F出現(xiàn)的頻率依次為30%,25%,20%,10%,10%,5%,求傳送它們的最優(yōu)前綴碼。解：相當于求最優(yōu)二元樹的過程。比較:用上例構(gòu)造的前綴碼傳送1000個同樣的字母所用的二進制位數(shù)與等長碼傳送1000個同樣的字母所用的二進制位數(shù)的差別？Lilzhang@hhu.edu.cn4Euler環(huán)游和Hamilton圈/4.1Euler環(huán)游Euler跡:經(jīng)過Ｇ的每條邊(恰好一次)的跡.Euler環(huán)游:經(jīng)過Ｇ的每條邊(恰好一次)的閉跡.Euler圖：包含Euler環(huán)游的圖。廣義歐拉圖：包含Euler跡的圖。定理4.1.1：一個非空連通圖是Euler圖當且僅當它沒有奇點（每點的度數(shù)都是偶數(shù)）.推論1：一個連通圖有Euler跡當且僅當它最多有兩個奇點.Lilzhang@hhu.edu.cn定理4.1.1的證明Lilzhang@hhu.edu.cn推論2：如果連通圖G中有2k個奇點,那末存在k個邊不交子圖,并且這些子圖包含了G所有的邊，每個子圖都是廣義歐拉圖。Lilzhang@hhu.edu.cn推論3：一個連通圖G是歐拉圖的充要條件是它能被分解為回路。（圖的分解：如果A∪B=G,且A∩B=零圖，則稱圖G被分解成兩個子圖A和B）Lilzhang@hhu.edu.cn例題例：某編輯部收到由n個人所寄的一些問題的解，他們發(fā)現(xiàn)每個人寄來4個不同問題的解，每個問題的解恰好由兩個人同時給出。問他們共收到幾個不同問題的解，并證明編輯部可以分兩次發(fā)表這些問題的解，使每人每次恰好被提到兩次。解：如何建立圖？歸結(jié)為何問題？Lilzhang@hhu.edu.cnFleury算法舉例說明。Lilzhang@hhu.edu.cn4.2Hamilton圖Hamilton路:包含G的每個頂點的路.Hamilton圈:包含G的每個頂點的圈.Hamilton圖:包含Hamilton圈的圖.[注1]：由以上定義可以看出如果一個圖是Hamilton圖，則有Hamilton圈，從而從Hamilton圈中任意去掉一條邊得到的都是一條Hamilton路。[注2]：Hamilton圈的長度是頂點數(shù)，而Hamilton路的長度是頂點數(shù)減一。[注3]：可以證明,任意階數(shù)的完全圖都是Hamilton圖。那末一般地要滿足那些條件才是Hamilton圖？Lilzhang@hhu.edu.cnLilzhang@hhu.edu.cn1.亞瑟王一次召見他的p個騎士.已知每一個騎士在騎士中的仇人不超過p/2-1個.證明：能讓這些騎士圍坐在圓桌旁，使每個人都不與他的仇人相鄰.2.4×4的棋盤上的馬圖是否是H-圖？即馬從任一方格出發(fā)，每個格恰跳到一次，再回到出發(fā)的那個格，是否可能？作業(yè)：定理7的應用Lilzhang@hhu.edu.cn充要條件閉包：從G出發(fā)，相繼連接所得圖中度數(shù)之和至少是P(G)的不相鄰頂點對，直到不能進行為止最后得到的圖是圖G的閉包。Lilzhang@hhu.edu.cn4.3分析相關(guān)的兩個實際問題1.（中國郵遞員問題）郵遞員的工作是每天在郵局里選出郵件，然后送到他所管轄的郵區(qū)的客戶手中，再返回郵局。問：采取怎樣的走法使他的投遞總行程最短？2.(旅行售貨員問題)設(shè)有p個城鎮(zhèn)，已知城鎮(zhèn)之間的距離，一個售貨員自某一城鎮(zhèn)出發(fā)巡回售貨，問：這個售貨員應如何選擇路線，使每個城鎮(zhèn)經(jīng)過一次且只經(jīng)過一次，最后返回出發(fā)地，而使總的行程最短？Lilzhang@hhu.edu.cn實例（一）計算機線路問題：在設(shè)計計算機接口時經(jīng)常遇到這樣的問題：一個接口由一些組件購成，每個組件上有幾個接線插頭連接起來。