圖的基本概念.ppt

《圖的基本概念.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第14章圖的基本概念離散數學中國地質大學本科生課程本章內容14.1圖14.2通路與回路14.3圖的連通性14.4圖的矩陣表示14.5圖的運算基本要求作業(yè)14.1圖的基本概念圖的定義圖的一些概念和規(guī)定簡單圖和多重圖頂點的度數與握手定理圖的同構完全圖與正則圖子圖與補圖無序積與多重集合元素可以重復出現(xiàn)的集合稱為多重集合或者多重集，某元素重復出現(xiàn)的次數稱為該元素的重復度。例如在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重復度分別為2,3,1,1。定義14.1一個無向圖是一個有序的二元組,記作G，其中（1）V≠?稱為頂點

2、集，其元素稱為頂點或結點。（2）E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。定義14.2一個有向圖是一個有序的二元組，記作D，其中（1）V≠?稱為頂點集，其元素稱為頂點或結點。（2）E為邊集，它是笛卡兒積V×V的多重子集，其元素稱為有向邊，簡稱邊。無向圖和有向圖說明可以用圖形表示圖，即用小圓圈（或實心點）表示頂點，用頂點之間的連線表示無向邊，用有方向的連線表示有向邊。例14.1例14.1(1)給定無向圖G＝，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2

3、,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(2)給定有向圖D=，其中V＝{a,b,c,d}，E＝{,,,,,,}。畫出G與D的圖形。圖的一些概念和規(guī)定G表示無向圖，但有時用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點集和邊集。若

4、V(G)

5、＝n，則稱G為n階圖。若

6、V(G)

7、與

8、E(G)

9、均為有限數，則稱G為有限圖。若邊集E(G)＝?，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖

10、，記作Nn，特別地，稱N1為平凡圖。在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產生頂點集為空集的運算結果，為此規(guī)定頂點集為空集的圖為空圖，并將空圖記為?。標定圖與非標定圖、基圖將圖的集合定義轉化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊），并稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。易知標定圖與非標定圖是可以相互轉化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。關聯(lián)與關聯(lián)次數、環(huán)、孤立點設G＝為無向圖，ek

11、＝(vi,vj)∈E，稱vi,vj為ek的端點，ek與vi或ek與vj是彼此相關聯(lián)的。若vi≠vj，則稱ek與vi或ek與vj的關聯(lián)次數為1。若vi＝vj，則稱ek與vi的關聯(lián)次數為2，并稱ek為環(huán)。若端點vl不與邊ek關聯(lián)，則稱ek與vl的關聯(lián)次數為0。設D＝為有向圖，ek＝∈E，稱vi,vj為ek的端點。若vi＝vj，則稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中，無邊關聯(lián)的頂點均稱為孤立點。相鄰與鄰接設無向圖G＝，vi，vj∈V，ek，el∈E。若?et∈E，使得et＝(vi，vj)，則稱vi與

12、vj是相鄰的。若ek與el至少有一個公共端點，則稱ek與el是相鄰的。設有向圖D＝，vi，vj∈V，ek，el∈E。若?et∈E，使得et＝，則稱vi為et的始點，vj為et的終點，并稱vi鄰接到vj，vj鄰接于vi。若ek的終點為el的始點，則稱ek與el相鄰。鄰域設無向圖G＝，?v∈V，稱{u

13、u∈V∧(u,v)∈E∧u≠v}為v的鄰域，記做NG(v)。稱NG(v)∪{v}為v的閉鄰域，記做NG(v)。稱{e

14、e∈E∧e與v相關聯(lián)}為v的關聯(lián)集，記做IG(v)。設有向圖D＝，?v∈V，

15、稱{u

16、u∈V∧∈E∧u≠v}為v的后繼元集，記做Г+D(v)。稱{u

17、u∈V∧∈E∧u≠v}為v的先驅元集，記做Г-D(v)。稱Г+D(v)∪Г-D(v)為v的鄰域，記做ND(v)。稱ND(v)∪{v}為v的閉鄰域，記做ND(v)。舉例NG(v1)＝Г+D(d)＝{v2，v5}NG(v1)＝{v1，v2，v5}IG(v1)＝{e1，e2，e3}{c}Г-D(d)＝{a，c}ND(d)＝{a，c}ND(d)＝{a，c，d}簡單圖與多重圖定義14.3在無向圖中，關聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行

18、邊的條數稱為重數。在有向圖中，關聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。含平行邊的圖稱為多重圖。既不含平行邊也不含環(huán)的圖稱為簡單圖。例如：在圖