圖和子圖1課件

1.1基本概念現(xiàn)實世界的許多現(xiàn)象可以用一類圖形來描述，這種圖形由一個點集和連接這個點集中某些點對的線所構(gòu)成．例如用點表示車站，線表示連接車站與車站的道路；或者用點表示人，連線表示一對朋友．在這種圖形中，人們主要感興趣的是：兩點是否被一條線所連接，而連線的長短曲直則無關(guān)緊要．大量的這類事實的數(shù)學抽象，產(chǎn)生了圖的概念．1.1基本概念現(xiàn)實世界的許多現(xiàn)象可以用一類圖形來描述，這1圖的概念有序三元組G＝[V(G)，E(G)，ΨG]稱為一個圖，其中：ⅰ)V(G)稱為頂點集合；ⅱ)E(G)∩V(G)=φ，E(G)稱為邊集合；ⅲ)ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射，稱為關(guān)聯(lián)函數(shù)．V(G)中的元素稱為頂點，E(G)中的元素稱為邊．V(G)所含元素的個數(shù)即頂點個數(shù)稱為圖的階，用|V(G)|表示．E(G)所含元素的個數(shù)稱為G的邊數(shù)，用|E(G)|表示．我們用G(p，q)表添一個階為p、邊數(shù)為q的圖G，這時也說G是一個(p，q)圖．圖的概念有序三元組G＝[V(G)，E(G)，ΨG]稱為一個圖2例題G＝[V(G)，E(G)，ΨG]，其中：V(G)={v1,v2,v3,v4}，E(G)={e1,e2,e3,e4,e5,e6}，ΨG定義為：ΨG(e1)=v2v3，ΨG(e2)=v3v4

ΨG(e3)=v4v4，ΨG(e4)=v2v4

ΨG(e5)=v2v3，ΨG(e6)=v1v3e1e6e5e4e3e2e1e6e5e4e3e2例題G＝[V(G)，E(G)，ΨG]，其中：V(G)={3相關(guān)概念在圖G＝[V(G)，E(G)，ΨG]中,若e∈E(G)，u,v∈V(G)，而ΨG(e)=(u,v)，則稱u和v是e的端點，或e和u,v關(guān)聯(lián)，此時稱u和v是鄰接的。若兩條不同的邊ei和ej有一個公共端點，則稱是鄰接的，不與任何邊鄰接的邊稱為孤立邊，不與任何邊關(guān)聯(lián)的頂點稱為孤立點。兩端重合的邊稱為環(huán)，端點不同的邊稱為桿。若V(G)和E(G)都是有限集，則稱G為有限圖。G(0,0)稱為空圖，E(G)=φ即G是由孤立點所組成，稱為零圖。G(1,0)稱為平凡圖。相關(guān)概念在圖G＝[V(G)，E(G)，ΨG]中,若e∈E4簡單圖和完全圖圖中若連接兩個相同頂點的邊的條數(shù)大于1，則說這對頂點間有重邊相連．同一對頂點間邊的條數(shù)稱為邊的重數(shù)，既沒有環(huán)也沒有重邊的圖稱為簡單圖，否則稱為偽圖，沒有環(huán)的偽圖稱為多重圖．每對不同的頂點均有邊相連的簡單圖稱為完全圖．n階完全圖記為Kn定理1.1：Kn有條邊簡單圖和完全圖圖中若連接兩個相同頂點的邊的條數(shù)大于1，則說這5二分圖圖G的頂點集V(G)若能分成兩個子集V1和V2，使得G的每條邊有一個端點在V1

，另一個端點在V2中，則G稱為二分圖或偶圖．這樣一個把V(G)分成兩個集合V1

、V2的分劃(V1,V2)稱為G的一個二分劃．設(shè)簡單二分圖G的二分劃為(V1,V2)，如果V1的每個頂點與V2的每一個頂點都鄰接，則G稱為完全二分圖．若|V1|=m,|V2|=n,則這樣的圖記為Km,n定理1.2

Km,n有mn條邊。二分圖圖G的頂點集V(G)若能分成兩個子集V1和V2，使得G6補圖G是簡單圖，如果簡單圖GC滿足，ⅰ)V(GC)=V(G)ⅱ)V(GC)中兩點當且僅當它們在G中不鄰接時在GC中鄰接．那么GC稱為G的補圖．G：GC：補圖G是簡單圖，如果簡單圖GC滿足，G：GC：7平面圖在保持圖的頂點和邊的關(guān)聯(lián)關(guān)系不變的情況下，一個圖可以作出許多圖形．如果一個圖具有這樣的圖形，它的邊僅在頂點處相交，則稱它為平面圖．判斷圖1是否為平面圖？圖1：圖2：平面圖在保持圖的頂點和邊的關(guān)聯(lián)關(guān)系不變的情況下，一個圖可以作8恒同和同構(gòu)兩個圖H和G，如果V(H)＝V(G)，E(H)＝E(G)且ΨH＝

