第14章图论基本概念

最优支撑树问题：某一地区有若干个主要城市，拟修 建高速公路把这些城市连接起来，使得从其中任何一个城 市都可以经高速公路直接或间接到达另一个城市。假设已 经知道了任意两个城市之间修建高速公路的成本，那么应 如何决定在哪些城市间修建高速公路，使得总成本最小？
第14章图论基本概念
3
第十四章 图的基本概念
第14章图论基本概念
7
相关概念
6. 顶点与边的关联关系 ① 关联、关联次数 ②环 ③ 孤立点
7. 顶点之间的相邻与邻接关系
第14章图论基本概念
8
源自文库
相关概念
8. 邻域与关联集 ① vV(G) (G为无向图)
v 的 邻 N (v ) { 域 u |u V ( G ) (u ,v ) E ( G ) u v }
实例
设 V = {v1, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3),
(v2,v5), (v1,v5), (v4,v5)} 则 G = <V,E>为一无向图
第14章图论基本概念
5
有向图
定义14.2 有向图D=<V,E>, 只需注意E是VV 的多重子集 图2表示的是一个有向图，试写出它的V 和 E
图论的作用：
图与计算机：计算机中数据结构，离不开数组、串、各种 链接表、树和图，因此图是计算机中数据表示、存储和运 算的基础
图与网络：
最大流问题：假设从城市P到城市Q的一个公路网， 公路网中每段公路上每天可以通过的汽车的数量有上限， 那么经过该公路网，每天最多可以有多少辆汽车从城市P 开到城市Q？
2 m d(v) d(v) d(v)
v V
v V 1
v V 2
由于2m, d (v) 均为偶数，所以 d (v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
第14章图论基本概念
13
图的度数列
1 . V={v1, v2, …, vn}为无向图G的顶点集，称d(v1), d(v2), …, d(vn)为G的度数列
v 的 闭 N (v ) N 邻 (v ) { v } 域
v 的关联集 I(v){e|e E (G )e与 v关}联 ② vV(D) (D为有向图)
v的后继元 D (v) 集 {u|uV(D)v,u E(D)uv}
v的先驱元 D (v) 集 {u|uV(D)u,v E(D)uv}
v的邻域ND(v)D (v)D (v)
易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可 简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简单图化 的，特别是后者也不是可图化的
第14章图论基本概念
11
握手定理
定理14.1 设G=<V,E>为任意无向图，V={v1,v2,…,vn}, |E|=m, 则
n
d(vi ) 2m
i1
证 G中每条边 (包括环) 均有两个端点，所以在计算G中各顶点 度数之和时，每条边均提供2度，m 条边共提供 2m 度.
定理14.2 设D=<V,E>为任意有向图，V={v1,v2,…,vn}, |E|=m, 则
注意：图的数学定义与图形表示，在同构（待叙）的意义下 是一一对应的
第14章图论基本概念
6
相关概念
1. 图 ① 可用G泛指图（无向的或有向的） ② V(G), E(G), |V(G)|, |E(G)| ③ n阶图：n 个顶点的图
2. 有限图 3. n 阶零图（0条边）与平凡图（1个顶点） 4. 空图——（运算中出现） 5. 用 ek 表示无向边或有向边
2. V={v1, v2, …, vn}为有向图D的顶点集， D的度数列：d(v1), d(v2), …, d(vn) D的出度列：d+(v1), d+(v2), …, d+(vn) D的入度列：d(v1), d(v2), …, d(vn)
3. 非负整数列d=(d1, d2, …, dn)是可图化的，是可简单图化的.
n
n
n
d (v i)2 m , 且d (v i)d (vi) m
i 1
i 1
i 1
此二定理是欧拉1736年给出，是图论的基本定理
第14章图论基本概念
12
握手定理推论
推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数.
证 设G=<V,E>为任意图，令
V1={v | vV d(v)为奇数} V2={v | vV d(v)为偶数} 则V1V2=V, V1V2=，由握手定理可知
第五部分 图论
本部分主要内容 图的基本概念 欧拉图、哈密顿图 树
第14章图论基本概念
1
绪论
图论的历史：
图论的第一篇论文是瑞士数学家欧拉（Euler）发表于1736年出版的
圣彼得堡科学院刊物中。讨论一个所谓Konigsberg Seven Bridges Problem。
第14章图论基本概念
2
绪论
v的闭邻N 域 D(v)ND(v){v}
9. 标定图与非标定图(顶点和边指定编号的）
10. 基图（有向图的有向边改为无向边）
第14章图论基本概念
9
多重图与简单图
定义14.3 (1) 无向图中的平行边及重数
关联一对顶点的边多于一条，条数称为重数 (2) 有向图中的平行边及重数（注意方向性） (3) 多重图 (4) 简单图（无平行边和环）
简单图是极其重要的概念
第14章图论基本概念
10
顶点的度数
定义14.4 (1) 设G=<V,E>为无向图, vV, d(v)——v的度数, 简称度 (2) 设D=<V,E>为有向图, vV,
d+(v)——v的出度 d(v)——v的入度 d(v)——v的度或度数 (3) (G)（最大度）, (G)（最小度） 无向图中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度数为1的点称为悬挂点，关联的边为悬挂边； 奇顶点度与偶度顶点
主要内容 图 通路与回路 图的连通性 图的矩阵表示 图的运算 预备知识 多重集合——元素可以重复出现的集合 无序集——AB={(x,y) | xAyB}
第14章图论基本概念
4
14.1 图
定义14.1 无向图G = <V,E>, 其中 (1) V 为顶点集，元素称为顶点 Vertex (2) E为VV 的多重集，其元素称为无向边，简称边 Edge