工學(xué)圖論與其應(yīng)用ch3ch4

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

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