第五章 图与网络分析
5-1.内 容 框 架 与 图 的 基 本 概 念
内容框架
一,图的基本概念 （讨论思路 ）
G=（ V,E）
子图
矩阵表示 含元素的个数
点的次
边
特殊的图
点边关系
简
单
图
多
重
图
空
图
连通图
树部分树
空 图
G=(V,E)
矩阵表示
A 邻接矩阵
B 关联矩阵
C 割集矩阵
L 圈矩阵
M 可达矩阵
D 距离矩阵
边 e=[u,v]
端点
重
合
环
自
回
路
多重边
平行边
简单图
多重图
含
点的次
0 1 奇数 偶数子图
真
子
图
部
分
图
导
出
子
图
孤
立
点
悬
挂
点
奇
点
偶
点
悬挂边
顶点数 p 边数 q
点边关系
各种链的概念
点边关系真
子
图
部
分
图
导
出
子
图
各种链的概念
?
?
?
?
?
?
?
?
?
?
?
点）初等链（无重边、无重
简单链（无重边）
初等回路
简单回路
路）链、开链、闭链（即回
点边交替序列序列
各种链的概念
通路
树
(6个等价定义 )
连通图
部分树
?
?
?
?
?
弱连通（半道路连接）
单侧连通
强连通
有
向
、
无
向
例 5-1：子图 基础图 (母图 )
真子图
部分图
导出子图
路 (通路 )
初等路
初等回路
例 5-2 链、路、树
4528572111 vevevevevQ ?
44322112 vevevevQ ?
1956452113 vevevevevQ ?
简单链
初等链
初等圈
树
两个主要定理
定理 1 图 G中，所有顶点的次的和等于所有
边数的 2倍。即
定理 2 在任一图中，奇点的个数必为偶数。
证明要点：
qvd
Vv
2)( ??
?
?????
??? VvVvVv
vdvdvd )()()(
21
（ V1,V2分别是图 G中次为奇数和偶数的顶点集合）
定理,(树的六个等价定义 )
& 无圈的连通图；
& 无圈,q=p-1;
& 连通,q=p-1;
& 无圈，但增加一条边，可得到一个且仅一
个圈；
& 连通，但舍弃一条边，图便不连通；
& 每一对顶点之间有一条且仅有一条初等链；
二,图论在网络分析中的应用
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
中心、重心
最小费用最大流
结果分析？
步骤？
求解原理？
使用条件？
理解各种算法
海斯算法
算法）列表法（
氏标号法
最短路问题
最大流问题（标号法）
最短树问题
应用
网络
赋权图
权
有向图
弧
网络有关概念
F o r d
D
（ 3） 权 —— 指与边或弧有关的数量指标。根据实
际背景可赋予不同含义，如距离、时间、
费用、容量等。
1．网络
（ 1） 弧 —— 点与点之间有方向的连线。
指从 ；
),( ji vva ? ji vv ?
（ 5） 网络 —— 指定了 起点、终点和中间点 的 连通
的 赋权有向图 。包括无向网络、
有向网络、混合网络。
),( EVG ?
（ 4） 赋权图 — 图 连同边上的权总体。),( EVG ?
),( AVD ?
（ 2） 有向图 —— 由点集 v和弧集 A组成的图
2．图论在网络分析中的应用
? 最短路问题
? 最短树问题
? 最大流问题
? 最小费用最大流问题
? 中心与重心问题
……