2023年7月19日发(作者：)

【离散数学】图论基础知识⽂章⽬录1 图的基本概念⽆向图：简⽽⾔之，边不带⽅向的图就是⽆向图。有向图：简⽽⾔之，边带⽅向的图就是有向图。特殊定义：有限图：边数和顶点数都是有限个的图。n阶图：n个顶点的图。零图：没有边的图。平凡图：只有⼀个顶点，⽽且没有边的图（1阶零图）。空图：没有顶点的图（⾃然也没有边，空图也是零图）。环：边的两头都是同⼀个顶点，这个边就是环。孤⽴点：没有边连着的点。⽆向图顶点的度：顶点的度：⼀个顶点有⼏个边连接着，就是⼏度(注意，环会提供两度）。悬挂顶点：度数为1的顶点。悬挂边：悬挂顶点连着的那个边。最⼩度：⼀个图中各顶点度数中最⼩的数值。最⼤度：⼀个图中各顶点度数中最⼤的数值。有向图顶点的度出度：从⼀个顶点出去的边的边数。⼊度：从外⾯进⼀个顶点的边数。总度数：总度数=⼊度+出度。最⼤⼊度：图中所有顶点中⼊度最⼤的数值。最⼤出度：图中所有顶点中出度最⼤的数值。最⼩⼊度：图中所有顶点中⼊度最⼩的数值。最⼩出度：图中所有顶点中出度最⼩的数值。握⼿定理图的顶点度数和数量是边数的2倍，证明很显然，⼀个边会提供两度。由握⼿定理推出的推论，图的奇度顶点为偶数个。证：如果有奇数个奇度顶点，那么图的总度数必定为奇数，⽽根据握⼿定理，总度数必定为偶数，⽭盾。度数列度数列就是将⼀个图中所有顶点的度按⼀定顺序写出来。注意：判断⼀个数列是否能构成度数列，先看是否满⾜握⼿定理推论(偶数个奇度顶点）。简单图简单图：不存在平⾏边的图，即每两个顶点之间最多只有⼀条边。完全图和正则图⽆向完全图就是任⼀个顶点都与其他所有顶点之间有边，边数：n(n-1)/2，最⼤度=最⼩度=n-1，记作Kn。k—正则图：每个顶点都是k度的⽆向简单图。圈图和轮图圈图Cn就是围成⼀个圈的图，轮图Wn就是在圈图Cn-1中放⼀个点，再把这个点和其它所有点连起来。（注：圈图顶点数>=3，轮图顶点数>=4）⼦图⼦图：从母图中选⼀些点和边构成的图就是该母图的⼦图。⽣成⼦图：删边不删点。导出⼦图：选母图中⼀些点构成点集，这些点和以它们为端点的边构成的图就是这个这个点集的导出⼦图；选母图中⼀些边构成边集，这些边和与它们关联的顶点构成的图就是这个这个边集的导出⼦图；补图补图：将原图补成完全图，再将原图中有的边删掉，就是补图。图的同构同构：同构就是指同⼀个图的不同画法。找⾮同构的⽅法就是根据条件找到不同的度数列，然后试着画出不同结构的图（类似有机化学中找同分异构体）。2 图的连通性通路和回路简单回路：回路中所有边各异。初级回路（圈）：回路中所有点各异（⾃然，边也各异，所以初级回路是简单回路）。⽆向图的连通性和连通分⽀连通就是两点之间有通路（能从⼀点⾛到另⼀点）；连通图就是任意两点都连通的图（特别的，平凡图是连通图）；连通分⽀就是图中的⼀个不跟其它部分连通的部分，连通图只有⼀个连通分⽀。短程线和距离短程线就是两点之间最短的通路，其长度称作距离。点割集和边割集点割集：删掉图中的⼀些点后，图的连通分⽀数增加，且这些点缺⼀不可，这些点的集合就是点割集，如果点割集只有⼀个点，这个点叫做割点；边割集：删掉图中的⼀些边后，图的连通分⽀数增加，且这些边缺⼀不可，这些边的集合就是边割集，如果边割集只有⼀个点，这个点叫做割边或桥。点连通度和边连通度点割集的元素数就是点连通度，如果没有点割集就是（总顶点数-1）；边割集的元素数就是边连通度。有向图的弱连通与强连通弱连通就是有向图忽略⽅向以后为连通图，强连通就是有向图中任意两个顶点相互可达。3 图的矩阵表⽰⽆向图的关联矩阵⽆向图关联矩阵：⾏代表边，列代表顶点。数值为0代表不关联，1代表关联，2代表成环。特殊性质：每⼀列的和为2，因为每⼀列代表⼀个边所关联的顶点，⼀个边关联两个顶点；每⼀⾏的和该顶点的度，显⽽易见；所有数加起来是边数的⼆倍,因为根据握⼿定理，总度数之和为边数的⼆倍。有向⽆环图的关联矩阵有向⽆环图关联矩阵：⾏代表边，列代表顶点。数值为1代表边从顶点出去，0代表不关联，-1代表边从顶点进来。邻接矩阵⾏和列都是顶点，矩阵数值是列对应顶点邻接到⾏对应顶点的边的条数。利⽤邻接矩阵求各个长度的通路和回路数量说明:A^n中的元素表⽰⼀个顶点到另⼀个顶点之间距离为n的通路数。所以可以通过矩阵乘法求邻接矩阵的n次⽅求有向图中的通路和回路数。例：可达矩阵可达矩阵；矩阵的⾏和列都是顶点，只要⼀个顶点可达另⼀个顶点，就为1，否则是0，⽆向图连通当且仅当这个图的可达矩阵的元素全为1，有向图强连通当且仅当这个图的可达矩阵的元素全为1。邻接矩阵转可达矩阵的⽅法假设图的顶点数为n，由邻接矩阵(A)计算可达矩阵§的⽅法如下：1.B = A + A ^ 2 + … + A ^ (n-1);2.将B的对⾓线元素全变成1，将B的⾮零元素全变为1.4 ⼏种特殊的图4.1 ⼆部图⼆部图定义⼆部图：如果能将⼀个图的所有顶点分为两份，图中的所有边的两个端点⼀个再⼀份⾥，⼀个在另⼀份⾥，这样的图就叫做⼆部图。完全⼆部图就是图中每⼀个顶点都跟另⼀份中的所有顶点相邻的⼆部图。⼆部图的判别定理（充要条件）证明如下：染⾊法判断⼆部图染⾊法：从图的⼀个顶点开始，将它染成红⾊，所有与它邻接的顶点染成⽩⾊，所有与刚刚染成红⾊的顶点相邻的顶点染成红⾊，如此反复，如果能不冲突地将图中所有点都染上⾊，说明这个图是⼆部图，举例如下：匹配匹配：在⼆部图中选⼀部分互不相邻的边，这些边就是原⼆部图的⼀个匹配。极⼤匹配：如果在已经选好的匹配中，再加任意⼀条边都不再是匹配，那么这个匹配就是极⼤匹配。最⼤匹配：⼀个图中边数最多的匹配(最⼤匹配是极⼤匹配)。完备匹配：如果V1=n-1则有哈密顿通路，>=n则有哈密顿回路。如果简单⽆向图的最⼩度>=n/2，则是哈密顿图，如果⼀个有向图略去⽅向以后所得⽆向图中含有⼦图Kn（n阶完全图），则有哈密顿通路。哈密顿图的应⽤（周游问题）先将本题转化成图论问题，将每个⼈看作点，如果两个⼈能交谈，就连上边，画出图以后，如果能找到哈密顿回路，那么就能坐成⼀圈。4.4 平⾯图平⾯图的定义平⾯图的概念⽐较抽象：如果⼀个图可以边不相交地画在平⾯上，那么就是平⾯图。如果⽆论怎么话都⽆法使边不相交，就不是平⾯图，如下图：(1)虽然有边相交，但是⼀个图并没有规定画成什么样⼦，只要顶点个数，边的个数，顶点和边之间的关联不变，那么两个图就是同构的，（1）的⼀种同构为（2），边不相交，所以图（1）是平⾯图，（2）是（1）的平⾯嵌⼊。（3）（4)同理。平⾯图的⾯和次数对于⾯的边界的判断容易出错，如下：注意到外部⾯R0的边界中，d应该记作两次，因为⾯的边界是以回路定义的；两个不同的回路之间要⽤逗号隔开。平⾯图⾯的次数和与边数的关系极⼤平⾯图简单平⾯图中，任意再加⼀条边就不是平⾯图了，这个平⾯图就是极⼤平⾯图。极⼤平⾯图的充分必要条件⼀个图是极⼤平⾯图的充要条件是它的所有⾯的次数都是3，注意外部⾯的次数也应该是3.平⾯图欧拉公式⼀个连通的平⾯图⾥，顶点数-边数+⾯数=2。更⼀般地：在有多个连通分⽀时，顶点数-边数+⾯数=连通分⽀数+1。注意：此处的l是⾯次最⼩值。利⽤该定理可以证明不是平⾯图，例如：平⾯图的充要条件（库拉图斯基定理）⾸先说明什么是同胚和收缩：同胚就是两个图同构，或者经过反复插⼊消去⼆度顶点后同构。收缩就是将两个点之间的边删掉，然后将这两个点“捏”到⼀起，变成⼀个点。库拉图斯基定理就是：图是平⾯图当且仅当这个图不与K5,K3,3同胚，也⽆可收缩为K5，K3,3的⼦图。库拉图斯基定理⽐较难理解，通过如下 实例可便于理解：⼀般来说，如果⼀个图含与K5,K3,3同胚的⼦图，那么也含能收缩到K5，K3,3的⼦图。因为收缩⽐同胚要直观，所以这⾥⽤收缩来解释这两道例题：第⼀个图可以先删除图中所有⿊⾊的边，之所以可以删除，是因为我们要找的是可以收缩为K5或K33的⼦图，然后最上和最下两个顶点可以收缩到左边相邻的顶点（也可以理解成删除这个点），最后就得到了K3,3，所以不是平⾯图；第⼆个图同理，删除两条⿊边，然后收缩最下⾯的两个点到相邻的点（也可以理解成删除这个点），最后收缩成了K5，所以不是平⾯图。对偶图简⽽⾔之，对偶图就是，原图的点变成⾯，⾯变成点。为了实现这个变换，将原图中的每个⾯（包括外部⾯）中画⼀个点，如果两个⾯原来相邻，那就通过每⼀条相邻边都画⼀条新的线来连接新的两个点，最后画出来的图就是对偶图，如下图所⽰：实线和空⼼点是原图，红⾊虚线和实⼼点是对偶图。对偶图的性质桥变环，环变桥，边数不变，顶点数和⾯数互换，⾯的次数对应点的度数。5 ⽆向树⽆向树的定义如果⼀个图是连通的⽽且没有回路，这个图就是树。⽆向树的性质以下三条任意满⾜两条，图就是树：1.连通2.⽆回路3.m=n-16 ⽣成树⽣成树的定义成⼦图（删边不删点）如果是树，这个树就是这个点的⽣成树。⽣成树的存在性⼀个⽆向连通图的⽣⽆向连通图都有⽣成树，可⽤破圈法证明。最⼩⽣成树总权值最⼩的⽣成树就是最⼩⽣成树。找最⼩⽣成树的⽅法如下：克鲁斯卡尔算法简⽽⾔之，从权最⼩的边开始按从⼩到⼤开始选择，如果不与已经选好的边构成回路，就选择这条边，直到对所有边的选择结束，就找到了最⼩⽣成树。例：红⾊为选择的，⿊⾊是不选择的，注意，环不选择，如果有权值⼀样的边，则随便选择⼀个，然后选择另⼀个。