离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
基本定义
Loading...
Del curso dictado por Shanghai Jiao Tong University
离散数学
19 calificaciones
Conoce a los instructores
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
[声音] 各位大家好！本次我们开始讲解图论有关的知识点
本次我们主要讲一些基本的定义，以及一些特殊的图，包含了比较多的一些基本概念
首先什么是图呢？图我们说是一个有序对，包含 两个元素，一个是
V，是所谓的顶点集，第二个是 E，是边集 E
呢我们说它是顶点集选二的这样一个子集，表现成在这里 给了一个图 G。
有的时候，为了方便我们也用函数的 形式，也就是说
V(G) 或者 E(G) 来分别表示图 G 的顶点，以及和图 G
的边集 什么叫画图？或者是什么叫把一张图画在一个、
一张纸上？就是说我们用点 用黑心的点来表示顶点，然后用 直线来表示边。
下面，我们给出了三个图的那个画法 G1、 G2、 G3。
我们说给了一个图之后，它的画法一般来说是不唯一的 图中顶点的个数我们取了一个名字叫做阶
经常是用那个 V 加它的一个绝对值符号来表示。
有的时候 呢也用 G 的绝对值来表示图中顶点的个数，也就是 |G| 的大小。
那么 E 呢，我们刚才说了，E 是顶点选二的这样一个子集
那么其中的每一条边用小写的 e 来表示
小写的 e 它有两个顶点，分别是 u 和 v 这个 u 和 v
我们在图中就称为它们是相邻的 或者是说 u 是 v 的邻居。
有的时候也称为 u 和 v 是相关联 那么我们说每一条边与且仅与两个顶点相 关联。
因为每一条边的话它是由两个顶点所决定的 那么 N(u)
呢是表示 u 的邻居点的个数 这里举了一个例子。
我们在这里的这张图中 我们说 v1、 v2、 v3、 v4，一共有四个顶点 那么图
G 的那个阶是 4，那么 v1 的 邻居个数呢就是
4，因为它包含了四个邻居 分别是v1、 v2、 v3 和 v4。
那么顶点的度 顶点的度数就是说我们的邻居的这个大小、 邻居的这个大小
那么刚才的那个图中我们已经提过了，刚才那个 G
的图中 刚才这样一个 G 图中，它们 V1 的邻居的大小就一共是四个
那么我们经常用两个符号 δ(G) 和
Δ(G) 来分别来表示图 G 的最小的度数和它的最大度数
当然我们说任给一张图的话，它其中任意一个顶点的度数一定是小于等于边集的大小
因为我们说度数就是它与多少个边相邻，那么跟它相邻的边的个数不会超过所有的边的个数
我们看这样一张图 G。
我们说最小，图 G 的最小的点的度数 是 1。
有两个点都只有一个邻居，就是用红色表示出来。
那么它的最 大的顶点度数 Δ(G) 呢是多少？是四。
我们这里用蓝色这个点表示出来 它与四个点相邻。
好了，我们之前介绍的图都是无向图 那么我们这里还要介绍所谓的有向图
就是说我们刚才的边如果大家记得的话，我们说边 e
是等于 这样一个 {u,v} 这样一个集合 我们是通过一对顶点来定义一条边。
注意这里是一个集合的表示。
如果我们把这个集合表示换成一个有序对 那么我们称它为一个有向阶，而原始的图称为一个有向图
u 呢经常称为 e 的起点，v 称为 e 的一个终点。
在图中表示呢就是用一条从 u 指向 v 的这样一个箭头。
我们把 u、 v 标在两侧，e 标在这个边的上头
所以在本课中呢，除了显示声明以外，我们一般来说都是讲的无向图 当我们说图论在生活中随处可见。
这里给出了 2015 年上海市 地铁一个线路图。
大家可以看到，我们如果把每一个站 理解成一个点，把两个站之间的那个地铁线路理解成一条边的话
那我们就可以的相应的给出图的、 这样一个图的这样 当然现实中还有很多其他的问题，我们都可以抽象成图
图论一个相关的重要概念叫做子图 我们现在已经有两个图 G 和 G'。
假如说我们知道 G 中包含的顶点，也就是说 V(G) 一定是都在
V(G') 中 它 G 的顶点都是 G' 的顶点。
并且 G 的边也都一定是 G' 的边 那么我们说 G 是
G' 的一个子图 比如说我们用这个现在这个黑色的表示图
G' 的话 那么我们说红色表示的这些点和边 形成原图 G' 的一个子图。
我们现在对子图加一个要求 如果我们还要要求
E 中的边呢，它正好等于 G'
中的边交上 V(G) 选二。
也就是说 凡是在 G' 中的边，并且这个点又已经是在 G 中的话 那么这个边一定也在 G 中。
那么这样的一个子图，我们叫做原始 图 G' 的一个导出子图。
大家看一下右边这个，还是同一个例子，我们用 灰色表示原始的
G'，然后红色高亮表示是那个 G 的 部分。
我们问现在红色的部分是否是原图的一个导出子图呢？ 答案是否定的。
因为我们说这三个点 这三个点。
比如说这一条边我们说它是在 它是在原图 G' 中的。
这条边也是在原图的 G' 中，但是 它们没有在新的那个子图
G 中，所以它不满足 导出子图的条件。
那我们如果把这两条边加回去 它就形成了原图的一个导出子图。
类似的我们可以 定义生成子图。
就是说现在我们不要求所有在原图 G' 中的边。
如果它的点也在 G 中的话，那么这个边也要一定在 G 中 而是我们对点有要求。
我们要要求 G 包含了 G' 中所有的顶点 那么我们说 G
是 G' 的一个生成子图 右边同样的给出了一个例子。
下面原始的 G' 就是我们开始给出的那个黑色的图，那我们用红色表示了 那个图 G。
注意到现在红色包含原始 G' 中所有的点 当然它的边也是原始图的一个子集。
所以说我们说它是 那个原始图的一个生成子图。
大家一定要注意的是导出子图和生成子图的区别
导出子图是说对边有一个强调，而生成子图是要求必须要包含所有的 所有的顶点。
当然我们说导出子图和生成子图都是原图的子图 那么介绍了图之后，我们要介绍图对象之间的一些基本操作
第一个是 G+eij 它的意思说就是在图
G 中间增加一条边 eij 这个 eij 呢，我们说它的两个顶点分别是
vi 和 vj 类似的去定义，从图 G 中减去一条边
eij 注意到我们如果这个减法操作，反复作用减法
操作的话，那么我们可以得到原图 G 的任意的一个生成子图 所以我们这个减这个边的时候，它的点是保留的
接着我们可以把刚才的操作推广到集合之间 我们这里用大 E
的 bar 表示，一根横线表示一个集合 E 拔呢是原图边集的一个子图
G 减去 E 拔表示从 G 中删去 E 拔中所有 的边。
还是要注意我们在删边的时候，它的两个顶点是保留的 那么
G-v，前面三个操作都是与边有关的操作，后面 两个是跟点有关的。
我们从图 G 中减去一个 点 v，是什么呢？我们要把这个点
v 以及相关联的边都删掉 我们这里画一个图的例子。
这是一个点和它相邻的另外一个点 那么这是原图 G，我们现在把这个点 v 删掉。
我们把这个点称为 v。
那么我们要把这个点去掉 并且要把这两条边都去掉。
也就是说新图中间只会剩下两个点 所以我们如果反复的操作减去这个
这个点的这个操作的话呢，我们可以得到原图的任意的导出子图 这里还是要强调的是导出子图。
我们刚才说我们任意 删边的话会得到任意生成子图，这两个之间的区别一定要小心
那么类似的我们可以扩展到点集的操作。
v 拔是 原始点集的一个子集。
那么我们从 G 中删去 v 拔中所有的顶点 以及与这些顶点所相关联的边
换句话说，与边相关的操作，加法和减法，我们对点是没有影响的
但是，当我们去删掉一些点的时候 不单要删掉点，还要删掉点相关联的边
就是说，我们刚才是用的加和减 在一些文献中也经常看到用集合的符号，就是用并来表示
加了一条边，比如说，用集合的减来表示 删去一条边。
类似的比如说，减去一个点，减去一个点集等等 就是说这里和刚才的定义基本上是一样，只是说符号上什么的有所不同
好了我们接着下来介绍一些重要的特殊图 这些图中的一些概念在后面会被反复用到
首先介绍一个比较简单的概念，是路径。
我们从直观上讲，什么是路径呢？路径就是 这样的一条线。
V 是，比如说是 n+1 个点，0 到 n。
然后什么是 E？E 每一个 表示的是从 i-1 号点到 i 的这样一个 二元组。
比如说这里是 0 号点、 1 号点、 2 号点、 3
号点等等 注意的是，第 i-1 号点只和第 i
点相邻 当然，我们说，比如说以 1 号点
它跟 0 和 2 都相邻，就是说后面不断地增长出来
有了路径之后我们可以定义环 环和路径的唯一区别在于，路径的话，第一个点
就是这个路径的，这个图的初始的这个顶点和最后这个顶点是不一样的
而环的话要求我们沿着这个环走，它最后会走回来 也就是说我们现在还是有
n 个点，那么第 i 个点和第 i+1 个点 又或者是第 i-1
个点，它们都是相邻的 最终，我们要加入一个特殊的边，是 1
和 n 大家注意，路径和环的区别，就在于我们最后有没有加入 这条边。
就是说，把整个路径给让它走回到出发点的这样的一条边 从图上来讲，就是比如说这个
C3 表示 3 个点的环，C4 表示 4 个点的环，类似
第二个我们想讲一个重要的特殊图是二分图 二分图直观上讲，我们把点分成了两部分。
第一部分 包含 n 个点，第二部分包含 m 个点，我们用 Bn,m
来表示 那么边呢都是在这两部分之间有边。
就是前 n 个点 和后面的 m 个点，它们之间有边。
但是内部，u1 到 un 内部，或者是 v1 到 vm 内部没有边的。
我们看一张图就明白了。
比如说 B1，1，我们说分成了两部分，第一部分是上面这个点 第二部分是下面这个点。
它们之间有边，但是没有从 比如说，没有从一个点到它自身的这样一个边 然后第二个例子是
B1，2，我们说第一个集合 中间包含下面的这一个点，第二个集合表现的是上面的两个点
它们两个集合之间有边。
但是，比如说 上面这个集合的两个点之间是没有边的。
类似的 B3，3，我们说把 点分成两部分，下面这三个点和上面这三个点
上下的顶点之间是有边的，但是上面的顶点之间没有边，下面的顶点之间也没有边
还有一个在，无论在 理论上或者在应用中都很重要的特殊图示，称为完全图
完全图我们一般来说用 Kn 表示，n 是表示那个图的阶
什么是完全图呢，就是说我给了你，比如说以 K3 为例
给了，我们说 K3就是表示它有三个点 K3
是说它所有的顶点彼此之间全部相连 这里的
K3，大家可以看，第一张图，所有的三个点 三个点之间所有的边都加进去。
类似的 K4，K4 是所有的 四个点，每两个点都彼此相连。
那么有多少条边呢？显然是有六条边 那么有了完全图和二分图的概念，我们可以引申定义什么是完全二分图
完全二分图是说，当然它首先是一个二分图。
它的点是分成了两部分 第一个部分是包含 n 个点，第二个部分包含 m 个点。
我们这里注意，完全二分图是用 Kn，m 来表示
什么是完全二分图呢？就是说，就是在定义二分图的时候，我们是说 这里是用的一个子集关系。
在定义完全二分图的时候，我们把这个子集关系 我们把它变成了一个等号关系。
比如说以 K1，2 为例子 它的点分成两个集合。
第一个集合只含有一个点 第二个集合包含了两个点。
但是 第二个集合跟第一个集合中间的点呢，所有的 所有的点它们都是相邻的这样一个关系
类似的我们可以看 K3，3，就上面的三个点和下面的三个点全部相邻，下面的三个点和上面的三个点也全部相邻
但是，它必须是一个二分图，也就是说上面的三个点之间没有边，下面的三个点之间也没有边
好了，还有一个常见的一个图的概念是叫做一个正则图
就是说我们定义了图，我们也定义了图的度数 如果图中每一个点的度数都是一个常值小
r 的话 那么我们把这个图称为一个 r-正则图。
首先是最简单是 r 为 0 的时候 0-正则图就是所有的点的度数都为零，那是什么呢？我们称为空图
这个图中只有有限个点，没有任何的边。
这里是一个例子，包含了三个点的一个空图 第二个当
r 为 1 的时候，我们称为 1-正则图，也就是说图中所有点的度数都为
1 这个时候是什么样子呢？它其实就是一些不相连的边集 它可能，当然可能只有一条边，当然也可能是有限条边这样
大家可以看到，在这样一条边或者是一个长度为 1 的路径 它的每个点的度数确实都是 1 的。
那么 2-正则图是什么呢？2-正则图我们说是不相交的一些环 环上每个点的度数都是2。
那么，2-正则图呢 可以是一个环，也可能是若干个不相交的环。
比如说在这里就是两个 这里是两个不相交的环，一个是 C10，一个是 C3
那么 3-正则图的可能性就多了，这里只画了三个
3-正则图有个特殊的名字叫做立方图 我们下面给出了三个
3-正则图的例子，每一个点的度数都是 3 这个在后面讨论中会用到这样一个概念
在之前我们讲的图中，我们对点和边的添加没有做限制
现在我们看有两类特殊的边。
第一个叫自环 自环说，是什么样一条边呢？是从一个点到它自身。
换句话说，是存在这样一个点 v e={v, v} 这个集合。
当然我们知道，它既然是集合的话，那么可以表示成其实只用到了 v
那么如果是这样一个，或者在图中就是右边这个 那么称它为一个自环。
那么什么是重边呢？重边是说我给了你 u 给了你 v
之后，如果有两条边 有两条边 e1 和 e2
都以 u 和 v 作为顶点 换句话说，这两个点之间有两条边的话，那么我们称 e1 和 e2 是重边。
当然，我们说可能还有第三条边 它也是重边，类似的情况。
那什么是简单图呢？ 就是说，如果原始的图中没有自环也没有重边，注意我们这里都默认的是无向图
那么我们就称它是一个简单图
关于图中有两个会一直被用到的概念，第一个是称为路径，第二个称为游走。
路径和游走 首先是介绍路径。
路径就是说我们沿着图上的顶点和边的这样一个
一个序列去走，但是并且我们要要求这个走的过程呢它不允许出现环
并且在这个走的过程中，每个顶点和每一条边至多只出现一次 我们在图中看一个例子。
我们在这个图中，我们说我们是从 v4 这个点一直走到了
v1，然后走到了 v5，然后走到了 v6，然后走到了 v3，然后是走到了
v7 大家可以看到，那么这个就是一个路径，这个就是一个路径
它每一个点都只用到了一次，每一条边也只用到了一次。
然后在写的时候呢，我们就是写成了这样一个 大家可以看到，我们写成了这样一个顶点和边，v4
经过 e3 到达 v1，然后 v1 经过 e4 到达 v5，类似的
那么什么是游走呢？游走是说我们现在还是沿着图上的顶点和边去走 但是我现在走得比较松了，要求比较松
我们可以允许环，而且点和边也可以重复使用 这里我们还是看一个例子。
从 v4 我经过边 e3 到 v1 然后经过
e4 到 v5，然后它经过 e5 到了 v2
当然它在 v2 上，大家可以看到，它可以多打一些圈 然后再经过
e6 到 v6，然后比如说我再经过 e9 到
v5 再类似地走，最后一个走到的是，终点我走到了 v7
这个点 注意的是，路径和游走都是说我们的，你可以理解成我们的笔
按点在这个图上的某一点，然后沿着这个图走，我的笔始终不离开 只不过路径呢，是要求点和边都不能重复使用
而游走的话就是说，你只要是一个合法的走的方案，也就是说不离开，不离开你原始的图的话
那么就是一个正确的一个游走方案 好了，我们定义了图之后
这里还有一个会被反复用到的概念，是称为所谓的连通性 什么是连通图呢？如果图中的任意两个点
u 和 v 之间都有一条路径的话，那么我们称它是一个连通图 否则的话，我们称图是一个非连通图。
我们看一个例子，就是首先下面这个 图的话，我们说它是一个连通图，以
u 和 v 为例 这两个点，我们说它们之间存在一条路径，从 u 走到
v，当然可能还存在其它的路径，比如说我们走这一条 我们走这一条，也是可以从 u
走到 v 的，但是只要存在这样一条就可以 但是我们把原始的图做一点改动，我们把
我们删掉两条边，删掉的边我们用虚线表示出来，我们把这两条边删掉 我们说，它现在就不是一个连通图了，因为还是说
u 和 v 而已，在新图中，也就是右边这个图中 我们从 u 到 v
不存在一个路径，路径我们刚刚定义好了 它是形成了两个，两个子块
那么对非连通图，或者是一般的图来说，我们可以定义所谓的极大连通子图
极大连通子图它要要求满足三个条件，就是首先第一
它是原图的子图，第二，它是连通的，第三 它已经和原图相等了，或者说你在原图
你在目前的这个连通子图上再增加点或者再增加边 都会破坏连通性。
我们看还是刚才这个例子 我们说，我们把整个理解成一张图的话，我们说它其实是有三个
极大连通分支，我们分别用红色、 蓝色和绿色来表示。
以红色这一块为例，我们再增加任意一个点 比如说绿色这个点，那么从红色任意一个点到这个绿色的点，没有路径 它连通性被破坏。
那么刚才我们讲的这个例子中的每一块 极大连通分支呢，都称为原始图的一个连通分支
当我们说，连通分支可能，可能是包含多，对一个，对非连通图来讲
它连通分支必然是 不是唯一的。
那么给一个图，它的极大连通分支的个数呢，是用 Con 这样一个 G，这个函数来表示。
还是刚才这个例子，我们说刚才这个图，它的极大连通分支个数是 3 它是包含了三个连通分支。
当然我们说，如果原始的图 就是一个连通图的话，那么它的那个
Con(G) 的话就是 1 但是如果是非连通图的话，那么一定是大于等于
2 好了，我们这一次课介绍最后一个概念，是所谓的树
就是，注意我们现在还是讨论的是无向图 那么树是什么呢？被定义为无环的连通图
就原始的图，它是一个连通的，但是又不含有任何的环，那么我们给它取一个名字叫做树 这里是一些树的例子。
比如说，大家可以看，第二个的话大家可以 看到，其实是一个，就是一个路径。
路径我们说第一个点和最后一个点之间是没关系的 并且它显然是连通的，因为每一个点到后一个点之间，都是有边相连
然后第三个例子，大家经常被称为所谓的星型图 它成为一个星的这样一个形状，它也是一个无环的一个连通图
当然还有最左边，这个可能就是一棵树的样子 我们说树是一类非常重要的对象，在实际中有非常广泛的应用
而且我们后面会专门讲到树的性质和树有关的一些重要算法
好了，本次课我们主要讲了图上的一些基本概念和一些重要的一些特殊图
好，谢谢大家
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
