第一章(圖論的基本概念)

任課教師:陳六新

chenliux@

答疑時(shí)間:星期三下午2:30-3:30;地點(diǎn):數(shù)理學(xué)院3樓應(yīng)用數(shù)學(xué)教學(xué)部建議參考書:圖論及其算法殷劍宏吳開亞中科大出版社圖論及其應(yīng)用張清華等編清華大學(xué)出版社圖論與網(wǎng)絡(luò)流理論,高隨祥,高教社通信網(wǎng)圖論及應(yīng)用,劉煥淋,陳勇,人民郵電電網(wǎng)絡(luò)理論(圖論，方程綜合)周庭陽,張紅巖;械工業(yè)出版社

圖論導(dǎo)引，（美）DouglasB.West

譯李建中，機(jī)械工業(yè)出版社

1.圖論問題的起源

18世紀(jì)東普魯士哥尼斯堡被普列戈?duì)柡臃譃樗膲K,它們通過七座橋相互連接,如下圖.當(dāng)時(shí)該城的市民熱衷于這樣一個(gè)游戲:“一個(gè)散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？”SNAB七橋問題的分析

七橋問題看起來不難，很多人都想試一試，但沒有人找到答案.后來有人寫信告訴了當(dāng)時(shí)的著名數(shù)學(xué)家歐拉.千百人的失敗使歐拉猜想,也許那樣的走法根本不可能.1876年,他證明了自己的猜想.Euler把南北兩岸和兩個(gè)島抽象成四個(gè)點(diǎn),將連接這些陸地的橋用連接相應(yīng)兩點(diǎn)的一條線來表示,就得到如下一個(gè)簡圖:BANS歐拉的結(jié)論歐拉指出:一個(gè)線圖中存在通過每邊一次僅一次回到出發(fā)點(diǎn)的路線的充要條件是:1)圖是連通的,即任意兩點(diǎn)可由圖中的一些邊連接起來;2)與圖中每一頂點(diǎn)相連的邊必須是偶數(shù).由此得出結(jié)論:七橋問題無解.

歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父.4.圖的作用

圖是一種表示工具,改變問題的描述方式,往往是創(chuàng)造性的啟發(fā)式解決問題的手段.一種描述方式就好比我們站在一個(gè)位置和角度觀察目標(biāo),有的東西被遮擋住了,但如果換一個(gè)位置和角度,原來隱藏著的東西就可能被發(fā)現(xiàn).采用一種新的描述方式,可能會(huì)產(chǎn)生新思想.圖論中的圖提供了一種直觀,清晰表達(dá)已知信息的方式.它有時(shí)就像小學(xué)數(shù)學(xué)應(yīng)用題中的線段圖一樣,能使我們用語言描述時(shí)未顯示的或不易觀察到的特征、關(guān)系,直觀地呈現(xiàn)在我們面前,幫助我們分析和思考問題,激發(fā)我們的靈感.5.圖的廣泛應(yīng)用

圖的應(yīng)用是非常廣泛的,在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò),如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計(jì)算機(jī)通訊網(wǎng)、輸電線網(wǎng)等等.還有許多看不見的網(wǎng)絡(luò),如各種關(guān)系網(wǎng),像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時(shí)間先后次序關(guān)系等等,這些網(wǎng)絡(luò)都可以歸結(jié)為圖論的研究對象—圖.其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要我們解決.還有象生產(chǎn)計(jì)劃、投資計(jì)劃、設(shè)備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題.可化為最短路問題的多階段決策問題6.基本的網(wǎng)絡(luò)優(yōu)化問題

基本的網(wǎng)絡(luò)優(yōu)化問題有:最短路徑問題、最小生成樹問題、最大流問題和最小費(fèi)用問題.圖論作為數(shù)學(xué)的一個(gè)分支,已經(jīng)有有效的算法來解決這些問題.當(dāng)然這當(dāng)中的有些問題也可以建立線性規(guī)劃的模型,但有時(shí)若變量特別多,約束也特別多,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時(shí)間內(nèi)解決.而根據(jù)這些問題的特點(diǎn),采用網(wǎng)絡(luò)分析的方法去求解可能會(huì)非常有效.

