过每一座桥,且仅通过一次回到原地?问题图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文,解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题:例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意,从而在这些问题研究的基础上,又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题随着科学技术的发展,图论在运筹学、网络理论、信息论、控制论和计算机科学等领域都得到广泛的应用。本章首先给出图、简单图、完全图、子图、路和图的同构等概念,接着研究了连通图性质和规律,给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图、树、二部图、平面图和图的着色。有趣的图论问题均分问题有3个没有刻度的桶a.b和c。其容积分别为8升,5升和3升。假定a桶中装满了酒,现可将酒均分成两份,除了3个桶以外,没有任何其他测量工具。试问该怎样均分?(B,C)表示b.c桶装酒的情况有趣的图论问题(0,0)(0,3)(3,0)(5,1)(0,1)(1,0)(1,3)(3,3)(5,0)(2,3)(2,0)(0,2)(5,2)(4,3)(4,0)(5,3)图有趣的图论问题解这是通路问题的一个典型实例。用f表示人,w表示狼,s表示羊,h表示草。集合{f,w,s,h}中能平安在一起的子集有:{f,w,s,h},{f,w,s},{f,s,h},{f,w,h},{f,w},{f,s},{f,h},{w,h},{f},{w},{s},{h}。用顶点表示渡河过程中的状态,状态是二元组:第一元素是集合{f,w,s,h}在渡河过程中留在原岸的子集,第二元素是在彼岸的子集,将一次渡河后代表状态变化的顶点间连边,得图。容易看出,一条路径就是一种渡河方案。有趣的图论问题
全文预览
