当前位置：文档之家 › 离散数学 图的概念与表示

离散数学 图的概念与表示

  • 格式：ppt
  • 大小：350.00 KB
  • 文档页数：79

下载文档原格式

  / 79

合集下载

离散数学课件_8 图的基本概念

离散数学课件_8 图的基本概念
13 2014-9-23
返回本章首页

返回本章首页
9 2014-9-23
第六节 哈密尔顿图(2)
(1) 设 G=(V,E) 是哈密尔顿图，则对 V 的任 意非空子集 S均有W(G-S) ≦|S|, 其中GS表示在G中删除S中的点以及以S为端点 的边后所构成的图； W(G-S) 表示 G-S 的 连通分支数; (2)设G=(V,E)是n阶无向简单图，若对G中 任 意 不 相 邻 的 顶 点 u,v 都 有 d(u)+d(v) ≧n-1,则G存在哈密尔顿路，因此G是半 哈密尔顿图； (3) 设 G 是 n 阶简单图，则是哈密尔顿图当 且仅当其闭包是哈密尔顿图.

返回本章首页
11 2014-9-23
第七节 二分图(2)
(2)图G的匹配M是最大匹配当且仅当G不含 M的可扩路; (3)设G=(V,E)为二分图,顶点划分为V= V1 ∪ V2 ,则G存在饱和V1的每个顶点匹配 的充要条件是对任何S V1均有 |N(S)|≧|S|； 3.算法：匈牙利算法，解决了二分图的匹 配问题。

返回本章首页

6 2014-9-23
第五节 欧拉图(1)
欧拉图是一类非常著名的图，之所以如 此，不仅是因为欧拉是图论的创始人， 更主要是欧拉图具有对边（弧）的“遍 历性”. 1.概念有:欧拉路,欧拉图,半欧拉路,半欧 拉图,割边等；

返回本章首页
7 2014-9-23
第五节 欧拉图(2)
2.结论有:(1)无向连通图G是欧拉图的充要 条件是G中每个顶点的度均为偶数； (2)设G是无向连通图，则G是半欧拉图 的充要条件是G恰含有两个奇数度点. 3.算法:在欧拉图中找欧拉路的Fleury算法.
第八章 图的基本概念

离散数学7[1].1-3

离散数学7[1].1-3

离散数学
31
定理
定理 一个连通无向图G =〈V,E〉的某一点v是 图G的割点，当且仅当存在两个节点u和w， 使得节点u和w的每一条路都通过v。
离散数学
32
三、有向图的连通性
三、有向图的连通性 定义 设G＝<V，E>是一个有向图，对vi，vjV，从vi到vj如
存在一条路，则称结点vi到vj是可达的。 在有向图中，如从vi到vj可达，但从vj到vi则不一定是可达的。
3) 在一个图中，关联结点vi和vj的边e，无论是有向的还是无 向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点， 否则称为不邻接的；
离散数学
2
续：
续： 4) 关联于同一个结点的两条边称为邻接边； 5) 图中关联同一个结点的边称为自回路(或环)； 6) 图中不与任何结点相邻接的结点称为孤立结点； 7) 仅由孤立结点组成的图称为零图； 8) 仅含一个结点的零图称为平凡图； 9) 含有n个结点、m条边的图称为(n，m)图；
证明 若G不连通，则k(G)=λ(G)=0，故上式成立。 若G连通， ①证明λ(G)≤δ(G)。若G是平凡图，则λ(G)=0≤δ(G)，若
G是非平凡图，则因每一结点的所有关连边必含一 个边割集，故λ(G)≤δ(G)。
离散数学
30
续：
②再证k(G)≤λ(G) .设λ(G)=1，即G有一割边，显然此时k(G)=1，上式成立。 .设λ(G)≥2，则必可删去某λ(G)条边，使G不连通，而删除λ(G)-
δ(G)最小度，Δ(G)最大度
定义 在图G＝<V，E>中，对任意结点vV，若度数deg(v)为奇 数，则称此结点为奇度数结点，若度数deg(v)为偶数，则 称此结点为偶度数结点。

第7章 图论 [离散数学离散数学(第四版)清华出版社]

第7章 图论 [离散数学离散数学(第四版)清华出版社]

6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e

2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)

离散数学7-1图论

离散数学7-1图论

