1/81離散數(shù)學(xué)集合論數(shù)理邏輯圖論代數(shù)2/81一個人要把他帶的一條狗，一只羊和一袋菜用一條小船擺渡到河的對岸。每次擺渡這個人只能將狗、羊和菜之一帶過去。但是，不能把狗和羊，也不能把羊和菜單獨的留在河的同一岸。V={被允許出現(xiàn)的局面}E={頂點之間的關(guān)系|一次擺渡能夠從一局面變?yōu)榱硪痪置鎪3/819.1圖的基本概念(一)有向圖(二)無向圖(三)圖的同構(gòu)(四)完全圖(五)握手定理頂點集、邊集多重邊、自環(huán)、孤立點簡單圖/多重圖圖的同構(gòu)映射子圖、生成子圖、補圖有向完全圖頂點的度數(shù)入度、出度有向圖G=(V,E)定義1設(shè)V是一個非空有限集合，E是V上的二元關(guān)系。則稱有序二元組G=(V,E)是一個有向圖，并稱V為頂點集，E為邊集。

其中，邊集E為有序二元組所構(gòu)成的集合。

5/81例設(shè)V={2，3，4，5，6}，E={(x,y)|x整除y},即

E={(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}

畫出有向圖G=(V,E)246356/81有向圖G=(V,E):邊、孤立點、自環(huán)若(a,b)?E，稱(a,b)為圖G中一條邊。設(shè)(a,b)?E，稱邊(a,b)關(guān)聯(lián)于頂點a和b，頂點a稱為該邊的始點，頂點b稱為該邊的終點，并稱a和b相鄰。若一個頂點沒有任何邊關(guān)聯(lián)于它，稱該頂點為孤立點。若一條邊的始點和終點是同一頂點，稱該邊為自環(huán)。246357/81多重集約定一個多重集是一些對象的總體，但這些對象不必不同。如:

{a,a,a,b,b,c}{a,a,a}

{a,b,c}一個元素的重數(shù)是它在該多重集里出現(xiàn)的次數(shù)集合僅是多重集中重數(shù)僅為0和1的特殊情況8/81無向圖G=(V,E)定義2設(shè)V是一個非空有限集合，E是一個多重集合，E的元素是僅含V中兩個元素的多重子集。則稱二元組G=(V,E)是一個無向圖，例1(p136)

圖G=(V,E)，

V={v1,v2,v3,v4,v5}，

E={{v1,v2},{v2,v3},

{v3,v3},{v3,v4},{v2,v4},{v4,v5},{v2,v5},{v2,v5}}9/81無向圖G=(V,E)

:邊、自環(huán)、孤立點{v,u}∈E,稱{v,u}是G中一條邊。稱V為頂點集，稱E為邊集。設(shè)e={v,u}是G中的一條邊，v和u稱為邊e的二個端點，稱邊e關(guān)聯(lián)

v和u，也稱v鄰接到u，或u鄰接于v。若u=v，稱{v,u}為G中的自環(huán)。對于任意的u∈

V，若不存在任何邊關(guān)聯(lián)u，說頂點u是孤立點。邊和點：關(guān)聯(lián)點和點：相鄰邊和邊：相鄰10/81多重圖、簡單圖一個圖，有向圖或無向圖，其邊集若是多重集，稱這樣的圖為多重圖，也簡稱圖。若一個圖，也就是多重圖，其重數(shù)大于1的邊稱為多重邊，又稱有這樣邊的圖為有多重邊的圖。稱一個沒有多重邊，沒有自環(huán)，也沒有孤立點的圖為簡單圖。若不聲明是簡單圖，就泛指圖或多重圖。11/81圖的畫法不同、實質(zhì)相同12/81圖的畫法不同、實質(zhì)相同13/81圖的同構(gòu)

G1?G2定義3設(shè)G1=(V1,E1)和G2=(V2,E2)是兩個圖，若存在函數(shù)f:V1→V2，f是雙射，且若定義函數(shù)g:E1→E2，對于任意的{v1,v1’}∈E1，g({v1,v1’})={f(v1),f(v1’)}，g也是一個雙射。則稱圖G1和圖G2是同構(gòu)的兩個圖，記為

G1?G2，并稱f為圖的同構(gòu)映射，。14/81完全圖Kn一個簡單圖，若每一對不同的頂點之間都有一條邊相連，這樣的圖稱為完全圖。一個有n(∈N)個頂點的完全圖在同構(gòu)的意義下是唯一的，記為Kn。15/81子圖、真子圖、生成子圖定義4設(shè)G=(V,E),H=(V’,E’)是兩個圖。若V’?V且E’?E，則說H是G的子圖。若V’V或E’E，則說H是G的真子圖。若H是G的子圖且V’=V，說H是G的生成子圖。?≠?≠K4的真子圖K4的生成子圖例:K416/81例

K4的所有的生成子圖有多少？64個！17/81例K4所有互不同構(gòu)的生成子圖有多少？11個！18/81補圖設(shè)G=(V,E)是一個圖，它沒有自環(huán)和多重邊。令=(V,E’)，其中E’={{u,v}│u≠v，u,v?V，{u,v}?E}稱為G的補圖。GG例下面兩圖互為補圖：19/81自互補圖一個無向簡單圖如果同構(gòu)于它的補圖，則稱這個圖為自互補圖。例4個頂點的自互補圖：20/81例

試畫出五個頂點的自互補圖21/81頂點的度數(shù)設(shè)G=(V,E)是一個圖，對于每一個v?V，稱關(guān)聯(lián)頂點v的邊數(shù)為頂點v的度數(shù)，記為d(v)。23322/81定理1(握手定理)設(shè)G=(V,E)是一個圖，對于每一個v?V，d(v)為頂點v的度數(shù)。則:∑d(v)=2|E|v?V23323/81推論任何一個無向圖，度數(shù)為奇數(shù)的頂點有偶數(shù)個。證明：設(shè)G=(V,E)是一個無向圖。令

V1={v?V│d(v)是奇數(shù)}，

V2={v?V│d(v)是偶數(shù)}，顯然{V1，V2}是V的一個劃分。

∑d(v)v?V1∑d(v)=v?V∑d(v)v?V2+∑d(v)v?V∑d(v)=v?V1∑d(v)v?V2－∵∴容易說明，等式右端是偶數(shù)，而等式左端是|V1|個奇數(shù)相加，故|V1|為偶數(shù)。24/81例2有9個人在一起打乒乓球，已知他們每人至少和其中另外3個人各打過一場球，則一定有一個人不止和3個人打過球。用圖論語言解釋這件事。解：設(shè)v1，v2，…，v9代表這9個人，建立頂點集

V={v1，v2，…，v9}，對于其中的任意兩個人vi和vj（i≠j），若vi和vj打過一場球，則{vi,vj}?E，得到邊集E，則我們有了一個無向圖G=（V，E）。若每一個人僅和其余3個人各打過一場球，則d(vi)=3，而此時圖G的奇數(shù)度的頂點是9個，即是奇數(shù)個，與推論矛盾。矛盾說明，至少有一個人vi，d(vi)≥4。25/81例(3,3,2,3)與(5,2,3,1,4)能成為圖的度數(shù)序列嗎?為什么?解:不能，因為度數(shù)為奇數(shù)的頂點數(shù)目不是偶數(shù)。26/81例已知圖G中有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2,問G中至少有多少個頂點?為什么?解:圖G中頂點度數(shù)之和為2×10=20，而已有4個頂點的度數(shù)之和為4×3=12，還剩下8度，按題意，還需至少4個頂點，所以圖G至少有8個頂點。27/81例3(p138)兩無向圖是否同構(gòu)？abcdegf1234567答：圖（a）中兩個3度頂點之間沒有邊，而圖（b）中兩個3度頂點之間有邊，故不存在兩圖之間的同構(gòu)映射。（a）（b）28/81同構(gòu)圖的頂點度設(shè)G1=(V1,E1)和G2=(V2,E2)同構(gòu)，即存在同構(gòu)映射f:V1→V2，則對于任意的vi?V1，一定有

d(vi)=d(f(vi))

任意兩個同構(gòu)的無向圖，一定有一個同樣的頂點度序列。頂點度序列是一組按大小排列的正整數(shù)，每一個數(shù)對應(yīng)某一個頂點的度數(shù)。29/81例考察兩個不同構(gòu)的簡單無向圖。

每一個圖都僅有6個頂點，且每個頂點都均是3度，并指出這兩個圖為什么不同構(gòu)。反證法：假使兩圖同構(gòu)。不妨假設(shè)紅點對應(yīng)紅點,則3個綠點對應(yīng)3個綠點,剩下的2個藍點對應(yīng)2個藍點，而在左圖中2個藍點間無邊，而在右圖中2個藍點間有邊。矛盾！30/81有向完全圖如果一個有向圖去掉邊的方向以后所得無向圖是完全圖，則稱為有向完全圖。31/81出度、入度定義5設(shè)G=(V,E)是一個有向圖，v?V，稱以v為始點的邊的條數(shù)為v的出度，記為

d出(v)或d+(v)；稱以v為終點的邊的條數(shù)為v的入度，記為d入(v)或d—(v)。32/81定理2∑

d出(v)=∑d入(v)=|E|v?Vv?V設(shè)G=(V,E)是一個有向圖，則33/81小結(jié)

圖的基本概念(一)有向圖(二)無向圖(三)圖的同構(gòu)(四)完全圖(五)握手定理頂點集、邊集多重邊、自環(huán)、孤立點簡單圖/多重圖圖的同構(gòu)映射子圖、生成子圖、補圖有向完全圖頂點的度數(shù)入度、出度34/819.2圖中的通路、圖的連通性和圖的矩陣表示(一)通路(二)簡單通路、初等通路(三)簡單回路、初等回路(四)連通圖(五)單側(cè)連通、強連通(六)關(guān)聯(lián)矩陣、鄰接矩陣、可達矩陣35/81通路:頂點序列稱頂點序列(vi1，vi2，…，vis)為圖G中的一條通路，若vij?V，1≤j≤s，且(vij,vi(j+1))?E，其中1≤j≤s-1。例

(v1,v2,v3)為通路(v1,v3,v4,v6,v7)為通路36/81通路:邊序列稱邊序列(ei1，ei2，…，eit)為圖G中的一條通路，若eij?E，1≤j≤t，且適當?shù)囊?guī)定邊eij(1≤j≤t)中的兩個端點，讓其中一個為起點，一個為終點，可以使eij的終點與ei(j+1)的起點是同一頂點，其中1≤j≤t-1。例