ΨG，那么H和G就稱為是恒同的，恒同的圖當然可以用一個圖形來表示．G＝[V(G)，E(G)，ΨG]和H＝[V(H)，E(H)，ΨH]，若存在1-1對應偶(θ,φ)，θ:V(G)→V(H)；φ:E(G)→E(H)，使得當且僅當ΨH(φ(e))=θ(u)θ(v)時，ΨG(e)=uv，則說這兩個圖同構(gòu)，記為G≌H恒同和同構(gòu)兩個圖H和G，如果V(H)＝V(G)，E(H)＝E9度與正則圖設(shè)v∈V(G)，G中與頂點v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度(次)，記為dG(v)或d(v)．一個環(huán)的端點的度數(shù)計為2．如果d(v)是奇數(shù)，就說v是奇頂點；如果d(v)是偶數(shù)，就說v是偶頂點．如果一個圖的每一個頂點都具有相同的度，則稱這個圖是正則圖。每個頂點的度均為k的正則圖，稱為k-正則圖．度與正則圖設(shè)v∈V(G)，G中與頂點v關(guān)聯(lián)的邊的數(shù)目稱為v在10有關(guān)度的定理定理1.3

圖G中各頂點度數(shù)之和等于邊數(shù)的2倍。推論1.4任意一個圖奇頂點的個數(shù)是偶數(shù)．推論1.5正則圖的階與各頂點度數(shù)不全為奇數(shù)．有關(guān)度的定理定理1.3圖G中各頂點度數(shù)之和等于邊數(shù)的211子圖設(shè)H和G是兩個圖，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH是

