案例ab鋼鐵的配礦問題教學(xué)用教案

2023/5/17管理運籌學(xué)課程組391第七章圖與網(wǎng)絡(luò)分析1.圖的基本概念2.最小樹問題3.最短路問題4.最大流問題5.最小費用最大流問題本章內(nèi)容2023/5/17管理運籌學(xué)課程組392例：七橋問題ABCD問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。問題：能否從某一點開始一筆畫出這個圖形，最后回到原點，而不重復(fù)。2023/5/17管理運籌學(xué)課程組393例：中國郵路問題

一個郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，最后返回郵局。郵遞員都會本能地以盡可能少的行程完成送信任務(wù)。問題：他如何走？點：路口；邊：兩路口之間道路，第i條道路長ei。問題：求一個圈，過每邊至少一次，并使圈的長度最短。2023/5/17管理運籌學(xué)課程組394例：四色猜想

能否用四種顏色給地圖染色，使相鄰的國家有不同的顏色。點：國家；邊：兩個國家有公共邊界。問題：能否用四種顏色給平面圖的點染色，使有公共邊的點有不同的顏色。2023/5/17管理運籌學(xué)課程組395

有二十個頂點標(biāo)以二十個城市的名字，要求游戲者找一條從某一城市出發(fā)的路線，它經(jīng)過每一個城市恰好一次，并且最后回到出發(fā)點。點：城市邊：城市之間的道路問題：游戲者怎么走才能恰好每個城市走一次，而且不重復(fù)？如圖：例：Hamilton2023/5/17管理運籌學(xué)課程組396

第一節(jié)圖的基本概念點：研究對象（陸地、路口、國家、球隊）；點間連線：對象之間的特定關(guān)系（陸地間有橋、路口之間道路、兩國邊界、兩球隊比賽及結(jié)果)。對稱關(guān)系：橋、道路、邊界；用不帶箭頭的連線表示，稱為邊。非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。圖：點及邊（或?。┙M成。2023/5/17管理運籌學(xué)課程組397例：有甲、乙、丙、丁、戊五個球隊，各隊之間比賽情況如表：2023/5/17管理運籌學(xué)課程組398點：球隊；連線：兩個球隊之間比賽過，如甲勝乙，用

v1v2表示。v1v2v3v4v52023/5/17管理運籌學(xué)課程組399一、圖的定義定義1：一個圖，是由非空集合V(G)={vi}和V(G)中元素的有序?qū)Γɑ驘o序?qū)Γ┑募螮(G)={ek}

所組成的二元組（V(G)，E(G)）所構(gòu)成。記為

G=（V(G)，E(G)）簡記G=（V，E）其中V={vi}稱為點集，vi為點。

E={ek}稱為邊集，ek為邊（或弧）。

當(dāng)V，E為有限集時，稱G為有限圖。否則稱為無限圖。2023/5/17管理運籌學(xué)課程組3910無向圖：由點及邊構(gòu)成，邊[vi，vj]有向圖：由點及弧構(gòu)成，?。╲i，vj）

圖G中點集V的頂點個數(shù)，記為p(G)，邊數(shù)記為q(G),簡記p，q。2023/5/17管理運籌學(xué)課程組39111.簡單圖與多重圖

某條邊兩個端點相同，稱這條邊為環(huán)。若兩點之間有多于一條的邊，稱這些邊為多重邊。無環(huán)、無多重邊的圖稱為簡單圖。多重圖：無環(huán)、但允許有多重邊。v1e1e2e3v2v3e5e4v4二、圖論中常用術(shù)語2023/5/17管理運籌學(xué)課程組39122.相鄰與關(guān)聯(lián)

若邊e=[u，v]∈E，稱u，v是e的端點，也稱u，v是相鄰的。稱e是點u（及點v）的關(guān)聯(lián)邊。

若兩條邊有一個公共的端點，則稱這兩條邊相鄰接。

vivjevi，vj相鄰

e

與vi，vj關(guān)聯(lián)vie1vjvke2

點與邊關(guān)聯(lián)點與點相鄰邊與邊相鄰接2023/5/17管理運籌學(xué)課程組3913定理1圖G=（V，E）中，所有點的次之和為邊數(shù)的兩倍，即3.奇點與偶點次為奇數(shù)的點稱為奇點，否則稱為偶點。定理2任一圖中奇點的個數(shù)為偶數(shù)。2023/5/17管理運籌學(xué)課程組3914證明：設(shè)v0和ve分別是G中的奇點和偶點的集合，由定理1，有因

是偶數(shù)，也是偶數(shù)，故必為偶數(shù)。即在一個圖中奇點的個數(shù)必為偶數(shù)。2023/5/17管理運籌學(xué)課程組39154.次與懸掛點、孤立點圖G中以點v為端點的邊的數(shù)目，稱為v在G中的次，記為d（v）。d(v1)=2d(v2)=3d(v3)=4d(v4)=1

次為1的點為懸掛點，懸掛點的關(guān)聯(lián)邊稱為懸掛邊，次為零的點稱為孤立點。v1e1e2e3v2v3e5e4v42023/5/17管理運籌學(xué)課程組39165.鏈與圈

給定一個圖G=（V，E），G中的一個點、邊交錯序列（vi1，ei1，vi2，ei2，…，vik-1，eik-1，vik），如果滿足eit=[vit，vit+1]（t=1，2，…，k-1），則稱為一條聯(lián)接vi1和vik的鏈，記為=（vi1，vi2，…，vik）。

鏈（vi1，vi2，…，vik）中，若vi1=vik

，稱之為一個圈，記為C=（vi1，vi2，…，vik-1，vi1