(e2,e3)為通路(e1,e5,e8,e12)為通路37/81通路的長度、頂點間的距離稱一條通路經(jīng)過的邊的多少為這條通路的長度。稱兩個頂點間的最短通路的長度為該兩個頂點間的距離。例

(v1,v2,v3)為通路，長度為2。

(v1,v3,v4,v6,v7)為通路,長度為4。38/81簡單通路、初等通路稱一條通路為簡單通路,如果它的每一條邊都不重復(fù)出現(xiàn)。稱一條通路為初等通路,如果它的每一個頂點都不重復(fù)出現(xiàn).例

(v1,v2,v5,v6,v4,v6,v8,v7)為簡單通路,但非初等通路.39/81回路、簡單回路、初等回路（圈）設(shè)(vi1，vi2，…，vis)是圖G=(V,E)中的一條通路，若vi1=vis，則這條通路為G中的一條回路。若一個回路中邊不重復(fù)出現(xiàn)，則稱之為簡單回路。若一個回路中頂點不重復(fù)出現(xiàn)，則稱之為初等回路，又稱之為圈。40/81例回路、簡單回路、初等回路（圈）

(v2,v4,v5,v6,v4,v3,v2)為一個簡單回路，但不是圈41/81定理1G=(V,E)是一個無向圖。v1，v2?V，若G中存在一條v1

