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

任課教師:陳六新

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è)簡(jiǎn)圖: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é)為圖論的研究對(duì)象—圖.其中存在大量的網(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ù)分析部門在對(duì)卡特爾稅制改革做評(píng)估的過程中,就有一個(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)間方向相同的若干條邊稱為平行邊或重邊.對(duì)稱邊:兩端點(diǎn)相同但方向相反的兩條有向邊.第一章圖的基本概念(3)定義3.

無向圖:每條邊都是無向邊的圖.有向圖:每條邊都是有向邊的圖.混合圖:圖中不全是有向邊,也不全是無向邊的圖.平凡圖:只有一個(gè)孤立結(jié)點(diǎn)的圖.定義4.多重圖:含有平行邊的圖.簡(jiǎn)單圖:無環(huán)且無平行邊的圖.完全圖:任何不同結(jié)點(diǎn)之間都有邊相連的簡(jiǎn)單無向圖.第一章圖的基本概念(4)說明:(1)在簡(jiǎn)單圖中,以x為起點(diǎn)y為終點(diǎn)的邊至多有一條,因此,圖中的邊可直接用頂點(diǎn)對(duì)表示,而關(guān)聯(lián)函數(shù)就可以直接表示在其邊集中,故可簡(jiǎn)記為G=<V(G),E(G)>.(2)對(duì)無向圖G,將G中的每條邊用兩條與e有相同端點(diǎn)對(duì)稱邊e和e’來代替后得到一個(gè)有向圖D,這樣得到的有向圖D稱為G的對(duì)稱有向圖.由此可見,無向圖可視為特殊的有向圖.(3)n個(gè)結(jié)點(diǎn)的完全圖記為Kn,完全圖Kn有條邊.完全圖的對(duì)稱有向圖稱為完全有向圖,記作.(4)圖G的頂點(diǎn)個(gè)數(shù)稱為圖G的階.(5)對(duì)于有向圖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為無向圖,對(duì)于G的每個(gè)結(jié)點(diǎn)x,若d(x)=K,則稱G為K正則的無向圖.設(shè)G為有向圖,對(duì)于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有向邊必對(duì)應(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知必要性成立.對(duì)于充分性取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相對(duì)應(yīng)的頂點(diǎn)vi兩兩配對(duì)并連上一條邊.最后所得的序列就是.第二節(jié)圖的頂點(diǎn)度和圖的同構(gòu)(4)圖序列:簡(jiǎn)單圖的度序列.定理4非負(fù)整數(shù)序列是圖序列當(dāng)且僅當(dāng)是偶數(shù),并且對(duì)一切整數(shù)k,有定義3設(shè)G1=<V1,E1>和G2=<V2,E2>是簡(jiǎn)單圖,若存在一個(gè)從V1到V2的雙射函數(shù)f，且f具有這樣的性質(zhì),對(duì)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條邊的簡(jiǎn)單無向圖。例2是否可以畫一個(gè)簡(jiǎn)單無向圖,使各點(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}簡(jiǎn)記為G-v,類似地,設(shè),G-E1表示在G中刪去E1中所有邊所得的子圖,同樣G-{e}簡(jiǎn)記為G-e.第三節(jié)圖的運(yùn)算(二）定義2設(shè)G＝<V，E>是n階無向簡(jiǎn)單圖,以V為頂點(diǎn)集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對(duì)于完全圖Kn補(bǔ)圖,簡(jiǎn)稱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ǔ)圖:若簡(jiǎn)單圖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è)長(zhǎng)度為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ù))稱為鏈的長(zhǎng)度.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是簡(jiǎn)單圖,G中的鏈u0e1u1e2…un-1enun還可用結(jié)點(diǎn)序列u0u1…un-1un表示.(3)不含邊的鏈(即長(zhǎng)度為0)稱為平凡鏈.(4)設(shè)W是有向圖D中u-v鏈(跡,路),指定W的方向從u到v.若W中所有邊的方向與此方向一致,則稱W為D中從u到v的有向鏈(跡,路).第四節(jié)路與連通圖(二)定義2兩端點(diǎn)相同的跡(即閉集)稱為回.兩端點(diǎn)相同的路(即閉路)稱為圈或回路.長(zhǎng)度為K,奇數(shù),偶數(shù)的回(圈)分別稱為K,奇,偶回(圈).有向閉跡(閉路)稱為有向回(有向圈).定理1.若簡(jiǎn)單圖G中每個(gè)頂點(diǎn)的度數(shù)至少是k(k2),則G中必含有一個(gè)長(zhǎng)度至少是k+1的圈.證明:在G的所有路中,取一條長(zhǎng)度最長(zhǎng)的路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è)長(zhǎng)為is+1的圈,顯然is+1k+1.第四節(jié)路與連通圖(三).定理2

