图论与网络课题.docx

图论与网络课题.docx

《图论与网络课题.docx》由会员分享，可在线阅读，更多相关《图论与网络课题.docx（12页珍藏版）》请在冰点文库上搜索。

图论与网络课题

网络与图论

内容：

中国邮递员问题；--欧拉图

旅行商问题；--汉密尔顿图

考试安排问题；--图的顶点着色

班级：

试1202

寂寞男孩队

本堂课我们组只针对性介绍以下的三个问题；（其它相关性知识可能介绍不全）

中国邮递员问题；

旅行商问题；

考试安排问题

以下先介绍一些基础的图论的基本概念：

定义7-1.1图G由一个三元组表示，其中：

非空集合V（G）={v1,v2,…,vr}称为图G的结点集，其成员vi（i=1,2,…,r）称为结点或顶点；

集合E（G）={e1,e2,…,es}称为图G的边集，其成员ej（j=1,2,…s）称为边。

函数G：

E（G）→（V（G）,V（G）），称为边与顶点的关联映射。

点的度数的定义：

在图G=，vV，与结点v关联的边数称为该点的度数，记为deg（v）。

中国邮递员问题背景：

一个邮递员从邮局出发投递信件，他必须在所管辖范围内的所有街道至少走一次，最后回到邮局。

选择一条最短的路线完成投递任务。

中国邮递员问题实质上是讨论邮递员如何才能够走最短的路径去穿过每一个街道。

这样就涉及到了2种可能性，其一：

邮递员不走重复的路就将所有的街道走一遍并且回到邮局。

这其实就是求无向欧拉回路的问题。

其二邮递员需要走过一条或多条的已经走过的路，但需要满足这几条重复的路路径最短，使他走完所有街道并回到邮局。

接下来我们讨论第一种情况：

欧拉回路（欧拉图）

如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路（Eulerwalk）。

如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图

判定以下的图是不是欧拉图：

（2）

（1）

无向欧拉图有以下定理：

无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。

（结点度数：

在每个结点上有N条路相连就称结点度数为N）

如果存在的这一条路是欧拉回路则邮递员所通过的最短路径就是所有路长的总和，即图中所有边长（权）的总和。

情况二：

不是欧拉回路

若G不是欧拉图，则最短的路径一定会出现走重复的边的情况，

此时图G中必定有奇数度顶点，为了消除奇顶点，必须加若干条重复边，使得重复边的权与原边的权相同，设所得图为G*，则最优投递路线等价于求G*的一条欧拉回路，使得重复边权之和最小.。

（如下图所示）

⏹定理1：

C是带权无向连通图G=（V,E,）中的最优投递路线当且仅当对应的欧拉图G*应满足：

（1）G的每条边在G*中至多重复出现一次；

（2）G的每个圈在G*中重复出现的边的权之和不超过该圈权的一半。

⏹定理2：

⏹设带权无向连通图G=（V,E,W），V’为G中奇度顶点集，设|V’|=2k（k0），F={e|eE在求G的最优回路时加了重复边}，则F的导出子图G[F]可以表示为以V’中顶点为起点与终点的k条不交的最短路径之并。

则上图可分解为：

在计算机中的编程思想：

⏹1）若G中无奇顶点，令G*=G，转2，否则转3。

⏹2）求G*中的欧拉回路，结束。

⏹3）求G中所有奇度顶点对之间的最短路径。

⏹4）以G中奇度顶点集V’为顶点集，vi,vjV’，边（vi,vj）的权为vi,vj之间最短路径的权，得完全带权图K2k（2k=|V’|）。

⏹5）写出所有齐次顶点的分对组合,如有4个奇次顶点Vi,Vj,Vk,Vs,那么,有3种组合法:

①（Vi,Vj）（Vk,Vs）

②（Vi,Vk）（Vj,Vs）

③（Vi,Vs）（Vj,Vk）

⏹6）（3）以奇次顶点间最短道路作为奇次顶点间的路长,对所有分对组合,计算道路总长,选取最短的一种组合,称为最佳匹配.

⏹

7）将M中边对应的各最短路径中的边均在G中加重复边，得欧拉图G*，转2。

例题如下：

以E点为起点，找一条最短路径，使得一个邮递员经过图中每一条路并且回到E点时，所走的路线最短；

步骤一.观察图发现有奇数度结点A、B、D、C四点

步骤二.求图中所有奇数度定点对之间的最短路径

所以A--B3D--C4

A--D4B--C3

D--B3A--C6

步骤三.求得三组的和分别为7、7、9

步骤四.选择和最小的那一组，

