中科大离散数学图论基础
- 格式：pptx
- 大小：9.50 MB
- 文档页数：236
下载文档原格式
合集下载
离散图论知识点总结
离散图论知识点总结一、基本概念图（Graph）是离散数学中的一个重要概念，它由顶点集合V和边集合E组成。
一般用G （V，E）来表示，其中V={v1,v2,…,vn}是有限非空集合，E是V中元素的无序对的集合。
图分为有向图和无向图。
无向图中的边是无序的，有向图中的边是有序的。
图中存在一些特殊的图，比如完全图、树、路径、回路等。
二、图的表示方法1. 邻接矩阵邻接矩阵是一种常见的图的表示方法，它使用一个二维数组来表示图的关系。
对于一个n 个顶点的图，邻接矩阵是一个n*n的矩阵A，其中A[i][j]表示顶点i到顶点j之间是否存在边。
对于无向图，A[i][j]=1表示顶点i与顶点j之间存在边，A[i][j]=0表示不存在。
对于有向图，A[i][j]=1表示i指向j的边存在，A[i][j]=0表示不存在。
2. 邻接表邻接表是另一种常见的图的表示方法。
它将图的信息储存在一个数组中，数组的每个元素与图的一个顶点相对应。
对于每个顶点vi，数组中储存与该顶点邻接的顶点的信息。
邻接表可以用链表或者数组来表示，链表表示的邻接表比较灵活，但是在查找某个边的相邻顶点时需要遍历整个链表。
三、图的性质1. 度图中每个顶点的度是与其相邻的边的数目。
对于无向图，顶点的度等于与其相邻的边的数目；对于有向图，则分为入度和出度。
2. 连通性对于无向图G，若图中任意两个顶点都有路径相连，则称图G是连通的。
对于有向图G，若从任意一个顶点vi到任意一个顶点vj都存在路径，则称G是强连通的。
3. 路径和回路路径是指图中一系列的边，连接图中的两个顶点；回路是指起点与终点相同的路径。
路径的长度是指路径中边的数目。
4. 树和森林一个无向图，如果是连通图且不存在回路，则称为树。
一个无向图，若它不是连通图，则称为森林。
四、图的常见算法1. 深度优先搜索（DFS）深度优先搜索是一种用于图的遍历的算法，它从图的某个顶点vi出发，访问它的所有邻接顶点，再对其中未访问的顶点继续深度优先搜索。
离散数学图论基础知识
3) 每条边都是无向边的图称为无向图；
S
4) 每条边都是有向边的图称为有向图；
T
5) 有些边是无向边，而另一些是有向边的图称为混合图。
用小圆圈表示V中的结点，用由u指向v的有向线段表示 <u,v>，无向线段表示(u,v)。
XDC
C
S
图的分类－按边的方向
|
S
W 上图所示的三个图分别表示为：
U
G1＝<V1,E1>＝<{v1,v2,v3,v4}，{(v1,v2),(v2,v3),
XDC
C
S
图的同构
|
S
W
U
图 的 同 构 ： 设 两 个 图 G = < V, E > 和 G ' = < V ' , E ' > ， 如 果
S
存在双射函数g：V→V'，使得对于任意的e
T
=(vi,vj)（或者<vi,vj>）∈E当且仅当e'=
(g(vi),g(vj))（或者<g(vi),g(vj)>）∈E'，
U
重数；
3) 含有平行边的图称为多重图；非多重图称为线图；
S
4) 无自回路的线图称为简单图。
T
G1、G2是多重图，G3, G4是线图，G4是简单图。
XDC
C
S
图的分类－按权
|
赋权图 G是一个三重组<V,E,g>或四重组<V,E,f,g>，
S
其中V是结点集合，E是边的集合，f是从V到非负
W
实数集合的函数，g是从E到非负实数集合的函数。
驾齐驱地成为研究复杂网络的两大解析方法之一。
离散数学基础图论
离散数学基础：图论Fundamentals of Discrete Mathematics:Graph Theory周晓聪(isszxc@)中山大学计算机科学系,广州5102752008年12月26日2版权所有，翻印必究目录目录i第一章图的基本概念11.1图的基本定义 (1)1.2道路与回路 (6)1.3图的连通性 (8)1.4邻接矩阵与可达矩阵 (12)第二章树的基本概念192.1树的基本定义 (19)2.2生成树 (21)2.3根树 (26)2.4哈夫曼树 (31)第三章路径问题413.1最短路径 (41)3.2最小生成树 (47)3.3关键路径 (49)第四章平面图与着色554.1平面图及其性质 (55)4.2图的着色 (58)第五章支配集、覆盖集、独立集和匹配655.1支配集、点独立集和点覆盖集 (65)5.2边覆盖与匹配 (67)5.3二部图中的匹配 (73)第六章欧拉图与哈密顿图776.1欧拉图 (77)6.2哈密顿图 (77)iii目录参考文献79第一章图的基本概念这一章介绍有关图论的一些基本概念，包括无向图（有向图）的定义、顶点与边之间的关系、顶点度数、握手定理、图的道路与回路等。
1.1图的基本定义定义1.1.1（无向）图(graph)是二元组G =(V,E )，其中V =∅是图G 的顶点(vertex)集，其中的元素称为G 的顶点(vertex)，E 是图G 的边(edge)集，其中的元素称为G 的边(edge)，且满足，对图G 的任意边e ∈E ，都有且仅有两个顶点u,v ∈V 与e 关联，称为e 的两个端点，通常将e 记为e =(u,v )或e =(u,v )。
对于边e =(u,v )，这里u,v 没有顺序，因此边e =(u,v )和e =(v,u )是同一条边。
我们只考虑有限图G =(V,E )，也即其顶点集V 和边集E 都是有限集。
上面的定义是说，在定义一个图的时候，要给出它的顶点集和边集，并说明每一条边的两个端点是那两个顶点。
离散数学图论(图、树)常考考点知识点总结
离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。
《离散数学》第6章图的基本概念
一、通路，回路。 1、通路 (回路)
—— G 中顶点和边的交替序列
v0e1v1e2
el vl ，其中 ei (vi 1 , vi )(无向图)，
或 ei vi 1 , vi (有向图)， v0 ——始点，
vl ——终点，称 为 v0 到 vl 的通路。当 v0 vl
时， 为回路。 2、简单通路，简单回路。 简单通路 (迹) 简单回路 (闭迹) 复杂通路 (回路)
3、初级通路，初级回路。 初级通路 (路径) 初级回路 (圈)
初级通路 (回路) 简单通路 (回路)， 但反之不真。
4、通路，回路 的长度—— 中边的数目。
例1、(1)
图(1)中，从 v1 到 v6 的通路有：
1 v1e1v2e5v5e7v6
2 v1e1v2e2v3e3v4e4v2e5v5e7v6 3 v1e1v2e5v5e6v4e4v2e5v5e7v6
设 V v1, v1,
, vn 为图 G 的顶点集，称 , d (vn ) 为G 的度数序列。
d (v1 ), d (v2 ),
2、握手定理。
定理1： 设图 G V , E 为无向图或有向图，
V v1, v1,
则
, vn ，E m ( m为边数)，
d (v ) 2 m
图论简介 图论是一个古老的数学分支，它起源于游戏 难题的研究。图论的内容十分丰富，应用得相当 广泛，许多学科，诸如运筹学、信息论、控制论、 网络理论、博弈论、化学、生物学、物理学、社 会科学、语言学、计算机科学等，都以图作为工 具来解决实际问题和理论问题。随着计算机科学 的发展，图论在以上各学科中的作用越来越大， 同时图论本身也得到了充分的发展。本课程在第 六、七章中介绍与计算机科学关系密切的图论的 基础内容。
离散数学第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 各不相同 （此时所有边也互不相同），则称该回路为环。
为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 各不相同 （此时所有边也互不相同），则称该回路为环。
离散数学中的图论基础知识讲解
离散数学中的图论基础知识讲解图论是离散数学中的一个重要分支，研究的是图的性质和图中的关系。
图论在计算机科学、网络科学、运筹学等领域有着广泛的应用。
本文将从图的基本概念、图的表示方法、图的遍历算法以及一些常见的图论问题等方面进行讲解。
一、图的基本概念图是由顶点和边组成的一种数学结构。
顶点表示图中的元素，边表示元素之间的关系。
图可以分为有向图和无向图两种类型。
1. 无向图：无向图中的边没有方向，表示的是两个顶点之间的无序关系。
如果两个顶点之间存在一条边，那么它们之间是相邻的。
无向图可以用一个集合V表示顶点的集合，用一个集合E表示边的集合。
2. 有向图：有向图中的边有方向，表示的是两个顶点之间的有序关系。
如果从顶点A到顶点B存在一条有向边，那么A指向B。
有向图可以用一个集合V表示顶点的集合，用一个集合E表示有向边的集合。
二、图的表示方法图可以用多种方式进行表示，常见的有邻接矩阵和邻接表两种方法。
1. 邻接矩阵：邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否存在边。
如果顶点i和顶点j之间存在边，那么矩阵的第i行第j列的元素为1；否则为0。
邻接矩阵适用于表示稠密图，但对于稀疏图来说，会造成空间浪费。
2. 邻接表：邻接表是一种链表的数据结构，用来表示图中的顶点和边。
每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。
邻接表适用于表示稀疏图，节省了存储空间。
三、图的遍历算法图的遍历是指按照某一规则访问图中的所有顶点。
常见的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
1. 深度优先搜索：深度优先搜索是一种递归的搜索算法。
从某个顶点出发，首先访问该顶点，然后递归地访问与它相邻的未访问过的顶点，直到所有的顶点都被访问过。
2. 广度优先搜索：广度优先搜索是一种迭代的搜索算法。
从某个顶点出发，首先访问该顶点，然后依次访问与它相邻的所有未访问过的顶点，再依次访问与这些顶点相邻的未访问过的顶点，直到所有的顶点都被访问过。
离散数学基础图论
离散数学基础：图论
Fundamentals of Discrete Mathematics: Graph Theory
周晓聪(isszxc@) 中山大学计算机科学系, 广州 510275
年 月 日 2008 11 9
2
版权所有，翻印必究
第三章 路径问题
这一章集中考虑几个与图的路径有关的几个问题，包括有向图中任意两点之间的最短路径，图 的最小生成树，以及有向网络关键路径问题，这些问题都是在实际应用中经常遇到的问题，例如求 网络的关键路径是项目管理（包括软件开发项目）中的重要问题之一。
3.1 最短路径
3
达比v较5）在u；5这比=里较∞，u和我6u=们3 +∞看d和到35uv=33的+3，邻d3因接6 此=顶将8点，u有因5修v此2改,将v为5u,63v修，6，相改比应为较地8u，将2相=q应57的和地值u将改3 q+6为的dv3值32（=也即7修v，1改经因为过此vv仍33，可保因以持此比u得2较的到快值：地为到7；
S = {v2, v4, v6}
U = 0, 6, 1, 8, 3, 8
到此为至的计算结果也可用下表给出：
Q = v1, v5, v1, v5, v3, v3
第0步 第1步 第2步
v1 0
v2 7/v1 7/v1 6/v5
U = ∞, 7, 1, ∞, ∞, ∞
而对任意的1 ≤ i ≤ n，都令qi = v1，即目前考虑的可能前趋都是v1：
Q = v1, v1, v1, v1, v1, v1
或者说，按照耿素云教材，我们使用下表给出U和Q：
第0步
v1 0
v2 7/v1
v3 1/v1
v4
v5
v6
Fundamentals of Discrete Mathematics: Graph Theory
周晓聪(isszxc@) 中山大学计算机科学系, 广州 510275
年 月 日 2008 11 9
2
版权所有，翻印必究
第三章 路径问题
这一章集中考虑几个与图的路径有关的几个问题，包括有向图中任意两点之间的最短路径，图 的最小生成树，以及有向网络关键路径问题，这些问题都是在实际应用中经常遇到的问题，例如求 网络的关键路径是项目管理（包括软件开发项目）中的重要问题之一。
3.1 最短路径
3
达比v较5）在u；5这比=里较∞，u和我6u=们3 +∞看d和到35uv=33的+3，邻d3因接6 此=顶将8点，u有因5修v此2改,将v为5u,63v修，6，相改比应为较地8u，将2相=q应57的和地值u将改3 q+6为的dv3值32（=也即7修v，1改经因为过此vv仍33，可保因以持此比u得2较的到快值：地为到7；
S = {v2, v4, v6}
U = 0, 6, 1, 8, 3, 8
到此为至的计算结果也可用下表给出：
Q = v1, v5, v1, v5, v3, v3
第0步 第1步 第2步
v1 0
v2 7/v1 7/v1 6/v5
U = ∞, 7, 1, ∞, ∞, ∞
而对任意的1 ≤ i ≤ n，都令qi = v1，即目前考虑的可能前趋都是v1：
Q = v1, v1, v1, v1, v1, v1
或者说，按照耿素云教材，我们使用下表给出U和Q：
第0步
v1 0
v2 7/v1
v3 1/v1
v4
v5
v6
《离散数学之图论》课件
二分图
二分图是指一个图中的所有顶点可 以被分成两个不相交的集合，即两 个集合内的点之间没有边。
树
树是一种特殊的无向图，他是一个 无环连通图。
图的表示
1
邻接矩阵
邻接矩阵是表示图的最直观的一种方法，它将图中的每个点与其他点之间的连接 关系用一个矩阵来表示。
2
邻接表
邻接表是图中比较常见的一种数据结构，用于存储有向图或无向图中顶点的邻接 关系。
Kruskal算法是一种贪心算
2 自反闭包
3 反对称闭包
在一个有向图中，如果由顶 点i到顶点j有路径，由顶点j 到顶点k有路径，则从i到k也 有路径。这种情况称为传递 闭包。
在一个有向图中，如果自己 只能到自己，则称之为自反 闭包。
在一个有向图中，如果存在 有向边从i到j，同时存在一 个从j到i的反向边，则称之 为反对称闭包。
3
关联矩阵
关联矩阵是一个图矩阵，它将图中的所有点和边都表示为元素，可以将和特定边 相关的点和总结点联系起来。
图的遍历
1 深度优先遍历
深度优先遍历是从图中的起始点开始，递归地访问所有可达的顶点。它通常用堆栈来实 现。
2 广度优先遍历
广度优先遍历是从图中的起始点开始访问每一层可达的顶点。它通常用队列来实现。
最短路径
Dijkstra算法
Dijkstra算法是一种用来求图中单个源点到其他所有点 的最短路径的平均算法。
Floyd算法
Floyd算法是一种用于发现非负权重图中所有点对之间 的最短路径的算法。
最小生成树
1
Prim算法
Prim算法用于寻找加权无向连通图的最小生
Kruskal算法
2
成树，该树包含了关键点并且保证了所有点 都连通。
离散数学中的图论代表知识点介绍
离散数学中的图论代表知识点介绍离散数学是数学的一个分支，它主要研究离散对象以及其离散性质和离散结构。
图论作为离散数学的重要组成部分，以图为研究对象，研究了图的基本概念、图的表示方法以及图的性质和应用。
本文将介绍离散数学中的图论代表知识点。
1. 图的基本概念图是由顶点集合和边集合组成的离散结构，用V表示顶点集合，E表示边集合。
图可以分为有向图和无向图两种类型。
有向图中的边是有方向的，而无向图中的边是无方向的。
图中的顶点可以表示为V={v1, v2, v3, ...}，边可以表示为E={(vi, vj)}。
在图中，两个顶点之间有边相连时，称这两个顶点是相邻的。
2. 图的表示方法图可以用多种方式来表示。
常见的表示方法有邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否存在边。
邻接表则是通过链表的方式来表示图的结构，每个顶点都对应一个链表，链表中存储着与该顶点相邻的顶点。
3. 图的性质图论研究了图的许多性质和特性。
其中一些重要的性质包括连通性、路径、回路、度数、树和连通分量等。
连通性是指图中任意两个顶点之间是否存在路径。
如果图中任意两个顶点都存在路径相连，则图被称为连通图。
反之，如果存在无法通过路径相连的顶点对，则图为非连通图。
连通图中的任意两个顶点之间至少存在一条路径。
路径是指从一个顶点到另一个顶点的顶点序列。
路径的长度是指路径上边的数量。
最短路径是指两个顶点之间边的数量最少的路径。
回路是指路径起点和终点相同的路径。
如果回路中除起点和终点以外的顶点不重复出现，则称为简单回路。
度数是指图中顶点的边的数量。
对于有向图来说，度数分为入度和出度，分别表示指向该顶点的边和从该顶点指出的边的数量。
树是一种无回路的连通图，它具有n个顶点和n-1条边。
树是图论中一个重要的概念，它有广泛的应用。
连通分量是指图中的极大连通子图，即在该子图中的任意两个顶点都是连通的，且该子图不能再加入其他顶点使其连通。
离散数学教学图论【共58张PPT】
一 、图的基本概念
• 邻接和关联 • 无向图和有向图 • 零图和平凡图 • 简单图 • 完全图（无向完全图和有向完全图） • 有环图
一 、图的基本概念
• 有限图和无限图 设图G为< V，E，Ψ>
（l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足
二、生成树
1、生成树定义：
若无向图的一个生成子图T是树，则称T 为G的生 成树，T中的边称为树枝，E（G）-E（T）称为树T 的补，其中的每一边称为树T 的弦。
在任何图中，结点v的度（degree）d(v)是v所关联边的数目。
第三节 生成树、最短路径和关键路径 由结点a和它所有的后代导的子图，称为T的子树.
∴ T连通且具有m=n-1的图
{e5,e4,e8} ， {e7，e6，e5，e2，e4} 第四节 欧拉图和哈密顿图
第四节 特殊图（欧拉图和哈密顿图等）
第五节 树、二叉树和哈夫曼树
离散数学教学图论
（优选 欧拉图和哈密顿图
(3)2=>3 ∴W(T)≤W(T1) ∴W(ei+1)≥W(f) 二. 哈密顿图的由来—周游世界问题：
第二节 图的矩阵表示 第四节 欧拉图和哈密顿图
证明：若G中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。 哈密顿图的由来—周游世界问题： c)对新图向下旋转45度。 ei之后将取f而不是ei+1
为该顶点的度,列之和一定为2. • 有向图的关联矩阵 ----- 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,
终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其 中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元 素的和为0,1的个数等于-1的个数,都等于边数m.
离散数学中的图论与算法
离散数学中的图论与算法离散数学是研究离散对象以及它们之间的关系和性质的数学学科。
其中，图论作为离散数学的重要分支，探究的是图和网络的理论性质和组合结构，而算法则是图论中用于解决问题和优化策略的重要手段。
一、图论基础图是由边和点构成的一种抽象结构。
在图中，点用圆圈表示，边用连接两个点的线表示。
图分为有向图和无向图两类。
有向图中的边跟一个箭头表示方向，无向图中则没有方向。
图的性质包括连通性、路径、环、度数等。
其中，连通性是指图中任意两点存在一条路径相互连通，路径是一条由边相连的点序列，环是有至少一条边和至少一个点与之相邻的路径。
图的度数指的是一个点所连接的边的数目，包括入度和出度。
入度是指指向该点的边的数目，出度是指由该点指向其他点的边的数目。
无向图每个点的度数为连接该点的边的数目。
在图中，存在欧拉回路和欧拉路径，它们分别指遍历图中所有边的路径和遍历所有点和边的路径。
二、图的表示图可以用邻接矩阵、邻接链表或关联矩阵表示。
邻接矩阵用一个二维数组表示，其中行列代表点，值代表边的存在与否。
邻接链表则将每个点的连边保存在链表中，关联矩阵表示的则是点和边的关系，每列代表一个边，每行代表一个点，值代表点和边之间的关系。
三、算法在图论中，不同的算法可以用于不同的问题，包括最小生成树、最短路径、网络流等。
最小生成树是指将一个连通带权图生成一颗生成树的权值和最小。
Prim算法和Kruskal算法是常见的最小生成树算法。
其中，Prim算法是以一个点为起点，每次选取与树中其他点距离最近的点并加入树中，直到生成一颗包括所有点的生成树；而Kruskal算法则是将边按权值从小到大排序，然后每次选取能够连接两个不在同一集合中的最小边。
最短路径算法是指求解两个节点之间最短路径长度的算法，包括Dijkstra算法和Floyd算法。
其中，Dijkstra算法是从起点出发，依次确定到每个节点的最短路径长度，直到到达目标节点；而Floyd算法则是对于所有点对之间的距离进行更新，最终得到任意两点之间的最短路径长度。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可
增加运输量； 反方向的边（V3，V2）的运输量为1；
4
2
4 8 1 3
产地 1
4 2 1 1
2 2 2 2
4
7 4 3 5 3
3 4
6
销地
22
如果将反向边（V3，V2）的运量调到正向边（V2，V4）上 去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增 加1。 4 2
27
例：一个网络流图：
a
源点
容量
4
s
2 3 3 b 1
3 2
汇点
t 4
4
2
d
c 2
中间点 中间点
28
对一个流网络G=(V,E,c)，每条边(u,v)上给定一个实数 f(u,v)，满足：0≤f(u,v) ≤ c(u,v)，则f(u,v)称为边(u,v)上的 流量。其中满足f(u,v)=c(u,v)的边称为饱和边。 如果有一组流量满足条件：
就需要定义一种参数来度量连通图连通程度的高低。
9
连通度
定义：连通度为 (G) min{|V || V 是G的顶点割集}
完全图的连通度定义为 ( Kn ) n 1，空图的连通度定义为0； 使得 | V | (G) 的顶点割集V’就是G的最小点割集； 若 (G) k ，则称G为k连通的； 所有非平凡连通图都是1-连通的； 就是一个图G最少要去掉 多少个点会变成非连通图。 若G不连通，则 (G) 0 ； 若G是平凡图，则 (G) 0 。
连通度分别是多少？
10
割边
定义：设 e E (G)，如果 w(G e) w(G) ，则称e为G的一
条割边。
u
v
• 边e是G的割边当且仅当e不在G的任何回路中； • 一个连通图是树当且仅当它的每条边都是割边。
11
边割集
定义：对图G，若E(G)的子集E’使得 w(G E ) w(G) ，
4
2
4 8 1 3 2 4
产地 1
P5（V1，V3，V4，V6） 也可再增加1吨运输量
4 2 1 1 2 1
4
7 3 3 5 3
2 4
6
销地
2 2
4
产地 1
思考：还能再增 加运输量吗？
3 4
8 1
3
4 2 1 1
4
7 4 3 5
2
6 3
销地
2
2 2
21
观察有向路P6（V1，V3，V2，V4，V6）
非连通图
3
定义8.6 一个有向图，如果忽略其边的方向后得 到的无向图是连通的，则称此有向图是连通图， 否则称为非连通图。
有向连通图
非连通图
4
5
6
割点
定义：设 v V (G) ，如果 w(G v ) w(G) ，则称v为G的
一个割点。
w(G)表示图G的连通分支数。
去掉v后，连通 分支增加了
4
产地 1
4
3 4
8 1 3
2 1 1 2
4
7 4
3 5 3
6
销地
2
2 2
反向边上流量含义：
• 节点2需要发出1吨货物，而节点3需要接收1吨货物； • 可以让该路径上的节点3前一条边增加流量，保持节点3的总进 入流量不变； • 同时让该路径上节点2之后的边上也增加流量，保持节点2的出 发流量不变。
23
网络流图中需要解决的基本问题
最大流问题 最大流最小割问题 最小费用最大流问题
25
流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有 一个非负容量c(u,v)>=0； 如果(u,v)不属于E，则假定c(u,v)=0； 流网络中有两个特别的顶点：源点s和汇点t；
一个流网络的实例（红 色数字表示边的最大容 量，蓝色数字表示边上 的实际流量）
17
产地 1
4 21 2 4
2 8
4 2 1 1 2 2 2
4
7 2
3
合并各个边上的运输 量，得到运输方案 4
5
2 1 3
6
销地
总共有5吨产 品从V1运到V6
2
3 8 3
产地 1
4 2 1 1
2 2 2
4
7 2 3 5 3
2 4
6
销地
18
可行的运输方案必须满足以下三个条件：
实际运输量不能是负的； 每条边的实际运输量不能大于该边的容量； 除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资， 即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。 思考：有没有可能改进运输方案？即 根据这个运输网，是否可增大运输量？ 4 7 2 3 2 2 5 3
即从源出发的所有流的总和 或到达汇的所有流的总和
对所有的u,v∈V，要求f(u,v)<=c(u,v)；
对所有的u,v∈V，要求f(u,v)=-f(v,u)； 流量平衡方程
平衡约束（反对称性）：
流守恒性：
对所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。
31
根据各点流量守恒的关系，可得下列各式： fsa+fsb+fsc=w (1) a 3 fat+fbt+fdt=w (2) 4 2 3 fsa+fba＝fat+fab (3) 2 3 b t s fsb+fcb+fab＝fba+fbt+fbd (4) 2 4 1 4 fsc＝fcb+fcd (5) c 2 d fbd+fcd＝fdt (6) 0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3， 0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2， 0≤fdt≤2，w≥0
说明
u
{u,v}是2-点割集
不管去掉多少结点， 剩下的图仍然连通
v
8
图的连通性
之前介绍过割点、割边、连通图的概念； 这里再补充一些概念和理论； 在连通图中，连通的程度也是有高有低；
(a)
(b)
(c)
图(a)、(b)删掉一个割点后，就不连通了，而图(c)，不管删掉那个点， 图仍然连通。（或者也可以用删掉边的条数来说明）
去掉一个节点后，图不再连 通，或者连通分支增加了
u
v
7
点割集（顶点割集）
定义：
去掉结点集合后，图不再连 通，或者连通分支增加了
对图G，若V(G)的子集V’使得 w(G V ) w(G)，则称V’为图G 的一个点割集； 含有k个顶点的点割集称为k-点割集； 若V’是图G的一个点割集，而V’减少任意一个点都不再是G的 点割集，则称V’是G的一个极小点割集； G中含点数最少的点割集称为G的最小点割集。 割点是1－顶点割集； 完全图没有点割集。
15
引例：运输方案
连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj） 表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上 的数字表示这条运输线的最大通行能力（简称容量）； 产品经过交通网从V1输送到V6，现要求制定一个输送方案， 使得从V1运到V6的产品数量最多。
4 2 8 4 1 2 4 4 7 6 5 2 3
则称E’为图G的一个边割集。含有k条边的边割集称为 k-边割集。
对非平凡图G，若E’是一个边割集，则 G \ E 不连通； 一条割边构成一个1－边割集； S V (G ) ， 设 S V (G )， S , S ，记号[S,S’] 表示一端在S中 另一端在S’中的所有边的集合。对图G的每个边割集，必存在 非空的S V (G )，使得 [S, S ] 是G的一个边割集，其中S V \ S 。
4
s 1
2 4 2 1 3
3 3
4 3 5
1 6
2 4
5 t
26
定义：带权的有向图G=(V,E)，满足以下条件，则 称为网络流图(flow network)：
（1）仅有一个入度为0的顶点s，称s为源点(source)或
出发点； （2）仅有一个出度为0的顶点t，称t为汇点(sink) 或结 束点； （3）每条边(u,v)的权值都为非负数，称为该边的容量， 记作c(u,v)； 满足上述的条件的图称为网络流图，也可以记作记为 G=(V,E,c)
29
例：一个网络流图上的可行流：
a
(4,3)
容量
(3,2) (3,0)
容许流fat
s
(2,1) (3,2) (4,3)
b
(2,2)
t
(4,4)
(1,1)
(2,2)
(2,2)
c
d
30
整个流网络G的流量为： |f|=∑f(s,v)(v∈V) 或 |f|=∑f(u,t)(u∈V) 『三个重要性质』
容量约束：
4
2
3 8 3
产地 1
4 2 1 1
2
2 4
6
销地
19
4
2 3 8 3 2
产地 1
4 2 1 1
2 2 2 4 2 1 1
4
7 2 3 5 3
2 4
6
销地
4
产地 1
4
增加运输量； 反方向的边（V3，V2）的运输量为1；
4
2
4 8 1 3
产地 1
4 2 1 1
2 2 2 2
4
7 4 3 5 3
3 4
6
销地
22
如果将反向边（V3，V2）的运量调到正向边（V2，V4）上 去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增 加1。 4 2
27
例：一个网络流图：
a
源点
容量
4
s
2 3 3 b 1
3 2
汇点
t 4
4
2
d
c 2
中间点 中间点
28
对一个流网络G=(V,E,c)，每条边(u,v)上给定一个实数 f(u,v)，满足：0≤f(u,v) ≤ c(u,v)，则f(u,v)称为边(u,v)上的 流量。其中满足f(u,v)=c(u,v)的边称为饱和边。 如果有一组流量满足条件：
就需要定义一种参数来度量连通图连通程度的高低。
9
连通度
定义：连通度为 (G) min{|V || V 是G的顶点割集}
完全图的连通度定义为 ( Kn ) n 1，空图的连通度定义为0； 使得 | V | (G) 的顶点割集V’就是G的最小点割集； 若 (G) k ，则称G为k连通的； 所有非平凡连通图都是1-连通的； 就是一个图G最少要去掉 多少个点会变成非连通图。 若G不连通，则 (G) 0 ； 若G是平凡图，则 (G) 0 。
连通度分别是多少？
10
割边
定义：设 e E (G)，如果 w(G e) w(G) ，则称e为G的一
条割边。
u
v
• 边e是G的割边当且仅当e不在G的任何回路中； • 一个连通图是树当且仅当它的每条边都是割边。
11
边割集
定义：对图G，若E(G)的子集E’使得 w(G E ) w(G) ，
4
2
4 8 1 3 2 4
产地 1
P5（V1，V3，V4，V6） 也可再增加1吨运输量
4 2 1 1 2 1
4
7 3 3 5 3
2 4
6
销地
2 2
4
产地 1
思考：还能再增 加运输量吗？
3 4
8 1
3
4 2 1 1
4
7 4 3 5
2
6 3
销地
2
2 2
21
观察有向路P6（V1，V3，V2，V4，V6）
非连通图
3
定义8.6 一个有向图，如果忽略其边的方向后得 到的无向图是连通的，则称此有向图是连通图， 否则称为非连通图。
有向连通图
非连通图
4
5
6
割点
定义：设 v V (G) ，如果 w(G v ) w(G) ，则称v为G的
一个割点。
w(G)表示图G的连通分支数。
去掉v后，连通 分支增加了
4
产地 1
4
3 4
8 1 3
2 1 1 2
4
7 4
3 5 3
6
销地
2
2 2
反向边上流量含义：
• 节点2需要发出1吨货物，而节点3需要接收1吨货物； • 可以让该路径上的节点3前一条边增加流量，保持节点3的总进 入流量不变； • 同时让该路径上节点2之后的边上也增加流量，保持节点2的出 发流量不变。
23
网络流图中需要解决的基本问题
最大流问题 最大流最小割问题 最小费用最大流问题
25
流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有 一个非负容量c(u,v)>=0； 如果(u,v)不属于E，则假定c(u,v)=0； 流网络中有两个特别的顶点：源点s和汇点t；
一个流网络的实例（红 色数字表示边的最大容 量，蓝色数字表示边上 的实际流量）
17
产地 1
4 21 2 4
2 8
4 2 1 1 2 2 2
4
7 2
3
合并各个边上的运输 量，得到运输方案 4
5
2 1 3
6
销地
总共有5吨产 品从V1运到V6
2
3 8 3
产地 1
4 2 1 1
2 2 2
4
7 2 3 5 3
2 4
6
销地
18
可行的运输方案必须满足以下三个条件：
实际运输量不能是负的； 每条边的实际运输量不能大于该边的容量； 除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资， 即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。 思考：有没有可能改进运输方案？即 根据这个运输网，是否可增大运输量？ 4 7 2 3 2 2 5 3
即从源出发的所有流的总和 或到达汇的所有流的总和
对所有的u,v∈V，要求f(u,v)<=c(u,v)；
对所有的u,v∈V，要求f(u,v)=-f(v,u)； 流量平衡方程
平衡约束（反对称性）：
流守恒性：
对所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。
31
根据各点流量守恒的关系，可得下列各式： fsa+fsb+fsc=w (1) a 3 fat+fbt+fdt=w (2) 4 2 3 fsa+fba＝fat+fab (3) 2 3 b t s fsb+fcb+fab＝fba+fbt+fbd (4) 2 4 1 4 fsc＝fcb+fcd (5) c 2 d fbd+fcd＝fdt (6) 0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3， 0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2， 0≤fdt≤2，w≥0
说明
u
{u,v}是2-点割集
不管去掉多少结点， 剩下的图仍然连通
v
8
图的连通性
之前介绍过割点、割边、连通图的概念； 这里再补充一些概念和理论； 在连通图中，连通的程度也是有高有低；
(a)
(b)
(c)
图(a)、(b)删掉一个割点后，就不连通了，而图(c)，不管删掉那个点， 图仍然连通。（或者也可以用删掉边的条数来说明）
去掉一个节点后，图不再连 通，或者连通分支增加了
u
v
7
点割集（顶点割集）
定义：
去掉结点集合后，图不再连 通，或者连通分支增加了
对图G，若V(G)的子集V’使得 w(G V ) w(G)，则称V’为图G 的一个点割集； 含有k个顶点的点割集称为k-点割集； 若V’是图G的一个点割集，而V’减少任意一个点都不再是G的 点割集，则称V’是G的一个极小点割集； G中含点数最少的点割集称为G的最小点割集。 割点是1－顶点割集； 完全图没有点割集。
15
引例：运输方案
连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj） 表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上 的数字表示这条运输线的最大通行能力（简称容量）； 产品经过交通网从V1输送到V6，现要求制定一个输送方案， 使得从V1运到V6的产品数量最多。
4 2 8 4 1 2 4 4 7 6 5 2 3
则称E’为图G的一个边割集。含有k条边的边割集称为 k-边割集。
对非平凡图G，若E’是一个边割集，则 G \ E 不连通； 一条割边构成一个1－边割集； S V (G ) ， 设 S V (G )， S , S ，记号[S,S’] 表示一端在S中 另一端在S’中的所有边的集合。对图G的每个边割集，必存在 非空的S V (G )，使得 [S, S ] 是G的一个边割集，其中S V \ S 。
4
s 1
2 4 2 1 3
3 3
4 3 5
1 6
2 4
5 t
26
定义：带权的有向图G=(V,E)，满足以下条件，则 称为网络流图(flow network)：
（1）仅有一个入度为0的顶点s，称s为源点(source)或
出发点； （2）仅有一个出度为0的顶点t，称t为汇点(sink) 或结 束点； （3）每条边(u,v)的权值都为非负数，称为该边的容量， 记作c(u,v)； 满足上述的条件的图称为网络流图，也可以记作记为 G=(V,E,c)
29
例：一个网络流图上的可行流：
a
(4,3)
容量
(3,2) (3,0)
容许流fat
s
(2,1) (3,2) (4,3)
b
(2,2)
t
(4,4)
(1,1)
(2,2)
(2,2)
c
d
30
整个流网络G的流量为： |f|=∑f(s,v)(v∈V) 或 |f|=∑f(u,t)(u∈V) 『三个重要性质』
容量约束：
4
2
3 8 3
产地 1
4 2 1 1
2
2 4
6
销地
19
4
2 3 8 3 2
产地 1
4 2 1 1
2 2 2 4 2 1 1
4
7 2 3 5 3
2 4
6
销地
4
产地 1
4