圖論基本概念課件

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。

圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。

哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐一個圖G=

(V

,

E

)

由一些點及點之間的連線（稱為邊）構(gòu)成，V、E

分別記G的點集合和邊集合。在圖的概念中，點的空間位置、邊的曲直長短都是無關(guān)緊要的，重要的是其有幾個點以及哪些點之間有邊相連。v1v2v3v4v5v1v2v3v4v5≌一個圖G=(V,E)由一些點及點之間的連線（稱如果用點表示要研究的對象，則圖的邊可以用來反映對象之間是否存在某種關(guān)系。用點表示人，邊表示兩個人是否互相認(rèn)識；在地區(qū)公路圖中，用點表示城市，邊表示城市之間是否有公路直接相連；在分子結(jié)構(gòu)圖中，用點表示原子，邊表示原子之間是否存在化學(xué)鍵；……如果用點表示要研究的對象，則圖的邊可以用來反映對象之間是否存哥尼斯堡

七橋問題

ABCDABCD(Euler,1736)右圖是否存在經(jīng)過每條邊恰好一次的回路，即是否為

Euler圖？是否可以一筆畫?哥尼斯堡七橋問化學(xué)藥品存放問題某單位需要存放一些化學(xué)藥品，其中某些藥品不能放在同一個庫房里，問至少需要幾個庫房？用點表示藥品，在不能放在同一個庫房的兩種藥品之間連邊。需要幾個庫房等價于需要用幾種顏色給圖的點著色可以使得相鄰的點有不同的顏色。abcdefg圖中的7種藥品需要3個庫房，例如{a

,b

,e}，{c

,d

,g}，{f}各放一個庫房?；瘜W(xué)藥品存放問題某單位需要存放一些化學(xué)藥品，其中某些藥品不能排課表問題有m位教師x1,

…,

xm和n個班級y1,

…,

yn，教師xi需要給班級yj

上wij

節(jié)課，試編制一張課表使得課時盡量少。構(gòu)造圖

G=(V

,

E

)，其中V={

x1,

…,

xm,y1,

…,

yn

}

,點

xi

與

yj

之間連有

wij

條邊。給G的邊著色，使得相鄰的邊有不同的顏色。需要3種顏色給邊著色y1y2y3x1x2x3x4排課表問題有m位教師x1,…,xm和n個班圖的基本概念一個有序二元組(V,E)稱為一個圖,記G=(V,E),其中①V或V(G)稱為G的頂點集,V≠Φ,其元素稱為頂點或結(jié)點,簡稱點;②

E或E(G)稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個點,如果這兩個點是無序的,則稱該邊為無向邊,否則,稱為有向邊.圖的基本概念一個有序二元組(V,E)稱為一個圖,點v

的度數(shù)：與v

相連的邊的條數(shù)，記作d(v)。與頂點v出關(guān)聯(lián)的邊的數(shù)目稱為出度，記作d

+(v),與頂點v入關(guān)聯(lián)的邊的數(shù)目稱為入度，記作d

-(v)。命題：圖的所有點的度數(shù)之和等于邊數(shù)的兩倍，即例.碳?xì)浠衔镏袣湓拥膫€數(shù)為偶數(shù)。CHHHHCCHHHHCCCCCCHHHHHH點v的度數(shù)：與v相連的邊的條數(shù)，記作d(v)。命兩個圖G=

(V

,

E

)和，如果有則稱G是G

的子圖。若G是G

的子圖，且V

=V，則稱G是G

的生成子圖。G

G'

G''

G'

和G''都是G的生成子圖。兩個圖G=(V,E)和邊數(shù)

k稱為鏈P

的長度。v1v2v4v3v5v6v7v8稱為鏈，其中當(dāng)v0

=

vk

時，稱P

為閉鏈。邊不重復(fù)的鏈稱為跡。點不重復(fù)的鏈稱為路，v0=vk

的回路稱為圈。圖G

的一條點與邊的交替序列跡的長度為7閉跡的長度為6圈的長度為4命題：若點v

與v

之間有Walk，則點v

與v

之間必有Path。邊數(shù)k稱為鏈P的長度。v1v2v4v3v5v6v7v8在圖G中，若點u、v之間有路，則稱u、v連通。若G的任何兩點之間有路，則稱G

是連通圖。G

的極大連通子圖稱為連通分支。有三個連通分支若刪去某條邊e之后圖的連通分支數(shù)增加，則稱e為割邊或橋；若刪去某個點v及相連的邊后連通分支數(shù)增加，則稱v為割點。euvwe為割邊u、v、w

