第11章图论问题.doc

图论问题有限个对象（图的顶点）具有某种特定的关系（图的边）就可构造出一个图。它的优点是形象直观，使得问题的本质结构一目了然，研究起来极其方便。注意：Mathematica4.0软件包只能处理无向图。例11-1（独立点集问题） 有7种化学品x1、x2、x3、x4、x5、x6、x7（在图中用点表示），它们有一些不能放在一起（在图中不能放在一起的化学品连边表示）：在Mathematica4.0软件包中的命令如下：第一步先打开离散数学的组合子程序包Combinatorica，输入并执行以下程序： 1= ”, f/.z-1 Print “ f /.z-2= ”, f/.z-2 Print “ f /.z-3= ”, f/.z-3 Print “ f /.z-4= ”, f/.z-4 运行后得到结果如下： f/.z-1 = 0 f/.z-2 = 0 f/.z-3 = 24 f/.z-4 = 552z = 3时图g1的色多项式取值大于零，表示可以用3种颜色染图g1的顶点，染同色的点之间不连边。同色点构成图g1的独立点集。由此知道，图G1的色数确实是3（因为图g1的色多项式ff在z = 1、z = 2时取0值，在z = 3时取值大于0），这说明，图g1的点集至少可分成3个独立点集（分法有24种）。方法2 染色分解独立点集法。输入以下程序： VertexColoring g1 执行后得到： 2, 1, 2, 1, 3, 1, 2 。即，图g1中的顶点 x1, x3, x7 染第二种色，把这三种化学品放在第二间仓库；图g1中的顶点 x2, x4, x6 染第一种色，把这三种化学品放在第一间仓库；图g1中的顶点 x5 染第三种中色，把这种化学品放在第三间仓库；例11-2（最短路问题） 求下列赋权图中顶点x1到 x11的最短路：首先输入其权矩阵WG如下：WG = 0, 8, 5, 7, 0, 0, 0, 0, 0, 0, 0 , 8, 0, 0, 0, 6, 2, 0, 0, 0, 0, 0 , 5, 0, 0, 0, 4, 5, 0, 0, 0, 0, 0 , 7, 0, 0, 0, 0, 4, 2, 0, 0, 0, 0 , 0, 6, 4, 0, 0, 0, 0, 4, 0, 0, 0 , 0, 2, 5, 4, 0, 0, 0, 4, 2, 4, 0 , 0, 0, 0, 2, 0, 0, 0, 0, 2, 4, 0 , 0, 0, 0, 0, 4, 4, 0, 0, 0, 0, 4 , 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 5 , 0, 0, 0, 0, 0, 4, 4, 0, 0, 0, 4 , 0, 0, 0, 0, 0, 0, 0, 4, 5, 4, 0 ;WG中的元素 Wij 表示点Xi到点Xj的边的距离，0表示此边不存在。求最短路程序如下：Clear g2 g2 = Graph WG, -2, 0 , -1, 1 , -1, 0 , -1, -1 , 0, 1 , 0, 0 , 0, -1 , 1, 1 , 1, 0 , 1, -1 , 2, 0 ;ShortestPath g2, 1, 11 得到结果： 1, 4, 7, 9, 11 。即，从x1到x11的最短路是：最短路长为：7 + 2 + 2 + 5 = 16。例11-3（排课表问题） 有m个老师X1，X2，Xm以及n个班级Y1，Y2，Yn，一天中老师Xi要给班级Yj上课aij节，如何安排上课？例如下例：Y1Y2Y3Y4Y5X120110X201010X301110X400011这可以理解为是一个图中边的极大匹配的分解问题。边的极大匹配又叫做边独立集。将必上的课时作为边的权重，输入以下权重矩阵：MM = 0, 0, 0, 0, 2, 0, 1, 1, 0 , 0, 0, 0, 0, 0, 1, 0, 1, 0 , 0, 0, 0, 0, 0, 1, 1, 1, 0 , 0, 0, 0, 0, 0, 0, 0, 1, 1 , 2, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 1, 1, 0, 0, 0, 0, 0, 0 , 1, 0, 1, 0, 0, 0, 0, 0, 0 , 1, 1, 1, 1, 0, 0, 0, 0, 0 , 0, 0, 0, 1, 0, 0, 0, 0, 0 ;Clear g3 g3 = Graph MM, 1, -3/2 , 1, -1/2 , 1, 1/2 , 1, 3/2 , 2, -2 , 2, -1 , 2, 0 , 2, 1 , 2, 2 ;ShowGraph g3 画出图为：方法1 求极大匹配的程序如下：第一次输入： MaximalMatching g3 执行后得到： 1, 5 ， 2, 6 ， 3, 7 ， 4, 8 。其中点5、6、7、8、9分别代表点Y1、Y2、Y3、Y4、Y5。以上结果表示：第一节课X1为Y1上课、X2为Y2上课、X3为Y3上课、X4为Y4上课；第二次输入：D1 = DeleteEdge g3, 1, 5 ;D2 = DeleteEdge D1, 2, 6 ;D3 = DeleteEdge D2, 3, 7 ;D4 = DeleteEdge D3, 4, 8 ;MaximalMatching D4 运行后得到： 1, 5 ， 2, 8 ， 3, 6 ， 4, 9 。即，第二节课X1为Y1上课（注意：1、5之间有两条边，去掉一条还有一条）、X2为Y4上课、X3为Y2上课、X4为Y5上课；第三次输入：D5 = DeleteEdge D4, 1, 5 ;D6 = DeleteEdge D5, 2, 8 ;D7 = DeleteEdge D6, 3, 6 ;D8 = DeleteEdge D7, 4, 9 ;MaximalMatching D8 运行后得到： 1, 7 , 3, 8 。即，第三节课X1为Y3上课、X3为Y4上课，其他老师轮空；最后第四节课X1为Y4上课，其他老师轮空。方法2 用边染色的方法。输入以下程序：EdgeColoring g3 运行后得到染色结果： 3, 2, 1, 1, 3, 3, 1, 2, 4, 1 。这个结果表示图g3的第1、5、6边染第三种色（边所代表的课程在第3节上课），第2、8边染第2种色（边所代表的课程在第2节上课），第3、4、7、10边染第一种色（边所代表的课程在第1节上课）。图中的边按字典序排列，下面的程序告诉我们边的顺序：ToUnorderedPairs g3 运行后得到结果： 1, 5 , 1, 7 , 1, 8 , 2, 6 , 2, 8 , 3, 6 , 3, 7 , 3, 8 , 4, 8 , 4, 9 。即：e1 = 1, 5 = x1, y1 、e2 = 1, 7 = x1, y3 、e3 = 1, 8 = x1, y4 、e4 = 2, 6 = x2, y2 、e5 = 2, 8 = x2, y4 、e6 = 3, 6 = x3, y2 、e7 = 3, 7 = x3, y3 、e8 = 3, 8 = x3, y4 、e9 = 4, 8 = x4, y4 、e10 = 4, 9 = x4, y5 。其实，x1到y1有两条边，染色按一条对待。所以，以上染色结果表示：（e1，e2，e3，e4，e5，e6，e7，e8，e9，e10）对应染色为（3，2，1，1，3，3，1，2，4，1），染色号码3表示第三节课。所以，以上染色结果即：第一节课X1为Y4上课、X2为Y2上课，X3为Y3上课、X4为Y5上课；第二节课X1为Y3上课、X3为Y4上课、X4为Y4上课、其他老师轮空；第三节课X1为Y1上课、X2为Y4上课、X3为Y2上课、其他老师轮空；第四节课X1为Y1上课、X4为Y4上课、其他老师轮空。其中，第四节课X1为Y1上课，在染色中并不出现，是人工加上去的。例11-4（极小点覆盖问题） 有一个社区街道图如下，选择适当的路口安装消防设施，使得各条街道都有可能使用。在中编制程序如下：W = 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 , 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0 , 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 , 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0 , 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0 , 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0 , 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0 , 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 , 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1 , 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1 , 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0 ; Print “ W = ”, MatrixForm W 运行后得到结果：再输入：Clear g4 g4 = Graph W, -2, 0 , -1, 1 , -1, 0 , -1, -1 , 0, 1 , 0, 0 , 0, -1 , 1, 1 , 1, 0 , 1, -1 , 2, 0 ;ShowLabeledGraph g4 得到图形如下：求解极小点覆盖程序如下：MinimumVertexCover g4 运行后得到： 2, 3, 4, 8, 9, 10 。即，将消防设施安装在路口2、3、4、8、9、10的地方，就能照顾到所有的街道。例11-5（极小支撑树问题） 有一个社区街道图如下，依街道安装自来水管道。问：如何安装，水能送到各点且所用管道总长最短？这可以理解为是求社区图的极小支撑树（Spanning Tree），社区街道边长矩阵及程序如下：W5 = 0, 8, 5, 7, 0, 0, 0, 0, 0, 0, 0 , 8, 0, 0, 0, 6, 2, 0, 0, 0, 0, 0 , 5, 0, 0, 0, 4, 5, 0, 0, 0, 0, 0 , 7, 0, 0, 0, 0, 4, 2, 0, 0, 0, 0 , 0, 6, 4, 0, 0, 0, 0, 4, 0, 0, 0 , 0, 2, 5, 4, 0, 0, 0, 4, 2, 4, 0 , 0, 0, 0, 2, 0, 0, 0, 0, 2, 4, 0 , 0, 0, 0, 0, 4, 4, 0, 0, 0, 0, 4 , 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 5 , 0, 0, 0, 0, 0, 4, 4, 0, 0, 0, 4 , 0, 0, 0, 0, 0, 0, 0, 4, 5, 4, 0 ;Clear g5 g5 = Gra