利用图论知识解决实际问题.doc

淮北师范大学 2013届学士学位论文 利用图论知识解决实际问题的方法探究 学院、专业 数学科学学院 数学与应用数学 研 究 方 向 离散数学 学 生 姓 名 杨 波 学 号 20091101179 指导教师姓名 刘楠楠 指导教师职称 讲 师 2013年3月25日利用图论知识解决实际问题的方法探究杨 波（淮北师范大学数学科学学院，淮北，235000）摘 要图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门新兴学科。随着科学的进步，图论知识越来越贴近于生产和生活，所以利用图论知识来解决实际问题又成为当今的一大热点。着色、绘图、运输最短路径、集合等都与图论知识离不开。本课题将重点利用图论知识来解决实际生活、生产中的问题。本文首先介绍了图的基本概念，对图论所涉及的基本知识进行简单的阐述，使读者对图论知识有一定的了解；再介绍图论中两种特殊的图形：欧拉图和哈密顿图，并用它们分析如何解决最短路问题和货郎担问题；然后介绍着色问题以及其与实际生活的联系；最后通过实例来说明图论知识在日常生产、生活中的运用。关键词 图论，欧拉图，哈密顿图，最短路径，着色问题, 应用The method of using graph theory knowledge to solve practical problems Yang Bo （College of Mathematical Science, Huaibei Normal University, Huaibei, 235000） Abstract Graph theory is a branch of mathematics that has been developed rapidly and used widely in recent years. With the progress of science, graph theory is increasingly close to the production and life, so using the knowledge of graph theory to solve practical problems has become a focus today. Coloring, drawing, the shortest path of transportation cannot be separated from graph theory knowledge. The article lays press on the using of graph theory to solve the practical problems in production knowledge in real life. This article first introduces the basic concept of graph, and make a further introduction to the basic knowledge of graph theory which involved a simple elaboration, then the reader can have a certain knowledge of graph theory knowledge; Then two kinds of special graphics are referred to: the Eulerian graph and Hamiltonian graph, along with their analysis of how to solve the problem of the short circuit and traveling salesman problem. Then the article discuss the coloring problem and its links with real life; Finally by an example to illustrate the application of graph theory knowledge in daily life and production.Keywords Graph theory, Eulerian graph, Hamiltonian graph, shortest paths,coloring, application 目 录引 言1（一）预备知识 1 1 图的基本概念 1 2 通路与回路4 3 图的连通性6 4 图的矩阵表示 8（2） 欧拉图与哈密顿图10 1 欧拉图10 2 哈密顿图.10 3 最短路问题与货郎担问题.13（三）着色16 1 点着色16 2 边着色16（四）图论知识在实际生活、生产中的应用18 1 哥尼斯堡七桥问题18 2 哈密顿图的实际应用19 3 教师如何分配课时问题 20 结 论21 参考文献21 致 谢23 引言 在现实生活中，我们会遇到很多复杂的问题，介于此我们希望用到我们所学过的数学方法去简化它，优化它和解决它。图论知识就是一个很好的工具，将实际问题化为图后，我们能清楚的观察到整个局面，方便我们进行具体的分析。所以研究和总结图的应用算法是件有意义且必要的事情。本课题将着重通过图论知识来解决实际生活、生产中所遇到的着色，最短路径，绘图等问题。通过其在实际生活中的应用，来认识图论知识在学习中的重要性。 （一）、预备知识 在日常生活、生产活动及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否有某种关系，这样构成的图形就是图论中的图。其实，集合论中二元关系的关系图都是图论中的图。在这些图中，人们只关心是否有连线，而不关心点的位置，以及连线的曲直，这就是图论中图与几何学中图形的本质区别，下面我们先来介绍图论中图的一些基本概念，再对来研究用图论知识解决实际问题的方法。 1图的基本概念 定义1.1 一个无向图是一个有序的二元组，其中 是一个非空有穷集，称为顶点集，其元素称为顶点或结点。 是无序积&的有穷多重子集（元素可以重复出现的集合称为多重集合。某元素重复的次数称为该元素的重复度。），称为边集，其元素称为无向边，简称为边。 定义1.2 一个有向图是一个有序的二元组，其中 是一个非空有穷集，称为顶点集，其元素称为顶点或结点。 是笛卡尔积的有穷多重子集，称为边集，其元素称为有向边，简称边。 通常用图形来表示无向图和有向图：用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用带箭头的连线表示有向边。 例1.1 给定无向图，其中，根据定义画出无向图，如图1.1中（a）. 给定有向图，其中，；根据定义画出有向图，如图1.1中（b）. 图1.1与定义1.1和1.2有关的还有下面一些概念和规定：1. 顶点数称为图的阶，个顶点的图称为阶图.2. 一条边也没有的图称为零图.阶零图记为.1阶零图称为平凡图.平凡图只有一个顶点，没有边.3. 当用图形表示图的时候，如果给每一个顶点和每一条边指定一个符号（字母或数字,当然字母还可以带下标），则称这样的图标定图，否则称为非标定图.定义1.3 在无向图中，如果关联一对顶点的无向边多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，如果关联一对顶点的有向边多于1条，并且这些边的始点与终点相同（也就是它们的方向相同），则称这些边为平行边。 例如在图1.1中，中与是平行边，在中，与是平行边，而与不是平行边。，两个图不是简单图。 例1.2 先将图1.2中各图的顶点标定顺序，然后写出各图的集合表示. 图1.2解 图1.2中（a）、（b）的顶点标定顺序如下图所示（a） 的集合表示为，其中 （b）的集合表示为，其中定义1.4 设为无向图，称作为边的端点的次数之和为的度数，简称为度，记作。在不发生混淆时，略去下标，简称为。设为有向图，称作为边的始点的次数之和为的出度，记作，简称。称作为边的始点的次数之和为的入度，记作，简称。称为的度数，记作，简记作.定义1.5 设为一个阶无向图，为的度数列.对于顶点标定的无向图，它的度数列是唯一的.反之，对于对于给定的非负整数列，若存在以为顶点集的阶无向图，使得，则称是可图化的.特别地，若所得到的图是简单图，则称是可简单图化的.下面关于图的度数给出两个结论。 定理1.15 非负整数列是可图化的当且仅当为偶数.定理1.25 设为任意阶无向简单图，则（在无向图中，）. 定义1.6 设，为两个无向图（两个有向图），若存在双射函数使得，当且仅当当且仅当，并且与与的重数相同，则称与同构，记作. 定义1.7 设为阶无向简单图，若中每个顶点均与其余的个顶点相邻，则称为阶无向完全图，简称阶完全图，记作. 2 通路与回路 定义2.1 设为无向标定图，中顶点与边的交替序列称为到的通路，其中为的端点，分别称为的始点与终点，中边的条数称为它的长度。若又有，则称为回路。若的所有边各异，则称为简单通路。若又有，则称为简单回路。若所有顶点（除与可能相同外）各异，所有边也各异。则称为初级通路或路径。若又有，则称为初级回路或圈。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。注意，在初级通路与初级回路的定义中，仍将初级回路看成初级通路（路径）的特殊情况，知识在应用中的初级通路（路径）都是始点与终点不相同的，长为1的圈智能由环生成，长为2的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为3.另外，若中有边重复出现，则称为复杂通路.若又有则称为复杂回路.定理2.15 在阶图中，若从顶点到存在通路，则从到存在长度小于或等于的通路. 推论5 在阶图中,若从顶点到存在通路，则从到一定存在长度小于或等于的通路（路径）. 定理2.25 在阶图中,若存在到自身的回路，则一定存在到自身长度小于或等于的回路. 推论5 在阶图中,若存在到自身的简单回路，则一定存在到自身长度小于或等于的初级回路. 例2.1 无向完全图中有几种非同构的圈？ 解 长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的.易知中含长度为的圈，所以中有种非同构的圈. 长度相同的圈都是同构的，因此在同构意义下给定长度的圈只有一个.在标定图中，圈表示成顶点和边的标记序列.如果只要两个标记序列不同，就认为这两个圈不同，称这两个圈在定义意义下不同. 例2.2 无向完全图的顶点依次标定为.在定义意义下有多少个不同的圈？ 解 在同构意义下，中只有一个长为3的圈.但在定义意义下，不同起点（始点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而中有6个不同的长为3的圈：，.如果只考虑起点（终点）的差异，而不考虑顺时针逆时针的差异，应该有3种不同的圈，当然它们的长度都是3. 3 图的连通性定义3.1 设无向图，若之间存在通路，则称是连通的，记作.规定：.若无向图是平凡图或中任何两个顶点都是连通的，则称为连通图，否则称为非连通图. 定义3.2 设无向图，是关于顶点之间的连通关系的一个等价类，称导出子图为的一个连通分支.的连通分支数记为. 定义3.3 设为无向图中任意两个顶点，若，则称之间长度最短的通路为之间的短程线.短程线的长度称为之间的距离，记作.当不连通时，规定.距离有以下性质：，1. ，且当且仅当时等号成立.2. 具有对称性：.3. 满足三角不等式：. 定义3.4 设无向图，若存在使得，且对于任意的，均有，则称是的边割集，或简称为割集.若，则称为割边或桥. 定义3.5 设为无向连通图且不是完全图，则称 为的点割集.为的点连通度，简称连通度.有时简记为.规定完全图的点连通度为，非连通图的点连通度为0.又若，则称是连通的，为非负整数.例图3.1中图的点连通度为1，此图为连通图，的点连通度，所以是连通图，连通图.连通图，连通图. 定义3.6 设是无向连通图，称 为的边割集为的边连通度.有时简记为.规定非连通图的边连通度为0.又若，则称边连通图. 例3.1 求图3.2所示各图的点连通度和边连通度，并指出它们各是几连通图及几边连通图，最后将它们按点连通程度及边连通程度排序. 图3.2 解 设第个图的点连通度为，边连通度为容易看出，,. 是连通图，边连通图， 是连通图，边连通图， 是连通图，边连通图， 是连通图，边连通图. 是连通图，边连通图， 是连通图，边连通图， 是连通图，边连通图. 是连通图，边连通图.点连通程度为：.边连通程度为：.定义3.7 设无向图，若能将划分成和（即， 且），使得中的每条边的两个端点都是一个属于，另一个属于，则称为二部图，称和为互补顶点子集，常将二部图记为.又若是简单二部图，中每个顶点均与中所有顶点相邻，则称为完全二部图，记为，其中. 4 图的矩阵表示 图可以用集合来定义，但多半用图形来表示，还可以用矩阵来表示。用矩阵表示图便于用代数方法研究图的性质。为了用矩阵表示图，必须指定顶点或边的顺序，使其成为标定图。 定义4.1 设无向图，令为顶点与边的关联次数，则称为的关联矩阵，记作。 定义2 设有向图中无环，令 则称为的关联矩阵，记作。图4.1所示图的关联矩阵为 图4.1有如下各条性质：1. 每一列恰好有一个和一个.2. 的个数等于的个数，都等于边数，这正是有向图握手定理的内容.3. 第行中，的个数等于，的个数等于.4. 平行边所对应的列相同. 例4.1 图4.2的完全关联矩阵为： 图4.2 设是无向图，的完全关联矩阵有如下性质： 1.每列元素之和为2.这说明每条边关联两个结点. 2.每行元素之和是对应结点的度数. 3.所有元素之和是图中各结点度数的总和，也是边数的2倍. 4.两列相同则对应的两条边是平行边. 5.某行元素全为0，则对应的结点为孤立点.（2） 欧拉图与哈密顿图 1 欧拉图 定义1.1 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路.通过图中所有边一次仅一次行遍所有顶点的回路称为欧拉回路.具有欧拉回路的图称为欧拉图.具有欧拉通路而无欧拉回路的图称为半欧拉图.规定平凡图是欧拉图.下面给出一些判断无向图和有向图是否为欧拉图或半欧拉图的方法1。 定理1.1 无向图是欧拉图当且仅当是连通图且没有奇度顶点. 定理1.2 无向图是半欧拉图当且仅当是连通图且且恰有两个奇度顶点. 定理1.3 有向图是欧拉图当且仅当是强连通的且每个顶点的入度等于出度. 定理1.4 有向图是半欧拉图当且仅当是单向连通的且恰有两个奇度顶点，其中一个的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的入度等于出度.定理1.5 是非平凡的欧拉图当且仅当是连通的且是若干个边不重的圈的并. 2 哈密顿图定义2.1 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路.经过图中所有顶点一次且仅一次的回路称为哈密顿回路.具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图.规定平凡图是哈密顿图.下面给出无向图或有向图为哈哈密顿图的一些充分或必要条件。定理2.15 设无向图是哈密顿图，则对于任意且，均有 证 设是中任意一条哈密顿回路.易知，当中顶点在上均不相邻时，所以有.而是的生成子图，所以有. 例2.1 在图2.1中给出的3个图都是二部图，它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？ (a) (b) (c) 图2.1解 在(a）中，互补顶点子集.设此二部图为.由定理2.1可知，不是哈密顿图，也不是半哈密顿图.设（b）中图为，其中.由定理2.1可知，不是哈密顿图.而是一条哈密顿通路，故是半哈密顿图.在（c）中，是一条哈密顿回路，所以（c)是哈密顿图.设这个图为，其中.此处有.一般情况下，设二部图，且由定理2.1可以得出下面结论：（1） 若是哈密顿图，则.（2） 若半哈密顿图，则.（3） 若，则不是哈密顿图，也不是半哈密顿图. 定理2.25 设是阶无向简单图，若对于中任意不相邻的顶点，均有 则中存在哈密顿通路. 推论 设为阶无向简单图，若对于中任意不相邻的顶点，均有 则中存在哈密顿回路. 定理2.35 设为阶无向简单图中两个不相邻的顶点，且，则为哈密顿图当且仅当为哈密顿图（是加的新边）. 下面我们举例来看哈哈密顿图在实际中的应用。 例2.2 在某次国际会议的预备会中，共有7人参加，他们来自不同的国家.已知他们中任何两个无共同语言的人，与其余由共同语言的人数之和大于或等于7，试证明能将这7个人排在圆桌旁，使其任何人能与两边的人交谈. 解 设7个人分别为作无向简单图，其中，与有共同语言，.为7阶无向简单图，为与有共同语言的人数.由已知条件，且，均有.由定理2.2的推论可知，中存在哈密顿回路，设为中一条哈密顿回路，按这条回路的顺序安排座次即可. 3 最短路问题与货郎担问题定义3.1 设图（无向图或有向图），给定，对的每一条边，称为边的权.把这样的图称为带权图，记作.当，把记作. 设是中的一条通路，中所有边的权之和称为的长度，记作，即.类似地，可定义回路的长度.本节考虑带权图上的两个问题最短路问题和货郎担问题.设带权图（无向图或有向图），其中每一条边的权为非负实数.当和连通（可达)时，称从到长度最短的路径为从到的最短路径，称其长度为从到的距离，记作.约定：；当和不连通（不可达)时，.最短路问题：给定带权图及顶点和，其中每一条边的权为非负实数，求从到的最短路径.不难看出，如果是从到的最短路径，则对每一个，其中表示的后的下标是从到的最短路径.根据此于1959年给出下述最短路径算法.算法给出从顶点的起点到每一点的最短路径.在计算过程中，赋予每一个顶点一个标号.标号分永久标号和临时标号.在的永久标号中，是从到的距离，是从到的最短路径上的前一个顶点.当为临时标号时，和分别是当前从经过永久标号的顶点到的长度最短的路径上的前一个顶点和这条路径的长度. 例3.1 货郎担问题（旅行商问题） 有n个城市，给定城市之间道路的长度（长度可以为无穷大，对应两个城市之间无交通线）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问如何走才能使他走的路线最短？这个问题可以用图论方法描述如下：设G=为一个n阶完全带权图，各边的权W（e）非负且可以.求G中一条最短的哈密顿回路.例如，图3.1（a）给出一个4阶完全带权图.不计起点、也不计顺时针和逆时针，只有3条不同的哈密顿回路： a b c d a a b d c a a c b d a分别如(b),(c),(d)所示，其长度分别为8,10,12.因此，是所求的最短路线. 图3.1 至今还没有找到解决货郎担问题的有效算法，还需要我们继续探讨. 例1 求图3.2所示带权图中的货郎担问题（即求图中的最短的哈密顿回路）. 解 由于完全图中共存在条不相同的哈密顿回路.在完全带权图中，设顶点分别为，回路与回路的权相同，因而仅要考虑条哈密顿回路.在图3.2中，因此共有12条回路.分别求出这12条回路的权，其中权最小的即为最短的哈密顿回路. 图3.2 设 ： ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权 ，其权从结果可知，最短哈密顿回路为，其权.至今还没有找到求解货郎担问题的快速算法，当较大时，计算量会迅速的增加. （三） 平面图的着色问题 图着色问题的研究起源于四色猜想，着色问题包含点着色，边着色和地图着色等.点着色和边着色都是对无环的无向图进行的，下面我们着重介绍点着色和边着色 1 点着色 定义1.1 设无向图无环，对的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图的一种点着色，简称着色。若能用种颜色给的顶点着色，则称是可着色的。若是可着色的，但不是可着色的，则称的色数为。的色数记作，简记作。定义1.2 对地图的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对地图的面着色。若能够用种颜色给的面着色，则称是可面着色的。若是可面着色的，但不是可面着色的，则称的面色数为。的面色数记作，简记作。 2 边着色 定义2.1 对图的每条边着一种颜色，使相邻的边着不同的颜色，称为对图的边着色。若能用种颜色给的边着色，则称是可边着色的。若是可边着色的，但不是可边着色的，则称的边色数为。的边色数记作，简记作。定理2.1定理 简单图的边色数只可能取两个值：或者. 定理2.2 n1，其中n4.证明 当n=4或5时，不难用3种颜色和4种颜色分别给和的边着色.如图4所示。又它们的分别为3和4，因此由定理得证结论正确。 图2.1 当n6时，中间顶点关联的n1条边用n1种颜色着色，而外圈上的每一条边都与4条边相邻，总可以从这n15种颜色中找到一种颜色给它着色，所以，又由定理，得证. 定理2.3 当为奇数时，而当为偶数时，. 证明： 为奇数且，由定理可知，.下面证明. 如下画：先画正边形，将上不相邻得顶点之间都连线段就得到.在中共有组平行线，每组条边.条平行边关联个顶点，因而在的边着色中至多有条边同色，故，得. 图2.2 为偶数时，由定理，.下面证明.可如下获得：先画出为奇数，然后在的中心放置一个顶点，连接中心点与上的所有顶点.时的情况如图5所示.用种颜色给的边着色，然后给与中心点关联的边着中与它垂直的边的颜色，就完成了的边着色. 图着色在实际中的应用设学校共有们功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把同一学生选修的两门课放在同一场次进行考试.问期末考试最少需要多少场次才能完成？解： 我们以每门功课为一个顶点当且仅当两门课被同一学生选修时，在两个顶点之间连一条边，得到一个图.我们将门课程划分为个子集两两子集的课程都不相同.每个子集的顶点不相邻，即子集内的任何两门课程都不能被一个学生选修.要求划分的子集数最少，即不能将门课程划分成个子集.然后我们对每个子集内的顶点涂一种颜色.同色顶点对应的课程安排在同一场次考试，颜色总数即为考试所需要的场次数，即所求的值.（四）图论知识在实际生活、生产中的运用 例1 哥尼斯堡七桥问题18世纪中叶在欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的普雷格尔河，河中有两个岛，由七座桥相连（如图1.1中（a）所示）.当时一直有一个难题困扰着人们：一个人怎么样不重复的走完七座桥，最后回到出发地点？这就是所谓的哥尼斯堡七桥问题. （a) (b) 图1.1很长时间没有人能解决这个问题.1736年，瑞士数学家欧拉发表论文，他用4个点分别表示两个岛和两岸，用连接两点的线段表示桥，如图1.1（b).即用到了图论中所涉及的欧拉图.哥尼斯堡七桥问题就是要求在这个图中走一条欧拉回路.欧拉在这篇论文中证明了定理1.1即无向图是欧拉图当且仅当是连通图且没有奇度顶点.由于图（b）中4个顶点均是奇度顶点，所以哥尼斯堡七桥问题无解.欧拉当时发表的论文现在被公认为是第一篇关于图论的论文.这也正是欧拉回路和欧拉图名字的由来.而哥尼斯堡七桥问题中所涉及的欧拉图知识即是图论知识在实际生活中的应用.例2 哈密顿图的实际应用现有个人，已知他们其中的任意两个人合起来认识其余的个人.证明： （1）当时，这个人能站成一列使得其中任何两个相邻的人都互相能认识. （2）当时，这个人能站成一个圈使得其中任何两个相邻的人都互相能认识. 证 做阶无向简单图，且与认识.由已知条件可知，均有 下面讨论与是否认识. （1）若与认识，则由知 （2）若与不认识，则对任意的，与必与都认识.否则，假如与不认识，则与和都不认识，所以与合起来至多认识其余的个人，这与已知条件矛盾.因而 当时，有 于是，当时，由，与式（根据定理2.2）中存在哈密顿通路，所有的人按在通路中的顺序排成一列，满足要求.当时，有 所以由，与式（根据定理2.2的推论）中存在哈密顿回路，所有的人按在回路中的顺序站成一圈满足要求. 此应用中主要根据哈密顿通路与回路解决实际中的交流问题，使我们更深刻的了解图论知识在日常生活中的作用.例3 教师如何分配课时问题某高中一年级有5个班，由4位老师为他们讲课，周二每位老师为每个班上课的课时如表3.1所示，问此年级周二至少要安排多少节课？需要多少个教室？ 表3.1 1班 2班 3班 4班 5班 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1 2 解 做二部图，其中表示所有4为教师.，分别表示每个班级.，在与之间连条边，每一条边代