离散数学-图论知识总结
文章目录
图论
基本概念
-
无序对和无序积:集合A&B={(a,b)|aA,bB},(a,b)=(b,a)
-
图:一个序偶<V,E>,V是结点集,E:边集,E中每个元素都有V中的结点对与之对应称之边。
-
图的表示:集合表示,图形表示,邻接矩阵
-
若两个结点vi,vj是边e的端点,则称vi,vj互为邻接点,具有公共节点的两条边称为邻接边,两个端点相同的边称为环或者自回路。图中不与任何点相邻接的结点叫孤立节点
-
仅含一个结点的零图叫做平凡图。
-
图的分类:无向图,有向图,混合图,多重图(有平行边),线图(非多重图),简单图(无环线图),赋值图,如G=<V,E,g>,g是从E到非负实数集合的函数
-
若V1V,E1E,则G1为G的子图,记为G1G
-
若,G1是G的生成子图
-
设且以V2为结点集,以两个端点均在V2中的边的全体边集的G的子图称为V2的导出子图
-
完全图:无向简单图:所有节点之间都有边相连,记为Kn
有向简单图:任意两个结点都有两条方向相反的有向边相连。
其矩阵除对角线上的元素为0,其余元素为1
-
补图:G为简单图<V,E>,G‘为完全图<V1,E1>。G1=<V,E1-E>为G的补图,记为(从完全图中删除G中的边)两个结点在中相邻在G中不相邻
-
度数:图G=<V,E>中以结点vV为端点的次数之和称为结点v的度数,记为deg(v),环记两次,有向图中以v为始点的次数称为v的出度,记为deg(v)以结点v为终点的次数称为v的入度,记为deg(v).deg(v)=入度加出度。deg(v)=1称为悬挂结点,以悬挂结点的边称为悬挂边。
- 用邻接矩阵计算度数:若G是无向图:deg(vi)=。有向图:deg+(vi)=;deg-(vi)=
-
握手定理:度数总和=2|E|。
推论:度数为奇数的结点个数为偶数。
有向图出度之和=入度之和=边数
-
图的同构:设两个图G=<V,E>,G’=<V,E’>,若存在VV’,使得对于任意e=(vi,vj)E,当且仅当e’=(g(vi),g(vj))E’,并且e和e’重数相同,称G与G’同构。
-
同构的必要条件:结点数目相等,边数相等,度数相同的节点数相同
-
路:给定图G=<V,E>,设v0,…vnV,e1,e2,…,enE,其中ei是关联结点vi-1和vi的边,交替序列voe1v1e2…envn称为连接v0到vn的路。若路中的所有边全不相同,则称此路为一条迹。若路中所有节点不同,则称此路为通路。
- v0和vn分别为该路的起点和终点,统称为路的端点。
- 路中边的条数称为路的长度。
- 若v0=vn,称为回路。
-
在一个具有n个结点的图中,如果从结点vj到结点vk存在一条路,则从结点vj到结点vk必存在一条不多于n-1条边的路
- 在无向图中G中,如果从结点vj到结点vk存在一条路,则必存在一条从vj到vk而长度小于n的通路
-
无向图的连通性
- 设G=<V,E>是一个图,对vi,vjV,从vi 到vj如、exist是一条路则称结点vi和vj 是连通的
- 设G=<V,E>是一个无向图,若G中任意两个结点之间都是连通的,则称该无向图G是一个无向连通图,否则,则称G是一个非连通图(分离图)
- 设G=<V,E>是一个无向图,该无向图G中的每个连通的划分块称为G的一个连通分支,用W(G)表示G中的连通分支数。无向图是连通图当且仅当W(G)=1
-
删除结点和边
- 删除结点:在图中删除结点v是把v以及、并为大哥v关联的边都删除
- 删除边:仅删除该边
-
割点:设无向图G=<V,E>是连通的,若有结点集V1是V的、素白色条,使得图G删除了V1的所有结点后,所得的子图是不连通的,而删除了V1的任意子集后,所得的子图还是连通图则称集合V1是图G的点割集。若某一个结点就构成点割集,则称该结点是割点。
- 一个连通图删除它的一个点割集后,将分成两个或者多于两个连通分支
- 若G不是完全图,定义k(G)=min{V1|V1是G的点割集}为G的点连通度。连通度是为了产生一个不连通图需要删除点的最少个数。
-
割边:设无向图G=<V,E>是连通的,若有边集E1是E的真子集,使得图G删除了E1 的所有边后,所得的子图是不连通的,而删除了E1的任意真子集后,所得子图仍是连通图。则称集合E1是图G的边割集。若某一边构成边割集,则称该边是割边(桥)。
- G的割边也就是G的一条边e使得W(G-r)>W(G)。、并为大哥点连通度相似,定义非平凡图G的连通度为:,边连通度是为了产生一个不连通图需要删去边的最少数目。
-
有向图的连通性:设G=<V,E>是一个有向图。对vi.vjV,从vi到vj如、exist是一条路,则称结点vi到vj是可达的。
- 设G=<V,E>是一个有向图,若略去G中所有有向边的方向后得到的无向图是一个无向连通图,则称该有向图G是一个弱连通图。
- 设G=<V,E>是一个有向图,若G中任意两个结点之间至少单方向是可达的,则称该有向图G是一个单侧有向图。
- 设G=<V,E>是一个有向图,若G中任意两个结点之间都是相互可达的,则称该有向图是一个强连通图。
-
一个有向图G是强连通图当且仅当G中有一个回路,至少包含每一个结点一次
矩阵
邻接矩阵
设G=<V,E>是一个简单图,,则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中:
令C=A,此时cij表示从vi到vj长度为m的路的数目。
可达性矩阵
设G=<V,E>是一个简单图,V={v1,v2,v3,…,vn},,则bij表明了从结点vi到vj长度为1至n的所有路数目之和。如bn=0,则表明从结点vi到vj是不可达的。如bij$\neq$0,则表明从结点vi到vj至少有长度为m(1<=m<=n)的通路.
定义:设G=<V,E>是一个简单图,V={v1,…vn},定义一个n阶方阵P=(pij)其中:
利用布尔矩阵运算直接求可达性矩阵:
P=
完全关联矩阵
定义:给定无向图C,令v1,v2,…,vp和e1,e2,…,eq分别记为G的结点和边,则矩阵M(G)=(mij),其中:
如:
定义:给定简单有向图G=<V,E>,V={v1.v2,…,vp},E={e1,e2,…,eq},p*q阶矩阵M(G)=(mij),其中:
矩阵与图连通性的关系:
-
无向简单图G是连通图当且仅当它的可达性矩阵P所有元素均为1
-
有向简单图G是强连通图当且仅当它的可达性矩阵P的所有元素均为1
-
有向简单图G是单侧连通图当且仅当它的可达性矩阵P及其转置矩阵经布尔求(并)和运算后所得矩阵中除对角线以外其余元素均为1
-
有向简单图G是弱连通图当且仅当它的邻接矩阵A及其转置矩阵经布尔求和(并)运算后作为新的邻接矩阵而求出的可达性矩阵中所有元素均为1
欧拉图
无向欧拉图
定义
给定G是一个无孤立节点的无向图,若存在一条路(回路),经过图中每边一次且仅一次,则此路(回路)为该图的一条欧拉路(回路)。具有欧拉回路的图叫做欧拉图。
判定定理
无向图G=<V,E>具有一条欧拉路当且仅当G是连通的,且仅有0个或者两个奇度数结点。
无向图G=<V,E>是欧拉图当且仅当G是连通的且G的所有结点的度数都是偶数
有向欧拉图
定义
给定G是一个无孤立节点的有向图,若存在一条单向路(回路)经过图中每边一次且仅一次,则称此单向路(回路)为该图的一条单向欧拉路(回路)。具有单向欧拉回路的图叫做欧拉图。
定理
有向图G=<V,E>具有一条单向欧拉路当且仅当G是连通的,且除了两个结点以外,其余结点的入度等于出度,而这两个例外的结点中,一个结点的入度比出度大一,另一个结点的出度比入度大1
有向图G=<V,E>是欧拉图当且仅当G是连通的,且所有结点的入度等于出度
哈密尔顿图
定义
给定G是一个无孤立节点的无向图,若存在一条路(回路),经过图中每个结点一次且仅一次,则此路(回路)为该图的一条哈密尔顿路(回路)。具有哈密尔顿回龙路的图称为哈密尔顿图。
必要条件
若图G=<V,E>具有哈密尔顿回路,则对于结点集V的每一个非空子集S均有W(G-S)|S|成立,其中W(G-S)是G-S的连通分支数。
充分条件
设G具有n个结点的简单图,如果G中每一对结点的度数之和大于等于n-1,则在G中存在一条哈密尔顿路。
设图G是具有n个结点的简单图,如果G中每一对结点的度数大于等于n,则在G中存在一条哈密尔顿回路。
闭包:给定图G=<V,E>有n个结点,若将图G中的度数之和至少是n的非邻接结点连接起来得G‘,对图G’重复上述步骤,直到不再有这样的结点为止,所得的图称为原图G的闭包。记作C(G).
当且仅当一个简单图的闭包是哈密尔顿图时,这个简单图是哈密尔顿图
平面图
定义
设G是一个无向图,若经过某种改画,能把G中所有结点和边都画在一个平面上,使得任何两边除公共结点之外没有其他交叉点,则称G为平面图,若G无论如何改画,它们的边之间总有交叉现象出现,则G是非平面图。结点数小于等于4的都是平面图。
一个有限平面图面的次数之和等于其边数的两倍。
欧拉公式
定理:设G=<V,E>是一个连通的平面图
- 若它有v个结点,e条边,r个面,则有:v-e+r=2
- 若G中无环,且每一个面至少由三条边围成,则有:e<=3v-6
- 若G中无环,且每一个面至少由k条边围成,则有:(k-2)e<=kv-2k
库拉托夫斯基图
插入和删除一个新的度数为2的结点,使一条边分成两条边,或者对于关联于一个度数为2的结点的两条边,去掉这个结点,是两条边变成一条边,这些都不印象图的平面性。
定义:给定两个图G1和G2,若它们是同构的,或通过反复插入或去除度数为2 的结点后,使得G1和G2同构,则称该图是在2度结点内同构
定理:一个图是平面图,当且仅当它不包含与k33或K5在2度结点内同构的子图。K33和K5常称为库拉托夫斯基图
对偶图
定义:给定平面图G=<V,E>,它有面F1,F2,…,Fn,若有图G*=<V*,E*>满足下述条件:
- 对于图G的任一个面Fi,内部有且仅有一个结点vi*V*
- 对于图G的面Fi,Fj的公共边ek,存在且仅存在一条边ek*E*,使ek*=(vi*,bj*),且ek*和ek相交。
- 当且仅当ek只是一个面Fi的边界时,vi*存在一个环ek*和ek相交,则图G*是图G的对偶图。
从这个定义看出,G*是G的对偶图,则G也是G*的对偶图。一个连通平面图的对偶图也必是平面图。
如果图G的对偶图G*同构于G,则称G是自对偶的。
着色
图G的正常着色(或简称为着色)是指对它的每一个结点指定一种颜色,使得没有两个相邻的结点有同一种颜色。如果图G在着色时有n种颜色,称G为n-色的。对于图G着色时,需最少的颜色数称为着色数,记为x(G).
韦尔奇鲍威尔法:
- 将图G的结点按照度数的递减顺序进行排列。
- 用第一种颜色对第一点进行着色,并且按排列次序,对于前面着色点不邻接的每一点着相同色
- 用第二种颜色对尚未着色的点进行重复步骤2,用第三种颜色继续这种做法,直到所有的点全部上色
对于n个结点的完全图Kn,有x(Kn)=n
设G是至少有三个结点的连通平面图,则G中必有一个结点u,使得deg(u)<=5
任意平面图G至多是5-色的
树
无向树
设T是一个连通且回路的无向图,则称T为无向树,简称树。树的度数为1的结点称为树叶,度数大于1的结点称为分枝点(内点)。
不含任何回路的简单无向图为森林
森林中的每一个连通的分支都是一棵树
性质
定理:设G=<V,E>是一个简单无向图,则以下关于图的定义都是等价的:
- G是连通的且不含回路的
- G中无回路,且m=n-1,其中,m是边数,n是结点数
- G是连通的,且m=n-1
- G无回路,但在G中的任何二结点之间增加一条新边,就得到唯一的一条回路
- G是连通的,但删除G中任意一条边后,就不连通
- G中每一对结点之间有唯一的一条路
任意非平凡的数T至少有两片树叶
生成树
-
定义:设G=<V,E>是一个连通的无向图,若G的某个生成子图是一棵树,则称该树为G的生成树,记为T。生成树T中的边称为树枝;在G中而不在中的边称位弦,的所有弦的集合称为生成树的补
-
定理:
- 任意一个连通图G至少存在一颗生成树。一个无向连通图G,如果G是一棵树则它的生成树是唯一的,即是G本身;如果不是,那么它的生成树就不是唯一的
- 一条回路和任意一棵生成树的补至少有一条公共边。
- 一个边割集和任何生成树至少有一条公共边
-
求生成树的方法
- 破圈法:每次去掉回路中的一条边,其去掉的边的总数是m-(n-1)
- 避圈法:每次选取G中的一条边,该边不能与已经选取的边构成回路,此时选取的边的总数是n-1
-
最小生成树:假设图G具有n个结点的连通图,对应于G的每一条边e,指定一个正数C(e),把C(e)称作边e权,G的生成树也具有一个树权,它是T的所有边权的和。在带全的图G的所有生成树中,树权最小的那颗生成树称作最小生成树
-
克鲁斯科尔算法:
设图G有n个结点
- 选择权最小的边e1,置边数i=1
- i=n-1结束否则转3
- 设定已选定e1,…ei在G中选取不同于ei的边e,使无回路且满足此条件的权最小的边
- i=i+1,转2
有向树
设G=<V,E>是一个简单有向图,若略去图G中所有边的方向后,得到的无向图是一棵树,则称这个有向图是一棵有向树
根树
-
一棵非平凡的有向树,如果恰好有一个结点的入度为0,其余所有结点的入度均为1,则称此有向树为根树。入度为0的结点称为树根,出度为0的结点称为树叶,出度不为0的结点称为内点,又将内点同树根统称为分枝点
-
根树包括一个或多个结点,这些节点的某一个称为根,其他所有结点被分成有限个子根树
-
在根树T中,任意一个结点v及其所有后代导出的子图T1称为T的以v为树根的子树
-
在根树中,任意一个结点v的层次即是从根到该结点的单向通路的长度,而同级的结点具有相同的通路长度
-
在根树中,若vi到vj可达,则称vi是vj的祖先,vj是vi的后代。若<vi,vj>是根树的有向边,则称vi是vj的父亲,vj是vi的儿子;如果两个结点是同一结点的儿子结点,则称这两个结点是兄弟
k叉树
-
若在根树T=<V,E>=(n,m)中,对任意结点viV,都满足
- deg+(vi)<k,则称此根树是k叉树
- deg+(vi)=k或deg+(vi)=0,则此根树为完全k叉树
- 在完全k叉树中若所有树叶层次相同,称为正则k叉树
- 在上述1,2,3中,当k=2时,此时分别称它们为二叉树,完全二叉树,正则二叉树
-
在二叉树中,每个结点v至多有两个儿子,分别称为左儿子结点和右儿子结点,二叉树的每个结点v至多有两棵子树,分别称为v的左子树和右子树
-
在完全k叉树中,若树叶数为t,分枝点树为j,则(k-1) j =t-1
-
将k叉树转换为二叉树的步骤:
从根节点逐级开始,按从左到右的顺序进行:
- 除了最左边的分枝点外,删除所有从每一个结点长出的分支,在同一层级中,兄弟结点用从左到右的有向边连接
- 若一个结点是某一节点的最左边的儿子结点,则在二叉树中作为某一个结点的左儿子。
- 若一个结点与前一个结点是兄弟结点,则在二叉树中作为前一个结点的右儿子。
- 森林转换成二叉树:
- 先把森林中的每一个树转换成一棵二叉树
- 除第一棵二叉树外,依次将剩下的每颗二叉树作为左边二叉树的根的右子树,直到所有的二叉树都练成一棵二叉树为止
最优树
-
在根树中,一个结点的通路长度,就是从树根到此结点的通路的边数。分枝点的通路长度称作内部通路长度,树叶的通路长度称作外部通路长度
-
给定一组权w1,w2,…,wt,不妨设w1<=w2<=…<=wt。设有一棵二叉树,共有t片树叶,分别带权w1,w2,…,wt,该二叉树称作带权二叉树
-
在带权二叉树中,若带权为wi的树叶其通路长度为L(wi),把称为该带权二叉树的权,在所有带这些权的二叉树中,使w(T)最小的那棵树,称作最优二叉树
-
设T为带权的最优二叉树,(w1<=w2<=…wt)
- 带权为w1,w2的树叶是兄弟
- 以树叶w1,w2为儿子的分枝点,其通路长度最长
-
设T带权的最优树,若将带权w1,w2的树叶为儿子的分枝点改为带权w1+w2的树叶,得到一棵树T‘,则T’也是最优树(w1<=w2<=…<=wt)
前缀码
给定一个序列集合,若没有一个序列是另一个序列的前缀,该序列集合称位前缀码
定理:任何一棵二叉树的树叶可对应一个前缀码
任何一个前缀码都对应一棵二叉树