ΨG在E(H)內(nèi)的導出函數(shù)，那么H稱為G的子圖，此時G稱為H的母圖，記為如果而H≠G，則說H是G的真子圖，記為設(shè)H是G的子圖，如果V(H)=V(G)，則H稱為G的生成子圖。子圖設(shè)H和G是兩個圖，如果V(H)是V(G)的子集，E(H)12導出子圖設(shè)V’是V(G)的非空子集，H是G的一個子圖，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e|e∈E(G),ΨG(e)=uv，u,v∈V’}；ⅲ)ΨH是ΨG在E(H)上的導出函數(shù)。那么H稱為由V’導出的G的子圖，記為G[V’]導出子圖G[V-V’]記為G-V’，它是從G中刪除V’中的頂點及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。若V’={v}，則把G-{v}簡記為G-v，稱為G的刪點子圖。同理以E’中的端點的全體為集所組成的子圖稱為由E’導出的子圖，記為G[E’]。刪去邊集合E’中的邊之后得出的導出子圖記為G-E’G-e,G+e導出子圖設(shè)V’是V(G)的非空子集，H是G的一個子圖，如果：13例GG的一個生成子圖G-{2,3}G[{3,4,6}]G-{e,g,h}G[{a,c,e,g,h}]例GG的一個生成子圖G-{2,3}G[{3,4,6}]G-{14子圖的運算(并、交、差、環(huán)和)G1G2G1∪

G2G1∩

G2G2-

G1G1

G2子圖的運算(并、交、差、環(huán)和)G1G2G1∪G2G1∩G15通路和回路圖G中一個點邊交替的非空有限序列w＝v0e1v1e2v2…envn稱為G的一個途徑．其中vi是頂點，ei是邊，對于1≤i≤n，e的端點是vi-1和vi，v0和vn分別稱為途徑的起點和終點，而v1,v2,…,vn-1稱為途徑的內(nèi)頂點，整數(shù)n稱為途徑w的長．途徑w中若干相連項構(gòu)成的子序列viei+1vi+1…ejvj稱為w的(vi,vj)節(jié)．將序列w逆轉(zhuǎn)后所得途徑vnenvn-1…v1e1v0記為w-1．在簡單圖中，途徑w可以由它的頂點序列v0e1v1e2v2…envn所確定．因此在簡單圖中可以用頂點序列表示一個途徑．通路和回路圖G中一個點邊交替的非空有限序列w＝v0e1v1e16相關(guān)概念若途徑的邊e1,e2,

…,en互不相同，則稱之為鏈，此外，若頂點也互不相同，則稱w為通路．對G的兩個頂點u和v,如果在G中存在一條(u,v)的通路，則稱頂點u與v是連通的．如果圖G中的任意一對頂點都是連通的，則G稱為連通圖．設(shè)G的頂點u與v是連通的，那么G中最短的(u,v)通路的長就稱為u與v的距離，記為d(u,v)．相關(guān)概念若途徑的邊e1,e2,…,en互不相同，則17回路一條具有正的長度且起點、終點重合的途徑稱為閉途徑．類似可以定義閉鏈、閉通路．閉通路稱為回路(亦稱圈)．長為K的回路稱為K-回路．定理1.7

對于階數(shù)不小于2的圖G，當且僅當G不含奇回路時，它才是二分圖．證明：充分性易證,下面證必要性。設(shè)G是無奇回路的連通圖，任取G的一個頂點u并將V(G)作如下的劃分(V1,V2)：V1={x|x∈V(G)，d(u,x)是偶數(shù)}V2={y|y∈V(G)，d(u,y)是奇數(shù)}然后證明這恰是G的一個二分劃。回路一條具有正的長度且起點、終點重合的途徑稱為閉途徑．類似可18設(shè)v和w是V1的兩個頂點，又設(shè)P是最短(u,v)-通路，Q是最短(u,w)-通路，以u1記P和Q的最后一個公共頂點，因為P、Q是最短通路，P和Q的(u,u1)-節(jié)也是最短的(u,u1)-通路，因此具有相同的長度．又因P和Q的長度是偶數(shù)，所以P上(u1,v)-節(jié)P1的長度與Q上(u1,w)-節(jié)Q1的長度具有相同的奇偶性，由此推出(v,w)通路P1-1Q1的長度為偶數(shù)，若v與w鄰接，則wv是G的一條奇回路，此與假設(shè)矛盾，故V1中任意兩點均不鄰接，同理V2中任意兩個頂點也不鄰接，因此G是二分圖。設(shè)v和w是V1的兩個頂點，又設(shè)P是最短(u,v)-通路，Q是19最短通路問題如果對圖G的一條邊，賦以一個實數(shù)w(e)，稱為這條邊的權(quán)，那么G連同它的邊上的權(quán)稱為賦權(quán)圖．若G是一個賦權(quán)圖，H是G的子圖，那么H的權(quán)是它所有邊的權(quán)之和，即如果P是G的一條通路，通路上各邊的權(quán)也稱為該邊的長度，通路上各邊的長度之和稱為通路的長．所謂最短通路問題，就是在G中所有(u0,v0)-通路中，尋找一條長度最小的(u0,v0)-通路．u0到v0的最短通路長記為d(u0,v0),稱作u0到v0的距離。最短通路問題如果對圖G的一條邊，賦以一個實數(shù)w(e)，稱為這20Dijkstra算法關(guān)于求最短通路問題，Dijkstra算法是最有名的方法之一，它的基本思想是：把G的頂點分為S，T兩類，若u0到某個頂點x的最短通路已求出，則將x歸入S，其余點歸入y，開始S中只有u0，隨著程序的運行，我們就把T的元素逐個轉(zhuǎn)入S直到v0也被轉(zhuǎn)入S，程序就結(jié)束了．使用這一算法不僅可以找出最短的(u0,v0)-通路，而且可以給出u0到其它任何頂點的最短通路．Dijkstra算法關(guān)于求最短通路問題，Dijkstra算法21Dijkstra算法流程圖i=0,S={u0}l(u0)=0,l(v)=∞v≠u0停！YESNO計算Dijkstra算法流程圖i=0,S={u0}停！YESNO22Dijkstra算法示例Dijkstra算法示例23練習求下圖中V1到其它各點的最短距離，并寫出V1到V6的最短路徑.求下圖中點U到點V的最短距離，并寫出其最短路徑.練習求下圖中V1到其它各點的最短距離，并寫出V1到V6的最短24教師社區(qū)如何下載課件教師社區(qū)如何下載課件25點擊此處如何下載課件點擊此處如何下載課件26選擇課件如何下載課件選擇課件如何下載課件27下載課件如何下載課件下載課件如何下載課件281.1基本概念現(xiàn)實世界的許多現(xiàn)象可以用一類圖形來描述，這種圖形由一個點集和連接這個點集中某些點對的線所構(gòu)成．例如用點表示車站，線表示連接車站與車站的道路；或者用點表示人，連線表示一對朋友．在這種圖形中，人們主要感興趣的是：兩點是否被一條線所連接，而連線的長短曲直則無關(guān)緊要．大量的這類事實的數(shù)學抽象，產(chǎn)生了圖的概念．1.1基本概念現(xiàn)實世界的許多現(xiàn)象可以用一類圖形來描述，這29圖的概念有序三元組G＝[V(G)，E(G)，ΨG]稱為一個圖，其中：ⅰ)V(G)稱為頂點集合；ⅱ)E(G)∩V(G)=φ，E(G)稱為邊集合；ⅲ)ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射，稱為關(guān)聯(lián)函數(shù)．V(G)中的元素稱為頂點，E(G)中的元素稱為邊．V(G)所含元素的個數(shù)即頂點個數(shù)稱為圖的階，用|V(G)|表示．E(G)所含元素的個數(shù)稱為G的邊數(shù)，用|E(G)|表示．我們用G(p，q)表添一個階為p、邊數(shù)為q的圖G，這時也說G是一個(p，q)圖．圖的概念有序三元組G＝[V(G)，E(G)，ΨG]稱為一個圖30例題G＝[V(G)，E(G)，ΨG]，其中：V(G)={v1,v2,v3,v4}，E(G)={e1,e2,e3,e4,e5,e6}，ΨG定義為：ΨG(e1)=v2v3，ΨG(e2)=v3v4

