资源描述：
《(计算机软件及应用)网络分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章网络分析模型5.1图论基础5.2网络分析模型5.3最短路径分析5.4最佳路径分析5.5资源分配5.6流分析5.1图论基础（1）一、图1、图的概念图:一个图G是指一个有序三元组（V（G），E（G），ΨG），其中V（G）是非空的顶点集，E（G）是边集，ΨG是关连函数，它使G的每条边对应于G的无序顶点对（不必相异）。边:E中的每个顶点对（u,v）称为G的边，记为e=（u,v）或简记为e=uv，称u，v是边e的端点，且称u和v是邻接的顶点。孤立点:没有边相邻的顶点。一条边的端点称为与这条边关联，若两条不同的边与一个公共的端点关联，则称这两条边是邻接
2、的。5.1图论基础（2）若连结两个顶点有不止一条边，这些边称为多重边。端点重合为一点的边称为环。简单图:没有环也没有多重边的图。有限图：一个图中顶点集及边集都是有限集。（u,v）空图：没有边的图，记为Φ。（p,q）图：一个有p个顶点和q条边的图。完全图：每一个不同的顶点均有边相连的简单图。有n个顶点的完全图记作Kn。子图：所有的顶点和边都属于G的图称为G的子图。生成子图：含有G的所有顶点的子图称为G的生成子图。5.1图论基础（3）顶点的度:G的顶点v的度d(v)是指G中与v关联的边的数目，每个环算作两条边。设G是一个（p,q）图，那么G的各个顶点
3、度的和是边数的二倍，即正则图：如果图G的所有顶点的度均相等，则称为正则的。顶点的度均为r的正则图，称为r度正则的。一个0度正则的图根本没有边。只有一条边两个顶点的图是1度正则的。完全图是正则的。2、路与连通性路径:G的一条途径是指一个有限非空序列μ=v0e1v1e2v2…envn,它的项交替地为顶点和边，使得对1≤i≤n,ei的端点是vi-1和vi。称μ是从v0到vn的一条途径。这条路径连接v0和vn，也可记作v0v1…vn-1vn，有时也称它为（v0,vn）路径。如果v0=vn，它称为闭合的，否则称为开的。路径中边的数目称为路径的长。5.1图论
4、基础（4）链:设μ=v0e1v1e2v2…envn是路径，若路径μ的边e1,e2,…,en均不同，则μ称为链。路:若路径的所有顶点都不同(从而所有的边必然不同)，它称为路。用Pn记由一条有n个顶点的路构成的一个图。回路:一条闭合的路，也称为圈。用Ｃn记由一条有n个顶点的回路构成的一个图。若n为奇数，则Ｃn称为奇回路，若n为偶数，则Ｃn称为偶回路。连通：如果在G中存在(u,v)路。则G的两个顶点u和v称为连通的。连通图：一个图的每一对顶点都有一条路连接。连通支：G的一个最大的连通子图称为一个连通支。简称为G的一个支。顶点距离：若在G中顶点u和v是连
5、通的，则u和v间的最短(u,v)路的长称为u和v间的距离，记为d(u,v);若不存在连接u和v的路，则记d(u,v)=∞。5.1图论基础（5）3、图的运算设G1和G2是没有孤立点的图。并：由G1和G2中的所有的边组成的图，记作。交：由G1和G2中的公共边组成的图，记作。差：由G1中去掉G2的边所得到的图称为G1和G2的差，记作。环和：在G1和G2的并中去掉G1和G2的交得到的图称为G1和G2的环和，记作。环和运算满足交换律和结合律：5.1图论基础（6）二、树1、基本概念树:一个连通的无回路的图。林:每个支都是树的分离图称为林。定理2.1：设T是一
6、个（p,q）图，若Ｔ是一棵树，则q=p-1。定理2.2：设T是一棵树。若在T中的任何两个不邻接的顶点连一条边e，则Ｔ＋e恰有一条回路。定理2.３：设Ｇ是一个（p,q）图，若Ｇ是连通的，且q=p-1，则Ｇ是一棵树。割边：如果去掉图的一条边后，剩下的图的支比原图增加，则称这样的边为割边，或称为桥。5.1图论基础（7）割边：如果去掉图的一条边后，剩下的图的支比原图增加，则称这样的边为割边，或称为桥。记W(G)为图G不连通子图的数目，则G的割边是指使得W(G-e)>W(G)的边e。5.1图论基础（8）2、生成树生成树:若T是连通图G的一个生成子图而且是一
7、棵树,则称T是G的一棵生成树（支撑树）。T中的边称为树枝，属于G而不属于T中的边称为弦。生成林:若G为分离图，则称T为生成林。定理2.4：图G是生成树的充要条件为G连通。定理2.5：T是连通（p,q）图Ｇ的一棵生成树的充要条件是T为G的有p-1条边的连通生成子图。求一个连通图G的生成树的主要方法有：避回路法：任取图G的一条边e1，再取一条边e2，e2和e1不构成回路；然后再取一条边e3，e3和e1e2不构成回路。如此下去，最后得到的不含回路的连通生成子图就是G的一棵生成树。破回路法：在G中任取一回路，去掉其中的一条边，然后取一条回路，再去掉这个回
8、路中的一条边。如此继续下去，最后得到的连通的无回路的生成子图就是G的一棵生成树。5.1图论基础（9）三、最短路径和最小生成树1、最短路径
