[数学]暑假建模培训图与网络模型.ppt

图与网络模型 鲁东大学 魏建新 2012.8.6 图与网络模型 1.欧拉与七桥问题 2.基本概念 3.经典问题 4.重要算法 5.实例练习 1.欧拉与七桥问题(1736) 从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。 2.基本概念 2.1 图与有向图 2.2 赋权图与子图 2.3 图的顶点度 2.4 常见的图类 2.5 路和连通 2.6 图的矩阵表示 2.1 图与有向图 定义 若一个图的顶点集和边集都是有限集，则称其为有限图. 只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图. 定义若图G中的边均为有序偶对 常用术语 2.2 赋权图与子图 定义 若图 的每一条边e 都赋以 2.3 图的顶点度 2.4 常见的图类 路:一个点和边交替序列; 圈:起点和终点重合的路； 树:无圈的简单连通图； 完全图:每一对不同的顶点都有一条边相连的简单图称为完全图； 正则图:顶点度都一样的图； 二部图(偶图):一个图的顶点集可以分解为两个（非空）子集X和Y，使得每条边都有一个端点在X中，另一个端点在Y中；这样一种分类（X，Y）称为图的一个二分类； 完全二部图:完全偶图是具有二分类（X，Y）的简单偶图，其中X的每个顶点都与Y的每个顶点相连。 2.5 路和连通 2.6 图的矩阵表示（图的存储结构或数据结构） 无向(有向)邻接矩阵 赋权图的邻接矩阵 关联矩阵 注：稀疏矩阵 无向(有向)邻接矩阵 赋权图的邻接矩阵 在图的各边上一个数量指标,具体表示这条边的权(距离,单价,通过能力等)---赋权图或网络. 以边长代替邻接矩阵中的元素得到边长邻接矩阵. 用?表示两点之间不能连接 用0表示同一个顶点之间的权 关联矩阵 3.经典问题 3.1 中国邮递员问题 3.2 哈密尔顿问题 3.3 货郎担问题 3.4 四色问题 3.5 稳定的婚姻问题 3.6 覆盖与控制问题 3.7 Ramsey问题 3.8 关键路径问题 3.1 中国邮递员问题 1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。 一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线。 3.2 Hamilton的游戏 著名英国数学家Hamilton在1859年发明的在正十二面体上的游戏:遍历每个顶点恰一次,并最终回到原出发点. 3.3 货郎担(推销员)问题 一个货郎要去若干城镇卖货，然后回到出发地，给定各城镇之间所需的旅行时间后，应怎样计划他的路线，使他能去每个城镇恰好一次而且总时间最短？ 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题． 3.4 四色问题 1852年,毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家着上不同的颜色.”这个结论能不能从数学上加以严格证明呢? 哲学狂人赌命方舟子 黎鸣 南昌人，1950年12月出生，，自称“思想狂徒”、“哲学乌鸦”。1961年毕业于江西大学物理系，后进入中国科技大学研究生院控制论与系统工程专业。长期进行哲学方面的研究。 方舟子　本名方是民，1967年生于福建。1985年考入中国科技大学生物系。1995年获美国密歇根州立大学生物化学博士学位。2000年创办中文网上第一个学术打假网站“立此存照”。 2006年4月20日，哲学狂人黎鸣在其博客上发表了一篇文章，题为《感谢老子，我发现了——“四色”难题终获简洁而绝妙的证明！》。 　 8月9日，哲学狂人黎鸣在自己的博客《方舟子先生，还是让我们来对决吧！》一文中，向“伪科学斗士”方舟子提出以命相搏的生死对决协议。 “如果破解四色定理失败，黎鸣先生愿按照协议，文明地进行自杀；如果破解四色定理成功，方舟子先生愿按照协议，文明地进行自杀。” 对此挑战，方舟子表示“没必要理他，这是他自我炒作，一场闹剧而已！” 关于图的着色 图的着色包括对边、顶点和平面区域的着色。四色问题考虑的是平面区域的着色。 [解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。 3.5 稳定的婚姻问题 有一个著名定理：如果一个村子里每一个女孩都恰好认识k个男孩，并且每一个男孩也恰好认识k个女孩，那么每一个女孩都可以嫁给她认识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩。（ k 正则二部图，一定存在一个完美匹配） 稳定的婚姻问题 但是这样的安排方法不一定是最好的。假如能找到两对夫妇，彼此都更喜欢对方的配偶，那么这样婚姻有潜在的不稳定性。 用图论匹配理