ΨG(e3)=v4v4，ΨG(e4)=v2v4

ΨG(e5)=v2v3，ΨG(e6)=v1v3e1e6e5e4e3e2e1e6e5e4e3e2例題G＝[V(G)，E(G)，ΨG]，其中：V(G)={31相關(guān)概念在圖G＝[V(G)，E(G)，ΨG]中,若e∈E(G)，u,v∈V(G)，而ΨG(e)=(u,v)，則稱u和v是e的端點，或e和u,v關(guān)聯(lián)，此時稱u和v是鄰接的。若兩條不同的邊ei和ej有一個公共端點，則稱是鄰接的，不與任何邊鄰接的邊稱為孤立邊，不與任何邊關(guān)聯(lián)的頂點稱為孤立點。兩端重合的邊稱為環(huán)，端點不同的邊稱為桿。若V(G)和E(G)都是有限集，則稱G為有限圖。G(0,0)稱為空圖，E(G)=φ即G是由孤立點所組成，稱為零圖。G(1,0)稱為平凡圖。相關(guān)概念在圖G＝[V(G)，E(G)，ΨG]中,若e∈E32簡單圖和完全圖圖中若連接兩個相同頂點的邊的條數(shù)大于1，則說這對頂點間有重邊相連．同一對頂點間邊的條數(shù)稱為邊的重數(shù)，既沒有環(huán)也沒有重邊的圖稱為簡單圖，否則稱為偽圖，沒有環(huán)的偽圖稱為多重圖．每對不同的頂點均有邊相連的簡單圖稱為完全圖．n階完全圖記為Kn定理1.1：Kn有條邊簡單圖和完全圖圖中若連接兩個相同頂點的邊的條數(shù)大于1，則說這33二分圖圖G的頂點集V(G)若能分成兩個子集V1和V2，使得G的每條邊有一個端點在V1

，另一個端點在V2中，則G稱為二分圖或偶圖．這樣一個把V(G)分成兩個集合V1

、V2的分劃(V1,V2)稱為G的一個二分劃．設(shè)簡單二分圖G的二分劃為(V1,V2)，如果V1的每個頂點與V2的每一個頂點都鄰接，則G稱為完全二分圖．若|V1|=m,|V2|=n,則這樣的圖記為Km,n定理1.2

Km,n有mn條邊。二分圖圖G的頂點集V(G)若能分成兩個子集V1和V2，使得G34補圖G是簡單圖，如果簡單圖GC滿足，ⅰ)V(GC)=V(G)ⅱ)V(GC)中兩點當且僅當它們在G中不鄰接時在GC中鄰接．那么GC稱為G的補圖．G：GC：補圖G是簡單圖，如果簡單圖GC滿足，G：GC：35平面圖在保持圖的頂點和邊的關(guān)聯(lián)關(guān)系不變的情況下，一個圖可以作出許多圖形．如果一個圖具有這樣的圖形，它的邊僅在頂點處相交，則稱它為平面圖．判斷圖1是否為平面圖？圖1：圖2：平面圖在保持圖的頂點和邊的關(guān)聯(lián)關(guān)系不變的情況下，一個圖可以作36恒同和同構(gòu)兩個圖H和G，如果V(H)＝V(G)，E(H)＝E(G)且ΨH＝

