1、圖論 (Graph Theory),圖論是個(gè)應(yīng)用十分廣泛而又極其有趣數(shù)學(xué)分支, 物理、 學(xué)、生物、經(jīng)濟(jì)、管理科學(xué)、信息論、計(jì)算機(jī)等各個(gè)領(lǐng) 域都可以找到圖論的足跡. 歷史上很多數(shù)學(xué)家對(duì)圖論的形成作出過貢獻(xiàn), 特別要提 到的歐拉 (Euler)、基爾霍夫(Kirchhoff)與凱萊(Cayley). 歐拉在1736年發(fā)表了第一篇圖論的論文, 解決了著名的 七橋問題. 拓?fù)鋵W(xué)中著名的歐拉公式,也是圖論中的重要 公式. 基爾霍夫?qū)﹄娐肪W(wǎng)絡(luò)的研究(基爾霍夫定律)以及凱萊在 有機(jī)化學(xué)計(jì)算中應(yīng)用了樹和生成樹等概念. 很多有趣的數(shù)學(xué)游戲也促進(jìn)了圖論的發(fā)展,如漢米爾頓 周游世界游戲, 四色定理等, 都促進(jìn)了圖論

2、的發(fā)展.,1. 圖的基本概念,例1. 多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換圖: (進(jìn)程:一個(gè)業(yè)務(wù)可以分成若干個(gè)階段,每個(gè)階段看成一個(gè)進(jìn)程. 一個(gè)進(jìn)程有三種狀態(tài).) 就緒狀態(tài):進(jìn)程具備執(zhí)行條件,因CPU少,要排隊(duì)等待分配 CPU.,進(jìn)程調(diào)度,請(qǐng)求I/O,I/O完成,執(zhí)行狀態(tài):進(jìn)程已經(jīng)分配到CPU,它的程序正被執(zhí)行.,等待狀態(tài):進(jìn)程等待某事件(如I/O完成),此時(shí)就是給它CPU 也不能執(zhí)行.,例2.“七橋問題” 十八世紀(jì),哥尼斯堡城內(nèi)有一條河-普雷 格爾河,河中有兩個(gè)島嶼,河面架有七座橋,使得島嶼與兩 岸之間互相貫通. V=A,B,C,D E=e1, e2, e3, e4, e5 e6, e7 人們茶余

3、飯后經(jīng)常到橋上散步,從而提出這樣問題:是否 可以從某地出發(fā)，每座橋都走一次,再回到出發(fā)點(diǎn). 很多 人試圖找出這樣的路徑, 都沒有找到. 后來歐拉證明這樣 的路徑根本不存在. 此圖可以抽象為上邊右圖.,例3. 在機(jī)械加工中,經(jīng)常需要在一塊金屬薄板上鉆若干孔 (或者是機(jī)械手在印刷電路板上安裝電子元件)如圖所示: 問如何確定鉆孔的次序,使之加工的時(shí)間最短. 這個(gè)問題可以抽象為在一個(gè)圖上求從某一個(gè)結(jié)點(diǎn)出發(fā), 經(jīng)過所有結(jié)點(diǎn)一次, 使得此路徑最短. 如何找到此路徑. 類似的: 旅行最優(yōu)問題, 工程最優(yōu)問題, 成本(費(fèi)用)最低. .,一. 圖的概念 一個(gè)圖 G=, 其中 V(G): 是G的結(jié)點(diǎn)的非空集合.

4、(V(G),簡(jiǎn)記成V. E(G): 是G的邊的集合. 有時(shí)簡(jiǎn)記成E. 結(jié)點(diǎn)(Vertices): 用 表示, 旁邊標(biāo)上該結(jié)點(diǎn)的名稱. 邊(Edges): 有向邊: 帶箭頭的弧線. 從u到v的邊表示成 無向邊:不帶箭頭的弧線. u和v間的邊表示成 (u,v),在圖中, 結(jié)點(diǎn)的相對(duì)位置不同, 邊的曲直、長(zhǎng)短無關(guān)緊要. 鄰接點(diǎn): 與一邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn). u v a b 鄰接邊: 關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊. 環(huán):只關(guān)聯(lián)一個(gè)結(jié)點(diǎn)的邊. 平行邊:在兩個(gè)結(jié)點(diǎn)之間關(guān)聯(lián)的多條邊. 二. 有向圖與無向圖 有向圖:只有有向邊的圖. 無向圖:只有無向邊的圖. 三. 零圖與平凡圖 孤立結(jié)點(diǎn):不與任何邊關(guān)聯(lián)的結(jié)點(diǎn). u 零

