图论应用问题探析

[摘要] 图论从诞生至今已近300年， 但很多问题一直没有很好地解决。随着计算机科学的发展， 图论又重新成为了人们研究讨论的热点， 这里给出图论在现实生活中的一些应用。

[关键词] 欧拉 图论 二分图 哈密顿回路 着色

在 18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣， 这个问题要求遍历普鲁士的哥尼斯堡七桥中的每一座桥恰好一次后回到出发点。欧拉证明了这是不可能完成的，此后， 欧拉发表了著名的论文《依据几何位置的解题方法》，这是图论领域的第一篇论文，标志着图论的诞生。图论的真正发展始于20世纪五六十年代之间， 是一门既古老又年轻的学科。

图论极有趣味性，严格来讲它是组合数学的一个重要分支。虽然图论只是研究点和线的学问，但其应用领域十分广阔，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理、电信领域等等。总的来说， 图论这门学科具有以下特点：图论蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化，非常灵活，常常是一种问题一种解法。由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法。而且图论所研究的内容非常广泛，例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等等。

一、二分图

有一类非常重要的图，如树，它是图的特例，这类图被称作二分图，经常应用在涉及匹配的问题中。例如， 某公司现在正经历一次罢工，为了使公司在罢工中照常运作，人事部确定了4项关键工作：销售、维修、安全控制和会计，其中销售需要2人。表中给出了每个人和他们能胜任的工作，判断是否所有工作都能有人来负责， 设每人只能负责一项工作。

这看起来是社会学领域的问题，我们可以尝试多种方法，而其中的一种方法就是将其化为图，建立一个图的模型。最基本的问题是如何描述它，什么是结点，什么是边？在本问题中，没有太多的选择，只有人和工作。我们可试着用集合X中的结点来代表人，用集合Y中的结点来代表工作。用边来代表图中结点之间的关系，在这里结点之间的关系是“人能否胜任工作”，因此，若某人能胜任工作，那么就在两个结点之间加上一条边。由于销售需要2人，所以用2个结点S1和S2来表示。如此得到二分图1，2给出了最大匹配，很容易看出每一项工作都有人来负责。

二、哈密顿回路

图论中许多理论和实际问题都需要我们以某种方法遍历整个图。例如在某些问题中，我们的目标是求出一条迹或回路，满足经过每条边一次且仅一次;在另一些问题中， 我们可能需要求出一条路或圈， 满足经过每个结点一次且仅一次。其中最著名的两个问题莫过于“旅行商”问题和“中国邮路”问题。

例如： 举行一个国际会议， 有A，B，C，D，E，F，G 7个人。已知下列事实：A会讲英语；B会讲英语和汉语；C会讲英语、意大利语和俄语；D会讲日语和汉语；E会讲德语和意大利语；F会讲法语、日语和俄语；G会讲法语和德语。试问这7个人应如何排座位， 才能使每个人都能和他身边的人交谈？我们还是用图来解决这个问题。依然是建立一个图的模型， 确定结点和边。这里有“人和语言”， 那么我们用结点来代表人， 于是结点集合V＝{A，B，C，D，E，F，G}对于任意的两点，若有共同语言，就在它们之间连一条无向边，可得边集E，图G＝（V，E）。

如何排座位使每个人都能和他身边的人交谈？问题转化为在图G中找到一条哈密顿回路的问题（哈密顿回路即是通过每个结点一次且仅一次的回路）。而A-B-D-F-G-E-C-A即是图中的一条哈密顿回路。照这个顺序排座位就可以解决问题了。

三、着色问题

许多由图论描述的现实问题都需要把结点集或边集划分为一些不相交的子集，使同一子集中的所有元素互不相邻。这类问题中比较常见的有：安排会议或考试的日程以免冲突，还有安排化学品的存储以避免互相反应。例如一名设计师为实验室设计化学药品存储仓库，希望建造尽量少的存储间。已知某些药品之间会起反应，不能存储在一起。作为简化，我们用字母a到n代表14种化学品；两种化学品之间的边代表它们可能起化学反应。求所需最少存储间，并指出每种药品放入哪个存储间。

虽然这样给人感觉很复杂，似乎色数会有爆炸性增长， 但实际上很容易就可以验证其色数等于3，而且是可唯一三着色的。在将其中的一个K3用3种不同颜色着色之后，我们可以继续移动到与该K3相邻的结点为，如果这个结点的颜色已经唯一确定，我们就能继续处理直到完成整个过程。其惟一三着色图使用了粉红（p）、褐色（t）和白色(w）。所以可以得知， 总共需要三间存储间，化学品将按如下方案存储:在粉红存储间中，我们存储 f、h、j、k和l；在褐色存储间中， 我们放置b、d、e、m和n； 在白色存储间中安排 a、c、g和i 。

如果能在平面内将图画出且使其边各不相交叉，那么这个图就是可平面化的。可平面图曾经受到了多年的广泛关注，其原因在于一个长期困惑人们的问题“四色猜想”。这个问题描述起来很简单，就是能否只用四种颜色来着色平面图，相邻的部分颜色要不相同，但最终花费了100多年的时间才得到证明， 证明最终公布于1977年，当时引起了强烈反响，国为这是第一个广泛利用计算机做出的证明。现如今，可平面图在其应用领域仍然占有很重要的地位，例如场地布局或是电路板设计等。

四、结论

从上面的例子我们可以看出，图论的应用十分广泛，如果我们在学习的过程中能打下坚实的基础，就有能力将图论的思想应用到纷乱复杂的现实问题中去。