图7-1.9 不同构的图
作业
P279 (1) (4)
如图7-1.6中的(a)和(b)互为补图。
[定义] 子图(subgraph) 设图G=<V,E>，如果有图G’= <V’,E’>，若有 V’ V ，E’ E，则称图G’是图G的子图。 [定义] 生成子图(spanning subgraph) 如果图G的子图G’包含G的所有结点,则称该图 G’为G的生成子图。如图7-1.8中G'和G"都是 G的生成子图。
[定义] 相对于图G的补图 设图G'＝〈V',E'〉是图G＝〈V,E〉的子图,若 给定另外一个图G"＝〈V",E"〉使得E"＝EE', 且 V" 中仅包含 E"的边所关联的结点。则 称G"是子图G'的相对于图G的补图。
图7-1.7 (c )为(b)相对于(a)的补图
如图 7-1.7 中的图 (c) 是图 (b) 相对于图 (a) 的补 图。而图 (b) 不是图 (c) 相对于图 (a) 的补图 , 因为图(b)中有结点c。在上面的一些基本概 念中,一个图由一个图形表示,由于图形的结 点的位置和连线长度都可任意选择 , 故一个 图的图形表示并不是唯一的。下面我们讨 论图的同构的概念。
表7-1.1
结 点 出 度 入 度
a 2 0
b 1 1
c 0 2
d 1 1
结 点 出 度
入 度
v1 1 1
v2 0 2
v3 2 0
v4 1 1
分析本例还可以知道 , 此两图结点的度数也 分别对应相等,如表7-1.1所示。
两图同构的一些必要条件: 1.结点数目相等; 3.边数相等; 3.度数相等的结点数目相等。 需要指出的是这几个条件不是两个图同构的 充分条件,例如图7-1.9中的(a)和(b)满足上 述的三个条件,但此两个图并不同构。

《离散数学》第6章 图的基本概念

《离散数学》第6章 图的基本概念

E ' E )。
生成子图—— G ' G 且 V ' V 。
导出子图 ——非空 V ' V ，以 V ' 为顶点集， 以两端均在 V ' 中的边的全体为边集的 G 的 子图，称 V ' 的导出子图。 ——非空 E ' E ，以 E ' 为边集，以
E ' 中边关联的顶点的全体为顶点集的 G 的子
0 vi与ek 不关联 无向图关联的次数 1 vi与ek 关联1次 2 v 与e 关联2次(e 为环) i k k
1 vi为ek的始点 有向图关联的次数 0 vi与ek 不关联 1 v 为e 的终点 (无环) i k
点的相邻——两点间有边，称此两点相邻 相邻 边的相邻——两边有公共端点，称此两边相邻
孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边 为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。
(3) 平行边——关联于同一对顶点的若干条边 称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。
简单图——不含平行边和环的图。
如例1的(1)中，
第六章 图的基本概念 第一节 无向图及有向图
内容：有向图，无向图的基本概念。
重点：1、有向图，无向图的定义， 2、图中顶点，边，关联与相邻，顶点 度数等基本概念，
3、各顶点度数与边数的关系
d (v ) 2m 及推论，
i 1 i
n
4、简单图，完全图，子图， 补图的概念， 5、图的同构的定义。
一、图的概念。 1、定义。 无序积 A & B (a, b) a A b B 无向图 G V , E E V & V ， E 中元素为无向边，简称边。 有向图 D V , E E V V ， E 中元素为有向边，简称边。

《离散数学》图论 (上)

《离散数学》图论 (上)
12
无向图与有向图
v2
e1
e2
e3
v3
e4
v1
e5 (e1)={( v42, v24 )}
v4
(e2)={( v32, v23 )} (e3)={( v3, v4 )}
(e4)=({ v43, v34 )}
(e5)=({ v4,}v4 )
13
无向图与有向图
A B C
D E F
14
无向图与有向图
第八章 图论
第八章 图论
§8.1 基本概念
§8.1.1 无向图、有向图和握手定理 §8.1.2 图的同构与子图 §8.1.3 道路、回路与连通性 §8.1.4 图的矩阵表示
§8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 顶点支配、独立与覆盖
2
无向图与有向图
3
无向图与有向图
一个无向图（undirected graph, 或graph） G 指一个三元组 (V, E, )，其中
vV
vV
24
特殊的图
假设 G=(V, E, ) 为无向图，若 G 中所有 顶点都是孤立顶点，则称 G 为零图（null graph）或离散图（discrete graph）；若 |V|=n，|E|=0，则称 G 为 n 阶零图 所有顶点的度数均相等的无向图称为正 则图（regular graph），所有顶点的度数 均为 k 的正则图称为k度正则图，也记作 k-正则图 注：零图是零度正则图
19
握手定理
定理（图论基本定理/握手定理）
假设 G=(V, E, ) 为无向图，则deg(v) 2 E ， vV
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。