到v2的通路，則一定存在一條從v1到v2的初等通路。42/81定理1的證明設(shè)S={n?N│G中存在一條長為n的從v1

到v2的通路}由題知S≠?，又S?N，由自然數(shù)集的非空子集有最小數(shù)，可設(shè)m?S，對于任意n?S，有m≤

n。設(shè)(v1=vi0，vi1，…，vi(m-1)，v2=vim)是G中一條從v1到v2長度為m的通路，則這條通路即是初等通路。否則，若它不是初等通路，一定存在兩個相同的頂點vij和vik(0≤j<k≤m)，使得vij=vik。于是(vi0，…，vij

，vi(k+1)，…，vim)也是中一條從v1到v2的通路，且長度為m-k+j(<m)，這與m最小矛盾。43/81推論G=(V,E)是一個無向圖，|V|=n。如果G中存在一條從v1到v2的通路，那么一定存在一條從v1到v2的長度小于等于n-1的通路。恰有n個頂點的圖G中的初等通路最長為n-1。44/81連通圖定義G=(V,E)是一個無向圖，若G中任意兩個不同的頂點之間在G中都有通路存在，則稱G是一個連通圖，否則稱G為不連通圖。45/81有向連通圖定義稱一個有向圖是連通的，如果去掉邊的方向后所得無向圖是連通的。46/81單側(cè)連通一個有向圖任意二點之間都有單向通路，則稱為單側(cè)連通圖。例連通、非單側(cè)連通單側(cè)連通47/81強連通如果一個有向圖任意二點之間都有雙向的通路，則稱為強連通圖。例單側(cè)連通非強連通強連通連通性判別定理(強連通判別法)

