離散數(shù)學(xué)

CH7圖的基本概念1無(wú)向圖及有向圖1

圖論的起源圖論是組合數(shù)學(xué)的一個(gè)分支,它起源于1736年歐拉的第一篇關(guān)于圖論的論文，這篇論文解決了著名的“哥尼斯堡七橋問(wèn)題”，從而使歐拉成為圖論的創(chuàng)始人。1.哥尼斯堡七橋問(wèn)題

哥尼斯堡位于前蘇聯(lián)的加里寧格勒，歷史上曾經(jīng)是德國(guó)東普魯士省的省會(huì)，普雷格爾河橫穿城堡，河中有兩個(gè)小島，共有七座橋連接兩岸和小島。問(wèn)題：在所有橋都只能走一遍的前提下，如何才能把這個(gè)地方所有的橋都走遍？哥尼斯堡七橋問(wèn)題解決方式萊昂哈德·歐拉（LeonhardEuler）在1735年圓滿地解決了這一問(wèn)題，證明這種方法并不存在，也順帶解決了一筆畫問(wèn)題。他在圣彼得堡科學(xué)院發(fā)表了圖論史上第一篇重要文獻(xiàn)。歐拉把實(shí)際的抽象問(wèn)題簡(jiǎn)化為平面上的點(diǎn)與線組合，每一座橋視為一條線，橋所連接的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)，則這一點(diǎn)的線數(shù)必須是偶數(shù)。

/wiki/File:Konigsberg_bridges.png→

圖論的起源歐拉最后給出任意一種河──橋圖能否全部走一次的判定法則。如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒(méi)有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)，他還說(shuō)明了怎樣快速找到所要求的路線。不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這些解析，最后發(fā)展成為了數(shù)學(xué)中的圖論。5

歐拉圖定義

一個(gè)圖,如果能夠從一點(diǎn)出發(fā),經(jīng)過(guò)每條邊一次且僅一次再回到起點(diǎn),則稱為歐拉圖

歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理,并證明了七橋圖不是歐拉圖。

從這個(gè)問(wèn)題可以看出：圖：圖用點(diǎn)代表各個(gè)事物,用邊代表各個(gè)事物間的二元關(guān)系。所以，圖是研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。

2、一百多年以后

“七橋”問(wèn)題以后，圖論的研究停滯了一百多年，直到1847年，基爾霍夫用“樹”圖解決了電路理論中的求解聯(lián)立方程的問(wèn)題，十年后凱萊用

“樹”圖計(jì)算有機(jī)化學(xué)中的問(wèn)題。在這一時(shí)期流行著兩個(gè)著名的圖論問(wèn)題：哈密爾頓回路問(wèn)題和“四色猜想”問(wèn)題。3.哈密爾頓回路問(wèn)題

1856年,英國(guó)數(shù)學(xué)家哈密爾頓設(shè)計(jì)了一個(gè)周游世界的游戲，他在一個(gè)正十二面體的二十個(gè)頂點(diǎn)上標(biāo)上二十個(gè)著名城市的名字，要求游戲者從一個(gè)城市出發(fā)，經(jīng)過(guò)每一個(gè)城市一次且僅一次，然后回到出發(fā)點(diǎn)。哈密爾頓回路圖

此路線稱為：哈密爾頓回路，而此圖稱為：哈密爾頓圖。4、“四色猜想”問(wèn)題

人們?cè)陂L(zhǎng)期為地圖(平面圖)上色時(shí)發(fā)現(xiàn)，最少只要四種顏色，就能使得有相鄰國(guó)界的國(guó)家涂上不同的顏色

四色猜想的證明一直沒(méi)有解決，直到一百多年后，在計(jì)算機(jī)出現(xiàn)以后，于1976年用計(jì)算機(jī)算了1200多小時(shí)，才證明了四色猜想問(wèn)題。

5、又過(guò)了半個(gè)世紀(jì)

