文档介绍：环境系统分析第 3 讲
主讲: 李明俊教授

2005-8-3
1
三、图与网络方法
1、图的概念
定义:无向图G=(V、E、φ),包含有顶点集合V,边的集合E,以及顶点与边之间的关系φ,有时无向图直接写成G=(V、E)
这样做便于将图用数学集合形式表达出来,反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方式来描述,以便进一步分析处理。
2
例:右图中,G=(V、E、φ)
其中:V={V1、V2、V3、V4}
E={e1、e2、e3、e4、e5、e6}
φ:e1=<V1、V2> e2=<V1、V4>
e3=<V2、V3> e4=<V3、V4>
e5=<V1、V3> e6=<V2、V4>
此处<Vi、Vj>表示以Vi、Vj为两端的无向边。
3
定义:有向图G=(V、E、ψ),与无向图的区别在于ψ与φ
ψ:ek=(Vi、Vj),以Vi为起点,Vj为终点.
φ:ek= <Vi、Vj > ,无始终点之说。
有向图的边带箭头,(对应于实际中的河流水流方向,管道中水流方向等)
4
2、点与边的关联关系
定义:设G=(V、E)是无向图,若顶点Vk是G的一个顶点,且不存在自身回路,则Vk点的线度是G中以Vk为端点的边数,记为d (Vk),若存在自身回路,则自身回路的顶点Vk,其线度d (Vk)也包括自身回路的边,且记两次。
5
例:左图中
d (V2)=3
d (V3)=3
d (V1)=4 (存在自身回路e3)
6
定义:对于有向图G=(V 、E 、ψ),Vk为G中一个顶点,则称以Vk为始点的有向边数为Vk点的正线度,记为d+(Vk) ,称以Vk点为终点的有向边数为Vk点为负线度,记为d-(Vk),Vk点的正线度与负线度之和称为顶点Vk的线度d (Vk)。
7
例:右图中
d+ (V1)=1
d- (V1)=1
d (V1)=2
特别对V3,有:
d+ (V3)=2 ,d- (V3)=2 d (V3)=4
自身回路以V3为始点,又以V3为终点。
8
3、图的矩阵表示法
矩阵是研究图论的一种有力工具,特别是利用计算机来研究有关图的算法时,首先遇到的问题是如何让计算机来识图,这不得不借助矩阵。
我们暂且不讨论两顶点之间存在平行的两条边的情况。
(1)邻接矩阵
定义:对于有向图G=(V、E),构造矩阵
A=(aij)nxn
9
其中:n为图G的顶点数,称矩阵A为图G的邻接矩阵。
10