）。初等鏈：鏈中點都不同。簡單鏈：鏈中邊都不同。（邊能否相同？）（點能否相同？）2023/5/17管理運籌學(xué)課程組3917v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9簡單鏈：1=（v2，v1，v3，v6，v4，v3，v5）初等鏈：2=（v2，v1，v3，v5）簡單圈：C1=（v1，v2，v4，v3，v5，v6，v3，v1）初等圈：C2=（v1，v2，v4，v6，v5，v3，v1）

有向圖中，不考慮弧的方向，有類似鏈（圈）的定義。當(dāng)鏈（圈）上弧的方向一致時，稱為路（回路）。2023/5/17管理運籌學(xué)課程組39183.連通圖

給定圖G=（V，E），任何兩點間至少有一條鏈，則稱G是連通圖，否則為不連通圖。

若G是不連通的，它的每個連通部分稱為G的連通分圖。三、一些特殊圖類

1.平凡圖節(jié)點數(shù)n=1,邊數(shù)m=0的圖。2.零圖邊數(shù)m=0的圖。2023/5/17管理運籌學(xué)課程組39195.完備圖無向圖的完備圖：任何兩點之間有一條邊；有向圖的完備圖：任何兩點u與v之間有兩條有向邊（u，v）及（v，u）?；緢D：把有向圖的每條邊除去方向得到的無向圖。

若V(G)=X∪Y,X∩Y=Ф，X、Y中的任兩頂點不相鄰，則G稱為二分圖，記為（S,X,Y）。4.樹無圈連通圖。6.二分圖2023/5/17管理運籌學(xué)課程組39209.網(wǎng)絡(luò)

若對圖G=（V，E）中每條邊[vi，vj]賦予一個數(shù)wij，則稱wij為邊[vi，vj]的權(quán)，并稱圖G為網(wǎng)絡(luò)（或賦權(quán)圖）。網(wǎng)絡(luò)：無向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)。7.完全二分圖

若V(G)=(S,X,Y),如果任意μ∈X、ν∈Y、，都有[μ，ν]∈E，則稱G是完全的二分圖。8.正則圖

如果G中每個點的次數(shù)都相同，則G叫做正則圖。2023/5/17管理運籌學(xué)課程組39211.子圖與支撐子圖定義2給定圖G=（V，E），若圖G1=（V1，E1），其中V1V，E1={uv|uv∈E，u，v∈v’}，則稱G1是G的子圖。定義3給定圖G=（V，E），若圖G1=（V，E1），其中E1E，則稱G1是G的一個支撐子圖。點全部保留（a）（b）子圖（c）支撐子圖四、圖的運算2023/5/17管理運籌學(xué)課程組39222.圖的收縮運算

設(shè)圖G=(V,E)，V1V,在G中收縮V1是指在圖G中，在V1中的點重為一個點，G與V1中的點相關(guān)聯(lián)的邊變?yōu)榕c這個新點相關(guān)聯(lián)的邊，稱這樣的圖為關(guān)于V1收縮，記為GoV1。2023/5/17管理運籌學(xué)課程組39233.割集

給定圖G=（V，E），點的子集S

V，T

V，定義G中邊的集合[S，T]G={uv|u∈s，v∈T}為一個割集。若X={v1}若X∈V是V的真子集，常記為v6v2v3v4v5v1v1v2v3v4v5v6若X={v1，v2}，2023/5/17管理運籌學(xué)課程組39244.圖的同構(gòu)定義4設(shè)圖G=（V，E）與G1=（V1，E1），若它們的點之間存在一一對應(yīng)，并且保持同樣的相鄰關(guān)系，則稱G與G1同構(gòu)。記為G≌G1。v1v2v3v4abcdv1v2v3v4abcd?2023/5/17管理運籌學(xué)課程組3925(a)(b)圖(a)和(b)就為同構(gòu)2023/5/17管理運籌學(xué)課程組3926五、圖的矩陣表示

圖的矩陣表示方法有：鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)矩陣、權(quán)矩陣等。2023/5/17管理運籌學(xué)課程組39271.鄰接矩陣

鄰接矩陣用于描述兩個頂點之間是否有邊（弧）相連。對于有n個頂點的無向圖G=(V,E)

，定義鄰接矩陣(B=bij)n×n

。其中，對于有幾個頂點的有向圖G=(V,A)

，定義鄰接矩陣(B=bij)n×n

。其中，2023/5/17管理運籌學(xué)課程組3928例題1已知無向圖所示，求其鄰接矩陣。v5v3v1v2v4v6則顯然，無向圖的鄰接矩陣是關(guān)于對角線的對稱矩陣。

2023/5/17管理運籌學(xué)課程組3929例2已知：圖所示，求其鄰接矩陣。v2v5v3v1v4v6則：v1v2v3v4v5v6v1011000v2001110v3000100v4000011v5001001v60000002023/5/17管理運籌學(xué)課程組3930其鄰接矩陣為：

v4v5v2v1v3當(dāng)G為無向圖時，鄰接矩陣為對稱矩陣。2023/5/17管理運籌學(xué)課程組3931在有向圖中可達(dá)矩陣用于描述兩點之間是否有路相連,即R=(rij)n×n,其中，2.可達(dá)矩陣

例題3求例題2的可達(dá)矩陣則v1v2v3v4v5v6v1111111v2011111v3001111v4000111v5000011v60000012023/5/17管理運籌學(xué)課程組39323.關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣也稱頂點—邊關(guān)聯(lián)矩陣。設(shè)有向圖G=(V,A)，其中rij=V=｛v1,v2,v3…vn｝，

，則關(guān)聯(lián)矩陣可定義為M=(mij)n×m其中：2023/5/17管理運籌學(xué)課程組3933例題4求下圖的關(guān)聯(lián)矩陣v4v2v1v3a