離散數(shù)學(xué)圖論-圖的基本概念.pptx

《離散數(shù)學(xué)圖論-圖的基本概念.pptx》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)圖論-圖的基本概念.pptx（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

圖論,圖的基本概念,七座橋所有的走法一共有7！=5040種。1736年，在經(jīng)過(guò)一年的研究之后，29歲的歐拉提交了《哥尼斯堡七橋》的論文，圓滿解決了這一問(wèn)題，同時(shí)開(kāi)創(chuàng)了數(shù)學(xué)新分支---圖論。,圖論,在許多應(yīng)用領(lǐng)域中：地圖導(dǎo)航、網(wǎng)絡(luò)技術(shù)研究及程序流程分析都會(huì)遇到由“結(jié)點(diǎn)”和“邊”組成的圖在計(jì)算機(jī)許多學(xué)科中如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、網(wǎng)絡(luò)理論、信息的組織與檢索均離不開(kāi)由這種“結(jié)點(diǎn)”和“邊”組成的圖以及圖的特殊形式--樹(shù)。圖與樹(shù)是建立和處理離散對(duì)象及其關(guān)系重要工具。如地圖導(dǎo)航、周游問(wèn)題、圖像分割等等。,一、圖的概念,1、無(wú)序積定義：設(shè)A，B為任意的兩個(gè)集合，稱(chēng)｛｛a，b｝┃a∈A∧b∈B｝為A與B的無(wú)序積，記作A&B其元素｛a，b｝可簡(jiǎn)記為（a，b）2、圖的定義1）定義1一個(gè)無(wú)向圖是一個(gè)有序的二元組，記作G，其中(1)V≠稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)．(2)E稱(chēng)為邊集，它是無(wú)序積V＆V的多重子集，其元素稱(chēng)為無(wú)向邊，簡(jiǎn)稱(chēng)為邊．例：無(wú)向圖G=其中頂點(diǎn)集合V＝｛v1,v2,v3,v4｝邊集合E＝｛(v1,v2),(v2,v3),(v3,v2),(v3,v1),(v2,v2),(v2,v2),(v1,v2),｝園括號(hào)表示無(wú)向邊有平行邊,2）定義2一個(gè)有向圖是一個(gè)有序的二元組，記作D，其中(1)V≠稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)．(2)E為邊集，它是笛卡兒積VⅹV的有窮多重子集，其元素稱(chēng)為有向邊，簡(jiǎn)稱(chēng)邊(弧)．有向圖D=其中V＝｛v1,v2,v3｝邊集合E＝｛,,,,｝（與前面的關(guān)系的圖表示相當(dāng)）,3、有關(guān)圖的術(shù)語(yǔ)1）用G表示無(wú)向圖，D表示有向圖。有時(shí)用V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。2）用|V(G)|，|E(G)|分別表示G的頂點(diǎn)數(shù)和邊數(shù)若｜V(G)｜＝n，則稱(chēng)G為n階圖。對(duì)有向圖有相同定義。3）在圖G中，若邊集E(G)＝，則稱(chēng)G為零圖若G為n階圖，則稱(chēng)G為n階零圖，記作Nn，特別是稱(chēng)N1為平凡圖4）在用圖形表示一個(gè)圖時(shí)，若給每個(gè)結(jié)點(diǎn)和每一條邊均指定一個(gè)符號(hào)（字母或數(shù)字），則稱(chēng)這樣的圖為標(biāo)定圖。5)常用ek表示邊(vi，vj)(或)設(shè)G＝為無(wú)向圖，ek=(vi，vj)∈E，則稱(chēng)vi，vj為ek的端點(diǎn)，ek與vi、vj是彼此相關(guān)聯(lián)的．起、終點(diǎn)相同的邊稱(chēng)為環(huán)不與任何邊關(guān)聯(lián)的結(jié)點(diǎn)稱(chēng)為孤立點(diǎn)（包括有向圖),6）鄰接：邊的相鄰：ek，el∈E．若ek與el至少有一個(gè)公共端點(diǎn)，則稱(chēng)ek與el是相鄰的頂點(diǎn)的相鄰：若?et∈E，使得et=，則稱(chēng)vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱(chēng)vi鄰接到vj，vj鄰接于vi兩個(gè)結(jié)點(diǎn)為一條邊的端點(diǎn)，則稱(chēng)兩個(gè)結(jié)點(diǎn)互為鄰接點(diǎn)，也稱(chēng)邊關(guān)聯(lián)于這兩個(gè)結(jié)點(diǎn)，或稱(chēng)兩個(gè)結(jié)點(diǎn)鄰接于此邊。7）平行邊：在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條，則稱(chēng)這些邊為平行邊，平行邊的條數(shù)稱(chēng)為重?cái)?shù)．在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條，并且它們的方向相同，則稱(chēng)這些邊為平行邊．8）多重圖和簡(jiǎn)單圖：含平行邊的圖稱(chēng)為多重圖既不含平行邊也不含環(huán)的圖稱(chēng)為簡(jiǎn)單圖．（主要討論簡(jiǎn)單圖）,4、結(jié)點(diǎn)的度1)定義4設(shè)G＝為無(wú)向圖，?v∈V，稱(chēng)v作為邊的端點(diǎn)的次數(shù)之和為v的度數(shù)，簡(jiǎn)稱(chēng)為度，記作dG(v)，簡(jiǎn)記為d(v)，即為：結(jié)點(diǎn)v所關(guān)聯(lián)的邊的總條數(shù)關(guān)于有向圖D＝有：?v∈V，稱(chēng)v作為邊的始點(diǎn)的次數(shù)之和為v的出度，記作d+(v)，稱(chēng)v作為邊的終點(diǎn)的次數(shù)之和為v的入度，記作d-(v)稱(chēng)d+(v)+d-(v)為v的度數(shù)，記作dD(v).2)稱(chēng)度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱(chēng)為懸掛邊根據(jù)結(jié)點(diǎn)的度數(shù)可將結(jié)點(diǎn)分為：度為偶數(shù)(奇數(shù))的頂點(diǎn)稱(chēng)為偶度頂點(diǎn)(奇度頂點(diǎn)).一個(gè)環(huán)提供的度為2（有向圖的環(huán)提供入度1和出度1）,3）定義：?(G)=max{d(v)|v∈V(G)}為圖G中結(jié)點(diǎn)最大的度δ(G)=min{d(v)|v∈V(G)}為圖G中結(jié)點(diǎn)最小的度簡(jiǎn)記為?、δ定義：?－(D)=max{d－(v)|v∈V(D)}為圖D中結(jié)點(diǎn)最大的入度?＋(D)=max{d＋(v)|v∈V(D)}為圖D中結(jié)點(diǎn)最大的出度δ-(D)=min{d－(v)|v∈V(D)}為圖D中結(jié)點(diǎn)最小的入度δ＋(D)=min{d＋(v)|v∈V(D)}為圖D中結(jié)點(diǎn)最小的出度5、握手定理（歐拉）1)定理1設(shè)G＝為任意無(wú)向圖,V＝{v1，v2，…，vn},｜E｜=m，則∑d(vi)＝2m(所有結(jié)點(diǎn)的度數(shù)值和為邊數(shù)的2倍)證:G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊共提供2m度2)定理2設(shè)D＝為任意有向圖,V＝{v1，v2，…，vn},|E|=m，則∑d+(vi)=∑d-(vi)=m．且∑d(vi)＝2m3)推論任何圖(無(wú)向的或有向的)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)個(gè),4)結(jié)點(diǎn)的度數(shù)序列(1)設(shè)G＝為一個(gè)n階無(wú)向圖，V＝{v1，v2，…，vn}稱(chēng)d(v1)，d(v2)，…，d(vn)為G的度數(shù)列注：由推論可知，不是任何一個(gè)非負(fù)整數(shù)序列均可作為一個(gè)圖的度數(shù)列。條件：奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)應(yīng)該是偶數(shù)個(gè)（2）序列的可圖化：對(duì)一個(gè)整數(shù)序列d=(d1,d2,…dn),若存在以n個(gè)頂點(diǎn)的n階無(wú)向圖G，有d(vi)=di，稱(chēng)該序列是可圖化的。特別的，如果得到的是簡(jiǎn)單圖，稱(chēng)該序列是可簡(jiǎn)單圖化的。（3）定理設(shè)非負(fù)整數(shù)列d＝(d1，d2，…，dn)，則d是可圖化的當(dāng)且僅當(dāng)∑di是偶數(shù)(序列之和必須是偶數(shù))（4）由于簡(jiǎn)單圖中沒(méi)有平行邊及環(huán)定理：設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則?(G)d2>…>dn>=1且Σdi=偶數(shù)d4=（3,3,3,1）分析d5=（4,4,3,3,2,2）,二、圖的同構(gòu)定義：設(shè)G1＝，G2=為兩個(gè)無(wú)向圖(有向圖)，若存在雙射函數(shù)f：V1→V2對(duì)于?vi，vj?V1，(vi，vj)?E1當(dāng)且僅當(dāng)(f(vi),f(vj))?E2并且(vi，vj)與(f(vi),f(vj))的重?cái)?shù)相同，則稱(chēng)G1與G2是同構(gòu)的，記作Gl?G2。對(duì)有向圖有相同的定義。定義說(shuō)明了:兩個(gè)圖的各結(jié)點(diǎn)之間，如果存在著一一對(duì)應(yīng)關(guān)系f這種對(duì)應(yīng)關(guān)系又保持了結(jié)點(diǎn)間的鄰接關(guān)系，那么這兩個(gè)圖就是同構(gòu)的在有向圖的情況下，f不但應(yīng)該保持結(jié)點(diǎn)間的鄰接關(guān)系，還應(yīng)該保持邊的方向。,結(jié)點(diǎn)數(shù)相同邊數(shù)相同結(jié)點(diǎn)的度相同但是兩個(gè)圖不同構(gòu),注：1)兩個(gè)圖同構(gòu)的必要條件階數(shù)相同（頂點(diǎn)）邊數(shù)相同度數(shù)相同的頂點(diǎn)數(shù)相同同構(gòu)的必要條件，并不是充分條件2)圖之間的同構(gòu)關(guān)系可看成全體圖集合上的二元關(guān)系。具有自反性，對(duì)稱(chēng)性和傳遞性，是等價(jià)關(guān)系。同構(gòu)的圖為一個(gè)等價(jià)類(lèi)，在同構(gòu)的意義之下都可以看成是一個(gè)圖。,例(1)畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖．結(jié)點(diǎn)個(gè)數(shù)與邊數(shù)相同，只需找出頂點(diǎn)度數(shù)序列不同的圖（2?3＝6）如何將度數(shù)6分配給4個(gè)結(jié)點(diǎn)：1113相應(yīng)的圖22112220例(2)畫(huà)出3階2條邊的所有非同構(gòu)的有向簡(jiǎn)單圖結(jié)點(diǎn)個(gè)數(shù)與邊數(shù)相同，只需找出頂點(diǎn)度（出度及入度）數(shù)序列不同的圖結(jié)點(diǎn)總度數(shù)：2＊2＝4,度數(shù)分配121按出度與入度分配：入度列110出度列011入度列020出度列101入度列101出度列020,度數(shù)分配220按出度與入度分配：入度列110出度列110,這只是對(duì)較為簡(jiǎn)單的情況給出的非同構(gòu)圖，對(duì)于一般的情況（n,m)圖到目前為止還沒(méi)有解決,三、特殊圖－完全圖與正則圖1)完全圖定義設(shè)G為n階無(wú)向簡(jiǎn)單圖，若G中每個(gè)頂點(diǎn)均與其余的n—1個(gè)頂點(diǎn)相鄰，則稱(chēng)G為n階無(wú)向完全圖，簡(jiǎn)稱(chēng)n階完全圖，記作Kn(n≥1)．設(shè)D為n階有向簡(jiǎn)單圖，若D中每個(gè)頂點(diǎn)都鄰接到其余的n—1個(gè)頂點(diǎn)，又鄰接于其余的n—1個(gè)頂點(diǎn)，則稱(chēng)D是n階有向完全圖．可畫(huà)圖表示（無(wú)向圖5階、有向圖3階和4階）2)完全圖的性質(zhì)：n階無(wú)向完全圖G的邊數(shù)與結(jié)點(diǎn)的關(guān)系m=n(n-1)/2n階有向完全圖G的邊數(shù)與結(jié)點(diǎn)的關(guān)系m=n(n-1),2,,3)正則圖定義設(shè)G為n階無(wú)向簡(jiǎn)單圖，若?v∈V(G)，均有d(v)＝k則稱(chēng)G為k-正則圖k-正則圖的邊數(shù)與結(jié)點(diǎn)個(gè)數(shù)的關(guān)系：m=kn/2如：3-正則圖,四、子圖、生成子圖、導(dǎo)出子圖1、定義設(shè)G＝，G‘＝為兩個(gè)圖(同為無(wú)向圖或有向圖)若V’?V且E’?E，則稱(chēng)G‘是G的子圖，G為G‘的母圖，記作G’?G，又若V‘?V或E’?E，則稱(chēng)G‘為G的真子圖若V’＝V（且E’?E），則稱(chēng)G‘為G的生成子圖(全部頂點(diǎn)),2、設(shè)G＝為圖，V1?V且V1≠，稱(chēng)以V1為頂點(diǎn)集，以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作G[V1]．可畫(huà)圖表示G及G［V1］（P279圖14.5）結(jié)點(diǎn)導(dǎo)出的子圖又設(shè)E1?E且E1≠，稱(chēng)以E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集V1的圖為G的E1導(dǎo)出的子圖，記作G[E1]．,3、補(bǔ)圖1）定義設(shè)G＝為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱(chēng)為G的補(bǔ)圖，記作??,2）性質(zhì)：設(shè)G是n階k-正則圖，證明G的補(bǔ)圖??也是正則圖對(duì)圖中任何結(jié)點(diǎn)v的度有dG(v)+d??(v)=dKn(v)=n-1d??(v)=n-1-dG(v)＝n-1-k=n-(k+1）3）自補(bǔ)圖：若圖G≌??(同構(gòu))則稱(chēng)G為自補(bǔ)圖。,