D強連通當且僅當D中存在經(jīng)過每個頂點至少一次的回路定理(單向連通判別法)

D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路

48(1)(2)(3)例下圖(1)強連通,(2)單連通,(3)弱連通49/81連通分支設(shè)G為一個無向圖,R是G中頂點之間的連通關(guān)系,按著R可將V(G)劃分成k(k≥1)個等價類,記成V1,V2,···,Vk,稱由它們導(dǎo)出的子圖G[V1],G[V2],…,G[Vk]為G的連通分支。其個數(shù)記作p(G)=k.50/81例連通分支連通分支數(shù)為1連通分支數(shù)為451點割集

記Gv:從G中刪除v及關(guān)聯(lián)的邊

GV:從G中刪除V中所有的頂點及關(guān)聯(lián)的邊

Ge:從G中刪除e

GE:從G中刪除E中所有邊定義設(shè)無向圖G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),則稱V為G的點割集.若{v}為點割集,則稱v為割點.52點割集(續(xù))例{v1,v4},{v6}是點割集,v6是割點.{v2,v5}是點割集嗎？53邊割集定義設(shè)無向圖G=<V,E>,EE,若p(GE)>p(G)且EE,p(GE)=p(G),則稱E為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.圖中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6}是邊割集嗎？54/81例G=(V,E)是一個簡單圖，試證明若G不連通，則G的補圖G一定連通。證明：因為G不連通，則G可以分為若干連通子圖：（V1，E1），---，（Vn，En）根據(jù)補圖構(gòu)造過程知，在G的補圖中，

V1中每個頂點與其它頂點集V2，---，Vn中頂點有邊相連。這樣，在G的補圖中，有分別屬于兩個頂點子集Vi與Vj中的任意兩個頂點之間有邊直接相連，屬于同一個頂點子集Vi的任意兩個頂點借助頂點子集Vj的任意一個頂點連通。所以，根據(jù)連通的定義知：G的補圖一定連通。圖的矩陣表示關(guān)聯(lián)矩陣（無向圖、有向圖）鄰接矩陣（無向圖、有向圖）有向圖的可達矩陣5556/81無向圖的關(guān)聯(lián)矩陣設(shè)G=(V,E)是一個無向圖，|V|=n，|E|=m，V={v1,v2,?,vn}，E={e1,e2,?,em}，則有n×m階矩陣，

