版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1.1基本概念現(xiàn)實(shí)世界的許多現(xiàn)象可以用一類圖形來描述,這種圖形由一個(gè)點(diǎn)集和連接這個(gè)點(diǎn)集中某些點(diǎn)對(duì)的線所構(gòu)成.例如用點(diǎn)表示車站,線表示連接車站與車站的道路;或者用點(diǎn)表示人,連線表示一對(duì)朋友.在這種圖形中,人們主要感興趣的是:兩點(diǎn)是否被一條線所連接,而連線的長(zhǎng)短曲直則無關(guān)緊要.大量的這類事實(shí)的數(shù)學(xué)抽象,產(chǎn)生了圖的概念.1.1基本概念現(xiàn)實(shí)世界的許多現(xiàn)象可以用一類圖形來描述,這1圖的概念有序三元組G=[V(G),E(G),ΨG]稱為一個(gè)圖,其中:ⅰ)V(G)稱為頂點(diǎn)集合;ⅱ)E(G)∩V(G)=φ,E(G)稱為邊集合;ⅲ)ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射,稱為關(guān)聯(lián)函數(shù).V(G)中的元素稱為頂點(diǎn),E(G)中的元素稱為邊.V(G)所含元素的個(gè)數(shù)即頂點(diǎn)個(gè)數(shù)稱為圖的階,用|V(G)|表示.E(G)所含元素的個(gè)數(shù)稱為G的邊數(shù),用|E(G)|表示.我們用G(p,q)表添一個(gè)階為p、邊數(shù)為q的圖G,這時(shí)也說G是一個(gè)(p,q)圖.圖的概念有序三元組G=[V(G),E(G),Ψ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的端點(diǎn),或e和u,v關(guān)聯(lián),此時(shí)稱u和v是鄰接的。若兩條不同的邊ei和ej有一個(gè)公共端點(diǎn),則稱是鄰接的,不與任何邊鄰接的邊稱為孤立邊,不與任何邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn)。兩端重合的邊稱為環(huán),端點(diǎn)不同的邊稱為桿。若V(G)和E(G)都是有限集,則稱G為有限圖。G(0,0)稱為空?qǐng)D,E(G)=φ即G是由孤立點(diǎn)所組成,稱為零圖。G(1,0)稱為平凡圖。相關(guān)概念在圖G=[V(G),E(G),ΨG]中,若e∈E4簡(jiǎn)單圖和完全圖圖中若連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)大于1,則說這對(duì)頂點(diǎn)間有重邊相連.同一對(duì)頂點(diǎn)間邊的條數(shù)稱為邊的重?cái)?shù),既沒有環(huán)也沒有重邊的圖稱為簡(jiǎn)單圖,否則稱為偽圖,沒有環(huán)的偽圖稱為多重圖.每對(duì)不同的頂點(diǎn)均有邊相連的簡(jiǎn)單圖稱為完全圖.n階完全圖記為Kn定理1.1:Kn有條邊簡(jiǎn)單圖和完全圖圖中若連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)大于1,則說這5二分圖圖G的頂點(diǎn)集V(G)若能分成兩個(gè)子集V1和V2,使得G的每條邊有一個(gè)端點(diǎn)在V1
,另一個(gè)端點(diǎn)在V2中,則G稱為二分圖或偶圖.這樣一個(gè)把V(G)分成兩個(gè)集合V1
、V2的分劃(V1,V2)稱為G的一個(gè)二分劃.設(shè)簡(jiǎn)單二分圖G的二分劃為(V1,V2),如果V1的每個(gè)頂點(diǎn)與V2的每一個(gè)頂點(diǎn)都鄰接,則G稱為完全二分圖.若|V1|=m,|V2|=n,則這樣的圖記為Km,n定理1.2
Km,n有mn條邊。二分圖圖G的頂點(diǎn)集V(G)若能分成兩個(gè)子集V1和V2,使得G6補(bǔ)圖G是簡(jiǎn)單圖,如果簡(jiǎn)單圖GC滿足,ⅰ)V(GC)=V(G)ⅱ)V(GC)中兩點(diǎn)當(dāng)且僅當(dāng)它們?cè)贕中不鄰接時(shí)在GC中鄰接.那么GC稱為G的補(bǔ)圖.G:GC:補(bǔ)圖G是簡(jiǎn)單圖,如果簡(jiǎn)單圖GC滿足,G:GC:7平面圖在保持圖的頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系不變的情況下,一個(gè)圖可以作出許多圖形.如果一個(gè)圖具有這樣的圖形,它的邊僅在頂點(diǎn)處相交,則稱它為平面圖.判斷圖1是否為平面圖?圖1:圖2:平面圖在保持圖的頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系不變的情況下,一個(gè)圖可以作8恒同和同構(gòu)兩個(gè)圖H和G,如果V(H)=V(G),E(H)=E(G)且ΨH=
ΨG,那么H和G就稱為是恒同的,恒同的圖當(dāng)然可以用一個(gè)圖形來表示.G=[V(G),E(G),ΨG]和H=[V(H),E(H),ΨH],若存在1-1對(duì)應(yīng)偶(θ,φ),θ:V(G)→V(H);φ:E(G)→E(H),使得當(dāng)且僅當(dāng)ΨH(φ(e))=θ(u)θ(v)時(shí),ΨG(e)=uv,則說這兩個(gè)圖同構(gòu),記為G≌H恒同和同構(gòu)兩個(gè)圖H和G,如果V(H)=V(G),E(H)=E9度與正則圖設(shè)v∈V(G),G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度(次),記為dG(v)或d(v).一個(gè)環(huán)的端點(diǎn)的度數(shù)計(jì)為2.如果d(v)是奇數(shù),就說v是奇頂點(diǎn);如果d(v)是偶數(shù),就說v是偶頂點(diǎn).如果一個(gè)圖的每一個(gè)頂點(diǎn)都具有相同的度,則稱這個(gè)圖是正則圖。每個(gè)頂點(diǎn)的度均為k的正則圖,稱為k-正則圖.度與正則圖設(shè)v∈V(G),G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目稱為v在10有關(guān)度的定理定理1.3
圖G中各頂點(diǎn)度數(shù)之和等于邊數(shù)的2倍。推論1.4任意一個(gè)圖奇頂點(diǎn)的個(gè)數(shù)是偶數(shù).推論1.5正則圖的階與各頂點(diǎn)度數(shù)不全為奇數(shù).有關(guān)度的定理定理1.3圖G中各頂點(diǎn)度數(shù)之和等于邊數(shù)的211子圖設(shè)H和G是兩個(gè)圖,如果V(H)是V(G)的子集,E(H)是E(G)的子集且ΨH是
ΨG在E(H)內(nèi)的導(dǎo)出函數(shù),那么H稱為G的子圖,此時(shí)G稱為H的母圖,記為如果而H≠G,則說H是G的真子圖,記為設(shè)H是G的子圖,如果V(H)=V(G),則H稱為G的生成子圖。子圖設(shè)H和G是兩個(gè)圖,如果V(H)是V(G)的子集,E(H)12導(dǎo)出子圖設(shè)V’是V(G)的非空子集,H是G的一個(gè)子圖,如果:ⅰ)V(H)=V’;ⅱ)E(H)={e|e∈E(G),ΨG(e)=uv,u,v∈V’};ⅲ)ΨH是ΨG在E(H)上的導(dǎo)出函數(shù)。那么H稱為由V’導(dǎo)出的G的子圖,記為G[V’]導(dǎo)出子圖G[V-V’]記為G-V’,它是從G中刪除V’中的頂點(diǎn)及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。若V’={v},則把G-{v}簡(jiǎn)記為G-v,稱為G的刪點(diǎn)子圖。同理以E’中的端點(diǎn)的全體為集所組成的子圖稱為由E’導(dǎo)出的子圖,記為G[E’]。刪去邊集合E’中的邊之后得出的導(dǎo)出子圖記為G-E’G-e,G+e導(dǎo)出子圖設(shè)V’是V(G)的非空子集,H是G的一個(gè)子圖,如果:13例GG的一個(gè)生成子圖G-{2,3}G[{3,4,6}]G-{e,g,h}G[{a,c,e,g,h}]例GG的一個(gè)生成子圖G-{2,3}G[{3,4,6}]G-{14子圖的運(yùn)算(并、交、差、環(huán)和)G1G2G1∪
G2G1∩
G2G2-
G1G1
G2子圖的運(yùn)算(并、交、差、環(huán)和)G1G2G1∪G2G1∩G15通路和回路圖G中一個(gè)點(diǎn)邊交替的非空有限序列w=v0e1v1e2v2…envn稱為G的一個(gè)途徑.其中vi是頂點(diǎn),ei是邊,對(duì)于1≤i≤n,e的端點(diǎn)是vi-1和vi,v0和vn分別稱為途徑的起點(diǎn)和終點(diǎn),而v1,v2,…,vn-1稱為途徑的內(nèi)頂點(diǎn),整數(shù)n稱為途徑w的長(zhǎng).途徑w中若干相連項(xiàng)構(gòu)成的子序列viei+1vi+1…ejvj稱為w的(vi,vj)節(jié).將序列w逆轉(zhuǎn)后所得途徑vnenvn-1…v1e1v0記為w-1.在簡(jiǎn)單圖中,途徑w可以由它的頂點(diǎn)序列v0e1v1e2v2…envn所確定.因此在簡(jiǎn)單圖中可以用頂點(diǎn)序列表示一個(gè)途徑.通路和回路圖G中一個(gè)點(diǎn)邊交替的非空有限序列w=v0e1v1e16相關(guān)概念若途徑的邊e1,e2,
…,en互不相同,則稱之為鏈,此外,若頂點(diǎn)也互不相同,則稱w為通路.對(duì)G的兩個(gè)頂點(diǎn)u和v,如果在G中存在一條(u,v)的通路,則稱頂點(diǎn)u與v是連通的.如果圖G中的任意一對(duì)頂點(diǎn)都是連通的,則G稱為連通圖.設(shè)G的頂點(diǎn)u與v是連通的,那么G中最短的(u,v)通路的長(zhǎng)就稱為u與v的距離,記為d(u,v).相關(guān)概念若途徑的邊e1,e2,…,en互不相同,則17回路一條具有正的長(zhǎng)度且起點(diǎn)、終點(diǎn)重合的途徑稱為閉途徑.類似可以定義閉鏈、閉通路.閉通路稱為回路(亦稱圈).長(zhǎng)為K的回路稱為K-回路.定理1.7
對(duì)于階數(shù)不小于2的圖G,當(dāng)且僅當(dāng)G不含奇回路時(shí),它才是二分圖.證明:充分性易證,下面證必要性。設(shè)G是無奇回路的連通圖,任取G的一個(gè)頂點(diǎn)u并將V(G)作如下的劃分(V1,V2):V1={x|x∈V(G),d(u,x)是偶數(shù)}V2={y|y∈V(G),d(u,y)是奇數(shù)}然后證明這恰是G的一個(gè)二分劃。回路一條具有正的長(zhǎng)度且起點(diǎn)、終點(diǎn)重合的途徑稱為閉途徑.類似可18設(shè)v和w是V1的兩個(gè)頂點(diǎn),又設(shè)P是最短(u,v)-通路,Q是最短(u,w)-通路,以u(píng)1記P和Q的最后一個(gè)公共頂點(diǎn),因?yàn)镻、Q是最短通路,P和Q的(u,u1)-節(jié)也是最短的(u,u1)-通路,因此具有相同的長(zhǎng)度.又因P和Q的長(zhǎng)度是偶數(shù),所以P上(u1,v)-節(jié)P1的長(zhǎng)度與Q上(u1,w)-節(jié)Q1的長(zhǎng)度具有相同的奇偶性,由此推出(v,w)通路P1-1Q1的長(zhǎng)度為偶數(shù),若v與w鄰接,則wv是G的一條奇回路,此與假設(shè)矛盾,故V1中任意兩點(diǎn)均不鄰接,同理V2中任意兩個(gè)頂點(diǎn)也不鄰接,因此G是二分圖。設(shè)v和w是V1的兩個(gè)頂點(diǎn),又設(shè)P是最短(u,v)-通路,Q是19最短通路問題如果對(duì)圖G的一條邊,賦以一個(gè)實(shí)數(shù)w(e),稱為這條邊的權(quán),那么G連同它的邊上的權(quán)稱為賦權(quán)圖.若G是一個(gè)賦權(quán)圖,H是G的子圖,那么H的權(quán)是它所有邊的權(quán)之和,即如果P是G的一條通路,通路上各邊的權(quán)也稱為該邊的長(zhǎng)度,通路上各邊的長(zhǎng)度之和稱為通路的長(zhǎng).所謂最短通路問題,就是在G中所有(u0,v0)-通路中,尋找一條長(zhǎng)度最小的(u0,v0)-通路.u0到v0的最短通路長(zhǎng)記為d(u0,v0),稱作u0到v0的距離。最短通路問題如果對(duì)圖G的一條邊,賦以一個(gè)實(shí)數(shù)w(e),稱為這20Dijkstra算法關(guān)于求最短通路問題,Dijkstra算法是最有名的方法之一,它的基本思想是:把G的頂點(diǎn)分為S,T兩類,若u0到某個(gè)頂點(diǎn)x的最短通路已求出,則將x歸入S,其余點(diǎn)歸入y,開始S中只有u0,隨著程序的運(yùn)行,我們就把T的元素逐個(gè)轉(zhuǎn)入S直到v0也被轉(zhuǎn)入S,程序就結(jié)束了.使用這一算法不僅可以找出最短的(u0,v0)-通路,而且可以給出u0到其它任何頂點(diǎn)的最短通路.Dijkstra算法關(guān)于求最短通路問題,Dijkstra算法21Dijkstra算法流程圖i=0,S={u0}l(u0)=0,l(v)=∞v≠u0停!YESNO計(jì)算Dijkstra算法流程圖i=0,S={u0}停!YESNO22Dijkstra算法示例Dijkstra算法示例23練習(xí)求下圖中V1到其它各點(diǎn)的最短距離,并寫出V1到V6的最短路徑.求下圖中點(diǎn)U到點(diǎn)V的最短距離,并寫出其最短路徑.練習(xí)求下圖中V1到其它各點(diǎn)的最短距離,并寫出V1到V6的最短24教師社區(qū)如何下載課件教師社區(qū)如何下載課件25點(diǎn)擊此處如何下載課件點(diǎn)擊此處如何下載課件26選擇課件如何下載課件選擇課件如何下載課件27下載課件如何下載課件下載課件如何下載課件281.1基本概念現(xiàn)實(shí)世界的許多現(xiàn)象可以用一類圖形來描述,這種圖形由一個(gè)點(diǎn)集和連接這個(gè)點(diǎn)集中某些點(diǎn)對(duì)的線所構(gòu)成.例如用點(diǎn)表示車站,線表示連接車站與車站的道路;或者用點(diǎn)表示人,連線表示一對(duì)朋友.在這種圖形中,人們主要感興趣的是:兩點(diǎn)是否被一條線所連接,而連線的長(zhǎng)短曲直則無關(guān)緊要.大量的這類事實(shí)的數(shù)學(xué)抽象,產(chǎn)生了圖的概念.1.1基本概念現(xiàn)實(shí)世界的許多現(xiàn)象可以用一類圖形來描述,這29圖的概念有序三元組G=[V(G),E(G),ΨG]稱為一個(gè)圖,其中:ⅰ)V(G)稱為頂點(diǎn)集合;ⅱ)E(G)∩V(G)=φ,E(G)稱為邊集合;ⅲ)ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射,稱為關(guān)聯(lián)函數(shù).V(G)中的元素稱為頂點(diǎn),E(G)中的元素稱為邊.V(G)所含元素的個(gè)數(shù)即頂點(diǎn)個(gè)數(shù)稱為圖的階,用|V(G)|表示.E(G)所含元素的個(gè)數(shù)稱為G的邊數(shù),用|E(G)|表示.我們用G(p,q)表添一個(gè)階為p、邊數(shù)為q的圖G,這時(shí)也說G是一個(gè)(p,q)圖.圖的概念有序三元組G=[V(G),E(G),Ψ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的端點(diǎn),或e和u,v關(guān)聯(lián),此時(shí)稱u和v是鄰接的。若兩條不同的邊ei和ej有一個(gè)公共端點(diǎn),則稱是鄰接的,不與任何邊鄰接的邊稱為孤立邊,不與任何邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn)。兩端重合的邊稱為環(huán),端點(diǎn)不同的邊稱為桿。若V(G)和E(G)都是有限集,則稱G為有限圖。G(0,0)稱為空?qǐng)D,E(G)=φ即G是由孤立點(diǎn)所組成,稱為零圖。G(1,0)稱為平凡圖。相關(guān)概念在圖G=[V(G),E(G),ΨG]中,若e∈E32簡(jiǎn)單圖和完全圖圖中若連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)大于1,則說這對(duì)頂點(diǎn)間有重邊相連.同一對(duì)頂點(diǎn)間邊的條數(shù)稱為邊的重?cái)?shù),既沒有環(huán)也沒有重邊的圖稱為簡(jiǎn)單圖,否則稱為偽圖,沒有環(huán)的偽圖稱為多重圖.每對(duì)不同的頂點(diǎn)均有邊相連的簡(jiǎn)單圖稱為完全圖.n階完全圖記為Kn定理1.1:Kn有條邊簡(jiǎn)單圖和完全圖圖中若連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)大于1,則說這33二分圖圖G的頂點(diǎn)集V(G)若能分成兩個(gè)子集V1和V2,使得G的每條邊有一個(gè)端點(diǎn)在V1
,另一個(gè)端點(diǎn)在V2中,則G稱為二分圖或偶圖.這樣一個(gè)把V(G)分成兩個(gè)集合V1
、V2的分劃(V1,V2)稱為G的一個(gè)二分劃.設(shè)簡(jiǎn)單二分圖G的二分劃為(V1,V2),如果V1的每個(gè)頂點(diǎn)與V2的每一個(gè)頂點(diǎn)都鄰接,則G稱為完全二分圖.若|V1|=m,|V2|=n,則這樣的圖記為Km,n定理1.2
Km,n有mn條邊。二分圖圖G的頂點(diǎn)集V(G)若能分成兩個(gè)子集V1和V2,使得G34補(bǔ)圖G是簡(jiǎn)單圖,如果簡(jiǎn)單圖GC滿足,ⅰ)V(GC)=V(G)ⅱ)V(GC)中兩點(diǎn)當(dāng)且僅當(dāng)它們?cè)贕中不鄰接時(shí)在GC中鄰接.那么GC稱為G的補(bǔ)圖.G:GC:補(bǔ)圖G是簡(jiǎn)單圖,如果簡(jiǎn)單圖GC滿足,G:GC:35平面圖在保持圖的頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系不變的情況下,一個(gè)圖可以作出許多圖形.如果一個(gè)圖具有這樣的圖形,它的邊僅在頂點(diǎn)處相交,則稱它為平面圖.判斷圖1是否為平面圖?圖1:圖2:平面圖在保持圖的頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系不變的情況下,一個(gè)圖可以作36恒同和同構(gòu)兩個(gè)圖H和G,如果V(H)=V(G),E(H)=E(G)且ΨH=
ΨG,那么H和G就稱為是恒同的,恒同的圖當(dāng)然可以用一個(gè)圖形來表示.G=[V(G),E(G),ΨG]和H=[V(H),E(H),ΨH],若存在1-1對(duì)應(yīng)偶(θ,φ),θ:V(G)→V(H);φ:E(G)→E(H),使得當(dāng)且僅當(dāng)ΨH(φ(e))=θ(u)θ(v)時(shí),ΨG(e)=uv,則說這兩個(gè)圖同構(gòu),記為G≌H恒同和同構(gòu)兩個(gè)圖H和G,如果V(H)=V(G),E(H)=E37度與正則圖設(shè)v∈V(G),G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度(次),記為dG(v)或d(v).一個(gè)環(huán)的端點(diǎn)的度數(shù)計(jì)為2.如果d(v)是奇數(shù),就說v是奇頂點(diǎn);如果d(v)是偶數(shù),就說v是偶頂點(diǎn).如果一個(gè)圖的每一個(gè)頂點(diǎn)都具有相同的度,則稱這個(gè)圖是正則圖。每個(gè)頂點(diǎn)的度均為k的正則圖,稱為k-正則圖.度與正則圖設(shè)v∈V(G),G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目稱為v在38有關(guān)度的定理定理1.3
圖G中各頂點(diǎn)度數(shù)之和等于邊數(shù)的2倍。推論1.4任意一個(gè)圖奇頂點(diǎn)的個(gè)數(shù)是偶數(shù).推論1.5正則圖的階與各頂點(diǎn)度數(shù)不全為奇數(shù).有關(guān)度的定理定理1.3圖G中各頂點(diǎn)度數(shù)之和等于邊數(shù)的239子圖設(shè)H和G是兩個(gè)圖,如果V(H)是V(G)的子集,E(H)是E(G)的子集且ΨH是
ΨG在E(H)內(nèi)的導(dǎo)出函數(shù),那么H稱為G的子圖,此時(shí)G稱為H的母圖,記為如果而H≠G,則說H是G的真子圖,記為設(shè)H是G的子圖,如果V(H)=V(G),則H稱為G的生成子圖。子圖設(shè)H和G是兩個(gè)圖,如果V(H)是V(G)的子集,E(H)40導(dǎo)出子圖設(shè)V’是V(G)的非空子集,H是G的一個(gè)子圖,如果:ⅰ)V(H)=V’;ⅱ)E(H)={e|e∈E(G),ΨG(e)=uv,u,v∈V’};ⅲ)ΨH是ΨG在E(H)上的導(dǎo)出函數(shù)。那么H稱為由V’導(dǎo)出的G的子圖,記為G[V’]導(dǎo)出子圖G[V-V’]記為G-V’,它是從G中刪除V’中的頂點(diǎn)及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。若V’={v},則把G-{v}簡(jiǎn)記為G-v,稱為G的刪點(diǎn)子圖。同理以E’中的端點(diǎn)的全體為集所組成的子圖稱為由E’導(dǎo)出的子圖,記為G[E’]。刪去邊集合E’中的邊之后得出的導(dǎo)出子圖記為G-E’G-e,G+e導(dǎo)出子圖設(shè)V’是V(G)的非空子集,H是G的一個(gè)子圖,如果:41例GG的一個(gè)生成子圖G-{2,3}G[{3,4,6}]G-{e,g,h}G[{a,c,e,g,h}]例GG的一個(gè)生成子圖G-{2,3}G[{3,4,6}]G-{42子圖的運(yùn)算(并、交、差、環(huán)和)G1G2G1∪
G2G1∩
G2G2-
G1G1
G2子圖的運(yùn)算(并、交、差、環(huán)和)G1G2G1∪G2G1∩G43通路和回路圖G中一個(gè)點(diǎn)邊交替的非空有限序列w=v0e1v1e2v2…envn稱為G的一個(gè)途徑.其中vi是頂點(diǎn),ei是邊,對(duì)于1≤i≤n,e的端點(diǎn)是vi-1和vi,v0和vn分別稱為途徑的起點(diǎn)和終點(diǎn),而v1,v2,…,vn-1稱為途徑的內(nèi)頂點(diǎn),整數(shù)n稱為途徑w的長(zhǎng).途徑w中若干相連項(xiàng)構(gòu)成的子序列viei+1vi+1…ejvj稱為w的(vi,vj)節(jié).將序列w逆轉(zhuǎn)后所得途徑vnenvn-1…v1e1v0記為w-1.在簡(jiǎn)單圖中,途徑w可以由它的頂點(diǎn)序列v0e1v1e2v2…envn所確定.因此在簡(jiǎn)單圖中可以用頂點(diǎn)序列表示一個(gè)途徑.通路和回路圖G中一個(gè)點(diǎn)邊交替的非空有限序列w=v0e1v1e44相關(guān)概念若途徑的邊e1,e2,
…,en互不相同,則稱之為鏈,此外,若頂點(diǎn)也互不相同,則稱w為通路.對(duì)G的兩個(gè)頂點(diǎn)u和v,如果在G中存在一條(u,v)的通路,則稱頂點(diǎn)u與v是連通的.如果圖G中的任意一對(duì)頂點(diǎn)都是連通的,則G稱為連通圖.設(shè)G的頂點(diǎn)u與v是連通的,那么G中最短的(u,v)通路的長(zhǎng)就稱為u與v的距離,記為d(u,v).相關(guān)概念若途徑的邊e1,e2,…,en互不相同,則45回路一條具有正的長(zhǎng)度且起點(diǎn)、終點(diǎn)重合的途徑稱為閉途徑.類似可以定義閉鏈、閉通路.閉通路稱為回路(亦稱圈).長(zhǎng)為K的回路稱為K-回路.定理1.7
對(duì)于階數(shù)不小于2的圖G,當(dāng)且僅當(dāng)G不含奇回路時(shí),它才是二分圖.證明:充分性易證,下面證必要性。設(shè)G是無奇回路的連通圖,任取G的一個(gè)頂點(diǎn)u并將V(G)作如下的劃分(V1,V2):V1={x|x∈V(G),d(u,x)是偶數(shù)}V2={y|y∈V(G),d(u,y)是奇數(shù)}然后證明這恰是G的一個(gè)二分劃?;芈芬粭l具有正的長(zhǎng)度且起點(diǎn)、終點(diǎn)重合的途徑稱為閉途徑.類似可46設(shè)v和w是V1的兩個(gè)頂點(diǎn),又設(shè)P是最短(u,v)-通路,Q是最短(u,w)-通路,以u(píng)1記P和Q的最后一個(gè)公共頂點(diǎn),因?yàn)?/p>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度廣告發(fā)布合同:品牌全媒體廣告投放2篇
- 二零二五年度辦公樓租賃合同續(xù)簽條件協(xié)議3篇
- 遼寧省本溪市(2024年-2025年小學(xué)六年級(jí)語文)部編版隨堂測(cè)試(下學(xué)期)試卷及答案
- 特種硫基復(fù)合肥生產(chǎn)項(xiàng)目可行性研究報(bào)告申請(qǐng)備案
- 黑龍江綏化市(2024年-2025年小學(xué)六年級(jí)語文)統(tǒng)編版期末考試((上下)學(xué)期)試卷及答案
- 二零二五年度醫(yī)療科研項(xiàng)目合作合同范本2篇
- 二零二五年度建筑消防設(shè)施維護(hù)服務(wù)合同范本2篇
- 二零二五年度光纖通信光纜購銷合作協(xié)議3篇
- 型煤生產(chǎn)建設(shè)項(xiàng)目可行性研究報(bào)告申請(qǐng)立項(xiàng)備案
- 二零二五年度軍人特定離婚事項(xiàng)處理協(xié)議書2篇
- 2025年八省聯(lián)考高考語文作文真題及參考范文
- 綠色施工管理體系與管理制度管理辦法(新版)
- 機(jī)動(dòng)車交通事故快速處理協(xié)議書(最新格式)
- 最新拉鏈廠安全操作規(guī)程
- 述職報(bào)告評(píng)分表
- 變壓器交接試驗(yàn)報(bào)告(1250)
- LOI外貿(mào)采購意向(標(biāo)準(zhǔn)樣本)
- 水電交接確認(rèn)單(共2頁)
- CTG-MBOSS CRM20 分總冊(cè)_普訓(xùn)版_圖文
- 低維材料與相變現(xiàn)象簡(jiǎn)介
- 2022年薄壁空心墩施工安全專項(xiàng)方案
評(píng)論
0/150
提交評(píng)論