設(shè)簡(jiǎn)單圖G中每個(gè)頂點(diǎn)的度數(shù)至少是3,則G中含有偶圈.證明:在G的所有路中,取一條長(zhǎng)度最長(zhǎng)的路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,它們的長(zhǎng)度分別為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才是連通的.第四節(jié)路與連通圖(四)Vi在G中的導(dǎo)出子圖G[V1],G[V2],…,G[Vm]稱為G的連通分支或分支,m稱為G的連通分支數(shù),記作W(G)=m.如下圖有4個(gè)連通分支.定義4.如果無向圖G中每一對(duì)不同的頂點(diǎn)x和y都有一條路,即W(G)=1,則稱G是連通圖,反之稱為非連通圖.[S,T]＝{e|e∈E(G),e的兩個(gè)端點(diǎn)分別在S和T中}，其中T=V-S。引理1非平凡圖G是連通圖當(dāng)且僅當(dāng)對(duì)V(G)的每一個(gè)非空真子集S,[S,S’]≠Ф,S’=V-S.第四節(jié)路與連通圖(五)定理3設(shè)G是P階連通圖,則證明:只需證明連通的簡(jiǎn)單圖成立即可.設(shè)懸掛點(diǎn):度數(shù)為1頂點(diǎn).第四節(jié)路與連通圖(六)定理4

設(shè)連通圖G至少有兩個(gè)頂點(diǎn),其邊數(shù)小于頂點(diǎn)數(shù),則此圖至少有一個(gè)懸掛點(diǎn).證明:設(shè)圖G是滿足條件的P階圖.反設(shè)圖G沒有懸掛點(diǎn),由于G是連通圖,故每個(gè)頂點(diǎn)的度數(shù)至少為2,即對(duì)每個(gè)頂點(diǎn)v,d(v)2,故,與矛盾.定理5設(shè)簡(jiǎn)單圖G的結(jié)點(diǎn)序列為.度數(shù)依次是d(v1)≤d(v2)≤…≤

d(vp),如果對(duì)任意的則G是連通圖.證明:反設(shè)G不連通,令G1是G中不含vp的一個(gè)連通分支,而G2是G中含vp的一個(gè)連通分支,則G2至少有個(gè)頂點(diǎn),且

第四節(jié)路與連通圖(七)則由已知.若記則,則與矛盾.推論1設(shè)G是P階簡(jiǎn)單圖,每個(gè)頂點(diǎn)的度至少是[P/2],則G是連通圖.定義5設(shè)是有向圖,,若圖D中存在x到y(tǒng)的有向路,稱結(jié)點(diǎn)x可達(dá)結(jié)點(diǎn)y.

規(guī)定x到自身總是可達(dá)的.定義6

設(shè)G是有向圖,任何結(jié)點(diǎn)間,至少有一個(gè)結(jié)點(diǎn)可達(dá)另一個(gè)結(jié)點(diǎn),則稱該有向圖是單側(cè)連通的.如果有向圖D的任何一對(duì)結(jié)點(diǎn)間是相互可達(dá)的,則稱該有向圖是強(qiáng)連通的.若有向圖G的基礎(chǔ)圖是連通的,則稱該有向圖D是弱連通的.定義7

設(shè)G是有向圖,,G中所有從x到y(tǒng)的有向路的最小長(zhǎng)度稱為從x到y(tǒng)的距離.定義8

設(shè)G是無向圖,,G中所有從x到y(tǒng)的路的最小長(zhǎng)度稱為從x到y(tǒng)的距離.稱為圖G的直徑.

第五節(jié)連通圖和二分圖(1)定義1如果在圖G中刪去一個(gè)結(jié)點(diǎn)x后,圖G連通分支數(shù)增加,即W(G-x)>W(G),則稱結(jié)點(diǎn)x為G的割點(diǎn).

如果在圖G中刪去一條邊e后,圖G的連通分支數(shù)增加,即W(G-e)>W(G),則稱邊e為G的割邊.定義2沒有割點(diǎn)的非平凡連通圖稱為塊.G中不含割點(diǎn)的極大連通子圖稱為圖G的塊.定義3如果G的頂點(diǎn)集的一個(gè)真子集T滿足G-T不連通或是平凡圖，任意T的真子集T’,而G-T’是連通的,則稱T為G的一個(gè)點(diǎn)割.如果圖G的邊集的一個(gè)真子集S滿足G-S不連通或是平凡圖，任意S的真子集S’滿足G-S’是連通的,則稱S為G的一個(gè)邊割.定義4設(shè)G是連通圖,稱是G的點(diǎn)割}為G的點(diǎn)連通度或連通度;稱是G的邊割}為G的邊連通度.定理1

對(duì)一個(gè)圖G,有是圖G的最小頂點(diǎn)度.(不證)證明:若G不連通,則結(jié)論成立.若G連通.(1)先證設(shè)x是G中度數(shù)最小的頂點(diǎn),即.設(shè)所有與關(guān)聯(lián)的邊集為S(x),顯然x是G-S(x)的一個(gè)孤立點(diǎn).所以(2)再證當(dāng)時(shí),顯然假設(shè)對(duì)所有的圖G有設(shè)

S是H的一個(gè)邊割,且若邊易知故由假設(shè)知并設(shè)T是H-e的一個(gè)點(diǎn)割,且此時(shí),就是H的一個(gè)點(diǎn)割,即

