圖的連通

無向圖

有向圖圖的割集

概念

主要結(jié)論13無向圖的路135426圖G中路：一個(gè)點(diǎn)和邊交替序列(ni,eij,nj,…,nk,ekl,nl)，簡(jiǎn)單路：邊不重的路初級(jí)路：點(diǎn)不重的路回路：在G中，一條至少包含一個(gè)邊并且ni=nl的{ni,nl}路簡(jiǎn)單回路：邊不重的回路初級(jí)回路：點(diǎn)不重的回路14連通性點(diǎn)i和j點(diǎn)是連通的：G中存在一條（i，j）路G是連通的：G中任意兩點(diǎn)都是連通的連通分支：G的極大連通子圖命題6.2.1設(shè)G有p個(gè)連通分支，則G的鄰接矩陣可以表示成分塊矩陣15有向路134256有向圖G中的一條有向路：個(gè)點(diǎn)和弧的交錯(cuò)序列(ni,aij,nj,…,nk,akl,nl)，記為(ni,nl)有向路簡(jiǎn)單有向路：弧不重的有向路初級(jí)有向路：點(diǎn)不重的有向路有向回路：至少包含一條弧且ni=nj的(ni,nj)有向路簡(jiǎn)單有向回路：弧不重的有向回路初級(jí)有向回路：點(diǎn)不重的有向回路16點(diǎn)i和點(diǎn)j是強(qiáng)連通的：G中存在一條(i,j)有向路，也存在一條(j,i)有向路G是強(qiáng)連通的：G中任意兩點(diǎn)都是強(qiáng)連通的G的強(qiáng)連通分支：G的極大連通子圖命題6.2.2設(shè)G有p個(gè)強(qiáng)連通分支，則G的鄰接矩陣可以表示成如下形式：強(qiáng)連通性17割集18割集的性質(zhì)19樹與支撐樹樹及其基本性質(zhì)

概念及符號(hào)

基本性質(zhì)支撐樹及其基本性質(zhì)

概念及符號(hào)

基本性質(zhì)20概念及符號(hào)21樹的基本性質(zhì)22概念及符號(hào)23支撐樹的基本性質(zhì)24最小樹最小樹及其性質(zhì)求最小樹的Kruskal算法

算法步驟

算例

算法復(fù)雜性Dijkstra算法

算法步驟

算例

算法復(fù)雜性25最小支撐樹26算法步驟27算例

28計(jì)算的迭代過程29算法復(fù)雜性30算法步驟31算例32計(jì)算的迭代過程

33算法復(fù)雜性34最短有向路最短有向路方程求最短有向路的Dijkstral算法

算法步驟

算例

算法復(fù)雜性35最短有向路方程36算法步驟37算例38計(jì)算的迭代過程

39算法復(fù)雜性40最大流最大流最小割定理

基本概念

主要結(jié)論最大流算法

算法步驟

算例

算法復(fù)雜性41基本概念42主要定理43算法步驟44算例45計(jì)算的迭代過程

46算法復(fù)雜性47最小費(fèi)用流最小費(fèi)用流算法

規(guī)劃形式

算法步驟

算例

算法復(fù)雜性最特殊的最小費(fèi)用流－－運(yùn)輸問題

規(guī)劃形式

算法步驟

算例

48問題49線性規(guī)劃形式50對(duì)偶規(guī)劃51算法步驟

52算例53計(jì)算的迭代過程（1）stabstabstab1，2，03,4,01,2,0

3,1,01,2,0stabstab(+s,2)(+a,2)stab(+s,2)54計(jì)算的迭代過程（2）stabstabstab(+s,2)stab(+a,2)(+b,2)stab(-b,1)(+s,1)stab1,2,23,4,01,2,23,1,01,2,255計(jì)算的迭代過程（3）stabstabstab(-b,1)(+s,1)(+a,1)56算法復(fù)雜性

57運(yùn)輸問題58對(duì)偶規(guī)劃59算法步驟60算例求如圖所示運(yùn)輸問題的最優(yōu)解1231234-45-20-30-30355040

8

69991213714916561迭代過程213123415

2030201030

初始原可行解

62續(xù)（1）213123486121014對(duì)偶解63w

w8

-6-10-29809-12513-7511429-116-5-486121u

V64續(xù)（2）15-

2030+20-10302131234調(diào)整原始可行解65續(xù)（3）213123403666101對(duì)偶解668

26-10-9909-12313-7531429-316-5-66610-1

67續(xù)（4）20-4515+510-302131234調(diào)整原始可行解68續(xù)（5）102131234033662對(duì)偶解69w

w8

26-10-9709-12313-7231459-1635-366102u

V70最大對(duì)集二分圖對(duì)集

基本概念

主要定理二分圖的最大基數(shù)對(duì)集

基本思想

算法步驟

算例

算法復(fù)雜性二分圖的最大權(quán)對(duì)集－－分派問題

規(guī)劃形式

算法步驟

算例71基本概念72主要定理73基本思想74算法步驟75算例求下圖a所示的二分圖G的最大基數(shù)對(duì)集，若初始解如下圖b所示1234567A98a1234567A98b76迭代過程（1）1234567A9831333標(biāo)號(hào)1234567A98333517810標(biāo)號(hào)1234567A98增廣路1234567A98增廣路77迭代過程（2）1234567A981257108標(biāo)號(hào)1234567A98增廣路78算法復(fù)雜性79分派問題80對(duì)偶規(guī)劃81算法步驟8283算例1234567812322132423求如圖所示的二分網(wǎng)絡(luò)中的最大權(quán)對(duì)集84計(jì)算的迭代過程（1）

=4

=1

=112345678

4

4

4

4

0

0

0

0

2

1

3

1

2

2

3

2

標(biāo)號(hào)1234567812345678

4

4

4

4

0

0

0

0

2

4

2

4

1

0

2

1

標(biāo)號(hào)

標(biāo)號(hào)

標(biāo)號(hào)

增廣路85計(jì)算的迭代過程（2）12345678

3

3

3

4

0

0

0

0

1

3

4

3

2

0

2

1

標(biāo)號(hào)1234567812345678

3

3

3