离散数学第8章 图论

离散数学第8章 图论
ij
为d（vi，vj）。
8.2
图的矩阵表示
一、图的邻接矩阵 二、图的连接矩阵
三、图的关联矩阵
二、图的连接矩阵 定义 8-9 设图 G= （ V ， E ），其中 V={v1 ，
v2 ， … ， vn } ， n 阶方阵 C= （ cij ），称为图 G 的连接 矩阵，其中第i行j列的元素
1 c ij 0
利用邻接矩阵，我们可以 （1）判断G中任意两个结点是否相连接；
方法是：对 l=1，2，…，n–1，依次检查Al的（i，j）
项元素
(l （ ) ij）是否为0，若都为0，那么结点v 与v 不 a ij i j
相连接，否则vi与vj有路相连接。 （2）计算结点vi与vj之间的距离。
(1) ( 2) ( n 1) 中至少有一个不为0， 若 aij , aij , , aij 则可断定vi与vj相连接，使 a (l ) 0 的最小的 l 即
若中有相同的结点，设为ur= uk（r<k），则子路ur+1…uk可以从 中删去而形成一条较短的路= viu1…ur uk+1…uh–1 vj，仍连接vi到 vj 。 若中还有相同的结点，那么重复上述过程又可形成一条 更短的路，…。这样，最后必得到一条真路，它连接vi到vj， 并短于前述任一非真路。因此，只有真路才能是短程。
非真 生成
真 生成
真 非生成
非真 非生成
真 非生成
七、路与回路 定义:图G中l条边的序列{v0，v1}{v1，v2}…{vl–1，vl}称为连
接v0到vl的一条长为 l 的路。它常简单地用结点的序列 v0v1v2…vl–1vl来表示。其中v0和vl分别称为这条路的起点和终点。 开路：若v0vl，则称路v0v1v2…vl–1vl为开路； 回路：若v0=vl，则称路v0v1v2…vl–1vl为回路； 真路：若开路v0v1v2…vl–1vl中，所有结点互不相同（此时所有 边也互不相同），则称该路为真路； 环：在回路v0v1v2…vl–1v0中，若v0，v1，v2，…，vl–1 各不相同 （此时所有边也互不相同），则称该回路为环。

离散数学——图论

离散数学——图论

2021/10/10
11
哥尼斯堡七桥问题
❖ 把四块陆地用点来表示，桥用点与点连线表 示。
2021/10/10
12
❖ 欧拉将问题转化为：任何一点出发，是否存在通过 每条边一次且仅一次又回到出发点的路？欧拉的结 论是不存在这样的路。显然，问题的结果并不重要， 最为重要的是欧拉解决这个问题的中间步骤，即抽 象为图的形式来分析这个问题 。
2021/10/10
2
图论的发展
❖ 图论的产生和发展经历了二百多年的历史， 从1736年到19世纪中叶是图论发展的第一阶 段。
❖ 第二阶段大体是从19世纪中叶到1936年，主 要研究一些游戏问题：迷宫问题、博弈问题、 棋盘上马的行走线路问题。
2021/10/10
3
❖ 一些图论中的著名问题如四色问题(1852年)和哈密 尔顿环游世界问题(1856年)也大量出现。同时出现 了以图为工具去解决其它领域中一些问题的成果。
❖ P（G）表示连通分支的个数。连通图的连通 分支只有一个。
2021/10/10
40
练习题---图的连通性问题
❖ 1.若图G是不连通的，则补图是连通的。 ❖ 提示：直接证法。
根据图的不连通，假设至少有两个连通分 支；任取G中两点，证明这两点是可达的。
2021/10/10
41
❖ 2.设G是有n个结点的简单图，且 |E|>(n-1)(n-2)/2，则G是连通图。
❖ 例子
2021/10/10
29
多重图与带权图
❖ 定义多重图：包含多重边的图。 ❖ 定义简单图：不包含多重边的图。 ❖ 定义有权图：具有有权边的图。 ❖ 定义无权图：无有权边的图。
2021/10/10
30

离散数学第七章图的基本概念

离散数学第七章图的基本概念

4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

离散数学第讲7

离散数学第讲7

