第五章图与网络分析 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 + = vV vV vV 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组成的图