1、第八章图与网络分析1本章内容 图的基本概念 树与最小支撑树 最短路问题 最大流问题 最小费用最大流问题 推销员及中国邮路问题2引言1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图。3哥尼斯堡七座桥问题 图4哥尼斯堡七座桥问题 问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。1736年欧拉将这个问题抽象成由点和线构成的 一笔画问题 图形：能否从某一点开始不重复地一笔画出这个图形，最终回到原点，欧拉证明了这是不可能的。这是古典图论中的
2、著名问题之一。5哥尼斯堡七桥 一笔画问题6ACDB引言在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例 8-1 我国北京、上海、重庆等14个城市之间的铁路交通可以通过用点表示城市，用点与点之间的线表示城市之间的铁路线，画出关系示意图。诸如此类还有城市中的市政管道图、民用航空线图等。714个城市之间的铁路交通示意图8太原重庆 武汉 南京徐州 连云港上海郑州石家庄 塘沽青岛济南天津北京第一节 图的基本概念图论中图的基本要素是点和点之间的线。一般来说，通常用点表示研究对象、用点与点之间的线表示研究对象之间的特定关系。在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系并不重要。因此，图论中的图与几何图，工程图等本质上是不同的。9基本概念 图设 V=v1,v2 , vn, E=e1,e2, em,若对于任一 ej E，均有 vs,vt V与之对应，则称VE为图 ，记为 G =(V， E)。 顶点、边、端点、关联边、邻接点在 G中，称 vi为 G的 顶点 ， ej为的 边 ，并记为 ej=vs ,vt =vt ,vs ，称 vs 、 vt 是 ej 的端点 ， ej 是与 vs 、 vt 关联的边 ， vs 、 vt 称为 邻接的点 。10
