数学问题与模式探求第27题 化学制品贮藏

第27题 化学制品贮藏 　　假设有10种化学制品需要贮藏在一个仓库中，其中有些化学制品不能放在同一房间内，因为它们所散发出来的气体混合后要发生爆炸，所以必须把它们分隔开来。但是，增加贮藏用房又增加开支。因此，必须求出安全地贮藏这些化学制品所必需的最小的房间间数，其中所有不相容的化学制品如表27-1所示。 　　：设法把这10种化学制品的相容关系用一个图来表示，然后运用第26题中所介绍的色数解决问题。 　　解：用v1，v2，…，v10十个顶点分别表示该10种化学制品。如果两个顶点所表示的化学制品不相容，那么在该两个顶点之间联结一条边。这样，就得到图27-1。 　　由于图中有边联结的两个顶点所表示的化学制品不能放在同一房间内，对它们必须着不同的颜色。对图27-1进行着色(得图27-2)：□=｛v1，v2，v4，v7｝，△=｛v3，v8，v9，v10｝，○=｛v5，v6｝。我们可以把着有3种颜色的顶点所表示的化学制品分别放在3间房间里： 　　房间1：1，2，4，7； 　　房间2：3，8，9，10； 　　房间3：5，6。 　　由于化学制品2，3和6互不相容，所以只用2间房间不能安全地贮藏这些化学制品，安全地贮藏这些化学制品所必需的最小房间数为3，也就是说，图27-1所表示的图的色数为3。 　　注：第26题和第27题都是将表26-1和表27-1的信息加以抽象和简化从而建立起描述该两个问题特征的图(图26-2和图27-1)这个数学模型，将实际问题转化为图论中的色数问题而得到解决。历史上最著名的色数问题是四色问题。它是将一张地图进行染色，使得有公共边界的两个国家染的颜色不同，对此地图染色的问题。1840年德国数学家牟比乌斯首先提出一个猜想：对于平面上的任何地图，用四种颜色总是足够的，这就是著名的四色猜想(亦即四色问题)。如果把地图上的每个国家看作一个顶点，在两个有公共边界的国家所对应的两个顶点之间联结一条边，那么得到一个图。于是，四色猜想就转化为图论中的色数问题：每个平面上的图的色数不大于4。一个多世纪以来，人们对四色问题的研究，推动了图论的发展。1976年美国的阿普尔、黑肯、考齐等，借助于电子计算机，了四色猜想成立。 练习27 　　1．假设有10种化学制品需要贮藏在一个仓库中，其中所有不相容的化学制品如表27-2所示： 　　(1)求安全地贮藏这些化学制品所必需的最小的房间间数？ 　　(2)表27-2中是否有多余的数据？ 　　2．将任意多条直线分平面为若干区域，可以发现，对这些区域染色，只要两种颜色就足够了，试问：为什么？ PAGE 3