运筹学8图与网络分析

《运筹学8图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章图与网络分析主要内容：8.1图与网络的基本知识8.2最短路问题8.3最大流问题8.4最小费用流问题8.1图与网络基本知识一、引言1。产生哥尼斯堡七桥难题例8-1：哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？ABCD数学家Euler在1736年解决：8.1图与网络基本知识ACBDABCD二、图与网络的基本概念8.1图与网络基本知识图论是专门研究图的理论

2、的一门数学分支，主要研究点和线之间的几何关系。图论是离散数学的范畴。8.1图与网络基本知识一、图的有关概念表示为：G=（V，E）V--点集合E--边集合简称图，由点和边组成。无向图：带箭头的联线，表示不对称关系。弧：不带箭头的联线，表示对称关系。边：反映对象之间关系的一种工具。图：表示两个对象之间的某种特定关系。连线：表示研究对象。点：8.1图与网络基本知识二、无向图的有关概念：有多重边的图。多重图：无环，无多重边的图。简单图：两点之间多于一条边。多重边：若u=v，e是环。环：e是点u，v的关联边。关联边：e=[u,v]∈E，则u,v是e的端点

3、，称u,v相邻。端点：8.1图与网络基本知识二、无向图的有关概念：V1v2v3v4e1e2e5e4e6e3次为偶数的点。偶点：次为奇数的点。奇点：次为0的点。孤立点：悬挂点的关联边。悬挂边：次为1的点。悬挂点：例:如图示d(v1)=4，d(v4)=4以点v为端点的边数称为v的次。表示为：d(v)次：8.1图与网络基本知识二、无向图的有关概念定理8-2：在任意一个图中，奇顶点的个数必为偶数。定理8-1：在一个图中，所有顶点次的和等于边的两倍。圈中边均不相同。简单圈：链中边均不相同。简单链：圈中无重复的点和边。初等圈：链中无重复的点和边。初等链：如

4、一条链中起点和终点重合。圈：点边交错序列。链：8.1图与网络基本知识二、无向图的有关概念：图G去掉点v及v的关联边的图。G-v：对G=（V，E），若Gˊ=(Vˊ，Eˊ),使Vˊ=V，Eˊ是E的子集，则Gˊ是G的一个支撑子图。支撑子图：对不连通图，每一连通的部分称为一个连通分图。连通分图：任意两点之间至少有一条链。连通图：例8-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？8.1图与网络基本知识提示：用顶点表示人，用边表示两者相邻。共有3种方案。8.1图与网络基本知识三、有向图的有关概念:有多重弧。多重

5、有向图：无自环，无多重弧。简单有向图：圈中无重复的点和弧。初等圈（回路）：链中无重复的点和弧。初等链（道路）：如一条链中起点和终点重合。圈（回路）：点弧交错序列。链（道路）：对弧a=(u，v)，u为a的始点，v为a的终点。始点和终点：由点和弧组成。表示为：D=（V，A）V--点集合A--弧集合有向图：树：一个无圈的无向连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。8.1图与网络基本知识四、树的概念树的性质：在图中任意两点之间必有一条而且只有一条通路。2）在图中划去一条边，则图不连通。3）在图中不相邻的两个顶点之间加一条边，可得

6、一个且仅得一个圈。4）图中边数为：p-1（p为顶点数）例8-4：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。8.1图与网络基本知识解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—

7、A—F—D—B，就是一个符合要求的考试课程表。8.1图与网络基本知识AFEDCBAFEDCBAFEDCB8.1图与网络基本知识四、树的概念图的支撑树（生成树）：1）定义:设图T=(V，E’)是图G=(V,E)的支撑子图,如果T是一个树,则称T是G的一个支撑树。最优树（最小生成树、最小支撑树）：在赋权图G中，一棵生成树所有树枝上权的总和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。2）定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。四、树的概念求最小生成树的方法有破圈法和避圈法。8.1图与网络基本知识v1v7v4v3v

8、2v5v620159162532817412336五、欧拉回路与中国邮递员问题8.1图与网络基本知识一笔划问题欧拉链（道路）：图中存在一条链，过每边一