无向图 <V,E> (2) 若|V(G)| 、|E(G)|均为有限数，则称G为有限图。
一个 为A与B的无序积，记作A&B.
是一个有序的二元组
，记作G， 其中
1 , vi可达vj
第十四章 图的(基1本)概念V≠φ称为顶点集，其元素称为顶点或结点。
第十四章 图的基本概念
第十四章 图的(基2本)概念E称为边集，它是无序积V&V的多重子集，其元素称为
所有边互不相同），则称此回路为基本回路或者初级 则V1∪ V2 =V, V1∩V2= φ,由握手定理知
若回路中的所有边e1，e2，…，ek互不相同，则称此回路为简单回路或一条闭迹；
回路、圈。 26 设有向图D=<V,E>中无环, V={v1,v2,…,vn}, E={e1,e2,…,em}, 令aij(1)为顶点vi与邻接到顶点vj边的条数，称(aij(1))n×n为D的邻接矩
第十四章 图的基本概念
例14.1 画出下列 图形。
v1。
。v2
(1) G=<V,E>,其中
V={v1,v2,v3,v4,v5},
v3
。
(1)
E={(v1,v1), (v1,v2), (v2,v3),
v4 。
。v5
(v2,v3), (v1,v5),
(v2,v5), (v4,v5)}。
(2) D=<V,E>,其中
顶点的度数均小于3,问G中至少有多少个顶点?
第十四章 图的基本概念
定义14.5完全图
1. 设G＝<V,E>为一个具有n个结点的无向简单图，如 果G中任一个结点都与其余n-1个结点相邻接，则称 G为无向完全图，简称G为完全图，记为Kn。

离散数学(第二版)第8章图的基本概念

离散数学(第二版)第8章图的基本概念

第八章 图的基本概念
用反证法，设G中各顶点的度数均不相同，则度数列 为0，1，2，…，n-1，说明图中有孤立顶点，这与有n-1度 顶点相矛盾(因为是简单图)，所以必有两个顶点的度数相 同。
2. 子图 在深入研究图的性质及图的局部性质时，子图的概念 是非常重要的。 所谓子图， 就是适当地去掉一些顶点或 一些边后所形成的图，子图的顶点集和边集是原图的顶点 集和边集的子集。
第八章 图的基本概念
一般称长度为奇数的圈为奇圈，称长度为偶数的圈为 偶圈。 显然，初级通路必是简单通路，非简单通路称为复 杂通路。 在应用中，常常只用边的序列表示通路，对于 简单图亦可用顶点序列表示通路，这样更方便。
第八章 图的基本概念
定理8.2.1 在一个n阶图中，若从顶点u到顶点v(u≠v) 存在通路， 则必存在从u到v的初级通路且路长小于等于n1。
第八章 图的基本概念
图8.1.2 图与子图
第八章 图的基本概念
3. 补图 定义8.1.3 G为n阶简单图，由G的所有顶点和能使G 成为完全图的添加边所构成的图称为G的相对于完全图的 补图，简称G的补图，记作。 【例8.1.6】图8.1.3(a)中的G 1是G1相对于K5的补图。 图8.1.3(b)中的G 2 是G2相对于四阶有向完全图D4的补图。 对于补图，显然有以下结论： (1) G与 G 互为补图，即 G =G。 (2) E(G)∪E(G )=E(完全图)且E(G)∩E( G )= 。 (3) 完全图与n阶零图互为补图。 (4) G与G 均是完全图的生成子图。
所谓子图就是适当地去掉一些顶点或一些边后所形成的图子图的顶点集和边集是原图的顶点第八章图的基本概念定义812设gvegve均是图同为第八章图的基本概念导出的导出子图记作gv第八章图的基本概念例815在图812中g均是g的真子图其中g第八章图的基本概念图812第八章图的基本概念补图定义813g为n阶简单图由g的所有顶点和能使g成为完全图的添加边所构成的图称为g的相对于完全图的补图简称g的补图记作

《离散数学》课件第14章图的基本概念

