运筹学图与网络分析.ppt

该【运筹学图与网络分析 】是由【1354793****】上传分享，文档一共【59】页，该文档可以免费在线阅读，需要了解更多关于【运筹学图与网络分析 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。CONTENTS目录01Part01第03Part03章02Part02八04Part04图05Part05与06Part06网球队间比赛问题中国邮路问题哥尼斯堡七空桥010203几个图论问题BDAC哥尼斯堡七空桥哥尼斯堡七座桥问题是200年前数学家欧拉所研究的问题之一。哥尼斯堡现名加里宁格勒,城中有小岛,周围有七座桥架立在波列格尔河上。欧拉想:在城中散步时,能否每座桥只走一次,走遍所有的七座桥。ABCD一笔画问题图1我国数学家管梅谷教授1962年首次提出,并给出了它的解法(奇偶点图上作业法)。邮递员在送报刊信件时,从邮局出发,一般地每次都要走遍所负责的全部街道,任务完成后返回邮局。那么邮递员应该选择哪一条路线才能以尽可能少的路程走完所有的街道呢?中国邮路问题有A、B、C、D、E五支球队,他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次,B队和A、C队比赛过,D队和E、C队比赛过,E队和A、D队比赛过。v1v2v3v4v5v1v2v3v4v5图2图3如果在比赛中:A胜E,B胜C,A胜D,C胜A,E胜D,A胜B,v1v2v3v4v5注:本章所研究的图与平面几何中的图不同,这里我们只关心图有几个点,点与点之间有无连线,两条线有无公共顶点,点与线是否有关联,至于连线的方式是直线还是曲线,点与点的相对位置如何都是无关紧要的。12434123图4图的基本概念若点与点之间的连线没有方向,称为边,由此构成的图为无向图。记为:G=(V,E)其中V是G的点的集合,E为G的边的集合,连接Vi,Vj的边记为[Vi,Vj]或[Vj,Vi]v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10图是由点和点与点之间的连线组成。若点与点之间的连线有方向,称为弧,由此构成的图为有向图。记为:D=(V,A),其中V是G的点的集合,A为G的弧的集合,一条方向为从Vi指向Vj的弧记为(Vi,Vj)v1v3v4v5v6e2e4e5e6e7e8e1e3v2相邻点:两点之间的边属于E01相邻边:如果两条边有一个公共端点02环:边的两个端点相同03多重边(平行边):两个点之间有多于一条边(弧)04多重图:无环但允许有多重边的图05简单图:无环且无多重边的图06注:在有向图中,如果两点之间有不同方向的两条弧,不是多重边07端点的次d(v):点v作为端点的边的个数;奇点:d(v)=奇数;偶点:d(v)=偶数;悬挂点:d(v)=1;悬挂边:与悬挂点连接的边,孤立点:d(v)=0;空图:E=?,无边图。在有向图中,以Vi为始点的边数称为Vi的出次,以Vi为终点的边数称为Vi的入次,入次和出次的和称为该点的次。有向图中所有顶点的入次之和等于所有顶点的的出次之和。图的连通性:链:由两两相邻的点及其相关联的边构成的点边序列。如:v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vnv0,vn分别为链的起点和终点简单链:链中所含的边均不相同。初等链:链中所含的点均不相同,也称通路。圈:起点和终点相同的链。