M(G)=(mij)n×m其中:

稱M(G)=(mij)n×m為圖G的關(guān)聯(lián)矩陣。mij=1如頂點vi與邊ei關(guān)聯(lián)0如頂點vi與邊ei關(guān)聯(lián)57/81例

e1e2e3e4e5e6e7e8

v1

11101000

v2

10010000

v3

00110011v4

00001101v5

01000110

M(G)=特點：1、行和為度數(shù)2、列和為23、所有元素的和為總

度數(shù)4、平行邊列相同有向圖的關(guān)聯(lián)矩陣58定義設(shè)無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).59例：寫出下圖的關(guān)聯(lián)矩陣60有向圖的關(guān)聯(lián)矩陣性質(zhì)

(4)平行邊對應(yīng)的列相同61/81鄰接矩陣(adjacencymatrix)

設(shè)G=(V,E)是一個無向圖，|V|=n，

V={v1,v2,?,vn}，則有n×n階矩陣，

A(G)=(aij)n×n其中:

稱A(G)=(aij)n×n為圖G的鄰接矩陣。aij=1{vi,vj}?E0{vi,vj}?E62/81例鄰接矩陣

v1v2v3v4v5v1

01111v2

10101v3

11011v4

10101v5

10110

A(G)=63定義設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點vi鄰接到頂點vj邊的條數(shù)，稱()mn為D的鄰接矩陣,記作A(D),簡記為A.有向圖的鄰接矩陣（補）

64例鄰接矩陣性質(zhì)65/81定理2設(shè)圖G=(V,E)，其中V={v1,v2,?,vn}。A是G的鄰接矩陣。對于任意的自然數(shù)k，設(shè)矩陣Ak的第i行第j列的元素為aij(k)，即

Ak=(aij(k))n×n則aij(k)

給出了所有的從vi到vj的長度為k的通路的條數(shù)。若aij(k)=0，說明沒有vi到vj的長度為k的通路。66/81例有向圖D如圖所示,求A,A2,A3,A4,

并回答諸問題：D中長度為1,2,3,4的通路各有多少條？

其中回路分別為多少條？(2)D中長度小于或等于4的通路為多少條？

其中有多少條回路？

長度通路回路

67合計50818121133141417368/81有向圖的可達矩陣定義設(shè)D=<V,E>為有向圖,V={v1,v2,…,vn},令

稱(pij)nn為D的可達矩陣,記作P(D),簡記為P.性質(zhì):

P(D)主對角線上的元素全為1.D強連通當且僅當P(D)的元素全為1.69例右圖所示的有向圖D的可達矩陣為70/819.3帶權(quán)圖與帶權(quán)圖中的最短通路(一)帶權(quán)圖(二)最短通路問題(三)狄克斯瑞(Dijkstra)算法71/81例假設(shè)有分布在不同建筑物中的5臺計算機C1,C2,C3,C4,C5。計算機連接的可能方案以及每種連接方式的成本（單位：元）如右圖所示。C1100C2C3C4C5120370200成本最低的安裝方案C1100C2900C3C4C512040020045037072/81帶權(quán)圖一個帶權(quán)圖規(guī)定為◆一個有序三元組(V，E，f)，或◆一個有序三元組(V，E，g)，或◆一個有序四元組(V，E，f，g)，其中，V是頂點集，E是邊集，f是定義在V上的函數(shù)，g是定義在E上的函數(shù)，f和g我們可以稱為權(quán)函數(shù)。對于每一個頂點或邊x，f(x)和g(x)可以是一個數(shù)字、符號或是某種量。73/81帶權(quán)圖中的最短通路設(shè)G=(V,E,W)是一個帶權(quán)圖，其W是邊集E到R+={x?R│x>0}的一個函數(shù)。通常稱W(e)為邊e的長度，圖G中一個通路的長度定義為通路中所經(jīng)過的邊的長度之和。設(shè)v0,z?V，要求從v0到z的最短通路的長。74/81Dijkstra算法的基本思想先把V分成兩個子集，一個設(shè)為T,T={v?V│v0到v的最短通路的長已經(jīng)求出}，另一個是P=V－T。顯然T≠?，因為至少v0?T。要不斷地擴大T，直到z?T。TP＝V－Tv0z75/81定理對于任意的x?P，設(shè)LT(x)表示從v0僅經(jīng)過T中的頂點到x的最短通路的長。若不存在這樣的通路，置LT(x)=∞。稱LT(x)為x關(guān)于T的指標。令

