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

任課教師:陳六新

chenliux@

答疑時間:星期三下午2:30-3:30;地點:數(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

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

1.圖論問題的起源

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

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

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

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

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

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

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

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

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

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

以x為始點的邊的條數(shù)稱為x的出度，記作deg-(x)或d-(x).注意：有向圖D中，結(jié)點x的度deg(x)=deg+(x)+deg-(x)。Δ(G)和δ(G)分別表示G的最大頂點度和最小頂點度，即Δ(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é)圖的頂點度和圖的同構(gòu)(1)定義2

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

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

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

設(shè)簡單圖G中每個頂點的度數(shù)至少是3,則G中含有偶圈.證明:在G的所有路中,取一條長度最長的路p,記p=v0v1…vt-1vt.則v0的所有鄰接點全在p中,設(shè)v0的所有鄰接點為vi1,vi2,…,vis,1i1i2…ist,其中s=d(v0)3,在G中取三個圈c1=v0v1…vi2v0,c2=v0v1…visv0,c3=v0vi2vi2+1…visv0,它們的長度分別為i2+1,is+1和is-i2+2.這三個數(shù)中至少有一個是偶數(shù).即c1,c2,c3中至少有一個是偶圈.定義3給定無向圖G=<V(G),E(G),(G)>,x,y∈V(G),若圖中存在連接x和y的路,稱節(jié)點x和y是連通的.規(guī)定x到自身總是連通的.說明：容易驗證,結(jié)點集V(G)上的頂點間的連通關(guān)系是V(G)上的一個等價關(guān)系,該等價關(guān)系確定V(G)的一個劃分{V1,V2,…,Vm},使得當(dāng)且僅當(dāng)兩個頂點x和y屬于同一子集Vi時,x和y才是連通的.第四節(jié)路與連通圖(四)Vi在G中的導(dǎo)出子圖G[V1],G[V2],…,G[Vm]稱為G的連通分支或分支,m稱為G的連通分支數(shù),記作W(G)=m.如下圖有4個連通分支.定義4.如果無向圖G中每一對不同的頂點x和y都有一條路,即W(G)=1,則稱G是連通圖,反之稱為非連通圖.[S,T]＝{e|e∈E(G),e的兩個端點分別在S和T中}，其中T=V-S。引理1非平凡圖G是連通圖當(dāng)且僅當(dāng)對V(G)的每一個非空真子集S,[S,S’]≠Ф,S’=V-S.第四節(jié)路與連通圖(五)定理3設(shè)G是P階連通圖,則證明:只需證明連通的簡單圖成立即可.設(shè)懸掛點:度數(shù)為1頂點.第四節(jié)路與連通圖(六)定理4

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

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

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

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

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

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

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

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

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

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

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

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連通的,則對(反證)定理3設(shè)G是2邊連通圖,則G有強連通的定向圖.證明:設(shè)G是2邊連通圖,則G必含有圈.先取一個圈C1,定義G的連通子圖序列G1,G2,…如下:G1=C1;若Gi(i=1,2,…)不是G的生成子圖,設(shè)vi是在G中而不在Gi中的一個頂點,則存在從vi到Gi的邊不重路Pi和Qi,定義由于該序列必終止于G的一個生成子圖Gn.依次對每個Gi定向:首先讓G1的定向圖成為一個有向圈;對設(shè)已有定向圖,讓Pi成為以vi為始點的有向路,而Qi成為以vi為終點的有向路,得,即是強連通圖i=1,2,…n.第五節(jié)連通圖和二分圖(4)

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

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

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

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