资源描述：
《第11章图论问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、图论问题有限个对象（图的顶点）具有某种特定的关系（图的边）就可构造出一个图。它的优点是形彖直观，使得问题的本质结构一冃了然，研究起来极其方便。注意:Mathematica4.0软件包只能处理无向图。例11-1（独立点集问题）有7种化学品xl>x2、x3、x4、x5、x6、x7（在图中用点表示），它们有一些不能放在一起（在图中不能放在一•起的化学品连边表示）:在Mathematica4.0软件包中的命令如下：第一步先打开离散数学的组合子程序包Combinatorica,输入并执行以下程序:«DiscreteMathsCombinatorica'第二步再输入
2、：gl=Graph!{{0,1,0,1,0,0,0},{1,0,1,0,1,0,1},{0,1,0,1,1,1,0},{1,0,1,0,1,0,1},{0,1,1,1,0,1,0},{0,0,1,0,1,0,1},{0,1,0,1,0,1,0}},{{0,1},{1,2},{1,1},{1,0},{2,1},{3,2},{4,1}}］；ShovvLabeledGraph［gl］其中Graph命令生成一个图，其输入形式为：Graph［图的邻接矩阵，图中点的坐标］o在这个化学品存放问题中，只有不连边的化学品才能放在一起，即，要将图的顶点分解为极大独立点集的并
3、，每个极大独立点集占据一个仓库即可。［方法1］逐步分解独立点集法。程序如下：运行后得到结果：{1,3,7}。即{xl,x3,x7}是gl的极大独立点集。然后在gl中将{xl,x3,x7}删除，再求极大独立点集。注意，Mathematica4每次只能删除一个点。于是，令删除点1后的图为g2,原來图gl的顶点{x2,x3,x4,x5,x6,x7}在g2中被重新编号为{1,2,3,4,5,6}。，即x3被编号为x2,余类推。后续程序如下：g2=DeleteVertex[gl,1];g3=DeleteVertex[g2,2];g4=DeleteVertex[g2
4、,5];MaximumIndependentSet[g4]运行后得到结果:{1,2,4}o即，图g4中的顶点{xl,x2,x4}是图gl的顶点{x2,x4,x6},它是极大独立点集。于是得到原来图gl的独立点集之并为：V（gl）={xl,x3,xl}o{%2,x4,%6}u{x5}最后得到只需3间仓库放置这7中化学品即可，储藏方式如下：{xl,x3,x7}放在一间仓库、｛x2,x4,x6｝放在一间仓库、｛x5｝放在一间仓库。另外，我们可以用图gl的色多项式求色数来验证：f=ChromaticPolynomial[gl,z];Print[“f二”，f/.z
5、->l]Print[“f/.z->2=”，]Print[“f/・z・>3二f/・">3]Print[“f/.z->4=f/.z->4]运行后得到结果如下：f/.z->l=0f/.z->2=0f/.z->3=24f/.z->4=552刁二3吋图gl的色多项式取值大于零，表示可以用3种颜色染图gl的顶点，染同色的点Z间不连边。同色点构成图gl的独立点集。由此知道，图G1的色数确实是3（因为图gl的色多项式ff在z=l.z=2时取0值，在z=3时取值大于0）,这说明，图gl的点集至少可分成3个独立点集（分法有24种）。[方法2]染色分解独立点集法。输入以下程序
6、：VertexColoring[gl]执行后得到:｛2,1,2,1,3,1,2｝。即，图gl中的顶点｛xl,x3,x7｝染第二种色,把这三种化学品放在第二间仓库；图gl中的顶点｛x2,x4,x6｝染第一种色，把这三种化学品放在第一间仓库；图gl中的顶点｛x5｝染第三种中色，把这种化学品放在第三间仓库；例11-2（最短路问题）求下列赋权图中顶点xl到xll的最短路:首先输入其权矩阵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
7、,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,U,0,0,4},{0,0,0,0,0,0,0,4,5,4,0}}；WG中的元素Wij表示点&到点Xj的边的距离，0表示此边不存在。求最短路程序如下：Clear[g2]g2=Graph[WG,{{20},{-1,1},{-1,0},{-1,-1},{0,1}
8、,{0,0},{0,-1},{1,1},{1,0},{1,-1},{2,0}}]
