第十章图与网络优化(GraphTheoryandNetworkAnalysis),图的基本概念树及最小支撑树最短路问题网络最大流问题最小费用最大流问题中国邮递员问题,图论的起源和发展,1736年，Euler哥尼斯堡七桥问题(KnigsbergBridgeProblem),一笔画问题,1847年，kirchhoff，电网络，“树”；,1852年，四色猜想；,1964年，华罗庚，统筹方法平话。,1857年，Cogley，同分异构，“树”；,1956年，杜邦公司，CPM，关键路线法；,1958年，美国海军部，PERT，计划评审技术；,1962年，管梅谷，中国邮路问题；,第一节图的基本概念,一、几个例子,例1是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。,北京,天津,济南,青岛,武汉,南京,上海,郑州,连云港,徐州,例2分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：,v1,v2,v3,v4,v5