LT(t1)=min{LT(x)│x?P}則LT(t1)是從v0到t1的最短通路的長。TP＝V－Tv0t1注：LT(x)即為教材上的l(t)x76/81定理的證明若存在從v0到t1的通路其長小于LT(t1)，這條路一定包含了P中的頂點（否則，與LT(t1)最小性矛盾）。設(shè)t2?P，且t2是從v0到t1的其長度小于LT(t1)的通路中遇到的第一個P中的點。于是有一條從v0到t2僅經(jīng)過T中的點的通路，其長度小于LT(t1)，而由LT(t2)的定義知，LT(t2)<LT(t1),這與假設(shè)LT(t1)=min{LT(x)│x?P}矛盾。TP＝V－Tv0t1t277/81命題設(shè)T和P已知，已找出t1,使LT(t1)=min{LT(x)│x?P}。令T’=T∪

{t1}P’=P－

{t1}，并設(shè)LT’(x)表示僅經(jīng)過T’中的點從v0到x的最短通路的長。則有

LT’(x)=min{LT(x),LT(t1)+W({t1,x})}這里，若圖中{t1,x}?E,取W({t1,x})=∞。v0t1xt’v0t1xv0t1x79/81命題的證明從v0到x且不含P’中頂點的任何一條最短通路，只有兩種可能的情況：一條既不包含P’中的頂點也不包含t1的通路.此時，最短通路長仍然為LT(x)v0t1x80/81命題的證明(2)一條由v0到t1不包含P中的其它頂點，然后由t1經(jīng)過{t1,x}到x的通路。此時，最短通路長為LT(t1)+W({t1,x})

.v0t1x81/81命題證明的說明：還有一種？實際上，從v0到t1再到t’的這條通路一定不短于從v0到t’的最短通路，而由作法可知從v0到t’的最短路經(jīng)過的點全在T中，所以即使有可能產(chǎn)生一條最短路，我們也可以用一條從v0到t’的僅經(jīng)過T中點的最短通路取代，也就是說這種情況可以歸化為第一種情況考慮。從v0到t1，再到T’中某一頂點t’，由t’到x中間不經(jīng)P’中點。v0t1xt’82/81Dijkstra算法設(shè)起點是v0，終點是z。具體程序如下：開始，設(shè)T={v0}，P=V－T，對P中的每一個頂點x,令LT(x)=W({v0,x})。設(shè)t1是P中關(guān)于T有最小指標的頂點,即

LT(t1)=min{LT(x)│x?P}。若t1=z，則終止。否則，設(shè)T’=T∪

{t1}，P’=P－

{t1}。對于P’中的每一個頂點，計算它關(guān)于T’的指標：

LT’(x)=min{LT(x),LT(t1)+W({t1,x})}。把T’代為T,把P’代為P,把LT’(x)代為LT(x)，重復(fù)步驟(2)。83/81例求圖9.9中從a到z的最短通路的長acebdz147123265T={a,b}386∞T={a,b,c}

84∞abcdezT={a}