5、圖:僅由一些孤立結(jié)點(diǎn)構(gòu)成的圖. a 即此圖的邊的集合E= b c 平凡圖:僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的零圖.|V(G)|=1,|E(G)|=0,G:,四. 簡(jiǎn)單圖與多重圖 簡(jiǎn)單圖:不含有環(huán)和平行邊的圖. 多重圖: 含有平行邊的圖. 五. 無向圖結(jié)點(diǎn)v的度: 1.定義:G是個(gè)無向圖, vV(G), 結(jié)點(diǎn)v所關(guān) 聯(lián)邊數(shù),稱之為結(jié)點(diǎn)v的度. 記作 deg(v).(或d(v). deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一個(gè)環(huán)給結(jié)點(diǎn)的度是2. 2.無向圖的結(jié)點(diǎn)度序列: 令G=是無向圖, V=v1,v2,v3,vn, 則稱: (deg(v1), deg(v2),deg(v3),

6、,deg(vn) 為圖G的結(jié)點(diǎn)度序列. 例如上圖的結(jié)點(diǎn)度序列為:(3,5,4,2) 3.圖的最大度(G)與最小度(G) :G=是無向圖, (G) =maxdeg(v)|vG (G) =mindeg(v)|vG,上圖中(G)=5 (G)=2 4. 定理8-1.1 每個(gè)無向圖所有結(jié)點(diǎn)度總和等于邊數(shù)的2倍. 即 證明:因?yàn)閳D中每條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),因此每條邊給予它所 關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)的度各是1, 即一條邊對(duì)應(yīng)的度數(shù)是2, 所 以整個(gè)圖的度數(shù)總和為邊數(shù)的2倍. 定理8-1.2(握手定理)每個(gè)無向圖中,奇數(shù)度的結(jié)點(diǎn)必為偶 數(shù)個(gè).(一次集會(huì)中,與奇數(shù)個(gè)人握手的人,必是偶數(shù)個(gè).) 證明:令G=是無向圖,將V分成

7、兩個(gè)子集V1 和V2, 其中 V1 -是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合, V2 -是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合 而 是偶數(shù). 所以 也是偶數(shù), 于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù).,deg(v)=2|E| vV,deg(v) + deg(v) =2|E| vV1 vV2,deg(v) vV2,deg(v) vV1,六. k-正則圖:一個(gè)無向簡(jiǎn)單圖G中,如果(G)=(G)=k 則稱G為k-正則圖. 課堂練習(xí): 1.下面哪些數(shù)的序列,可能是一個(gè)圖的度數(shù)序列? 如果可能,請(qǐng)?jiān)嚠嫵鏊膱D. 哪些可能不是簡(jiǎn)單圖? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) 2.已知無向簡(jiǎn)單圖G中,有

8、10條邊,4個(gè)3度結(jié)點(diǎn),其余結(jié)點(diǎn)的 度均小于或等于2,問G中至少有多少個(gè)結(jié)點(diǎn)?為什么?,1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) 解:a)不是, 因?yàn)橛腥齻€(gè)數(shù)字是奇數(shù). b) 是. c) 可能不是簡(jiǎn)單圖,如圖： 2.解:已知邊數(shù)|E|=10, deg(v)=2|E|=20 其中有4個(gè)3度結(jié)點(diǎn), 余下結(jié)點(diǎn)度之和為: 20-34=8 因?yàn)镚是簡(jiǎn)單圖, 其余每個(gè)結(jié)點(diǎn)度數(shù)2, 所以至少還有 4個(gè)結(jié)點(diǎn). 所以G中至少有8個(gè)結(jié)點(diǎn).同時(shí)，8個(gè)結(jié)點(diǎn)也是 足夠的。例如“目”的圖形就是滿足條件的例子。,七. 有向圖結(jié)點(diǎn)的出度和入度:(in degree out

9、 degree) G=是有向圖,vV v的出度: 從結(jié)點(diǎn)v射出的邊數(shù). 記作deg+(v) 或 dego(v) v的入度: 射入結(jié)點(diǎn)v的邊數(shù). 記作deg-(v) 或 degi(v) degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1 dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0 定理8-1.3 G=是有向圖, 則G的所有結(jié)點(diǎn)的出度之和 等于入度之和. 證明: 因?yàn)閳D中每條邊對(duì)應(yīng)一個(gè)出度和一個(gè)入度. 所以所 有結(jié)點(diǎn)的出度之和與所有結(jié)點(diǎn)的入度之和都等于有向邊 數(shù). 必然有所有結(jié)點(diǎn)的出度之和等于入度之和.,八. 完全圖 1.無向完全圖

