關(guān)于圖的基本概念無向圖及有向圖第1頁，課件共61頁，創(chuàng)作于2023年2月

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

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

/wiki/File:Konigsberg_bridges.png→

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

歐拉圖定義

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

歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理,并證明了七橋圖不是歐拉圖。第6頁，課件共61頁，創(chuàng)作于2023年2月

從這個問題可以看出：圖：圖用點代表各個事物,用邊代表各個事物間的二元關(guān)系。所以，圖是研究集合上的二元關(guān)系的工具，是建立數(shù)學模型的一個重要手段。第7頁，課件共61頁，創(chuàng)作于2023年2月

2、一百多年以后

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

“樹”圖計算有機化學中的問題。在這一時期流行著兩個著名的圖論問題：哈密爾頓回路問題和“四色猜想”問題。第8頁，課件共61頁，創(chuàng)作于2023年2月3.哈密爾頓回路問題

1856年,英國數(shù)學家哈密爾頓設(shè)計了一個周游世界的游戲，他在一個正十二面體的二十個頂點上標上二十個著名城市的名字，要求游戲者從一個城市出發(fā)，經(jīng)過每一個城市一次且僅一次，然后回到出發(fā)點。第9頁，課件共61頁，創(chuàng)作于2023年2月哈密爾頓回路圖

此路線稱為：哈密爾頓回路，而此圖稱為：哈密爾頓圖。第10頁，課件共61頁，創(chuàng)作于2023年2月4、“四色猜想”問題

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

四色猜想的證明一直沒有解決，直到一百多年后，在計算機出現(xiàn)以后，于1976年用計算機算了1200多小時，才證明了四色猜想問題。第11頁，課件共61頁，創(chuàng)作于2023年2月

5、又過了半個世紀

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

學好圖論十分重要

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

無向圖及有向圖2.

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

圖的矩陣表示4.

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

第14頁，課件共61頁，創(chuàng)作于2023年2月15今日內(nèi)容無向圖及有向圖圖的一些相關(guān)概念度握手定理子圖相關(guān)概念圖同構(gòu)第15頁，課件共61頁，創(chuàng)作于2023年2月16預備知識有序積: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}重復度:a的重復度為3,b的為2,c的為1第16頁，課件共61頁，創(chuàng)作于2023年2月171、無序積：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)}第17頁，課件共61頁，創(chuàng)作于2023年2月182、無向圖一個無向圖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頁，課件共61頁，創(chuàng)作于2023年2月無向圖示例

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

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

第19頁，課件共61頁，創(chuàng)作于2023年2月203、有向圖

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

即D=<V,E>,其中：①.V同無向圖中的頂點集;②.E是笛卡兒積的多重子集,其元素稱為有向邊,也簡稱邊.第20頁，課件共61頁，創(chuàng)作于2023年2月有向圖示例給定有向圖D=<V,E>，其中V＝{a,b,c,d}，E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。

