運籌學

Operations

ResearchChapter7圖與網絡GraphandNetwork1.圖的基本概念

BasicConceptsofGraph2.最小樹問題MinimumSpanningTreeProblem3.最短路問題ShortestPathProblem

4.最大流問題MaximumFlowProblem4/8/2025ACBDCBA引例：哥尼斯堡七橋問題您能從A、B、C或D任意一點出發走遍7座橋并且每座橋只走一次最后回到原出發點嗎？D4/8/2025圖Ｇ可定義為點和邊的集合，記作式中Ｖ是點的集合，Ｅ是邊的集合。注意上面定義的圖Ｇ區別于幾何學中的圖。在幾何學中，圖中點的位置、線的長度和斜率等都十分重要，而這里只關心圖中有多少點以及哪些點之間有線相連，如果給圖中的點和邊賦以具體的含義和權數，如距離、費用、容量等，把這樣的圖稱為網絡圖，記作Ｎ。圖和網絡分析的方法已廣泛應用于物理、化學、控制論、信息論、計算機科學和經濟管理等各個領域。4/8/2025v3e7e4e8e5e6e1e2e3v1v2v4v5例如圖6－1，端點，關聯邊，相鄰

若有邊e可表示為e=[vi,vj],稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關聯邊。若點vi、vj與同一邊關聯，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。例如圖6－1，v2和v4是邊e6的端點，反之邊e6是點v2、v4的關聯邊。點v2、v4相鄰；邊e6與e5、e4j相鄰。圖6－1e2可記作：4/8/2025環，多重邊，簡單圖

如果邊e的兩個端點相重，稱該邊為環。如圖６－１中邊e1為環。如果兩個點之間多于一條，稱為多重邊，如圖６－１中的e4和e5，對無環、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5

次，奇點，偶點，孤立點

與某一個點vi相關聯的邊的數目稱為點vi的次（也叫做度），記作d(vi)。圖６－１中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數的點稱作奇點，次為偶數的點稱作偶點，次為0的點稱作孤立點。圖的次一個圖的次等于各點的次之和。4/8/2025

鏈、路、回路（圈）

圖中有些點和邊的交替序列對任意vi,t－1

和vit(2≤t≤k)均相鄰，稱μ從v0到vk的鏈。如果鏈中所有的頂點v0，v1，…，vk也不相同，這樣的鏈稱初等鏈（路）。如果鏈中各邊e1,e2…,ek互不相同稱為簡單鏈。當v0與vk重合時稱為回路（圈），如果邊不重復稱為簡單回路（圈）v3e7e4e8e5e6e1e2e3v1v2v4v5圖6－1中，μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4}是一條鏈μ1中因頂點v3重復出現，不能稱作路。4/8/2025是一條鏈也是一條路。是一條回路并且是簡單回路。v3e7e4e8e5e6e1e2e3v1v2v4v5連通圖若在一個圖中，如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱該圖是不連通的。圖6－1是連通圖。μ3={v4,e7,v3,e3,v1,e2,v2,e6,v4}4/8/2025子圖、支撐子圖圖G1={V1、E1}和圖G2={V2，E2}如果稱G1是G2的一個子圖。若有則稱G1是G2的一個支撐子圖（部分圖），圖6-2（a）是圖6-1的一個子圖，圖6-2（b）是圖6-1的支撐子圖，注意支撐子圖也是子圖,子圖不一定是支撐子圖。v3e7e6e1e2e3v1v2v4v5e4v3e8e5e6v2v4v5圖6－2(a)v3e7e4e8e5e6e1e2e3v1v2v4v5圖6－2(b)4/8/2025有向圖如果圖的每條邊都有一個方向則稱為有向圖混合圖

如何圖G中部分邊有方向則稱為混合圖①②③④⑤⑥有向圖4/8/2025賦權圖設圖G＝（V，E），對G的每一條邊(vi,vj)相應的有一條數w(vi,vj)(或記為wij)，wij稱為邊(vi,vj)的權,賦有權的圖G稱為賦權圖。這里的權數可以是時間、費用、距離等，視不同背景代表不同的含義。①②③④⑤⑥910201571419256賦權圖4/8/2025網絡圖在一個有向賦權圖G中規定了一個起點（發點）和一個終點（收點），其余是中間點，這樣的圖稱為網絡。①②③④⑤⑥910201571419256⑦1130起點為v1終點為v7的一個網絡圖4/8/2025樹、支撐樹：無圈的連通圖稱為樹；若G1是G2的一個支撐子圖并且是一棵樹，則稱G1是G2的一棵支撐樹。圖6－2(a)、6－2(b)都不是樹。想一想，為什么？圖6－3(a)是一棵樹，圖6－3(b)是圖6－1的一棵支撐樹。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1圖6－1圖6－3(a)圖6－3(b)v3e2e3v2v