图论-概念-树.pptVIP

图与网络分析 问题提出 应用：生产组织，邮递员问题，通讯网络等。 哥尼斯堡七桥问题 1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。 关系的对称性：两对象之间的关系可互换。 边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，有点和边组成。 表示为： G=（V，E） V--点集合 E--边集合 例：右图 有向图：由点和弧组成。表示为： D=（V，A） V--点集合 A--弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D) 无向图的有关概念 端点: e=[u,v]∈E, 则u,v是e的端点, 称u,v相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点. 定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1--奇点的集合, V2--偶点的集合 链：点边交错系列， 记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 例：右图 有向图的有关概念 基础图: 对D=(V, A), 去掉图上的箭头. 始点和终点: 对弧a=(u,v), u为a的始点, v为a的终点. 链: 点弧交错序列, 若在其基础图中对应一条链, 则称为 D的一条链. 道路:若 是D中的一条链，且 ，t=1,2,…,k-1,称之为从 到 的一条道路。 回路: 的路. 连通图 连通图：任意两点之间至少有一条链。 不连通图： 连通分图：对不连通图，每一连通的部分称为一个连通分图。 支撑子图：对G=（V，E），若G`=(V`,E`), 使V`=V, E`? E, 则G`是G的一个支撑子图（生成子图）. G-v: 图G去掉点v及v的关联边的图. 图的矩阵表示 权矩阵A 邻接矩阵A 欧拉回路（一笔划问题） 欧拉道路：连通图中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。 欧拉回路：若存在一条回路，经过每边一次且仅一次，则称这条路为欧拉回路。 欧拉图：具有欧拉回路的图。 无向连通图G是欧拉图，当且仅当G中无奇点。 有向连通图G是欧拉图，当且仅当G中每个顶点的出次=入次。 中国邮路问题 问题：一个邮递员每天从邮局出发，走遍所负责的片区所有的街道在返回邮局，如何安排送信线路可使所走的总路程最短？ 中国邮路问题转化为寻找欧拉回路，或构造最小欧拉回路问题。 奇偶点作业法 若图中无奇点, 问题已解决; 否则： 构造第一可行方案: 奇点配对, 找奇点间的一条链。 调整可行方案：使重复边总长度下降。 a)最优方案中, 每一边上最多有一条重复边. b)最优方案中, 每个圈上重复边的总权不大于圈总权的一半. 最优性判定: 满足a)和b)两条. 2. 树——特殊的连通图 2.1 树及其性质 例: 电话线架设、比赛程序、组织结构等。 树:连通的无圈的无向图称为树。 树的性质： 图G=（V，E），p个点、q条边下列说法是等价的 （1）G是一个树 （2）G连通，且恰有p-1条边。 （3）G无圈，且恰有p-1条边。 （4）G连通，但每舍去一边就不连通。 （5）G无圈，但每增加一边即得唯一一个圈。 （6）G中任意两点之间恰有一条链(简单链)。 2.2 图的支撑树（生成树） 定义:设图T=(V，E’) 是图G=(V,E)的支撑子图,如果T是一个树, 则称T是G的一个支撑树。 定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。 找图中生成树的方法： 求支撑树的破圈法 找图中生成树的方法： 求支撑树的避圈法 2.3最小支撑树问题 赋权图(网络）: 给图G=(V,E), 对G中的每一条边[vi,vj], 相应地有一个数wij, 则称这样的图为赋权图, wij 称为边[vi,vj]上的权. 支撑树的权:若T=(V,E’) 是G的一个支撑树, E’中的所