资源描述：
《运筹学图与网络分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第6章图与网络分析第1节图的基本概念与模型图是点与边的集合，记为G={V.E}V是点的集合，有V={vhv2,...,vJ,E是边的集合，有E={q,£2,…，边是两个点0间的连线，有s=[*旳]伙二1,2,・・・,税;心二1,2,・・・,〃)。如图：叼=[V
2、,vI],e2=[vbv2l或切=1>2，叩图屮的点、边的几何展性无意义，有意义的是点、边2间的连接关系。边连接的点称为边的端点。点所连接的边称为点的关联边。同一条边的两个端点，称为相邻。连接同一个端点的两条边，也称为相邻环：两个端点相同的边。上图屮©为环多重边：两点之间多于一条边
3、。上图屮g与厲为多重边。简单图：无环、无多重边的图。若将上图屮匚和s去掉则成为简单图。点的次：与点相关联的边的数量，记为)。也称度、线度。图中,d(y})=4,d(v2)=4,"(v3)=5,r/(v4)=2,J(v5)=l所有点的次之和等于边数的两倍，即工d(*・)=2加。上图屮，所有点的次之和/=
4、为16,边数为80奇点：次为奇数的点。偶点：次为偶数的点。孤立点：次为零的点。链：依次相连的点、边交替序列，且边不存在重复，记为“。如：“[={勺，02川3，%°4，匂*3}，“2={"3，"川2，幺5，巾，幺8川5}路：点无重复的链。如“
5、
6、为路，血则不为路。起点和终点相同的链。如：“3={卩2，纟6，"4，纟7，卩3，£4，卩2}回路：起点和终点相同的路。如“3亦为回路。若图屮每一对点之间均至少存在一条链，则称该图为连通图。否则称该图不连通，或称非连通图。完全图：任意两点Z间均有边相连的简单图。完全图屮边的数量为：也二U。2图屮的顶点分为两个非空集合匕和内，同一集合内任意两点均不相邻，则称该图为偶图，也称二分图。若匕、内之间的每一对顶点均有边和连，则称该图为完全偶图。设匕中有m个顶点,乞中有n个顶点,则完全偶图有mxn条边。子图：包含原图屮部分或全部点和边的图。即，G
7、=
8、{%,£[}和G2={V2，E2}，若VicV2,E1cE2,称G1是G2的一个子图。部分图：包含原图屮全部点和部分边的图。若V
9、=V2,£)o£2,则称Gi是G2的一个部分图。部分图也是子图，但子图不一定是部分图。例1以比赛项Fl为节点，两个项Fl若有同i个运动员参赛则连-条边。在图屮找出•一个点的全序列，使依次排列的点不相邻，即为一个有效的比赛项冃排序。习题6・1以八种化学药站为节点，在不能共储的药站间连接边。将所有点归于若干个集合，使同一集合内任意两点均不相邻，且集合数最少。习题6.2根据给出的旅行链，确定每个点的相邻点及次。根据点
10、之间的相邻关系，首先定位屮间四个次为4的点，然后依次定位其它点。最后沿链模拟行走一次以作检验。习题6.3分别以6门考试课程和6个半天为节点。按题屮的要求，在课程节点和时间节点之间两两连线，最终形成一个偶图，即为考试日程安排。作业5：P169,6.1,6.2,6.3o第二节树图和图的最小部分树树图是龙圈的连通图。连通图：任意两点之问均存在至少一条链。圈：起点与终点相同的链。树图的形状与大自然小的树相似。—、树图的性质性质1任何树图屮必存在次为1的点。反证法，如果所有点次都大于等于2,则可以逐点往下连，必然会形成一个圈。次为1的点称为悬挂点,
11、性质2具有〃个顶点的树图的边数恰好为（介1）条。用归纳法，已矢口n==2,n=3时成立，假设〃二hl吋成立，当〃=代时，去掉-一条悬挂点及悬挂边，则仍为树图，则有n=k-,m=k-2,在该图上加回原来的点和边，则有：n=k,m=k-1o性质3任何具有〃个点、“・1条边的连通图是树图。反证法，若不是树图则必有圈，去掉圈屮的一条边，则仍联通，若此时无圈,则成为树图，而边数小于介1,与性质3矛盾。推论：1.在树图屮任意再加一条边必然会出现圈；2.树图的任意两点间有且仅有一条唯一的链；3.若从树图屮任意去掉一条边，则图不连通。二、图的最小部分树
12、如果G是G2的部分图（G］含有G2的所有点），又是树图，则称Gi是G2的部分树（支撑树、牛成树）。树图的边称为树枝，树枝丄赋以的数值（权重）称为树枝的长度。一个连通图通常具有多个部分树，其屮树枝总长最小的部分树，称为该图的最小部分树（最小支撑树、最小牛成树）。定理1图中任一点Z,若/是与i相邻点中距离最近的点,贝I」边卩，刀一定含在该图的最小部分树内。反证法：设［门］不在最小部分树内，将该边加上，则图屮必出现圈，设图，点的原关联边是［/,k］,应有［z,k］＞［z,j］,因此在树图中加上［门］,去掉卩，幻，该图仍为树图，但树枝总长度减小，
13、所以原来的树不是最小部分树。推论把图屮所有点分成V和卩两个集合，则两集合之间的最短边一定包含在最小部分树内。反证法。卩,刀是卩和卩之间的最短边，但不包含在最小部分树内，加上［「J］则必出现圈,