例如,在1978年,美國財(cái)政部的稅務(wù)分析部門在對卡特爾稅制改革做評估的過程中,就有一個(gè)100,000個(gè)約束以上，25,000,000個(gè)變量的問題,若用普通的線性規(guī)劃求解,預(yù)計(jì)要花7個(gè)月的時(shí)間.他們利用網(wǎng)絡(luò)分析的方法,將其分解成6個(gè)子問題,利用特殊的網(wǎng)絡(luò)計(jì)算機(jī)程序,花了大約7個(gè)小時(shí)問題就得到了解決.

由于后續(xù)學(xué)習(xí)的需要,我們補(bǔ)充離散數(shù)學(xué)中的一些基本內(nèi)容:關(guān)系與函數(shù).第一章圖的基本概念(1)(1)定義1圖G是一個(gè)三元組,記作其中稱為圖G的結(jié)點(diǎn)集.(2)或是G的邊集合,其中或?yàn)檫?。若為稱為端點(diǎn)的無向邊。為以稱為關(guān)聯(lián)函數(shù).若為稱為起點(diǎn)，為以為終點(diǎn)的有向邊。第一章圖的基本概念(2)定義2.鄰接結(jié)點(diǎn):關(guān)聯(lián)于同一條邊的兩個(gè)結(jié)點(diǎn).孤立結(jié)點(diǎn):不與任何結(jié)點(diǎn)相連接的結(jié)點(diǎn).鄰接邊:關(guān)聯(lián)于同一頂點(diǎn)的兩條邊.環(huán):兩端點(diǎn)相同的邊稱為環(huán)或自回路.平行邊:兩個(gè)結(jié)點(diǎn)間方向相同的若干條邊稱為平行邊或重邊.對稱邊:兩端點(diǎn)相同但方向相反的兩條有向邊.第一章圖的基本概念(3)定義3.

無向圖:每條邊都是無向邊的圖.有向圖:每條邊都是有向邊的圖.混合圖:圖中不全是有向邊,也不全是無向邊的圖.平凡圖:只有一個(gè)孤立結(jié)點(diǎn)的圖.定義4.多重圖:含有平行邊的圖.簡單圖:無環(huán)且無平行邊的圖.完全圖:任何不同結(jié)點(diǎn)之間都有邊相連的簡單無向圖.第一章圖的基本概念(4)說明:(1)在簡單圖中,以x為起點(diǎn)y為終點(diǎn)的邊至多有一條,因此,圖中的邊可直接用頂點(diǎn)對表示,而關(guān)聯(lián)函數(shù)就可以直接表示在其邊集中,故可簡記為G=<V(G),E(G)>.(2)對無向圖G,將G中的每條邊用兩條與e有相同端點(diǎn)對稱邊e和e’來代替后得到一個(gè)有向圖D,這樣得到的有向圖D稱為G的對稱有向圖.由此可見,無向圖可視為特殊的有向圖.(3)n個(gè)結(jié)點(diǎn)的完全圖記為Kn,完全圖Kn有條邊.完全圖的對稱有向圖稱為完全有向圖,記作.(4)圖G的頂點(diǎn)個(gè)數(shù)稱為圖G的階.(5)對于有向圖D,去掉邊上的方向得到的無向圖G稱為D的基礎(chǔ)圖.反之,任一個(gè)無向圖G,將G的邊指定一個(gè)方向得到一個(gè)有向圖D,稱D為G的一個(gè)定向圖.例證明:在任意六個(gè)人的聚會(huì)上,要么三個(gè)曾相識(shí),要么三個(gè)不曾相識(shí).證明:用A,B,C,D,E,F代表這六個(gè)人,若兩人曾相識(shí),則在代表該兩人的頂點(diǎn)間連一條紅邊;否則連一條藍(lán)邊.于是,原問題等價(jià)于證明所得圖中必含有同色三角形.考察某一頂點(diǎn),設(shè)為F.與F關(guān)聯(lián)的邊中必有三條同色,不妨設(shè)它們是三條紅邊FA,FB,FC.再看三角形ABC.若它有一條紅邊,設(shè)為AB,則FAB是紅邊三角形;若三角形ABC沒有紅邊,則其本身就是藍(lán)邊三角形.第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(1)定義1設(shè)G是任意圖,x為G的任意結(jié)點(diǎn),與結(jié)點(diǎn)x關(guān)聯(lián)的邊數(shù)(一條環(huán)計(jì)算兩次)稱為x的度數(shù).記作deg(x)或d(x).

