图的概念.pptVIP

第六章 图与网络方法 图的概念 树 最短路问题 网络最大流 最小费用流 引言--哥尼斯堡七桥问题 十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。 顶点 (Vertex) 表示研究对象 －－物理实体、事物，一般用 vi 表示 边 (Edge) 表示两个对象之间的某种特定关系 －－顶点间的连线，一般用 ei 表示 ? 图 (Graph) 顶点和边的集合 G＝（V，E） V--点集合 E--边集合 无向图 由顶点和边组成 G=（V，E） 弧(Arc) 顶点与顶点之间有方向的连线 ? 有向图：由点和弧组成 G=（V，A） 3、子图 子图 设： G1=(V1，E1)，G2=(V2，E2) 若： V1?V2 ，又E1?E2 则称G1是G2的子图 生成子图（支撑子图） 设： G1=(V1，E1) G2=(V2，E2) 若： V1＝V2 又E1?E2 则称G1是G2的生成子图 链 点边交错系列， 记为： 圈 的链 简单链（圈） 链（圈）中的边均不相同 初等链（圈） 点均不相同 路 初等链 回路 初等圈 K部图 6、加权图 权 程度的度量，数量描述 线权 给图的边赋以某一数值 点权 给图的顶点赋以某一数值 网络 赋权的图（边权图、点权图、混合图） 7、关联矩阵和邻接矩阵 图与矩阵 在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有——邻接矩阵、关联矩阵、权矩阵等。 邻接矩阵示例 图（1）的邻接矩阵是 图（2）的邻接矩阵是 说明 当图的顶点和边（弧）的编号确定之后，关联矩阵和邻接矩阵就与图建立了确定的一一对应关系，因而可用关联矩阵或邻接矩阵来表达图。一般来说，图的邻接矩阵比关联矩阵小，因而在存贮和计算时用得较多。 二、树 1、 什么是树 树:连通的无圈图称为树，通常用字 母T表示 2、生成树（支撑树） 定义 设图T是图G的一个生成子图,如果T是一棵 树, 则称树T是G的一个生成树（支撑树） 3、最小生成树 支撑树的权 若T=(V,E) 是G的一个支撑树, E中的所有边的权（ ）之和称为支撑树的权, 记为w(T): 最小树（T*） 在赋权图G的所有支撑树中，必有某个支撑树，其所有边的权的和最小，称为最小树。 求最小树的丢边法（破圈法） 求最小树的加边法（避圈法） 欧 拉 图 v1 v2 v3 v5 e2 e3 e5 e1 e6 e7 e8 v1 v2 e1 v3 e2 e4 e4 v4 v4 v5 e6 加边法（避圈法） 思路：从所有边中选出一条权最小的边，并把它纳入树中；在余下的未选边中，再选出一条最小且与已选入树中的边不构成圈的边，将其纳入树中；如此重复，直到树中含有n－1条边为止。 图G 1 5 4 2 4 5 3 1 3 4 4 2 1 5 1 2 生成最小树T 生成最小树T 1 2 3 1 2 1 1 2 1 2 3 1 2 1 1 2 破圈法 避圈法 避圈法的第二种表述 便于编程使用 步骤 1、将图中所有的点分V为V两部分， V——最小生成树内点的集合 V——非最小生成树内点的集合 2 任取一点vi，令vi∈V 3 取V中与V相连的边中一条