《离散数学》课件第14章图的基本概念
像这种形状不同，但本质上是同一个图的现象称 为图同构。
定义14.5（图同构）设两个无向图G1=<V1，E1>， G2=<V2，E2>，如果存在双射函数f：V1→V2，使得对 于 任 意 的 e=（vi，vj）∈E1 当 且 仅 当 e’=（f(vi)， f(vj)）∈E2，并且e与e’的重数相同，则称G1和G2是 同构的，记作G1≌G2。
若vi=vj，则称ek与vi的关联次 数为2；
若vi不是ek的端点，则称ek与vi 的关联次数为0。
无边关联的顶点称为孤立点 （isolated vertex） 。
19
定义(相邻) 设无向图G=<V，E>， 若∃et∈E且et=（vi,vj），则称vi和vj是相邻的 若ek,el∈E且有公共端点，则称ek与el是相邻的。
素称为有向边，简称边。 由定义，有向图的边ek是有序对<vi，vj>，称vi，
vj是ek的端点，其中vi为ek的始点（origin），vj为ek 的终点（terminus）。
当vi=vj时，称ek为环，它是vi到自身的有向边。
11
每条边都是无向边的图称为无向图（undirected graph）。
定义(邻接与相邻) 设有向图D=<V，E>， 若∃et∈E且et=<vi,vj>，则称vi邻接到vj，vj邻接 于vi。 若ek,el∈E且ek的终点为el的始点，则称ek与el是相 邻的。
20
定义14.4（度） 设G=<V，E>为一无向图，∀v∈V，称 v作为边的端点的次数之和为v的度数，简称为度 （degree），记为d(v)。
定理14.2 （有向图握手定理）设D=<V，E>为任 意的有向图，V={v1,v2,…,vn}，|E|=m，则

离散数学ch2 (10)

离散数学ch2 (10)

i
1
i
证明：由定理14.1，必要性显然 充分性：由已知条件可知，d中有2k个奇数，不妨设它们为 d1, d2, …, dk , dk+1 ， dk+2 …, d2k，构造以d为度数列的n阶无 向图G=<V,E>,如下： V={v1, v2, …, vn}，在顶点vr和vr+k之 间连边，r=1,2，…, k，若di为偶数，令di’= di ，若di为奇数， 则令di’= di -1，得到d’=(d1’, d2’, …, dn’),则di’均为偶数， 再在vi处画di’/2条环，i= 1,2，…, n, 这就证明了d是可图 化的 易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，而(1, 2, 3, 4, 5)，(3, 3, 3, 4) 不是可图化的
第五部分 图论
本部分主要内容 图的基本概念 欧拉图、哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色
1
图论的研究可以追溯到1736 年, 图论中几个重要的结论也 是在19 世纪得到的，但图论引起人们兴趣是20 世纪20 年代。 应用：计算机科学、化学、运筹学、经济学、语言学等。 内容：图的基本概念包括路径和环，欧拉回路，哈密尔顿 回路/货郎担问题，图同构、平面图等。
9
相关概念
7. 设D=<V,E>为有向图， ek =<vi,vj>E ，称vi,vj为ek的端点， vi为ek的始点，vj为ek的终点， ek与vi（vj）关联，若vi =vj， 则称ek为D中的环 8. 若两个顶点之间有一条有向边，则称这两个顶点相邻， 若两条边中一条边的终点是另一条边的始点则称这两条 边相邻 图（无向的或有向的）中没有边关联的顶点称作孤立点

离散数学-第七章-图论

离散数学-第七章-图论

5
离 例1、G1=<V,E>
散 数
V＝{v0, v1, v2,v3}
学 E＝{(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2，v3)}
v0
v3
v1
第
七
章
v2
图
论
4/24/2020 2:55 PM
G1
6
离 例2、
散 数 学
G2=<V,E> V＝{v0, v1, v2,v3}
中的所有边，称为删除E´ 。
(2)设vV，用G-v表示从G中去掉v及所关联的 一切边，称为删除结点v；又设V´ V，用G-V´ 表示从G中删除V´中所有结点，称为删除V´ 。
学 u,v之间存在路，则称u,v是连通的，记作uv 。
定义2.3 设无向图Ｇ是平凡图或G中任何两个结 点都是连通的，则称G为连通图，否则称G为非连 通图或分离图。
第
任意一个连通无向图的任两个不同结
七 点都存在一条通路。
章
图
论
4/24/2020 2:55 PM
38
离
非连通图Ｇ可分为几个不相连通的子图，
七 章
边，构成一个无向重图，问题化为图论中简单道路
的问题。
图
论
4/24/2020 2:55 PM
3
离 一、图的基本概念
散 数 学
旧金山
丹佛
洛杉矶
第 七 章
图
论
4/24/2020 2:55 PM
底特律
芝加哥
纽约 华盛顿
4
离
散 设A、B是两个集合，称
数
学
A&B={{a,b}|aA, bB}

离散数学 第7章 图论

离散数学 第7章 图论