四色猜想問(wèn)題出現(xiàn)后，圖論的研究又停滯了半個(gè)世紀(jì)，直到1920年科尼格寫了許多關(guān)于圖論方面的論文，并于1936年發(fā)表了第一本關(guān)于圖論的書。此后圖論從理論上到應(yīng)用上都有了很大發(fā)展。特別是計(jì)算機(jī)的出現(xiàn)使圖論得到飛躍的發(fā)展。

學(xué)好圖論十分重要

圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系。圖論給含有二元關(guān)系的系統(tǒng)提供了數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來(lái)越重要的地位，并且在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。從二十世際50年代以來(lái)，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。第7章圖的概念本章學(xué)習(xí)：1.

無(wú)向圖及有向圖2.

通路、回路、圖的連通性3.

圖的矩陣表示4.

最短路徑及關(guān)鍵路徑

14今日內(nèi)容無(wú)向圖及有向圖圖的一些相關(guān)概念度握手定理子圖相關(guān)概念圖同構(gòu)15預(yù)備知識(shí)有序積:A×B={<x,y>|x∈A∧y∈B}有序?qū)?<x,y>≠<y,x>無(wú)序積:A&B={(x,y)|x∈A∧y∈B}無(wú)序?qū)?(x,y)=(y,x)多重集:{a,a,a,b,b,c}≠{a,b,c}重復(fù)度:a的重復(fù)度為3,b的為2,c的為1161、無(wú)序積：A&B設(shè)A、B為兩集合，稱{{a,b}|a∈A∧b∈B}為A與B的無(wú)序積，記作A&B。為方便起見，將無(wú)序?qū)a,b}記作

(a,b)。

(a,b)＝(b,a)例：設(shè)A={a,b},B={c,d},則A&B＝？A&A＝？

A&B={(a,c),(a,d),(b,c),(b,d)}A&A={(a,a),(a,b),(b,b)}172、無(wú)向圖一個(gè)無(wú)向圖G是一個(gè)二元組<V,E>,即G=<V,E>,其中:①.

V是一個(gè)非空集合,稱為G的頂點(diǎn)集,V中元素稱為頂點(diǎn)或結(jié)點(diǎn);②.

E是無(wú)序積V&V的一個(gè)多重子集,稱E為G的邊集,E中元素稱為無(wú)向邊或簡(jiǎn)稱邊。?用小圓圈表示V中頂點(diǎn),若(a,b)∈E,就在a,b之間連線段表示邊(a,b),其中頂點(diǎn)的位置、連線的曲直及是否相交都無(wú)關(guān)緊要。18無(wú)向圖示例

給定無(wú)向圖G＝<V,E>，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.

3、有向圖

一個(gè)有向圖D是一個(gè)二元組<V,E>,

即D=<V,E>,其中：①.V同無(wú)向圖中的頂點(diǎn)集;②.E是笛卡兒積的多重子集,其元素稱為有向邊,也簡(jiǎn)稱邊.20有向圖示例給定有向圖D=<V,E>，其中V＝{a,b,c,d}，E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。

圖的一些概念和規(guī)定G表示無(wú)向圖，但有時(shí)用G泛指圖(無(wú)向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝，則稱G為零圖，此時(shí)，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖

在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空?qǐng)D，并將空?qǐng)D記為

。標(biāo)定圖與非標(biāo)定圖、基圖將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無(wú)向邊(vi,vj)（或有向邊<vi,vj>），并稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。將有向圖各有向邊均改成無(wú)向邊后的無(wú)向圖稱為原來(lái)圖的基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無(wú)向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn)設(shè)G＝<V,E>為無(wú)向圖，ek＝(vi,vj)∈E， 稱vi,vj為ek的端點(diǎn)，ek與vi或ek與vj是彼此相關(guān)聯(lián)的。 若vi≠vj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。 若vi＝vj，則稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱ek為環(huán)。 任意的vl∈V，若vl≠vi且vl≠vj，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn)設(shè)D＝<V,E>為有向圖，ek＝<vi,vj>∈E， 稱vi,vj為ek的端點(diǎn)。 若vi＝vj，則稱ek為D中的環(huán)。無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)。相鄰與鄰接設(shè)無(wú)向圖G＝<V，E>，vi，vj∈V，ek，el∈E。 若