設(shè)D是任意有向圖，x為G的任一結(jié)點(diǎn)，以x為終點(diǎn)的邊的條數(shù)稱為x的入度，記作deg+(x)或d+(x).

以x為始點(diǎn)的邊的條數(shù)稱為x的出度，記作deg-(x)或d-(x).注意：有向圖D中，結(jié)點(diǎn)x的度deg(x)=deg+(x)+deg-(x)。Δ(G)和δ(G)分別表示G的最大頂點(diǎn)度和最小頂點(diǎn)度，即Δ(G)=max{dG(x)|x∈V(G)};δ(G)=min{dG(x)|x∈V(G)}.有向圖D中，記Δ+(G)=max{d+G(x)|x∈V(G)};δ+(G)=min{d+G(x)|x∈V(G)}.

Δ-(G)=max{d-G(x)|x∈V(G)};δ-(G)=min{d-G(x)|x∈V(G)}.第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(1)定義2

設(shè)G為無向圖,對于G的每個(gè)結(jié)點(diǎn)x,若d(x)=K,則稱G為K正則的無向圖.設(shè)G為有向圖,對于G的每個(gè)結(jié)點(diǎn)x,若d+(x)=d-(x),則稱G為平衡有向圖.在有向圖G中,若則稱G為K正則有向圖.定理1(握手定理，圖論基本定理)每個(gè)圖中,結(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的二倍,即定理2每個(gè)圖中,度數(shù)為奇數(shù)的結(jié)點(diǎn)必定是偶數(shù)個(gè).第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(2)定理3在任何有向圖中,所有結(jié)點(diǎn)入度之和等于所有結(jié)點(diǎn)出度之和.證明因?yàn)槊織l有向邊必對應(yīng)一個(gè)入度和出度,若一個(gè)結(jié)點(diǎn)具有一個(gè)入度或出度,則必關(guān)聯(lián)一條有向邊.因此,有向圖中各結(jié)點(diǎn)的入度之和等于邊數(shù),各結(jié)點(diǎn)出度之和也等于邊數(shù).定義度序列若V(G)={v1,v2,…,vp},稱非負(fù)整數(shù)序列(d(v1),d(v2),…,d(vp))為圖G的度序列.第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(3)推論1非負(fù)整數(shù)序列是某個(gè)圖的度序列當(dāng)且僅當(dāng)是偶數(shù).證明:由定理1知必要性成立.對于充分性取p各相異頂點(diǎn)v1,v2,…,vp,若di是偶數(shù),就在vi處作di/2個(gè)環(huán);若di是奇數(shù),在vi處作(di-1)/2個(gè)環(huán),由于是偶數(shù),故中由偶數(shù)個(gè)奇數(shù)頂點(diǎn),從而將所有與奇數(shù)di相對應(yīng)的頂點(diǎn)vi兩兩配對并連上一條邊.最后所得的序列就是.第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(4)圖序列:簡單圖的度序列.定理4非負(fù)整數(shù)序列是圖序列當(dāng)且僅當(dāng)是偶數(shù),并且對一切整數(shù)k,有定義3設(shè)G1=<V1,E1>和G2=<V2,E2>是簡單圖,若存在一個(gè)從V1到V2的雙射函數(shù)f，且f具有這樣的性質(zhì),對V1中的所有x和y,x和y在G1中相鄰,當(dāng)且僅當(dāng)f(x)和f(y)在G2中相鄰,就說G1和G2是同構(gòu)的,記作G1∽G2.例1畫出所有不同構(gòu)的具有5個(gè)結(jié)點(diǎn),3條邊的簡單無向圖。例2是否可以畫一個(gè)簡單無向圖,使各點(diǎn)度數(shù)與下列的序列一致:2,2,2,2,2,22,2,3,4,5,61,2,3,4,4,5第三節(jié)圖的運(yùn)算(一）定義1設(shè)與是任何兩個(gè)圖.若且是在上的限制,則稱是G的子圖,記作稱G為G1的母圖.

若且,則稱是G的生成子圖或支撐子圖.

設(shè),以V1為頂點(diǎn),以兩端點(diǎn)均在V1中的G的邊的全體為邊集的G的子圖,稱為V1的導(dǎo)出子圖,記作G[V1].設(shè),以E1為邊集,以E1中的邊關(guān)聯(lián)的全部頂點(diǎn)集的G的子圖,稱為E1的導(dǎo)出子圖,記作G[E1].特別,若,則以G-V1表示從G中刪去V1內(nèi)的所有點(diǎn)以及與這些頂點(diǎn)關(guān)聯(lián)的邊所得到的子圖,若V1={v},常把G-{v}簡記為G-v,類似地,設(shè),G-E1表示在G中刪去E1中所有邊所得的子圖,同樣G-{e}簡記為G-e.第三節(jié)圖的運(yùn)算(二）定義2設(shè)G＝<V，E>是n階無向簡單圖,以V為頂點(diǎn)集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對于完全圖Kn補(bǔ)圖,簡稱G的補(bǔ)圖,記作.定義3設(shè)G1和G2都是圖G的子圖.G1和G2的并:僅由G1和G2中所有邊組成的圖.G1和G2的交G1∩G2:僅由G1和G2的公共邊組成的圖.G1和G2的差G1-G2:僅由G1中去掉G2中的邊組成的圖.G1和G2的環(huán)和

G1⊕G2:在G1和G2的并中去掉G1和G2的交所得到的圖.(見p12)定義4.自補(bǔ)圖:若簡單圖G同構(gòu)于G的補(bǔ)圖,則稱G為自補(bǔ)圖.(1)證明:自補(bǔ)圖的階數(shù)為n=4k或n=4k+1,k為某個(gè)自然數(shù).(自己查閱)(2)找出所有4階和5階的自補(bǔ)圖.例在一次舞會(huì)上,A,B兩國留學(xué)生各n人,A國每個(gè)學(xué)生都與B國一些學(xué)生(不是所有)跳過舞.B國每個(gè)學(xué)生至少與A國一個(gè)學(xué)生跳過舞.證明一定可以找到A國兩個(gè)學(xué)生a1,a2及B國兩個(gè)學(xué)生b1,b2,使得a1和b1,a2和b2跳過舞,而a2和b1,a1和b2沒有跳過舞.(自己思考)圖的運(yùn)算(三)定義四:設(shè)G1和G2是任兩個(gè)無向圖,G1和G2的笛卡兒積為圖G=G1×G2,其中G滿足:V(G)=V(G1)×V(G2);G中的兩頂點(diǎn)<a,b>和<c,d>是鄰接的當(dāng)且僅當(dāng)a=c且{b,d}∈E(G2)或者b=d且{a,c}∈E(G1).說明:(1)通過圖的笛卡兒積運(yùn)算,可歸納地定義一個(gè)重要的圖類--n立方體Qn(n1):當(dāng)n=1,Qn=K2;當(dāng)n>1,Qn=Qn-1K2.(2)n立方體Qn也可以看作是用頂點(diǎn)表示2n個(gè)長度為n的位串圖.兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們所表示的位串恰恰差一位.第四節(jié)路與連通圖(一)定義1設(shè)u和v是任意圖G的頂點(diǎn),圖G的一條u-v是有限的頂點(diǎn)和邊交替序列u0e1u1e2…un-1enun(u=u0,v=un),其中與邊ei(1in)相鄰的兩頂點(diǎn)ui-1和ui正好是ei的兩個(gè)端點(diǎn).數(shù)n(鏈中出現(xiàn)的邊數(shù))稱為鏈的長度.u(或u0)和v(或un)稱為鏈的端點(diǎn),其余的頂點(diǎn)稱為鏈的內(nèi)部點(diǎn).一條u-v鏈,當(dāng)uv時(shí),稱它為開的,否則稱為閉的.邊互不相同的鏈稱為跡,內(nèi)部點(diǎn)互不相同的鏈稱為路.注釋1.(1)在一條鏈中,頂點(diǎn)和邊可以重復(fù).(2)若G是簡單圖,G中的鏈u0e1u1e2…un-1enun還可用結(jié)點(diǎn)序列u0u1…un-1un表示.(3)不含邊的鏈(即長度為0)稱為平凡鏈.(4)設(shè)W是有向圖D中u-v鏈(跡,路),指定W的方向從u到v.若W中所有邊的方向與此方向一致,則稱W為D中從u到v的有向鏈(跡,路).第四節(jié)路與連通圖(二)定義2兩端點(diǎn)相同的跡(即閉集)稱為回.兩端點(diǎn)相同的路(即閉路)稱為圈或回路.長度為K,奇數(shù),偶數(shù)的回(圈)分別稱為K,奇,偶回(圈).有向閉跡(閉路)稱為有向回(有向圈).定理1.若簡單圖G中每個(gè)頂點(diǎn)的度數(shù)至少是k(k2),則G中必含有一個(gè)長度至少是k+1的圈.證明:在G的所有路中,取一條長度最長的路p,記p=v0v1…vt-1vt.則v0的所有鄰接點(diǎn)全在p中,由于d(v0)k2,所以v0至少有k個(gè)鄰接點(diǎn),設(shè)所有鄰接點(diǎn)為vi1,vi2,…,vis,1i1i2…ist,其中s=d(v0)k2,則C=v0v1v2…visv0就是G的一個(gè)長為is+1的圈,顯然is+1k+1.第四節(jié)路與連通圖(三).定理2

設(shè)簡單圖G中每個(gè)頂點(diǎn)的度數(shù)至少是3,則G中含有偶圈.證明:在G的所有路中,取一條長度最長的路p,記p=v0v1…vt-1vt.則v0的所有鄰接點(diǎn)全在p中,設(shè)v0的所有鄰接點(diǎn)為vi1,vi2,…,vis,1i1i2…ist,其中s=d(v0)3,在G中取三個(gè)圈c1=v0v1…vi2v0,c2=v0v1…visv0,c3=v0vi2vi2+1…visv0,它們的長度分別為i2+1,is+1和is-i2+2.這三個(gè)數(shù)中至少有一個(gè)是偶數(shù).即c1,c2,c3中至少有一個(gè)是偶圈.定義3給定無向圖G=<V(G),E(G),(G)>,x,y∈V(G),若圖中存在連接x和y的路,稱節(jié)點(diǎn)x和y是連通的.規(guī)定x到自身總是連通的.說明：容易驗(yàn)證,結(jié)點(diǎn)集V(G)上的頂點(diǎn)間的連通關(guān)系是V(G)上的一個(gè)等價(jià)關(guān)系,該等價(jià)關(guān)系確定V(G)的一個(gè)劃分{V1,V2,…,Vm},使得當(dāng)且僅當(dāng)兩個(gè)頂點(diǎn)x和y屬于同一子集Vi時(shí),x和y才是連