ΨG，那么H和G就稱為是恒同的，恒同的圖當然可以用一個圖形來表示．G＝[V(G)，E(G)，ΨG]和H＝[V(H)，E(H)，ΨH]，若存在1-1對應偶(θ,φ)，θ:V(G)→V(H)；φ:E(G)→E(H)，使得當且僅當ΨH(φ(e))=θ(u)θ(v)時，ΨG(e)=uv，則說這兩個圖同構(gòu)，記為G≌H恒同和同構(gòu)兩個圖H和G，如果V(H)＝V(G)，E(H)＝E37度與正則圖設(shè)v∈V(G)，G中與頂點v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度(次)，記為dG(v)或d(v)．一個環(huán)的端點的度數(shù)計為2．如果d(v)是奇數(shù)，就說v是奇頂點；如果d(v)是偶數(shù)，就說v是偶頂點．如果一個圖的每一個頂點都具有相同的度，則稱這個圖是正則圖。每個頂點的度均為k的正則圖，稱為k-正則圖．度與正則圖設(shè)v∈V(G)，G中與頂點v關(guān)聯(lián)的邊的數(shù)目稱為v在38有關(guān)度的定理定理1.3

圖G中各頂點度數(shù)之和等于邊數(shù)的2倍。推論1.4任意一個圖奇頂點的個數(shù)是偶數(shù)．推論1.5正則圖的階與各頂點度數(shù)不全為奇數(shù)．有關(guān)度的定理定理1.3圖G中各頂點度數(shù)之和等于邊數(shù)的239子圖設(shè)H和G是兩個圖，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH是