K(H)≤︱T∪{u}︱≤n+1=（H）.

再由歸納假設(shè)即知K(G)≤（G）結(jié)論成立.第五節(jié)連通圖和二分圖(3)定義5如果無向圖G的連通度稱圖G是n連通的或G為n連通圖.若稱圖G是n邊連通的或G為n邊連通圖.定理2設(shè)圖G是n連通的,則對(duì)(反證)定理3設(shè)G是2邊連通圖,則G有強(qiáng)連通的定向圖.證明:設(shè)G是2邊連通圖,則G必含有圈.先取一個(gè)圈C1,定義G的連通子圖序列G1,G2,…如下:G1=C1;若Gi(i=1,2,…)不是G的生成子圖,設(shè)vi是在G中而不在Gi中的一個(gè)頂點(diǎn),則存在從vi到Gi的邊不重路Pi和Qi,定義由于該序列必終止于G的一個(gè)生成子圖Gn.依次對(duì)每個(gè)Gi定向:首先讓G1的定向圖成為一個(gè)有向圈;對(duì)設(shè)已有定向圖,讓Pi成為以vi為始點(diǎn)的有向路,而Qi成為以vi為終點(diǎn)的有向路,得,即是強(qiáng)連通圖i=1,2,…n.第五節(jié)連通圖和二分圖(4)

因此,最后的是強(qiáng)連通有向圖.由于Gn是G的生成子圖,所以G有強(qiáng)連通的定向圖.

一個(gè)圖G有強(qiáng)連通的定向圖的必要條件是G為2邊連通的.否則G有割邊,這與G有強(qiáng)連通的定向圖矛盾.定義6把簡(jiǎn)單圖G的頂點(diǎn)集合分成兩個(gè)不相交的非空集合V1,V2,使得圖G中的每一條邊,與其關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)分別在V1和V2中,則G稱為偶圖或二分圖,記作G=<V1,V2,E>,其中V1和V2叫做G的二劃分.

對(duì)于二分圖G=<V1,V2,E>,若,V1中的任意一點(diǎn)與V2中的所有點(diǎn)相鄰且V2中的任意一點(diǎn)與V1中的所有點(diǎn)相鄰,則稱該圖為結(jié)點(diǎn)m和n的完全偶圖或完全二分圖,記作Km,n.例1試說明n立方體Qn是二分圖.證明:不妨設(shè)由Qn的定義知Qn是簡(jiǎn)單圖.假定則邊,即兩結(jié)點(diǎn)序列恰差一位.令顯然.而且,若存在即與矛盾.所以X中任何兩頂點(diǎn)之間無邊相連.同理可證Y中任何兩頂點(diǎn)之間也無邊相連.因此Qn是二分圖.定理4非平凡圖G是二分圖當(dāng)且僅當(dāng)G中不含有長(zhǎng)為奇數(shù)的圈.證明:(→)設(shè)G是一個(gè)二分圖,G的二分為V1和V2,則G[V1]和G[V2]為零圖.設(shè)v=v1v2…vkv1是G中長(zhǎng)度為k的一個(gè)圈.下證k為偶數(shù).不妨設(shè)由于v2和v1相鄰,故;同樣有又最后一個(gè)頂點(diǎn)是v1,故k必為偶數(shù).(←)不妨設(shè)G中每一對(duì)點(diǎn)之間有路連接(否則只考慮G的每個(gè)每一對(duì)點(diǎn)之間有路連接的極大子圖).任取G的一個(gè)頂點(diǎn)u,由G的假設(shè),對(duì)G的每個(gè)頂點(diǎn)v,在G中存在u-v路.現(xiàn)利用u對(duì)G的頂點(diǎn)進(jìn)行分類.設(shè)

顯然,.由于G中不存在長(zhǎng)度為奇數(shù)的圈,所以對(duì)任意一個(gè)點(diǎn)v,G中所有從u到v的路的長(zhǎng)度都有相同的奇偶性,因而由G的假設(shè),現(xiàn)對(duì)G的每一條邊e={u1,u2},若u1,u2都在V1上,則存在兩條路P1與P2分別連接u與u1和u與u2,且P1與P2的長(zhǎng)度均為偶數(shù),閉鏈的長(zhǎng)度為奇數(shù),故G中有一條長(zhǎng)為奇數(shù)的圈,矛盾.同樣u1和u2不能同時(shí)在V2中.故e的兩個(gè)端點(diǎn)分別在V1和V2中.因此G是二分圖.第六節(jié)圖的矩陣表示(1)1.鄰接矩陣:設(shè)是有向圖,其中V={x1,x2,…,xn},E={e1,e2,…,em},則n階方陣A=(aij)稱為G的鄰接矩陣.其中aij為圖G中以xi為起點(diǎn)且以xj為終點(diǎn)的邊的數(shù)目。若G是無向圖，aij為圖G中以xi和xj為端點(diǎn)的邊的數(shù)目.說明1:由定義易知,無向圖的鄰接矩陣是對(duì)稱矩陣,而有向