10、定義:G是個(gè)簡(jiǎn)單圖, 如果每對(duì)不同結(jié)點(diǎn)之間都有邊相連 則稱G是個(gè)無向完全圖. 如果G有n個(gè)結(jié)點(diǎn), 則記作Kn. 定理8-1.4 無向完全圖Kn, 有邊數(shù) 證明: 因?yàn)镵n中每個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)關(guān)聯(lián), 即每 個(gè)結(jié)點(diǎn)的度均為n-1, 所以Kn的所有結(jié)點(diǎn)度數(shù)總和為 n(n-1), 設(shè)邊數(shù)為|E|, 于是n(n-1)=2|E| 所以|E|=,2. 有向圖的完全圖(注:這里的定義與教材不同) 1).有向簡(jiǎn)單完全圖:G是個(gè)有向簡(jiǎn)單圖,如果任何兩個(gè)不同結(jié)點(diǎn)之間都有相互可達(dá)的邊,則稱它是有向簡(jiǎn)單完全圖. 例如: 定理8-1.5: 有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單完全圖有邊數(shù)為n(n-1). 證明: 顯然它的邊數(shù)是

11、Kn邊數(shù)的2倍.所以是n(n-1). 2).有向完全圖(有向全圖) (它與完全關(guān)系圖一致) G是個(gè)有向圖如果任何兩個(gè)結(jié)點(diǎn)之間都有相互可達(dá)的邊,則稱它是有向完全圖. 其圖形如下:,所以有n個(gè)結(jié)點(diǎn)的有向完全圖, 有邊數(shù) n2. 九.子圖和生成子圖 1.子圖:設(shè)G=是圖,如果G=且VV, V, EE, 則稱G是G的子圖. 可見G1,G2,G3都是K5的子圖.,2. 生成子圖 設(shè)G=是圖, G=, G是G的子圖,如果V=V, 則稱G是G的生成子圖. 上例中, G1是K5的生成子圖. 十. 補(bǔ)圖 由G的所有結(jié)點(diǎn)和為使G變成完全圖,所需要添加的那些 邊組成的圖, 稱之為G相對(duì)完全圖的補(bǔ)圖,簡(jiǎn)稱G的補(bǔ)圖,

12、記作 .,*十一.相對(duì)補(bǔ)圖 設(shè)G1=是圖G=的子圖,如果有G2= 使得E2=E-E1且V2中僅包含E2中的邊所關(guān)聯(lián)的結(jié)點(diǎn),則稱 G2是G1相對(duì)G的補(bǔ)圖. 可見G2是G3相對(duì)G的補(bǔ)圖. G3也是G2相對(duì)G的補(bǔ)圖. 而G1不是G3相對(duì)G的補(bǔ)圖(多了一個(gè)結(jié)點(diǎn)). 但是G3是G1相對(duì)G的補(bǔ)圖. 可見: 相對(duì)補(bǔ)圖無相互性.,十二. 圖的同構(gòu) 設(shè)G=和G=是圖,如果存在雙射f:VV 且 任何vi,vjV,若邊(vi,vj)E,當(dāng)且僅當(dāng) 邊(f(vi),f(vj)E, (或若邊E,當(dāng)且僅當(dāng) 邊E),則稱G與 G同構(gòu),記作GG. (同構(gòu)圖要保持邊的“關(guān)聯(lián)”關(guān)系) 例如:右邊所示的兩個(gè)圖: G= G= 構(gòu)造映射f:VV 兩個(gè)圖同構(gòu)的必要條件:1.結(jié)點(diǎn)個(gè)數(shù)相等. 2.邊數(shù)相等. 3.度數(shù)相同的結(jié)點(diǎn)數(shù)相等. 4. 對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)相等.,下面是同構(gòu)的圖: 右面兩個(gè)圖不同構(gòu): 左圖中四個(gè)3度結(jié)點(diǎn) 構(gòu)成四邊形,而右圖, 則不然. 練習(xí):請(qǐng)畫出K4的所有不