et∈E，使得et＝(vi，vj)，則稱vi與vj是彼此相鄰的 若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是彼此相鄰的。設(shè)有向圖D＝<V，E>，vi，vj∈V，ek，el∈E。 若

et∈E，使得et＝<vi，vj>，則稱vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。 若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。例：點(diǎn)邊之間的關(guān)聯(lián)次數(shù)27例：點(diǎn)點(diǎn)、邊邊之間的相鄰關(guān)系28頂點(diǎn)的度數(shù)定義設(shè)G＝<V,E>為一無(wú)向圖，

v∈V，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡(jiǎn)稱為度，記做dG(v)。 在不發(fā)生混淆時(shí)，簡(jiǎn)記為d(v)。 設(shè)D＝<V，E>為有向圖，

v∈V， 稱v作為邊的始點(diǎn)次數(shù)之和為v的出度，記做d+D(v)，簡(jiǎn)記作d+(v)。 稱v作為邊的終點(diǎn)次數(shù)之和為v的入度，記做d-D(v)，簡(jiǎn)記作d-(v)。 稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=030d+(v1)=2d+

(v2)=1d+

(v3)=3d+

(v4)=1d+

(v5)=1d-(v1)=1d-

(v2)=3d-

(v3)=0d-

(v4)=3d-

(v5)=1d(v1)=3d

(v2)=4d

(v3)=3d

(v4)=4d

(v5)=231最大(出/入)度,最小(出/入)度在無(wú)向圖G中，最大度:Δ(G)=max{dG(v)|v∈V(G)}最小度:δ(G)=min{dG(v)|v∈V(G)}在有向圖D中，最大出度:Δ+(D)=max{dD+(v)|v∈V(D)}最小出度:δ+(D)=min{dD+(v)|v∈V(D)}最大入度:Δ-(D)=max{dD-(v)|v∈V(D)}最小入度:δ-(D)=min{dD-(v)|v∈V(D)}簡(jiǎn)記為Δ,δ,Δ+,δ+,Δ-,δ-32握手定理（圖論基本定理）定理7.1設(shè)圖G=<V,E>為無(wú)向圖或有向圖，

V={v1,v2,…,vn},,|E|=m，則說(shuō)明

任何無(wú)向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明

G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。

推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。

33問(wèn)題研究問(wèn)題：在一個(gè)部門的25個(gè)人中間，由于意見不同，是否可能每個(gè)人恰好與其他5個(gè)人意見一致？解答：不可能?？紤]一個(gè)圖，其中頂點(diǎn)代表人，如果兩個(gè)人意見相同，可用邊連接，所以每個(gè)頂點(diǎn)都是奇數(shù)度。存在奇數(shù)個(gè)度數(shù)為奇數(shù)的圖，這是不可能的。說(shuō)明： (1)很多離散問(wèn)題可以用圖模型求解。 (2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。 (3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。握手定理定理7.2設(shè)有向圖D=<V,E>，

V={v1,v2,…,vn},,|E|=m，則

35度數(shù)列設(shè)G＝<V,E>為一個(gè)n階無(wú)向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}為頂點(diǎn)集的n階無(wú)向圖G，使得d(vi)＝di，則稱d是可圖化的。特別地，若所得圖是簡(jiǎn)單圖，則稱d是可簡(jiǎn)單圖化的。類似地，設(shè)D＝<V,E>為一個(gè)n階有向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，…，d+(vn)與d-(v1)，d-(v2)，…，d-(vn)分