运筹学全套课件.pptxVIP

第六章 图与网络分析§ 1．图的基本概念与模型§ 2．树图和图的最小部分树§ 3．最短路问题§ 4．网络的最大流§ 5．最小费用流§1．图的基本概念与模型 一个图（graph）是由一些结点或顶点（ nodes or vertices ）以及连接点的边（edges）构成。记做G = {V,E}，其中 V 是顶点的集合，E 是边的集合。 给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图） 图中的点用 v 表示，边用 e 表示，对每条边可用它所联结的点表示，如图，则有：e1 = [v1 , v1]，e2 = [v1 , v2]或e2= [v2 , v1] 端点，关联边，相邻 若边 e 可表示为e = [vi , vj]，称 vi 和 vj 是边 e 的端点，同时称边 e 为点 vi 和 vj 的关联边，若点 vi , vj 与同一条边关联，称点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称边 ei 和 ej 相邻； 环，多重边，简单图 如果边 e 的两个端点相重，称该边为环，如果两个点之间的边多于一条，称为具有多重边，对无环、无多重边的图称为简单图。 次，奇点，偶点，孤立点 与某个点相关联的边的数目，称为该点的次（或度、线度），记作 d(v)。次为奇数的点称为奇点，次为偶数的点称为偶点，次为零的点称为孤立点。如图：奇点为 v5 ， v3偶点为 v1 , v2 , v4 , v6孤立点为 v6 链，圈，路，回路，连通图 图中有些点和边的交替序列 μ={v0 , e1 , v1 , e2 , … , ek , vk}，若其各边 e1 , e2 , … , ek 各不相同，且任意 vi,t-1 , vit (2 ≤ t ≤ k)都相邻，称 μ 为链，如果链中所有的顶点 v0 , v1 , … , vk也不相同，这样的链成为路，起点和终点重合的链称为圈，起点和终点重合的路称为回路，若在一个图中，每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图为不连通的。 完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有 n 个顶点的完全图，其边数有 1/2[n(n-1)] 条。 如果图的顶点能分成两个互不相交的非空集合 V1 和V2 , 使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1 和V2 之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1 含m 个顶点，V2 含有 n 个顶点，则其边数共 m · n 条。 图 G1={V1 , E1} 和 G2={V2 , E2}，如果有 和 ，称 G1 是 G2 的一个子图，若有则称 G1 是 G2 的一个部分图。注意部分图也是子图，但子图不一定是部分图。部分图子图： 子图，部分图§2．树图和最小部分树 树图（简称树，记作 T(V, E)）是简单连通图。（无圈，无重边） 一. 树的性质 性质1. 任何树中必存在次为1 的点。 次为1的点称为悬挂点，与之关联的边称为悬挂边。 性质2. 具有 n 个顶点的树恰有（n-1）条边。 性质3. 任何具有n 个点、(n - 1)条边连通图是树。 说明： 1. 树中只要任意再加一条边，必出现圈。 2. 树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。 推论. 把图的所有点分成 V 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。 二. 图的最小部分树 如果 G1 是 G2 的部分图，又是树图，则称 G1 是 G2 的部分树（或支撑树）。树图的各条边称为树枝(假定各边均有权重)，一般图 G2 含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树(也称最小支撑树)。 定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最近的，则边 [ i , j ] 一定包含在该图的最小部分树中。 1. 从图中任选一点 vi ，让 vi ∈V ，图中其余点均包含在 中； 2. 从 V 与 的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为[vi , vj]将其加粗，标记为最小部分树中的边。 3. 令 V∪vj→V， - vj→ ； 三. 避圈法和破圈法 寻找最小部分树的方法主要有避圈法和破圈法两种。 避圈法步骤： 4. 重复2、3两步，一直到图中所有点均包含在 V 中。 避圈法另一种做法： 1. 在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边； 2. 在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则