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

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

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