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

《離散數(shù)學(xué)圖論-圖的基本概念x》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、圖論圖的基本概念七座橋所有的走法一共有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)”和“邊”組成的圖以及圖的特殊形式--樹。圖與樹是建立和處理離散對(duì)象及其關(guān)系重要工具。如地圖導(dǎo)航、周游問(wèn)題、圖像分割等等。一、圖的概念1、無(wú)序積定義：設(shè)A，B為任意的兩個(gè)集合，稱｛｛a，b｝┃

2、a∈A∧b∈B｝為A與B的無(wú)序積，記作A&B其元素｛a，b｝可簡(jiǎn)記為（a，b）2、圖的定義1）定義1一個(gè)無(wú)向圖是一個(gè)有序的二元組，記作G，其中(1)V≠?稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)．(2)E稱為邊集，它是無(wú)序積V＆V的多重子集，其元素稱為無(wú)向邊，簡(jiǎn)稱為邊．例：無(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)

3、V≠?稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)．(2)E為邊集，它是笛卡兒積VⅹV的有窮多重子集，其元素稱為有向邊，簡(jiǎn)稱邊(弧)．有向圖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）用

4、V(G)

5、，

6、E(G)

7、分別表示G的頂點(diǎn)數(shù)和邊數(shù)若｜V(G)｜＝n，則稱G為n階圖。對(duì)有向圖有相同定義。3）在圖G中，若邊集E(G)＝?，則稱G

8、為零圖若G為n階圖，則稱G為n階零圖，記作Nn，特別是稱N1為平凡圖4）在用圖形表示一個(gè)圖時(shí)，若給每個(gè)結(jié)點(diǎn)和每一條邊均指定一個(gè)符號(hào)（字母或數(shù)字），則稱這樣的圖為標(biāo)定圖。5)常用ek表示邊(vi，vj)(或)設(shè)G＝為無(wú)向圖，ek=(vi，vj)∈E，則稱vi，vj為ek的端點(diǎn)，ek與vi、vj是彼此相關(guān)聯(lián)的．起、終點(diǎn)相同的邊稱為環(huán)不與任何邊關(guān)聯(lián)的結(jié)點(diǎn)稱為孤立點(diǎn)（包括有向圖)6）鄰接：邊的相鄰：ek，el∈E．若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是相鄰的頂點(diǎn)的相鄰：若?et∈E，使得et=，則稱vi為et的

9、始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi兩個(gè)結(jié)點(diǎn)為一條邊的端點(diǎn)，則稱兩個(gè)結(jié)點(diǎn)互為鄰接點(diǎn)，也稱邊關(guān)聯(lián)于這兩個(gè)結(jié)點(diǎn)，或稱兩個(gè)結(jié)點(diǎn)鄰接于此邊。7）平行邊：在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)．在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條，并且它們的方向相同，則稱這些邊為平行邊．8）多重圖和簡(jiǎn)單圖：含平行邊的圖稱為多重圖既不含平行邊也不含環(huán)的圖稱為簡(jiǎn)單圖．（主要討論簡(jiǎn)單圖）4、結(jié)點(diǎn)的度1)定義4設(shè)G＝為無(wú)向圖，?v∈V，稱v作為邊的端點(diǎn)的次數(shù)之和為v的度數(shù)，簡(jiǎn)稱為度，記作dG(v)

10、，簡(jiǎn)記為d(v)，即為：結(jié)點(diǎn)v所關(guān)聯(lián)的邊的總條數(shù)關(guān)于有向圖D＝有：?v∈V，稱v作為邊的始點(diǎn)的次數(shù)之和為v的出度，記作d+(v)，稱v作為邊的終點(diǎn)的次數(shù)之和為v的入度，記作d-(v)稱d+(v)+d-(v)為v的度數(shù)，記作dD(v).2)稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊根據(jù)結(jié)點(diǎn)的度數(shù)可將結(jié)點(diǎn)分為：度為偶數(shù)(奇數(shù))的頂點(diǎn)稱為偶度頂點(diǎn)(奇度頂點(diǎn)).一個(gè)環(huán)提供的度為2（有向圖的環(huán)提供入度1和出度1）3）定義：?(G)=max{d(v)

11、v∈V(G)}為圖G中結(jié)點(diǎn)最大的度δ(G)=min{d(v)

12、v∈V(G)}為圖G中結(jié)點(diǎn)最小的

13、度簡(jiǎn)記為?、δ定義：?－(D)=max{d－(v)

14、v∈V(D)}為圖D中結(jié)點(diǎn)最大的入度?＋(D)=max{d＋(v)

15、v∈V(D)}為圖D中結(jié)點(diǎn)最大的出度δ-(D)=min{d－(v)

16、v∈V(D)}為圖D中結(jié)點(diǎn)最小的入度δ＋(D)=min{d＋(v)

17、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條邊共提供2

18、m度2)定理2設(shè)D＝為任意有向圖,V＝{v1，v2，…，vn},

19、E

20、=m，則∑d+(vi)=∑d