着色问题 许多由图论描述的现实问题都需要把结点集或边集划分为一些不相交的子集, 使同一子集中的所有元素互不相邻。这类问题中比较常见的有: 安排会议或考试的日程以免冲突, 还有安排化学品的存储以避免互相反应。例如一名设计师为实验室设计化学药品存储仓库, 希望建造尽量少的存储间。已知某些药品之间会起反应, 不能存储在一起。作为简化, 我们用字母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 年, 当时引起了强烈反响, 国为这是第一个广泛利用计算机做出的证明。现如今, 可平面图在其应用领域仍然占有很重要的地位,例如场地布局或是电路板设计等。 哈密顿回路 图论中许多理论和实际问题都需要我们以某种方法遍历整个图。例如在某些问题中, 我们的目标是求出一条迹或回路, 满足经过每条边一次且仅一次; 在另一些问题中, 我们可能需要求出一条路或圈, 满足经过每个结点一次且仅一次。其中最著名的两个问题莫过于“旅行商”问题和“中国邮路”问题。 例如: 举行一个国际会议, 有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 即是图中的一条哈密顿回路。照这个顺序排座位就可以解决问题了。 二分图 有一类非常重要的图, 如树, 它是图的特例, 这类图被称作二分图, 经常应用在涉及匹配的问题中。 例如, 某公司现在正经历一次罢工, 为了使公司在罢工中照常运作, 人事部确定了4 项关键工作: 销售、维修、安全控制和会计, 其中销售需要2 人。表1 给出了每个人和他们能胜任的工作, 判断是否所有工作都能有人 本文来源：https://www.wddqw.com/doc/2c5cbe2e7e21af45b307a867.html