圖的基本概念 無向圖及有向圖

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

CH7圖的基本概念1無向圖及有向圖1

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

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

/wiki/File:Konigsberg_bridges.png→

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

歐拉圖定義

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

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

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

2、一百多年以后

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

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

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

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

人們在長期為地圖(平面圖)上色時發(fā)現(xiàn)，最少只要四種顏色，就能使得有相鄰國界的國家涂上不同的顏色

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

5、又過了半個世紀(jì)

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

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

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

無向圖及有向圖2.

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

圖的矩陣表示4.

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

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

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

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

給定無向圖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、有向圖

一個有向圖D是一個二元組<V,E>,

即D=<V,E>,其中：①.V同無向圖中的頂點集;②.E是笛卡兒積的多重子集,其元素稱為有向邊,也簡稱邊.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表示無向圖，但有時用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖

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

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

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

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

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

v∈V， 稱v作為邊的始點次數(shù)之和為v的出度，記做d+D(v)，簡記作d+(v)。 稱v作為邊的終點次數(shù)之和為v的入度，記做d-D(v)，簡記作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最大(出/入)度,最小(出/入)度在無向圖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)}簡記為Δ,δ,Δ+,δ+,Δ-,δ-32握手定理（圖論基本定理）定理7.1設(shè)圖G=<V,E>為無向圖或有向圖，

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

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

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

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

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

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

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