皆為割點在圖G中，若點u、v之間有路，則稱u、v連通。若簡單圖：任何一條邊連結(jié)兩個不同的點，任何兩個點之間至多有一條邊的圖。完全圖：任何兩個點之間都有邊相連的簡單圖。n

個點的完全圖記作Kn。

K3K4K5該圖非簡單圖多重邊自環(huán)簡單圖：任何一條邊連結(jié)兩個不同的點，任何兩個點之間至多有一條二分圖：點集

V能劃分成兩個子集X、Y，使得每條邊的兩個端點分別屬于X

和Y

的圖。二分圖G

也記作G=(X,Y,E

)。稱G=(X,Y,E

)為完全二分圖，若

X中的每個點和Y中的每個點之間皆有邊相連，記作。K1,3K2,3K3,3命題：圖

G是二分圖當(dāng)且僅當(dāng)G中不存在長度為奇數(shù)的圈。二分圖：點集V能劃分成兩個子集X、Y，使得每條邊的兩在圖G

=

(V

,E

)的邊集上定義權(quán)函數(shù)后就得到一個賦權(quán)圖，記為G=(V

,

E

,

w)

。對于賦權(quán)圖，路的長度（即路的權(quán)）通常指路上所有邊的權(quán)之和。最短路問題：求賦權(quán)圖上指定點之間的權(quán)最小的路。在圖G=(V,E)的邊集上定義權(quán)函數(shù)

鄰接矩陣

A=(aij)n×n,例:寫出右圖的鄰接矩陣：解：圖的矩陣表示鄰接矩陣A=(aij)n×n,例:寫出右圖的鄰權(quán)矩陣W=(wij)n×n例:寫出右圖的權(quán)矩陣：解：圖的矩陣表示權(quán)矩陣W=(wij)n×n例:寫出右圖的權(quán)矩陣：

關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無向圖：圖的矩陣表示關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無向圖：圖例:寫出右圖與其基本圖的關(guān)聯(lián)矩陣解：分別為：圖的矩陣表示例:寫出右圖與其基本圖解：分別為：圖的矩陣表示用圖論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。圖論的基本概念用圖論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃解：用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0.）共24=16種狀態(tài)，由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，圖論的基本概念解：用四維0-1向量表示（人，狼，羊，菜）的在西岸共24=1人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個向量作為頂點，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個頂點的偶圖。問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達(dá)沒有到達(dá)的相鄰頂點，到（0,0,0,0）終止，得到有向圖即是。人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,例2、證明：在任意6人的集會上，總有3人互相認(rèn)識，或總有3人互相不認(rèn)識。解：以頂點表示人，以邊表示認(rèn)識，得6個頂點的簡單圖G。問題：3人互相認(rèn)識即G包含K3為子圖，3人互相不認(rèn)識即G包含（3,0）圖為子圖。圖論的基本概念例2、證明：在任意6人的集會上，總有3人互相認(rèn)解：以頂點表示圖論的基本概念圖論的基本概念

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。

圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。

哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐一個圖G=

(V

,

E

)

由一些點及點之間的連線（稱為邊）構(gòu)成，V、E

分別記G的點集合和邊集合。在圖的概念中，點的空間位置、邊的曲直長短都是無關(guān)緊要的，重要的是其有幾個點以及哪些點之間有邊相連。v1v2v3v4v5v1v2v3v4v5≌一個圖G=(V,E)由一些點及點之間的連線（稱如果用點表示要研究的對象，則圖的邊可以用來反映對象之間是否存在某種關(guān)系。用點表示人，邊表示兩個人是否互相認(rèn)識；在地區(qū)公路圖中，用點表示城市，邊表示城市之間是否有公路直接相連；在分子結(jié)構(gòu)圖中，用點表示原子，邊表示原子之間是否存在化學(xué)鍵；……如果用點表示要研究的對象，則圖的邊可以用來反映對象之間是否存哥尼斯堡

七橋問題

ABCDABCD(Euler,1736)右圖是否存在經(jīng)過每條邊恰好一次的回路，即是否為

Euler圖？是否可以一筆畫?哥尼斯堡七橋問化學(xué)藥品存放問題某單位需要存放一些化學(xué)藥品，其中某些藥品不能放在同一個庫房里，問至少需要幾個庫房？用點表示藥品，在不能放在同一個庫房的兩種藥品之間連邊。需要幾個庫房等價于需要用幾種顏色給圖的點著色可以使得相鄰的點有不同的顏色。abcdefg圖中的7種藥品需要3個庫房，例如{a

,b

,e}，{c

,d

,g}，{f}各放一個庫房。化學(xué)藥品存放問題某單位需要存放一些化學(xué)藥品，其中某些藥品不能排課表問題有m位教師x1,