第21頁，課件共61頁，創(chuàng)作于2023年2月圖的一些概念和規(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為非空集，但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果，為此規(guī)定頂點集為空集的圖為空圖，并將空圖記為。第22頁，課件共61頁，創(chuàng)作于2023年2月標定圖與非標定圖、基圖將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊<vi,vj>），并稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。易知標定圖與非標定圖是可以相互轉(zhuǎn)化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。第23頁，課件共61頁，創(chuàng)作于2023年2月關(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。第24頁，課件共61頁，創(chuàng)作于2023年2月關(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)的頂點均稱為孤立點。第25頁，課件共61頁，創(chuàng)作于2023年2月相鄰與鄰接設(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相鄰。第26頁，課件共61頁，創(chuàng)作于2023年2月27例：點邊之間的關(guān)聯(lián)次數(shù)第27頁，課件共61頁，創(chuàng)作于2023年2月28例：點點、邊邊之間的相鄰關(guān)系第28頁，課件共61頁，創(chuàng)作于2023年2月頂點的度數(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)。第29頁，課件共61頁，創(chuàng)作于2023年2月30d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=0第30頁，課件共61頁，創(chuàng)作于2023年2月31d+(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)=2第31頁，課件共61頁，創(chuàng)作于2023年2月32最大(出/入)度,最小(出/入)度在無向圖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頁，課件共61頁，創(chuàng)作于2023年2月33握手定理（圖論基本定理）定理7.1設(shè)圖G=<V,E>為無向圖或有向圖，

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

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

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

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

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

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

第35頁，課件共61頁，創(chuàng)作于2023年2月度數(shù)列設(shè)G＝<V,E>為一個n階無向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對于頂點標定的無向圖，它的度數(shù)列是唯一的。反之，對于給定的非負整數(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)分別為D的出度列和入度列。第36頁，課件共61頁，創(chuàng)作于2023年2月度數(shù)列舉例按頂點的標定順序，度數(shù)列為 4,4,2,1,3。第37頁，課件共61頁，創(chuàng)作于2023年2月度數(shù)列舉例按字母順序，度數(shù)列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2第38頁，課件共61頁，創(chuàng)作于2023年2月39(4，4，3，1，0)(3，4，3，4，2)練習：第39頁，課件共61頁，創(chuàng)作于2023年2月可圖化的充要條件定理

設(shè)非負整數(shù)列d＝(d1，d2，…，dn)，則d是可圖化的當且僅當證明 必要性。由握手定理顯然得證。

充分性。由已知條件可知，d中有偶數(shù)個奇數(shù)度點。 奇數(shù)度點兩兩之間連一邊，剩余度用環(huán)來實現(xiàn)。5331第40頁，課件共61頁，創(chuàng)作于2023年2月41例7.1：(3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？已知圖G中有10條邊，4個3度頂點，其余頂點的度數(shù)均小于等于2，問G中至少有多少個頂點？為什么？解：1.由于這兩個序列中，奇數(shù)度頂點個數(shù)均為奇數(shù)，由握手定理的推論可知，它們都不能成為圖的度數(shù)序列。2.顯然，圖G中的其余頂點度數(shù)均為2時G圖的頂點數(shù)最少.設(shè)G圖至少有x個頂點.由握手定理可知，

3×4+2×(x-4)=2×10

解得:x=8

所以G至少有8個頂點。第41頁，課件共61頁，創(chuàng)作于2023年2月簡單圖與多重圖定義在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。 在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖。 既不含平行邊也不含環(huán)的圖稱為簡單圖。第42頁，課件共61頁，創(chuàng)作于2023年2月43簡單圖與多重圖示例第43頁，課件共61頁，創(chuàng)作于2023年2月完全圖定義7.7

設(shè)G為n階無向簡單圖，若G中每個頂點均與其余的n-1個頂點相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n≥1)。

設(shè)D為n階有向簡單圖，若D中每個頂點都鄰接到其余的n-1個頂點，又鄰接于其余的n-1個頂點，則稱D是n階有向完全圖。

設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖。第44頁，課件共61頁，創(chuàng)作于2023年2月完全圖舉例n階無向完全圖的邊數(shù)為： n(n-1)/2n階有向完全圖的邊數(shù)為： n(n-1)n階競賽圖的邊數(shù)為： n(n-1)/2K53階有向完全圖4階競賽圖第45頁，課件共61頁，創(chuàng)作于2023年2月正則圖定義設(shè)G為n階無向簡單圖，若v∈V(G)，均有d(v)＝k，則稱G為k-正則圖。舉例

n階零圖是0-正則圖

n階無向完全圖是(n-1)-正則圖 彼得森圖是3-正則圖說明

n階k-正則圖中，邊數(shù)m＝kn/2。 當k為奇數(shù)時，n必為偶數(shù)。第46頁，課件共61頁，創(chuàng)作于2023年2月子圖定義設(shè)G＝<V,E>，G＝<V,E>為兩個圖(同為無向圖或同為有向圖)，若VV且EE，則稱G是G的子圖，G為G的母圖，記作GG。 若VV或EE，則稱G為G的真子圖。 若V＝V，則稱G為G的生成子圖。 設(shè)G＝<V,E>為一圖，V1V且V1≠，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導出的子圖，記作G[V1]。 設(shè)E1E且E1≠，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點為頂點集V1的圖為G的E1導出的子圖，記作G[E1]。第47頁，課件共61頁，創(chuàng)作于2023年2月48在上圖中，(2)，(3)均為(1)的子圖；(3)是生成子圖；(5)，(6)均為(4)的子圖；(5)是生成子圖；第48頁，課件共61頁，創(chuàng)作于2023年2月導出子圖舉例在上圖中，設(shè)G為(1)中圖所表示，取V1＝{a,b,c}，則V1的導出子圖G[V1]為(2)中圖所示。取E1＝{e1,e3}，則E1的導出子圖G[E1]為(3)中圖所示。第49頁，課件共61頁，創(chuàng)作于2023年2月補圖定義7.9設(shè)G＝<V,E>為n階無向簡單圖，以V為頂點集，以所有為邊集使G成為完全圖Kn的添加邊組成的集合的圖，稱為G的補圖，記作G。

若圖G≌G，則稱為G是自補圖。(1)為自補圖(2)和(3)互為補圖第50頁，課件共61頁，創(chuàng)作于2023年2月51在下圖中，(1)是(2)的補圖，當然(2)也是(1)的補圖，就是說，(1)，(2)互為補圖。同樣，(3)，(4)互為補圖。第51頁，課件共61頁，創(chuàng)作于2023年2月52圖的同構(gòu)在圖論的研究中，我們更關(guān)心的是圖的結(jié)構(gòu),而這種結(jié)構(gòu)與頂點與邊的具體元素或與圖的圖形的畫法無關(guān).對此,我們引進同構(gòu)的概念.第52頁，課件共61頁，創(chuàng)作于2023年2月53圖同構(gòu)(graphisomorphism)定義7.10:設(shè)兩個無向（有向）圖G1=<V1,E1>,G2=<V2,E2>,若存在雙射f:V1→V2,滿足?u∈V1,?