运筹学第五章 图与网络理论.pdf

运筹学第五章运筹学第五章 运筹学第五章运筹学第五章 图与网络理论 交大管理学院 杨民助 图与网络理论 图的概念图的概念 图的概念图的概念 网络概念网络概念 网络概念网络概念 网络最短树问题网络最短树问题 网络最短树问题网络最短树问题 网络最短路问题网络最短路问题 网络最短路问题网络最短路问题 网络最大流问题网络最大流问题 网络最大流问题网络最大流问题 图的概念 什么是图 • 图的概念图的概念 图的概念图的概念 • 所谓图所谓图，就是顶点和边的集合，就是顶点和边的集合，点的集合记为，点的集合记为 所谓图所谓图，，就是顶点和边的集合就是顶点和边的集合，，点的集合记为点的集合记为 V ，边的集合记为，边的集合记为E ，则图可以表示为，则图可以表示为：：G ＝＝ ，，边的集合记为边的集合记为 ，，则图可以表示为则图可以表示为：： ＝＝ （（V，，E ），），点代表被研究的事物点代表被研究的事物，边代表事，边代表事 （（，， ），），点代表被研究的事物点代表被研究的事物，，边代表事边代表事 物之间的联系物之间的联系，因此，因此，边不能离开点而独立存，边不能离开点而独立存 物之间的联系物之间的联系，，因此因此，，边不能离开点而独立存边不能离开点而独立存 在，在，每条边都有两个端点每条边都有两个端点。。 在在，，每条边都有两个端点每条边都有两个端点。。 • 在画图时在画图时，顶点的位置，顶点的位置、边和长短形状都是无、边和长短形状都是无 在画图时在画图时，，顶点的位置顶点的位置、、边和长短形状都是无边和长短形状都是无 关紧要的关紧要的，只要两个图的顶点及边是对应相同，只要两个图的顶点及边是对应相同 关紧要的关紧要的，，只要两个图的顶点及边是对应相同只要两个图的顶点及边是对应相同 的，的，则两个图相同则两个图相同。。 的的，，则两个图相同则两个图相同。。 图的概念图的概念 图的表示图的表示 图的概念图的概念 图的表示图的表示 υ = (υ ,υ ,υ ,υ ,υ ,υ ), E = (e , e , e , e , e , e , e , e , e ) 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 e = [υ ,υ ] e = [υ ,υ ] 1 1 2 2 1 2 v 1 e = [υ ,υ ] e = [υ ,υ ] 3 1 4 4 1 3 e e e e e 1