步骤五.将改组的最小路径在原图中重复叠加。

步骤五.算整个图的权之和。

得如下图：

旅行商问题背景：

“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。

它的实质是在图中找到一个回路，使它含有图中所有结点一次且仅一次，也就是所谓的汉密尔顿回路；

定义给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。

若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路；

例如：

左图就具有一条汉密尔顿回路

下面的定理给出一个无向图具有汉密尔顿路的充分条件。

定理设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。

例题：

某地有5个风景点，若每个景点均有两条道路与其他景点相通，问是否可经过每个景点一次而游完这5处。

解：

将景点作为结点，道路作为边，则得到一个有5个结点的无向图。

由题意，对每个结点vi（i=1,2,3,4,5）有

deg（vi）=2。

则对任两点和均有

deg（vi）+deg（vj）=2+2=4=5–1

所以此图有一条汉密尔顿路。

即经过每个景点一次而游完这5个景点。

定理设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则G中存在一条汉密尔顿回路。

例题：

判定图是否存在汉密尔顿回路?

解：

在图中，有5个结点，

结点1的度数deg

（1）＝3，deg

（2）＝3，

deg（3）＝4，deg（4）＝3，deg（5）＝3。

由

于每一对结点的度数之和都大于5，

所以G中存在一条汉密尔顿回路，如

1—3—2—5—4—1。

关于图中有没有汉密尔顿路的判别尚没有确定的方法，下面通过一个例子，介绍一个判别汉密尔顿路不存在的标号法。

例证明下图没有汉密尔顿路。

证明任取一结点如v1,用A标记，所有与它邻接的结点标B。

继续不断地用A标记所有与B邻接的结点，用B标记所有与A邻接的结点，直到图中的所有结点全部标记完毕。

如果图中有一条汉密尔顿路，则必交替通过结点A和B。

因此或者结点A和B数目一样，或者两者相差1个。

而本题有3个结点标记A，5个结点标记B，它们相差2个，所以该图不存在汉密尔顿路。

遇到相邻结点出现相同标记，可在此对应边上增加一个结点，并标上相异标记。

见右图：

考试安排问题----定点着色

首先我们先介绍下图论中节点的着色问题的概念和基本做法：

图的正常着色：

图G的正常着色（或简称着色）是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。

如果图在着色时用了n种颜色，我们称G为n-色的；如（右图）

色数：

对于图G着色时，需要的最少颜色数称为G的色数，记作x（G）。

对点着色的韦尔奇.鲍威尔方法：

第一步：

对每个结点按度数递减次序进行排列（相同度数的结点次序可随意）

第二步：

用第一种颜色对第一个结点着色，并按次序对与前面着色点不相邻的每一点着同样的颜色。

第三步：

用第二种颜色对未着色的点重复第二步，用第三种颜色继续这种做法，直到全部点均着了色为止。

例题1用韦尔奇·鲍威尔法对图7-6.3着色。

第一步：

根据递减次序排列各点A5，A3，A7，A1，A2，A4，A6，A8。

第二步：

第一种颜色对A5着色，并对不相邻结点A1也着第一种色。

第三步：

对结点A3和它不邻接的A4，A8着第二种颜色。

第四步：

对结点A7和它不邻接的A2，A6着第三种颜色。

因此G是三色的。

注意G不可能是二色的，因为A1，A2，A3相互邻接。

故必须着三种颜色。

所以x（G）＝3。

考试安排问题：

如何安排一次7门课程考试，使得没有学生在同一时有两门考试？

构造数学模型：

步骤一：

设G=（V,E）,以每门课程为一个顶点，当且仅当两门课被同一个学生选修时，在相应两个顶点之间连一条边。

得图G。

步骤二：

用不同颜色来表示考试的各个时间段。

考试的安排就对应于图的着色。

如图所示：

在课程和学生选修的课程的相应条件限制下，连接如图所示的图形；

算出每一个节点的度数：

deg（v1）=5deg（v2）=4deg（v3）=5deg（v4）=5deg（v5）=5deg（v6）=4deg（v7）=4

将所有节点度数按从大大小排列：

C1C3C4C5C2C6C7

将C1涂上红色，则与它不相邻的C5也涂上红色；

将C3涂上黄色，则与之不相邻的C7涂上黄色；

将C4涂上蓝色，则与它不相邻的C6涂上蓝色

将C2涂上紫色。

Endl；

如上图所示，因为这个图的色数为4，所以需要4个时间段：

1和5、3和7、4和6、2。

以上所有概念出自石家庄铁道大学离散数学教师赵志宏的课件，部分习题为小组人员自编，若有错误，敬请原谅；