ΨG在E(H)內(nèi)的導出函數(shù)，那么H稱為G的子圖，此時G稱為H的母圖，記為如果而H≠G，則說H是G的真子圖，記為設(shè)H是G的子圖，如果V(H)=V(G)，則H稱為G的生成子圖。子圖設(shè)H和G是兩個圖，如果V(H)是V(G)的子集，E(H)40導出子圖設(shè)V’是V(G)的非空子集，H是G的一個子圖，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e|e∈E(G),ΨG(e)=uv，u,v∈V’}；ⅲ)ΨH是ΨG在E(H)上的導出函數(shù)。那么H稱為由V’導出的G的子圖，記為G[V’]導出子圖G[V-V’]記為G-V’，它是從G中刪除V’中的頂點及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。若V’={v}，則把G-{v}簡記為G-v，稱為G的刪點子圖。同理以E’中的端點的全體為集所組成的子圖稱為由E’導出的子圖，記為G[E’]。刪去邊集合E’中的邊之后得出的導出子圖記為G-E’G-e,G+e導出子圖設(shè)V’是V(G)的非空子集，H是G的一個子圖，如果：41例GG的一個生成子圖G-{2,3}G[{3,4,6}]G-{e,g,h}G[{a,c,e,g,h}]例GG的一個生成子圖G-{2,3}G[{3,4,6}]G-{42子圖的運算(并、交、差、環(huán)和)G1G2G1∪

G2G1∩

G2G2-

G1G1

G2子圖的運算(并、交、差、環(huán)和)G1G2G1∪G2G1∩G43通路和回路圖G中一個點邊交替的非空有限序列w＝v0e1v1e2v2…envn稱為G的一個途徑．其中vi是頂點，ei是邊，對于1≤i≤n，e的端點是vi-1和vi，v0和vn分別稱為途徑的起點和終點，而v1,v2,…,vn-1稱為途徑的內(nèi)頂點，整數(shù)n稱為途徑w的長．途徑w中若干相連項構(gòu)成的子序列viei+1vi+1…ejvj稱為w的(vi,vj)節(jié)．將序列w逆轉(zhuǎn)后所得途徑vnenvn-1…v1e1v0記為w-1．在簡單圖中，途徑w可以由它的頂點序列v0e1v1e2v2…envn所確定．因此在簡單圖中可以用頂點序列表示一個途徑．通路和回路圖G中一個點邊交替的非空有限序列w＝v0e1v1e44相關(guān)概念若途徑的邊e1,e2,

…,en互不相同，則稱之為鏈，此外，若頂點也互不相同，則稱w為通路．對G的兩個頂點u和v,如果在G中存在一條(u,v)的通路，則稱頂點u與v是連通的．如果圖G中的任意一對頂點都是連通的，則G稱為連通圖．設(shè)G的頂點u與v是連通的，那么G中最短的(u,v)通路的長就稱為u與v的距離，記為d(u,v)．相關(guān)概念若途徑的邊e1,e2,…,en互不相同，則45回路一條具有正的長度且起點、終點重合的途徑稱為閉途徑．類似可以定義閉鏈、閉通路．閉通路稱為回路(亦稱圈)．長為K的回路稱為K-回路．定理1.7

對于階數(shù)不小于2的圖G，當且僅當G不含奇回路時，它才是二分圖．證明：充分性易證,下面證必要性。設(shè)G是無奇回路的連通圖，任取G的一個頂點u并將V(G)作如下的劃分(V1,V2)：V1={x|x∈V(G)，d(u,x)是偶數(shù)}V2={y|y∈V(G)，d(u,y)是奇數(shù)}然后證明這恰是G的一個二分劃?；芈芬粭l具有正的長度且起點、終點重合的途徑稱為閉途徑．類似可46設(shè)v和w是V1的兩個頂點，又設(shè)P是最短(u,v)-通路，Q是最短(u,w)-通路，以u1記P和Q的最后一個公共頂點，因為