無向圖及有向圖課件

第七章圖的基本概念7.1無向圖及有向圖7.2通路、回路、圖的連通性7.3圖的矩陣表示第七章圖的基本概念7.1無向圖及有向圖1作業(yè)作業(yè)27.1無向圖及有向圖設(shè)A,B為兩集合,稱{{a,b}｜a∈A∧b∈B}為A與B的無序積,記作A＆B．將無序?qū)a,b}記作(a,b).7.1無向圖及有向圖設(shè)A,B為兩集合,稱3無向圖一個無向圖G是一個二元組<V,E>,即G＝<V,E>,其中,(1)V是一個非空的集合,稱為G的頂點集,V中元素稱為頂點或結(jié)點；(2)E是無序積V＆V的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.無向圖一個無向圖G是一個二元組<V,E>,即G＝<V,E>,4有向圖一個有向圖D是一個二元組<V,E>,即D＝<V,E>,其中,(1)V同無向圖中的頂點集；(2)E是卡氏積的多重子圖,其元素稱為有向邊,也簡稱邊.有向圖一個有向圖D是一個二元組<V,E>,即D＝<V,E>,5給每條邊賦與權(quán)的圖G=<V,E>稱為加權(quán)圖，記為G=<V,E,W>,其中W表示各邊權(quán)的集合。23.57.8給每條邊賦與權(quán)的圖G=<V,E>稱為加權(quán)圖，23.57.86設(shè)ek＝(vi,vj)為無向圖G＝<V,E>中的一條邊,稱vi,vj為ek的端點,ek與vi(或vj)是彼此關(guān)聯(lián)的.無邊關(guān)聯(lián)的頂點稱為孤立點.若一條邊所關(guān)聯(lián)的兩個頂點重合,則稱此邊為環(huán).設(shè)ek＝(vi,vj)為無向圖G＝<V,E>中的一條邊,稱v7ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi≠vj,2vi＝vj,0vi(vj)不是ek的端點bavV’ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi≠vj,2vi＝vj8設(shè)G＝<V,E>為一無向圖或有向圖(1)若V,E都是有窮集合,則稱G是有限圖.(2)若｜V｜＝n,則稱G為n階圖．(3)若E＝,則稱G為零圖．特別是,若此時又有｜V｜＝1,則稱G為平凡圖.設(shè)G＝<V,E>為一無向圖或有向圖9相鄰設(shè)無向圖G＝〈V,E〉,vi,vj∈V,ek,el∈E.(1)若存在一條邊e以vi,vj為端點,即e＝(vi,vj),則稱vi,vj是彼此相鄰的,簡稱相鄰的．(2)若ek,el至少有一個公共端點,則稱ek,el是彼此相鄰的,簡稱相鄰的．相鄰設(shè)無向圖G＝〈V,E〉,vi,vj∈V,ek,el∈10始點終點以上兩定義對有向圖也是類似的若ek＝〈vi,vj〉,除稱vi,vj是ek的端點外,還稱vi是ek的始點,vj是ek的終點,vi鄰接到vj,vj鄰接于vi.始點終點以上兩定義對有向圖也是類似的11度設(shè)G＝<V,E>為一無向圖,vj∈V,稱vj作為邊的端點的次數(shù)之和為vi的度數(shù),簡稱度,記作d(vj).稱度數(shù)為1的頂點為懸掛頂點,它所對應(yīng)的邊為懸掛邊.度設(shè)G＝<V,E>為一無向圖,vj∈V,稱vj作為邊的端點的12設(shè)D＝<V,E>為一有向圖,vj∈V,稱vj作為邊的始點的次數(shù)之和,為vj的出度,記作d+(vj)；稱vj作為邊的終點的次數(shù)之和,為vj的入度,記作d-(vj)；稱vj作為邊的端點的次數(shù)之和,為vj的度數(shù),簡稱度,記作d(vj).顯然d(vj)＝d+(vj)＋d-(vj).設(shè)D＝<V,E>為一有向圖,vj∈V,13deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝deg+(v4)＝deg-(v4)＝0；deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；其中，v5是懸掛結(jié)點，<v1，v5>為懸掛邊。deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝14最大度和最小度對于圖G＝<V,E>,記Δ(G)＝max{d(v)｜v∈V},(G)＝min{d(v)｜v∈V},分別稱為G的最大度和最小度.最大度和最小度對于圖G＝<V,E>,記15若D＝〈V,E〉是有向圖,除了Δ(D),(D)外,還有最大出度、最大入度、最小出度、最小入度,分別定義為若D＝〈V,E〉是有向圖,除了Δ(D),(D)外,還有最大16基本定理(握手定理)設(shè)圖G＝<V,E>為無向圖或有向圖,V＝{v1,v2,...,vn},|E|=m(m為邊數(shù)),則基本定理(握手定理)設(shè)圖G＝<V,E>為無向圖或有向圖,V＝17推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點個數(shù)為偶數(shù).推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點個數(shù)為偶數(shù).18定理設(shè)有向圖D＝<V,E>,V＝{v1,v2,...,vn},｜E｜＝m,則定理設(shè)有向圖D＝<V,E>,V＝{v1,v2,...,vn}19度數(shù)序列設(shè)V＝{v1,v2,...,vn}為圖G的頂點集,稱(d(v1),d(v2),...,d(vn))為G的度數(shù)序列.度數(shù)序列設(shè)V＝{v1,v2,...,vn}為圖G的頂點集,稱20例7.1(1)(3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？(2)已知圖G中有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2.問G中至少有多少個頂點？為什么？例7.1(1)(3,3,2,3),(5,2,3,121平行邊、重數(shù)、多重圖、簡單圖在無向圖中,關(guān)聯(lián)一對頂點的無向邊如果多于1條,稱這些邊為平行邊.平行邊的條數(shù)稱為重數(shù).在有向圖中,關(guān)聯(lián)一對頂點的有向邊如果多于1條,且它們的始點與終點相同,則稱這些邊為有向平行邊,簡稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡單圖.平行邊、重數(shù)、多重圖、簡單圖在無向圖中,關(guān)聯(lián)一對頂點的無向邊22例例23無向完全圖、有向完全圖設(shè)G=<V,E>是n階無向簡單圖,若G中任何頂點都與其余的n－1個頂點相鄰,則稱G為n階無向完全圖,記作Kn.設(shè)D=<V,E>為n階有向簡單圖,若對于任意的頂點u,v∈V(u≠v),既有有向邊<u,v>,又有<v,u>,則稱D是n階有向完全圖.Kn均指無向完全圖.無向完全圖、有向完全圖設(shè)G=<V,E>是n階無向簡單圖,若G24圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,(3)所示為3階有向完全圖.圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,25子圖、真子圖設(shè)G=<V,E>,G‘=<V’,E'>是兩個圖.若V’V,且E'E,則稱G'是G的子圖,G是G’的母圖,記做G’G.若G’G且G‘≠G(即V’V或E‘E),則G’是G的真子圖.子圖、真子圖設(shè)G=<V,E>,G‘=<V’,E'>是兩個26生成子圖、導(dǎo)出子圖若G’G且V’=V則稱V’是V的生成子圖.設(shè)V1V,且V1≠,以V1為頂點集,以兩端點均在V1中的全體邊為邊集的G的子圖,稱為V1導(dǎo)出的導(dǎo)出子圖.設(shè)E1

E,且E1≠,以E1為邊集,以E1中關(guān)聯(lián)的頂點的全體為頂點集的G的子圖稱為E1導(dǎo)出的導(dǎo)出子圖.生成子圖、導(dǎo)出子圖若G’G且V’=V則稱V’是V的生成子27在如下圖中，給出了圖G以及它的真子圖G’和生成子圖G’’。G’是結(jié)點集{v1，v2，v4，v5，v6}的導(dǎo)出子圖。在如下圖中，給出了圖G以及它的真子圖G’和生成子圖G’’。G28無向圖及有向圖課件29補圖設(shè)G=<V,E>是n階無向簡單圖.以V為頂點集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對于完全圖Kn的補圖,簡稱G的補圖,記作.有向簡單圖的補圖可類似定義.補圖設(shè)G=<V,E>是n階無向簡單圖.以V為頂點集,以所有能30圖7.4圖7.431圖的同構(gòu)例如下圖(a)、(b)、(c)、(d)所示，圖(a)、圖(b)、圖(c)和圖(d)所表示的圖形實際上都是一樣的。圖的同構(gòu)例如下圖(a)、(b)、(c)、(d)所示，32同構(gòu)設(shè)兩個無向圖G1=<V1,E1>,G2=<V2,E2>,如果存在雙射函數(shù)：V1→V2,使得對于任意的e=(vi,vj)∈E1當(dāng)且僅當(dāng)e’=((vi),(vj))∈E2,并且e與e’的重數(shù)相同,則稱G1與G2是同構(gòu)的,記作G1≌G2.同構(gòu)設(shè)兩個無向圖G1=<V1,E1>,G2=<V33有向圖的同構(gòu)有向圖的同構(gòu)34(1)≌(2),頂點之間的對應(yīng)關(guān)系為av1,bv2,cv3,dv4,ev5.(1)≌(2),頂點之間的對應(yīng)關(guān)系為35兩圖同構(gòu)1、頂點個數(shù)相同2、邊的條數(shù)相同3、度數(shù)相同的結(jié)點數(shù)相同兩圖同構(gòu)1、頂點個數(shù)相同36(a)≌(b)≌(c).(a)所示圖稱為彼德森圖.(a)≌(b)≌(c).(a)所示圖稱為彼德森圖.37例7.2(1)畫出4個頂點3條邊的所有可能非同構(gòu)的無向簡單圖；(2)畫出3個頂點2條邊的所有可能非同構(gòu)的有向簡單圖.例7.2(1)畫出4個頂點3條邊的所有可能非同構(gòu)的無向簡單387.1結(jié)束，返回目錄7.1結(jié)束，返回目錄39第七章圖的基本概念7.1無向圖及有向圖7.2通路、回路、圖的連通性7.3圖的矩陣表示第七章圖的基本概念7.1無向圖及有向圖40作業(yè)作業(yè)417.1無向圖及有向圖設(shè)A,B為兩集合,稱{{a,b}｜a∈A∧b∈B}為A與B的無序積,記作A＆B．將無序?qū)a,b}記作(a,b).7.1無向圖及有向圖設(shè)A,B為兩集合,稱42無向圖一個無向圖G是一個二元組<V,E>,即G＝<V,E>,其中,(1)V是一個非空的集合,稱為G的頂點集,V中元素稱為頂點或結(jié)點；(2)E是無序積V＆V的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.無向圖一個無向圖G是一個二元組<V,E>,即G＝<V,E>,43有向圖一個有向圖D是一個二元組<V,E>,即D＝<V,E>,其中,(1)V同無向圖中的頂點集；(2)E是卡氏積的多重子圖,其元素稱為有向邊,也簡稱邊.有向圖一個有向圖D是一個二元組<V,E>,即D＝<V,E>,44給每條邊賦與權(quán)的圖G=<V,E>稱為加權(quán)圖，記為G=<V,E,W>,其中W表示各邊權(quán)的集合。23.57.8給每條邊賦與權(quán)的圖G=<V,E>稱為加權(quán)圖，23.57.845設(shè)ek＝(vi,vj)為無向圖G＝<V,E>中的一條邊,稱vi,vj為ek的端點,ek與vi(或vj)是彼此關(guān)聯(lián)的.無邊關(guān)聯(lián)的頂點稱為孤立點.若一條邊所關(guān)聯(lián)的兩個頂點重合,則稱此邊為環(huán).設(shè)ek＝(vi,vj)為無向圖G＝<V,E>中的一條邊,稱v46ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi≠vj,2vi＝vj,0vi(vj)不是ek的端點bavV’ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi≠vj,2vi＝vj47設(shè)G＝<V,E>為一無向圖或有向圖(1)若V,E都是有窮集合,則稱G是有限圖.(2)若｜V｜＝n,則稱G為n階圖．(3)若E＝,則稱G為零圖．特別是,若此時又有｜V｜＝1,則稱G為平凡圖.設(shè)G＝<V,E>為一無向圖或有向圖48相鄰設(shè)無向圖G＝〈V,E〉,vi,vj∈V,ek,el∈E.(1)若存在一條邊e以vi,vj為端點,即e＝(vi,vj),則稱vi,vj是彼此相鄰的,簡稱相鄰的．(2)若ek,el至少有一個公共端點,則稱ek,el是彼此相鄰的,簡稱相鄰的．相鄰設(shè)無向圖G＝〈V,E〉,vi,vj∈V,ek,el∈49始點終點以上兩定義對有向圖也是類似的若ek＝〈vi,vj〉,除稱vi,vj是ek的端點外,還稱vi是ek的始點,vj是ek的終點,vi鄰接到vj,vj鄰接于vi.始點終點以上兩定義對有向圖也是類似的50度設(shè)G＝<V,E>為一無向圖,vj∈V,稱vj作為邊的端點的次數(shù)之和為vi的度數(shù),簡稱度,記作d(vj).稱度數(shù)為1的頂點為懸掛頂點,它所對應(yīng)的邊為懸掛邊.度設(shè)G＝<V,E>為一無向圖,vj∈V,稱vj作為邊的端點的51設(shè)D＝<V,E>為一有向圖,vj∈V,稱vj作為邊的始點的次數(shù)之和,為vj的出度,記作d+(vj)；稱vj作為邊的終點的次數(shù)之和,為vj的入度,記作d-(vj)；稱vj作為邊的端點的次數(shù)之和,為vj的度數(shù),簡稱度,記作d(vj).顯然d(vj)＝d+(vj)＋d-(vj).設(shè)D＝<V,E>為一有向圖,vj∈V,52deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝deg+(v4)＝deg-(v4)＝0；deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；其中，v5是懸掛結(jié)點，<v1，v5>為懸掛邊。deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝53最大度和最小度對于圖G＝<V,E>,記Δ(G)＝max{d(v)｜v∈V},(G)＝min{d(v)｜v∈V},分別稱為G的最大度和最小度.最大度和最小度對于圖G＝<V,E>,記54若D＝〈V,E〉是有向圖,除了Δ(D),(D)外,還有最大出度、最大入度、最小出度、最小入度,分別定義為若D＝〈V,E〉是有向圖,除了Δ(D),(D)外,還有最大55基本定理(握手定理)設(shè)圖G＝<V,E>為無向圖或有向圖,V＝{v1,v2,...,vn},|E|=m(m為邊數(shù)),則基本定理(握手定理)設(shè)圖G＝<V,E>為無向圖或有向圖,V＝56推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點個數(shù)為偶數(shù).推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點個數(shù)為偶數(shù).57定理設(shè)有向圖D＝<V,E>,V＝{v1,v2,...,vn},｜E｜＝m,則定理設(shè)有向圖D＝<V,E>,V＝{v1,v2,...,vn}58度數(shù)序列設(shè)V＝{v1,v2,...,vn}為圖G的頂點集,稱(d(v1),d(v2),...,d(vn))為G的度數(shù)序列.度數(shù)序列設(shè)V＝{v1,v2,...,vn}為圖G的頂點集,稱59例7.1(1)(3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？(2)已知圖G中有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2.問G中至少有多少個頂點？為什么？例7.1(1)(3,3,2,3),(5,2,3,160平行邊、重數(shù)、多重圖、簡單圖在無向圖中,關(guān)聯(lián)一對頂點的無向邊如果多于1條,稱這些邊為平行邊.平行邊的條數(shù)稱為重數(shù).在有向圖中,關(guān)聯(lián)一對頂點的有向邊如果多于1條,且它們的始點與終點相同,則稱這些邊為有向平行邊,簡稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡單圖.平行邊、重數(shù)、多重圖、簡單圖在無向圖中,關(guān)聯(lián)一對頂點的無向邊61例例62無向完全圖、有向完全圖設(shè)G=<V,E>是n階無向簡單圖,若G中任何頂點都與其余的n－1個頂點相鄰,則稱G為n階無向完全圖,記作Kn.設(shè)D=<V,E>為n階有向簡單圖,若對于任意的頂點u,v∈V(u≠v),既有有向邊<u,v>,又有<v,u>,則稱D是n階有向完全圖.Kn均指無向完全圖.無向完全圖、有向完全圖設(shè)G=<V,E>是n階無向簡單圖,若G63圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,(3)所示為3階有向完全圖.圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,64子圖、真子圖設(shè)G=<V,E>,G‘=<V’,E'>是兩個圖.若V’V,且E'E,則稱G'是G的子圖,G是G’的母圖,記做G’G.若G’G且G‘≠G(即V’V或E‘E),則G’是G的真子圖.子圖、真子圖設(shè)G=<V,E>,G‘=<V’,E'>是兩個65生成子圖、導(dǎo)出子圖若G’G且V’=V則稱V’是V的生成子圖.設(shè)V1V,且V1≠,以V1為頂點集,以兩端點均在V1中的全體邊為邊集的G的子圖,稱為V1導(dǎo)出的導(dǎo)出子圖.設(shè)E1

E,且E1≠,以E1為邊集,以E1中關(guān)聯(lián)的頂點的全體為頂點集的G的子圖稱為E1導(dǎo)出的導(dǎo)出子圖.生成子圖、導(dǎo)出子圖若G’G且V’=V則稱V’是V的生成子66在如下圖中，給出了圖G以及它的真子圖G’和生成子圖G’’。G’是結(jié)點集{v1，v2，v4，v5，v6}