v2 v3
v4
v3
(b) 图G
v3 (c) 图G’
(a) 完全图K5
图G是图G’ 相对于图K5的补图。 图G’不是图G 相对于图K5的补图。（图G’中有结点v5 ）
例：276页图7-1.7 图(c)是图(b)相对于图(a)的补图。 图(b)不是图(c)相对于图(a)的补图。
25
7-1
图的同构
图的基本概念
8
7-1
图的基本概念
1.无向图：每条边均为无向边的图称为无向图。 2.有向图：每条边均为有向边的图称为有向图。 3.混合图：有些边是无向边，有些边是有向边的图称 为混合图。
v1 (孤立点) v5 V1’
v1 v2
v2
v4 v3 (a)无向图
V2’
V3’ (b)有向图 V4’
v4 v3 ( c ) 混合图
17
7-1
图的基本概念
三、特殊的图
定义4 含有平行边的图称为多重图。 不含平行边和环的图称为简单图。
定义5 简单图G=<V，E>中，若每一对结点间均有边 相连，则称该图为完全图。
无向完全图：每一条边都是无向边 不含有平行边和环 每一对结点间都有边相连
有n个结点的无向完全图记为Kn。
18
7-1
图的基本概念
推论 在一个具有n个结点的图中，如果从结点vj 到结点vk存在一条路，则从结点vj到结点vk 必存在一条边数小于n的通路。
32
7-2
路与回路
定理7-2.1的证明 如果从结点vj到vk存在一条路，该路上的结点序列 是vj…vi…vk，如果在这条中有l条边，则序列中必有 l+1个结点，若l>n-1，则必有结点vs，它在序列中不止 出现一次，即必有结点序列vj…vs…vs…vk，在路中去 掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比 原来的路边数要少，如此重复进行下去，必可得到一 条从vj到vk的不多于n-1条边的路。

图的概念术语

图的概念术语

图的概念术语图是离散数学中的一种数学模型，用来描述对象之间的关系。

图由节点（顶点）和边组成，节点表示对象，边表示对象之间的关系。

在图中，一对节点之间的关系可以有多种不同的定义方式，这决定了图的种类和图的应用领域。

图论是研究图的性质、结构和算法的学科。

图的概念术语包括以下内容：1. 节点（顶点）：图中的基本元素，用来表示对象。

节点可以是任意类型的数据，比如人、城市、物品等等。

2. 边：图中节点之间的关系，用来表示节点之间的连接或者直接关系。

边可以是有向的（有方向的）或无向的（无方向的），分别用箭头或无箭头表示。

3. 有向图：边是有方向的图，表示节点之间具有指向性的关系。

如果节点A指向节点B，表示A与B有关联，但B与A不一定有关联。

4. 无向图：边是无方向的图，表示节点之间的关系是相互的，没有指向性。

如果节点A与节点B相连，表示A与B有关联，同时B与A也有关联。

5. 权重（边的权值）：边上的值或者权重，用来表示两个节点之间的关系的程度。

可以是一个实数或其他类型的值。

6. 路径：在图中，通过多个节点和边连接而成的序列。

路径可以是简单路径（不重复经过节点）或者回路（首尾相连）。

7. 连通图：在无向图中，如果任意两个节点之间都存在路径相连，则称该图为连通图。

如果部分节点之间没有路径相连，则称为非连通图。

8. 强连通图：在有向图中，如果任意两个节点之间都存在路径相连（可以是单向或双向），则称该图为强连通图。

9. 子图：图的一个子集，包含了原图的一部分节点和边。

10. 图的度：一个节点的度是指与该节点相连的边的数量。

对于有向图，分为入度和出度，分别表示指向该节点和指出该节点的边的数量。

11. 图的邻接：两个节点之间直接相连，也即存在一条边直接连接这两个节点。

如果两个节点之间没有直接边相连，则称为不邻接。

12. 连通分量：无向图中的最大连通子图，其中任意两个节点之间都存在路径相连。

13. 图的密度：图中边的数量与节点数量的比值，用来描述图的紧密程度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

