《运筹学》课程教学资源（PPT课件讲稿）第五章 图与网络分析（5.1）内容框架与图的基本概念

第五章图与网络分析 51内容框架与图的基本概念

第五章 图与网络分析 5-1.内 容 框 架 与 图 的 基 本 概 念

内容框架 图的基本概念(讨论思路 矩阵表示 含元素的个数 特殊的图 边 多简空 重单 G=(V, E) 图图图 点边关系 子图 点的次 连通图 部分树 树

内容框架 一、 图的基本概念（讨论思路） G=（V，E） 子图 矩阵表示 含元素的个数 点的次 边 特殊的图 点边关系 简 单 图 多 重 图 空 图 连通图 部分树 树

矩阵表示「顶点数P边数q 环、简单图 A邻接矩阵 合 B关联矩阵 沙端点 C割集矩阵 L圈矩阵 mGNE)→边=多重一名 平行边 M可达矩阵 D距离矩阵 子 多重图 点的次 子图 术 奇数偶数 空图 点边关系 真部导 孤悬奇偶 子分出 立挂点点 图图子 点点 图 各种链的概念 悬挂边

空 图 G=(V,E) 矩阵表示 A 邻接矩阵 B 关联矩阵 C 割集矩阵 L 圈矩阵 M 可达矩阵 D 距离矩阵 边e=[u,v] 端点 重 合 环 自 回 路 多重边 平行边 简单图 多重图 含 点的次 0 1 奇数 偶数 子图 真 子 图 部 分 图 导 出 子 图 孤 立 点 悬 挂 点 奇 点 偶 点 悬挂边 顶点数p 边数q 点边关系 各种链的概念

点边关系 真部导 子分出 图图子 各种链的概念 图 序列→点边交替序列 简单回路 各种链的念链、开链、闭链(即回路 初等回路 简单链(无重边) 初等链(无重边、无重点) 连通图 通路 有(强连通 向 单侧连通 树 无(弱连通(半道路连接) 部分树 向 (6个等价定义)

点边关系 真 子 图 部 分 图 导 出 子 图 各种链的概念           → 初等链（无重边、无重点） 简单链（无重边） 初等回路 简单回路 链、开链、闭链（即回路） 序列 点边交替序列 各种链的概念 通路 树 (6个等价定义) 连通图 部分树      弱连通（半道路连接） 单侧连通 有 强连通 向 、 无 向

例51:子图 基础图(母图 真子图 5 ● 导出子图 e:部分图 e2 物4 5 (c)

例5-1：子图 基础图(母图) 真子图 部分图 导出子图

例52链、路、树 e es as e e e t e es e g=e2eye8"2e3V4—简单链路(通路) Q2=Vev2a2v34V4—初等链初等路 树 初等回路 =ve1v2esV4e6v5e9v1初等圈

路(通路) 初等路 初等回路 例5-2 链、路、树 1 1 1 2 7 5 8 2 5 4 Q = v e v e v e v e v 2 1 1 2 2 3 4 4 Q = v e v e v e v 3 1 1 2 5 4 6 5 9 1 Q = v e v e v e v e v 简单链 初等链 初等圈 树

两个主要定理 定理1图G中,所有顶点的次的和等于所有 边数的2倍。即 ∑d(v)=2q V∈ 定理2在任一图中,奇点的个数必为偶数。 证明要点:∑d(v)+2(v)=∑l(v) V∈ v∈ v∈ (Ⅴ1、V2分别是图G中次为奇数和偶数的顶点集合)

两个主要定理 定理1 图G中，所有顶点的次的和等于所有 边数的2倍。即 定理2 在任一图中，奇点的个数必为偶数。 证明要点： d v q v V  ( ) = 2   +  =  vV vV vV d(v) d(v) d(v) 1 2 （V1、V2分别是图G中次为奇数和偶数的顶点集合）

定理:(树的六个等价定义) &无圈的连通图; &无圈,q=p-1; &连通,q=p1; &无圈,但增加一条边,可得到一个且仅 个圈; &连通,但舍弃一条边,图便不连通; &每一对顶点之间有一条且仅有一条初等链;

定理：(树的六个等价定义) & 无圈的连通图； & 无圈，q=p-1; & 连通，q=p-1; & 无圈，但增加一条边，可得到一个且仅一 个圈； & 连通，但舍弃一条边，图便不连通； & 每一对顶点之间有一条且仅有一条初等链；

二、图论在网络分析中的应用 弧 有向图 网络有关概念{权 赋权图 网络 最短树问题 最大流问题(标号法) 使用条件 D氏标号法 应用最短路问题列表法(FOnd算法)理解各种算汁求解原理 步骤? 海斯算法 结果分析 最小费用最大流 中心、重心

二、 图论在网络分析中的应用                                中心、重心 最小费用最大流 结果分析？ 步骤？ 求解原理？ 使用条件？ 理解各种算法 海斯算法 列表法（ 算法） 氏标号法 最短路问题 最大流问题（标号法） 最短树问题 应用 网络 赋权图 权 有向图 弧 网络有关概念 Ford D

1.网络 (1)弧点与点之间有方向的连线。 a=(v12v)指从v→>v (2)有向图由点集v和弧集A组成的图 D=(,A (3)权—指与边或弧有关的数量指标。根据实 际背景可赋予不同含义,如距离、时间、 费用、容量等。 (4)赋权图图G=(,E连同边上的权总体。 (5)网络指定了起点、终点和中间点的连通 的赋权有向图G=(V,E)。包括无向网络、 有向网络、混合网络

（3）权——指与边或弧有关的数量指标。根据实 际背景可赋予不同含义，如距离、时间、 费用、容量等。 1．网络 （1）弧——点与点之间有方向的连线。 a = (vi , v j ) 指从 v i → v j ； （5）网络——指定了起点、终点和中间点的连通 的 赋权有向图 。包括无向网络、 有向网络、混合网络。 G = (V , E) （4）赋权图—图 G = (V , E) 连同边上的权总体。 D = (V , A ) （2）有向图——由点集v和弧集A组成的图