由于图的结构的直观性，运用图论的方法更有助 于我们分析问题、描述问题、解决问题 .
第十章 网络规划
§0 图的基本概念 §1 最小生成树问题 §2 最短路问题 §3 最大流问题 §4 中国邮递员问题
第十章 网络规划
该问题由Euler在
§0 图的基本概念 1736年解决
Example 1 七桥问题
18世纪的德国有个哥尼斯堡城，在流贯全城的普
回路： 起点与终点重合的初等链；
§0 图的基本概念
赋连(通加图)权：图图：G图中G任的意每两条点边ue和= (vvi存，在vj)一与条一链实；数 割边w(：e) =若w去ij 对掉应边. ew将(e使) =连w通ij 称图为G边不e再的连权通.，则称 e
割集：边为的G集的合割，边从；连通图 G 中移去这些边，则 G 线度不：连与通顶，点且v 关不联存的在边这数些(边环的算真两子次集)称使为图v不的连线通度.;
其中
v1 e2 v4
1 aij 0
e1
e3
e8
e4 v3 e7 e5
vi与e
关联
j
则称矩阵 A 是图 G
否则
的关联矩阵 .
e1 e2 e3 e4 e5 e6 e7 e8
v2
v1 1 1 1 0 0 0 0 0
e6
v2
1
0
0
0
0
1
0
1
A
v3
0
0
1
1
0
0
1
1
v5
v4 0 1 0 1 1 0 0 0
雷尔则河七两桥岸问和题河就中成两为个无岛向之图间中架是设否了存七在座通桥过，每把一河边的
两一岸次和且两仅岛一连次接的起路来（，即能一否笔有画这）样问一题种. 走法，它通过
每座桥一次且仅一次 .
C
A
D
B
§0 图的基本概念
人状态转狼移问羊题 菜
Example 2 人、狼、羊、菜渡河问题 F W G C
e = (u，v), 顶点 u 及 v
并称 u 与 v 关联，顶点
为u 与无顶向点边的v 相两e邻个6 端.e2 点与；同e边一3 个ee4 与顶
点关联的若干条边称为是相邻的 . v4 e5
v3
自环： 两个端点重合为一个顶点的边；
Note : 是图
平行边： 关联于同一对顶点的两条边；
简单图： 没有自环和平行边的图；
v5 0 0 0 0 1 1 1 0
v5§0 图的基本概念
Go back
邻接矩阵： 对无向图 G = (V, E)，其中 V =对{称v矩1,阵…,vn },
构造 n×n 矩阵 B =( bij ) n×n
其中
v1 e2 v4
1 bij 0
e1
e3
e8
e4 v3 e7 e5
(vi , vj ) E 否则
e1
v1
e2
v2
完备图：任两个顶点之间恰有一条边相关联；
子图：设 G = (V, E)，G1 = (V1,
E1 E, 则称图 G1 为图
EG1)若的都简e子是记=图(为图vev43；i ，e, ivj j且)e4V1e6
Ve,5
v3
第十章 网络规划
生成(支撑)子图： 若图 G1 是图 G 的子图，且 V1 = V， 则称 G1 是 G 的生成子图； 链（道路）：图 G 中一个由顶点和边交错而成的非空 有限序列：W = v0e1v1e2…ekvk，ei ∈E，i = 1,2,…,k， vj ∈V，j =0,1,2,…,k, 且 ei = (vi-1，vi), 则称 W 是 G的一 条链（道路）； v0、vk 称为 W 的起终点，k为路长； 初等链： 各顶点相异的链； 圈： 起点与终点重合的链；
一F个WG摆C 渡人希FW望G 用一F条WC小船把FG一C 只狼、F一G 头羊和
一篮白菜 从一条河的南岸渡到北岸去，而船小只能容
纳人、狼、羊、菜中的两个，决不能在无人看守的情
况下，留下狼和羊在一起或羊和白菜在一起，应怎样
渡河才能O将狼、羊C、白菜都G运过河？W
WC
考虑渡河过程中河南岸的变化情况，最初的状态 是人、则狼渡、河羊问、题菜归，结最为终寻状找态从成顶空点状态“，FW中G间C的” 到状顶态 为点人“、O狼”、的羊路、线菜. 的不同组合 . 共有 16 种状态， 但有 6 种状态是不允许的，如狼、羊、菜等.
的集合的映射，称为关联函数 .
无向图： 在图 G = (V，E) 中， 与 V 中的无序偶对应的边 e , 称 为图 G 的无向边，每条边都是 无向边的图，称为无向图 .
v1
e1
v2
e3 e2 e4
e8
e6 v3 e7
v4
e5
v5
§0 图的基本概念
E 中任一条边 e 若连接顶点 u 和 v ， v1 则记e1 为 v2
记记为为Sd, S(v ) .S 为d一(v个2) 连= 3通，分d(支v3)的=顶4 点集.
有向ve图有12的：向ee边43 边在eev1的3,图e称8图eG7为，=e图称v62(V为G，有的E向)有中图向，边. 与（记V弧为ve中12）G的ee，43=有(每Ｖev序13条，e偶8边eＡ7对都)e应v6是2
则称矩阵 B 是图 G 的邻接矩阵 .
组合优化理论
Combinatorial Optimization Theory
第十章 网络规划
第十章 网络规划
我们生活在一个网络世界中，从某种意义上说现 代社会是一个由计算机信息网络、电话通讯网络、运 输服网务络网规络划、是能运源筹和学物（质组分合派优网化络）等的各一种个网经络典所又组重成 的要复分杂支的，网所络研系究统的.问网题络涉规及划经就济是管研理究、如工何业有工效程地、计交 划通运、输管、理计和算控机制科这学个与网信络息系技统术，、使通之讯发与挥网最络大技的术社等会 和经济效益 . 诸多领域 .
对有v4向图有e5类似无v向5 图的概念A，rc如 dv+4(vi)，de-5(vi) . v5
第十章 网络规划
图的矩阵表示：
关联矩阵： 对无向图 G = (V, E)，其中 V = { v1, …,vn },
E = { e1, e2,…,em } . 构造 n×m 矩阵 A =( aij ) n×m
第十章 网络规划
图简关记系为
Definition
Graph Vertex GE=Rd（eglVaet，ionE）
பைடு நூலகம்
图： 有序三元组 G = ( V，E，R ) 称为一个图，其中
① V = { v1，v2,…，vn }是有穷非空集，称为顶点集； ② E 称为边集，其中的元素叫做边；
③ R 是从边集 E 到 V 中的有序或无序的元素偶对应