资源描述：
《《图与网络分析》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章图与网络分析§6.1图与网络的基本概念§6.2树与最小生成树§6.3最短路问题§6.4网络最大流问题§6.5最小费用最大流问题§6.6中国邮递员问题§6.7运输问题§6.8应用LINGO、MATLAB软件求解网络问题网络模型企业管理组织生产交通运输图论“七桥”难题:Euler图6.0.1图6.0.2自然界和人类社会中的许多事务之间的关系都可以用点和线连结起来的图形来描述，例如在交通运输图上，产地和销地通常用点来表示，有连线就意味着这两地可以直接到达，无连线就表示不能到达，可以研究从产地到销地的最短路径或者分析运费最小的运输方案。类似地，城市规划、电视网络、信息传递
2、等问题均可以这样用点和线连接起来的图进行模拟。我们除去这些实际问题的具体名称和含义，保留它们的共同点，便有了图的概念。§6.1图与网络的基本概念§6.1.1图及其分类定义6.1.1称二元组(V,E)为一个图，记为G=(V,E)。其中为若干个点构成的集合，点称为图G的顶点。为点与点之间的连线构成的集合，称为边。当V，E均为有限集时，G称为有限图，否则，称为无限图。一般地，若边e连结顶点u和v，则记为e=(u,v)或e=(v,u)，称u和v为e的端点，且称e与端点u和v关联，e称为u和v的关联边。若u，v之间有一条边，则称u和v相邻，若两条边有一个公共端点，则称这两条边相邻
3、。没有边与之关联的顶点称为孤立点。例6.1.1如图6.1.1，图6.1.1这里，和和相邻，和和不相邻，和不关联。顶点和的关联边有两条：和而两个端点合二为一，的称两个端点重合的边为环或自回路。这里为环。两个顶点之间多于一条边的，称称为多重边，也称为平行边。为平行边。和为图6.1.1孤立点。在图论中，常用m=
4、E
5、表示图的边数，用n=
6、V
7、图的顶点个数。若图G=(V,E)中既不含环，也不含多重边，则称之为简单图。若G中含有多重边，则称之为多重图。称这样的边为无向边，对若G中的边没有方向，应的图称为无向图。而有方向的边称为弧或有向边。在图中，用箭头表示方向。由顶点u指向顶点v
8、的弧记为a=(u,v),u称为a的始点，v称为a的终点。此时(u,v)和(v,u)不同。由点集V和弧集A构成的图记为D=(V,A)，称为有向图。图6.1.2为有向图。图6.1.2定义6.1.2每一对顶点间都有相连的无向简单图称为完全图。有n个顶点的无向完全图记为点间有且仅有一条有向边的简单图称为有向完全图。每一对顶图6.1.3（a）图6.1.3（b）图6.1.3（a）为完全图，可记为为有向完全图，图6.1.1则不是完全图。图6.1.3（b）称定义6.1.3若图G=(V,E)的顶点集V可分成两个非空子集X和Y，即使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y
9、，则称G为二部图，也称G为偶图，并记图6.1.4（a）二部图图6.1.4（b）非二部图§6.1.2顶点的次定义6.1.4以点v为端点的边数称为点v的次，记为deg(v)，简记d(v)。若则称为图G的次序列。次为1的点称为悬挂点，连结悬挂点的边称为悬挂边。称为奇点，次为偶数的点称为偶点。次为奇数的点如图6.1.1中，为悬挂点，为悬挂边。图6.1.1定理6.1.1任何图G=(V,E)中，所有顶点的次数之和等于边数的两倍，即证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的两倍。证毕。定理6.1.2任何图G=(V,E)中，奇点的
10、个数必为偶数。证明：设G中奇点与偶点的集合分别为则由定理6.1.1知由于2
11、E
12、为偶数，而也为偶数，故亦必为偶数，即奇点的个数为偶数。证毕。在有向图中，注1：以点v为起点的边数称为点v的出次，记为以点v为终点的边数称为点v的入次，记为如图6.1.2中，显然，点v的出次与入次之和就是点v的次。有向图中，所有顶点的出次之和等于所有入次之和。而且，在图6.1.2§6.1.3子图设有两个图G=(V,E)和若且对中任意一条边均有则称是G的子图，记为若是G的子图，且则称是G的生成子图.设G是一个有向图，去掉每条边的方向之后，便得到一个无向图，称该图为G的基础图。在有向图中也有环，平
13、行边，简单图和子图的概念，可参考无向图的相关概念给出。图6.1.5（a）图6.1.5（b）图6.1.1的子图图6.1.1的生成子图§6.1.4.连通图定义6.1.5设无向图G=(V,E)中，某些点与边的交替序列可以排成的形式，且序列中的每一条边的端点恰好是与它前后相邻的两个顶点，即则称序列为连接与的一条链，记为S，链长为k，即若此点边序列中没有重复的点和重复的边，链为初等链。则称此如图6.1.1中图6.1.1为一条连接的链。而为一条初等链。定义6.1.6设无向图G=(V,E)中，链S为连接与的一条链，若S的首尾两端点重合，即则称S为圈。若
