2020年6月20日星期六 Page 10 of 13
设图G＝（V，E），对G的每一条边(vi,vj)相应的有一条数w (vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为赋权图。
§7.1 图的基本概念 Basic Concepts of Graph
Ch7 Graph and Network
2020年6月20日星期六 Page 8 of 13
子图、支撑子图 图G1={V1、E1}和图G2={V2，E2}如果
V1 V2和E1 E2 称G1是G2的一个子图。若 有 V1＝V2，E1 E2 则称 G1是G2的一个支撑 子图（部分图），图6-2（a）是图 6-1的一
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
图6－1中， μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4}是一条链μ1中 因顶点v3重复出现，不能称作路。
§7.1 图的基本概念 Basic Concepts of Graph
2＝v5, e8, v3, e7 , v4
§7.1 图的基本概念 Basic Concepts of Graph
Ch7 Graph and Network
2020年6月20日星期六 Page 2 of 13
引例：哥尼斯堡七桥问题
D
您能从A、B、C或D任意一点出发
走遍7座桥并且每座桥只走一次最
后回到原出发点吗？
A
C
B
A
D C
B
§7.1 图的基本概念 Basic Concepts of Graph
一个图的次等于各点的次之和。
Ch7 Graph and Network
2020年6月20日星期六 Page 5 of 13
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
§7.1 图的基本概念 Basic Concepts of Graph
Ch7 Graph and Network
2020年6月20日星期六 Page 6 of 13
个子图，图6-2（b）是图 6-1的支撑子图， 注意支撑子图也是子图,子图不一定是支撑 e1
e1
e2 e4 v1 e3
v2
e5
v3
e6
e7
e8
v4
v5
子图。 v2
e4 e5
v3 v2
e2 v1 e3 v3
e6
e8
e6
e7
v4
v5
图6－2(a)
v4 图6－2(b) v5
有向图
§7.1 图的基本概念 Basic Concepts of Graph
等，把这样的图称为网络图，记作Ｎ。图和网络分析的方法已广泛
应用于物理、化学、控制论、信息论、计算机科学和经济管理等各 个领域。
§7.1 图的基本概念 Basic Concepts of Graph
Ch7 Graph and Network
2020年6月20日星期六 Page 4 of 13
例如图6－1，
是一条链也是一条路。 μ3={v4,e7,v3,e3,v1,e2,v2,e6,v4} 是一条回路并且是简单回路。
连通图
Ch7 Graph and Network
2020年6月20日星期六 Page 7 of 13
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
若在一个图中，如果每一对顶点之间至少存在一条链 ，称这样的图为连通图，否则称该图是不连通的。图6 －1是连通图。
v4
v5
ቤተ መጻሕፍቲ ባይዱ
边ei和ej具有公共的端点，称边ei和ej相邻。
图6－1
例如图6－1，
v2和v4是边e6的端点，反之边e6是点v2、v4的 关联边。点v2、v4相邻；边e6与e5、 e4j相邻。
§7.1 图的基本概念 Basic Concepts of Graph
环，多重边，简单图 如果边e的两个端点相重，称该边为
V v1, v2, , v5, E e1, e2, , e8
e2可记作： e2 [v1, v2 ]
e1
e2 e4 v1 e3
v2
v3
e5
端点，关联边，相邻
e6
若有边e可表示为e=[vi,vj],称vi和vj是边e
e7
e8
的端点，反之称边e为点vi或vj的关联边。若 点vi、vj与同一边关联，称点vi和vj相邻；若
Ch7 Graph and Network
2020年6月20日星期六 Page 9 of 13
如果图的每条边都有一个方向则称为有向图
混合图 如何图G中部分边有方向则称为混合图
② ⑤
④ ①
⑥ ③
有向图
赋权图
§7.1 图的基本概念 Basic Concepts of Graph
Ch7 Graph and Network
运筹学
Operations Research
Chapter 7 图与网络
Graph and Network
1. 图的基本概念 Basic Concepts of Graph 2. 最小树问题 Minimum Spanning Tree Problem 3. 最短路问题 Shortest Path Problem 4. 最大流问题 Maximum Flow Problem
链、路、回路（圈）
图中有些点和边的交替序列
v0 , e1, v1, , ek , vk
对任意vi,t－1 和vit(2≤t≤k)均相邻，称μ从v0到vk 的链。如果链中所有的顶点v0，v1，…，vk 也不相同，这样的链称初等链（路）。如果
链中各边e1,e2…,ek互不相同称为简单链。当 v0与vk重合时称为回路（圈），如果边不重 复称为简单回路（圈）
环。如图６－１中边e1为环。如果两个点 之间多于一条，称为多重边，如图６－１ 中的e4和e5，对无环、无多重边的图称作 简单图。
次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为
点vi的次（也叫做度），记作d(vi)。图６ －１中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇 数的点称作奇点，次为偶数的点称作偶 点，次为0的点称作孤立点。 图的次
Ch7 Graph and Network
2020年6月20日星期六 Page 3 of 13
图Ｇ可 定义为点和边的集合，记作
G V , E
其中V
式中Ｖ是点的集合，Ｅ是边的集合。注意上面定义的图Ｇ区别
于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等 都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连， 如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量