…,

xm和n個班級y1,

…,

yn，教師xi需要給班級yj

上wij

節(jié)課，試編制一張課表使得課時盡量少。構(gòu)造圖

G=(V

,

E

)，其中V={

x1,

…,

xm,y1,

…,

yn

}

,點

xi

與

yj

之間連有

wij

條邊。給G的邊著色，使得相鄰的邊有不同的顏色。需要3種顏色給邊著色y1y2y3x1x2x3x4排課表問題有m位教師x1,…,xm和n個班圖的基本概念一個有序二元組(V,E)稱為一個圖,記G=(V,E),其中①V或V(G)稱為G的頂點集,V≠Φ,其元素稱為頂點或結(jié)點,簡稱點;②

E或E(G)稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個點,如果這兩個點是無序的,則稱該邊為無向邊,否則,稱為有向邊.圖的基本概念一個有序二元組(V,E)稱為一個圖,點v

的度數(shù)：與v

相連的邊的條數(shù)，記作d(v)。與頂點v出關(guān)聯(lián)的邊的數(shù)目稱為出度，記作d

+(v),與頂點v入關(guān)聯(lián)的邊的數(shù)目稱為入度，記作d

-(v)。命題：圖的所有點的度數(shù)之和等于邊數(shù)的兩倍，即例.碳?xì)浠衔镏袣湓拥膫€數(shù)為偶數(shù)。CHHHHCCHHHHCCCCCCHHHHHH點v的度數(shù)：與v相連的邊的條數(shù)，記作d(v)。命兩個圖G=

(V

,

E

)和，如果有則稱G是G

的子圖。若G是G

的子圖，且V

=V，則稱G是G

的生成子圖。G

G'

G''

G'

和G''都是G的生成子圖。兩個圖G=(V,E)和邊數(shù)

k稱為鏈P

的長度。v1v2v4v3v5v6v7v8稱為鏈，其中當(dāng)v0

=

vk

時，稱P

為閉鏈。邊不重復(fù)的鏈稱為跡。點不重復(fù)的鏈稱為路，v0=vk

的回路稱為圈。圖G

的一條點與邊的交替序列跡的長度為7閉跡的長度為6圈的長度為4命題：若點v

與v

之間有Walk，則點v

與v

之間必有Path。邊數(shù)k稱為鏈P的長度。v1v2v4v3v5v6v7v8在圖G中，若點u、v之間有路，則稱u、v連通。若G的任何兩點之間有路，則稱G

是連通圖。G

的極大連通子圖稱為連通分支。有三個連通分支若刪去某條邊e之后圖的連通分支數(shù)增加，則稱e為割邊或橋；若刪去某個點v及相連的邊后連通分支數(shù)增加，則稱v為割點。euvwe為割邊u、v、w

皆為割點在圖G中，若點u、v之間有路，則稱u、v連通。若簡單圖：任何一條邊連結(jié)兩個不同的點，任何兩個點之間至多有一條邊的圖。完全圖：任何兩個點之間都有邊相連的簡單圖。n

個點的完全圖記作Kn。

K3K4K5該圖非簡單圖多重邊自環(huán)簡單圖：任何一條邊連結(jié)兩個不同的點，任何兩個點之間至多有一條二分圖：點集

V能劃分成兩個子集X、Y，使得每條邊的兩個端點分別屬于X

和Y

的圖。二分圖G

也記作G=(X,Y,E

)。稱G=(X,Y,E

)為完全二分圖，若

X中的每個點和Y中的每個點之間皆有邊相連，記作。K1,3K2,3K3,3命題：圖

G是二分圖當(dāng)且僅當(dāng)G中不存在長度為奇數(shù)的圈。二分圖：點集V能劃分成兩個子集X、Y，使得每條邊的兩在圖G

=

(V

,E

)的邊集上定義權(quán)函數(shù)后就得到一個賦權(quán)圖，記為G=(V

,

E

,

w)

。對于賦權(quán)圖，路的長度（即路的權(quán)）通常指路上所有邊的權(quán)之和。最短路問題：求賦權(quán)圖上指定點之間的權(quán)最小的路。在圖G=(V,E)的邊集上定義權(quán)函數(shù)

鄰接矩陣

A=(aij)n×n,例:寫出右圖的鄰接矩陣：解：圖的矩陣表示鄰接矩陣A=(aij)n×n,例:寫出右圖的鄰權(quán)矩陣W=(wij)n×n例:寫出右圖的權(quán)矩陣：解：圖的矩陣表示權(quán)矩陣W=(wij)n×n例:寫出右圖的權(quán)矩陣：

關(guān)聯(lián)矩陣A=(aij)n×m