资源描述：
《运筹学-图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、OPERATIONSRESE运筹学OR31第六章图与网络分析ABCDE引论:哥尼斯堡七桥问题ABCDABcDOR32铁路交通图此图是我国北京,上海等十个城市间的交通图,反映了这十个城市间的铁路分布情况.点表示城市,点间的连线表示两个城市间的铁路线.诸如此类问题还有电话线分布图或煤气管道分布图等.北京济南徐州青岛南京上海连云港郑州武汉天津OR33球队比赛图五个球队比赛,比过的两个队之间用连线相连，还没有比赛的队之间没有连线v5v4v3v2v1OR346.1图的基本概念图是由点和线构成的。点代表所研究的对象，线表示对象间的关系。1、图的分类：无向图，有
2、向图无向图：由点和边所组成的图。表示为G=(V,E).有向图：由点和弧所组成的图。表示为D=(V,A)点的集合用V表示，V={vi}2、图上的基本概念：（1）边：图中不带箭头的连线叫做边(edge)，边的集合记为E={ej}，一条边可以用两点[vi,vj]表示,ej=[vi,vj].弧：图中带箭头的连线叫做弧(arc),弧的集合记为A，A={ak},一条弧也是用两点表示，ak=[vi,vj],弧有方向：vi为始点，vj为终点OR35例1.v7v1v2v3v4e1e2e3e4e5e6e7a9v1v2v3v4v5v6a1a2a8a4a3a5a6a7a1
3、0环：两端点相同的边。多重边：若两点之间有多于一条边，则称这些边为多重边。简单图：无环、无多重边的图。多重图：无环，但允许有多重边的图。e7OR36（2）次：以点u为端点的边的条数，叫做点u的次。悬挂点：次为1的点叫做悬挂点；孤立点：次为0的点叫做孤立点；奇点：次为奇数则称奇点；偶点：次为偶数则称偶点。基本定理：1、图G=(V,E)中，所有点的次之和是边数的两倍，即2、任一图中，奇点的个数为偶数。OR37（3）链：点边交替序列称为链；圈：首尾相连的链称为圈；初等链：链中各点均不同的链；初等圈：圈中各点均不同的圈；简单链：链中边均不同的链；简单圈：圈
4、中边均不同的圈。（4）连通图：任意两点之间至少有一条链的图。连通分图：对不连通的图，每一连通的部分称为一个连通分图。支撑子图：对G=(V,E)，若G’=(V’,E’)，使V’＝V，E’包含于E，则G’是G的一个支撑子图。赋权图：在图中，如果每一条边（弧）都被赋予一个权值wij，则称图G为赋权图。（5）路：在有向图中，如果链上每条弧的箭线方向与链行进方向相同，则称之为路。回路：首尾相接的路称回路OR386.2树与最小生成树1、树的概念与性质树：无圈的连通图称为树。定理：定量3：设图G=（V,E)是一个树，p(G)≥2,则G中至少有两个悬挂点。定量4：
5、图G=（V,E)是一个树的充要条件是G不含圈，且恰有p－1条边。定量5：图G=（V,E)是一个树的充要条件是G是连通图，并且q(G)=p(G)-1.定量6：图G=（V,E)是一个树的充要条件是任意两个顶点之间恰好有一条链。OR392、图的支撑树支撑树：设T=(V,E’)是图G=(V,E)的支撑子图，如果T是一个树，则称T为G的支撑树。定理7：图G有支撑树的充要条件是图G是连通的。求支撑树的方法：破圈法：即任取一个圈，从圈中去掉一条边，对余下的图重复这个步骤，直至图中不含圈为止。避圈法：在图中每次任取一条边，与已经取得的任何一些边不够成圈，重复这个过
6、程，直到不能进行为止。OR3103、最小支撑树最小支撑树：当一个连通图的所有边都被赋权，则取不同边构成的支撑树具有不同的总权数，其中总权数最小的支撑树称为最小支撑树。求最小支撑树的方法：破圈法：在连通图中任取一个圈，去掉一条权数最大的边，在余下的图中重复上述步骤，直至无圈为止。避圈法：将连通图所有边按权数从小到大排序，每次从未选的边中选一条权数最小的边，并使之与已选的边不能构成圈，直至得到最小支撑树。OR311避圈法的基本步骤P259第一步：令i＝1，E0＝空集。第二步：选一条边ei∈E﹨Ei-1,使ei是使（V,Ei-1∪｛e｝）不含圈的所有边e
7、（e∈E﹨Ei-1）中权最小的边。令Ei＝Ei-1∪｛ei｝,如果这样的边不存在，则T=(V,Ei-1)是最小树。第三步：把i换成i＋1，转入第2步。OR3126.3最短路问题引例:单行线交通网：v1到v8使总费用最小的旅行路线。最短路问题的一般描述：对D=（V，A），a=（vi，vj），w（a）=wij，P是vs到vt的路，定义路P的权是P中所有弧的权的和，记为w（P），则最短路问题为：V2(v1,6）路P0的权称为从vs到vt的距离，记为：d（vs，vt）最短路：赋权有向图D=（V，A）中，从始点到终点的权值最小的路称为最短路。OR313最短路
8、算法Dijkstra算法：有向图，wij≥0一般结论：Dijkstra算法基本思想:采用标号法:P标号和T标号P标号：已确
