第五章 图与网络分析
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.图论在网络分析中的应用
? 最短路问题
? 最短树问题
? 最大流问题
? 最小费用最大流问题
? 中心与重心问题
……
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.图论在网络分析中的应用
? 最短路问题
? 最短树问题
? 最大流问题
? 最小费用最大流问题
? 中心与重心问题
……