与它自身的一条边，称为环。环的方向是无意
义的。
如果把图G中的弧或边总看作联结两个结点，则 图G可简记为G=<V，E>，其中V是非空结点集，E是联 结结点的边集或弧集。 定义16.1.2 在图G=<V，E>中，如果每条边都是
弧，该图称为有向图；若每条边都是无向边，该图G称
为无向图；如果有些边是有向边，另一些边是无向边， 图G称为混合图。
一般说来，证明两个图是同构的并非 是轻而易举的事情，往往需要花些气力。 请读者证明图16.1.13中两个图是同构的。
根据图的同构定义，可以给出图同构的必 要条件如下： (1) 结点数目相等； (2) 边数相等；
(3) 度数相同的结点数目相等。
但这仅仅是必要条件而不是充分条件。例如 图10.1.14中(a)与(b)满足上述三个条件，然而并不 同构。因此在(a)中度数为3的结点x与两个度数为1
结点，而边(或弧)的数目称为链(或路)的长度。若v0=vm
时，该链(或路)称为圈(或回路)。
定义16.2.2 在一条链(或路)中，若出现的
边(或弧)都是不相同的，称该链(或路)为简单链
(或简单路)；若出现的结点都是不相同的，称该
链(或路)为基本链(或基本路)。
显然，每条基本链(或基本路)必定是简单
的结点邻接，而(b)中度数为3的结点y仅与一个度
数为1的结点邻接。
寻找一种简单有效的方法来判定图题。
图 10.1.13
返回
图 1.1.14
返回
16.2 链(或路)与圈(或回路)
在无向图 ( 或有向图 ) 的研究中，常常考虑
从一个结点出发，沿着一些边(或弧)连续移动而
达到另一个指定结点，这种依次由结点和边(或
弧)组成的序列，便形成了链(或路)的概念。
定义16.2.1 给定无向图(或有向图)G=<V，E>。令
v0，v1，…，vm∈V，边(或弧)e1，e2，…，em∈E，其中
vi-1，vi是ei的结点，交替序列v0e1v1e2v2…emvm称为连接v0 到vm的链(或路)。v0和vm分别称为链(或路)的始结点和终
<E2>或G〔E2〕。
定义 16.1.10
设图 G1=<V1 ， E1> 和图
G2=<V2 ， E2> 是图 G=<V ， E> 的子图。如
果 E2=E-E1 且 G2=<E2> ，则称图 G2 是相对
于图G的子图G1的补图。
定义16.1.11 给定图G=<V，E>，若存在图
G1=<V，E1>，并且E1∩E=和图<V，E1∪E>是
链(或简单路)。
定义16.2.3 在一圈(或回路)中，若出现的每条边
(或弧)恰好一次，称该圈(或回路)为简单圈(或简单回路)；
若出现的每个结点恰好一次，称该圈(或回路)为基本圈 (或基本回路)。 可以看出，对于简单图来说，链(或路)和圈(或回 路)能够仅用结点序列表示之。
定理 16.2.1 本链(或基本路)。
定义16.1.1 一个图G定义为一个三元组<V， E，φ>，记作G=<V，E，φ>。其中V是个非空 有限集合，它的元素称为结点；E也是个有限集 合，其元素称为边，而φ是从E到V中的有序对
或无序对的映射。
由定义可知，图G中的每条边都与图中的
无序或有序结点对相联系的。若边e∈E与无序
结点对〔vi，vj〕相联系，则φ(e)=〔vi，vj〕， 这时边e称为无向边，有时简称为边；若边e∈E 与有序结点对<vi，vj>相联系，则φ(e)=<vi，vj>， 此时边e称为有向边或弧，vi称为弧e的始结点， vj称为弧e的终结点。
若结点vi与vj由一条边(或弧)e所联结，则称
结点vi和vj是边(或弧)e的端结点；同时也称结点
vi与vj是邻接结点，记作vi adj vj；否则为非邻接 结点，记作vi nadj vj；也说边(或弧)e关联vi与vj 或说结点vi与vj关联边(或弧)e。关联同一个结点 的两条边或弧称为邻接边或弧。而联结一结点
结点连通度、边连通度和最小度的不等式联系的定理：
定理16.2.3 对于任何一个无向图G，有 (G)≤(G)≤δ(G)。
定理16.2.4 一个连通无向图G中的结点v是割点
存在两个结点u和w，使得联结u和w的每条链都经过v。
定理16.2.5
一个连通无向图G中的边e
在两个结点u和w，使得联结u与w的每条链都经过e。 下面再给出一个判定一条边是割边的充要条件。 定理16.2.6 连通无向图G中的一条边e是割边e不
定义16.1.3
在图G=<V，E>中，如果任何两结点
间不多于一条边 ( 对于有向图中，任何两结点间不多于 一条同向弧)，并且任何结点无环，则图G称为简单图； 若两结点间多于一条边 ( 对于有向图中，两结点间多于
一条同向弧)图G称为多重图，并把联结两结点之间的多
条边或弧，称为平行边或弧，平行边或弧的条数称为重 数。
所谓图G=<V,E>增加结点集S，是指作
V∪T以及向E中并入S中、S与V中所成的边而得
到的图，记作G+S；特别当S={v}时，简记为
G+v；图G=<V,E>增加边集（或弧集）T是指作
E∪T所得到的图，记作G+T，这里T中全部边 （或弧）的关联结点属于V。
定义16.2.6 给定连通无向图G=<V，E>，SV。若
定义16.1.12 给定无向图(或有向图)G1=<V1，E1> 和 G2=<V2 ， E2> 。若存在双射 f∈V2V1 ，使得对任意 v ， u∈V1 ， 有 〔u ， v〕∈E1〔f(u) ， f(v)〕∈E2( 或 <u ， v>∈E1<f(u) ， f(v)>∈E2) 则称 G1 同构于 G2 ，记为 G1G2 。 显然，两图的同构是相互的，即 G1同构于 G2， G2 同构于G1。 由同构的定义可知，不仅结点之间要具有一一对 应关系，而且要求这种对应关系保持结点间的邻接关系。 对于有向图的同构还要求保持边的方向。
定理16.1.1 给定无向图G=<V，E>，则
定理16.1.2 在任何无向图中，奇度结点的
数目为偶数。
定义16.1.7
在无向图 G=<V， E>中，如果
每个结点的度是 k ，即 (v)(v∈V→d(v)=k) ，则
图G称为k度正则图。
显然，对于k度正则图G，Δ(G)=δ(G)=k。
定义16.1.8 E2>，于是
在一个图中，若从结点 vi到结
点vj存在一条链(或路)，则必有一条从vi到vj的基
定理16.2.2 在一个具有n个结点的图中，则 (1) 任何基本链(或路)的长度均不大于n-1。 (2) 任何基本圈(或路)的长度均不大于n。
定义16.2.4 在一个图中，若从vi到vj存在任何一条 链(或路)，则称从vi到vj是可达的，或简称vi可达vj。 为完全起见，规定每个结点到其自身是可达的。 对于无向图 G 来说，不难证明结点间的可达性是 结点集合上的等价关系。因此它将结点集合给出一个划 分，并且划分中的每个元素形成一个诱导子图；两结点 之间是可达的当且仅当它们属于同一个子图，称这种子 图为图 G 的连通分图，图 G 的连通分图的个数，记为 ω(G)。
第十六章 图的概念与表示
16.1 图的基本概念
16.2 链(或路)与圈(或回路) 16.4 图的矩阵表示
退出
16.1 图的基本概念
什么是图?可用一句话概括，即：图是用点 和线来刻划离散事物集合中的每对事物间以某 种方式相联系的数学模型。 因为它显得太抽象，不便于理解，所以有 必要给出另外的回答。下面便是把图作为代数 结构的一个定义。
对于无向图 G=<V ， E> ，结点 v∈V 的度数等于联 结它的边数，也记为d(v)。若v点有环，规定该点度因环 而增加2。
显然，对于孤立结点的度数为零。
此外，对于无向图G=<V，E>，记
Δ(G)或Δ=max{d(v)|v∈V}
δ(G)或δ=min{d(v)|v∈V}
它们分别称为图G的最大度和最小度。 关于无向图中的结点的度，欧拉给出一个 定理，这是图论中的第一个定理。
包含在图的任何基本圈中。
对于有向图而言，结点间的可达性不再是 等价关系，它仅仅是自反的和传递的。一般说 来，不是对称的。因此，有向图的连通概念较
之无向图要复杂得多。
定义 16.1.4 边之权的集合。
给每条边或弧都赋予权的图 G=<V ，
E>，称为加权图，记为G=<V，E，W>，其中W表示各
加权图在实际中有许多应用，如在输油管系统图 中权表示单位时间流经管中的石油数量；在城市街道中， 权表示表示通行车辆密度；在航空交通图中，权表示两 城市的距离等等。
定义16.1.5 在无向图G=<V，E>中，如果V 中的每个结点都与其余的所有结点邻接，即 (vi)(vj)(vi，vj∈V→〔vi，vj〕∈E) 则 该 图 称 为 无 向 完 全 图 ， 记 作 K|V| 。 若
给定无向图G1=<V1，E1>和G2=<V2，
(1) 如果 V2V1 和 E2E1 ，则称 G2 为 G1 的子图，记 为G2G1。
(2) 如果V2V1，E2E1且E2≠E1，则称G2为G1的真 子图，记为G2G1。 (3) 如果 V2=V1 ， E2E1 ，则称 G2 为 G1 的生成子图， 记为G2 G1。
连通图G，(G)=1。
类似地定义边连通度(G)=
{|T||T是G
的分离边集}，它表明产生不连通图而需要删去
边的最少数目。可见，对于分离图G，(G)=0；