运筹学全套课件.pptxVIP

第八章 图与网络分析图的基本概念最小树问题最短路问题最大流问题最小费用最大流问题 例：七桥问题AB CD问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。 问题：能否从某一点开始一笔画出这个图形，最后 回到原点，而不重复。 例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。问题：他如何走？点：路口；边：两路口之间道路，第i条道路长ei。问题：求一个圈，过每边至少一次，并使圈的长度最 短。 例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家；边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共 边的点有不同的颜色。 第一节 图的基本概念点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。对称关系：桥、道路、边界；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。图：点及边（或弧）组成。 一、图的定义定义1：一个图，是由非空集合V(G)={vi} 和V(G)中 元素的有序对（或无序对）的集合E(G)={ek} 所组成的二元组（ V(G)， E(G) ）所构成。记为 G= （ V(G)， E(G) ） 简记 G=（V，E）其中 V= {vi} 称为点集，vi为点 。 E={ek}称为边集， ek为边（或弧）。 当V，E为有限集时，称G为有限图。否则称为 无限图。 无向图：由点及边构成 ，边[vi，vj]有向图：由点及弧构成，弧（ vi，vj）图G中点集V的顶点个数，记为p (G) ，边数记为q(G),简记p，q。 二、图论中常用术语1. 相邻与关联 若边e=[u，v]∈E，称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关联边。 若两条边有一个公共的端点，则称这两条边相邻。 vivjevi，vj相邻 e 与vi，vj关联vie1e1 与e2相邻vjvke2 点与边关联点与点相邻边与边相邻 2. 简单图与多重图 某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。 无环、无多重边的图称为简单图。多重图：无环、但允许有多重边。v1e1e2e3v2v3e5e4v4 3. 次与悬挂点、孤立点图G中以点v为端点的边的数目，称为v在G中的次， 记为d（v）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次为1 的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。v1e1e2e3v2v3e5e4v4 定理1 图G=（V，E）中，所有点的次之和为边数的两倍， 即4. 奇点与偶点次为奇数的点称为奇点，否则称为偶点。定理2 任一图中奇点的个数为偶数。 证明：设v1和v 2分别是G中的奇点和偶点的集合，由定理1，有因 是偶数， 也是偶数，故必为偶数。即在一个图中奇点的个数必为偶数。 5. 链与圈 给定一个图G=（V，E），G中的一个点、边交错序列（vi1，ei1，vi2，ei2，…，vik-1，eik-1，vik），如果满足eit=[vit，vit+1]（t=1，2，…，k-1），则称为一条联接vi1和vik的链，记为?=（vi1，vi2，…，vik）。 链（vi1，vi2，…，vik）中，若vi1=vik ，称之为一个圈，记为C= （vi1，vi2，…，vik-1， vi1 ） 。初等链：链中点都不同。简单链：链中边都不同。（边能否相同？）（点能否相同？） v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链：?1=（v2，v1，v3，v6，v4，v3，v5）初等链：?2=（v2，v1，v3，v5）简单圈：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ）初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ） 有向图中，不考虑弧的方向，有类似链（圈）的定义。当链（圈）上弧的方向一致时，称为路(回路) 6. 子图与支撑子图定义2 给定图G=（V，E），若图G’=