做电子商城网站,深圳做二类学分的网站,企业安全文化建设方案,软件开发app制作公司文章目录1 图的基本概念2 图的连通性3 图的矩阵表示4 几种特殊的图4.1 二部图4.2 欧拉图4.3 哈密顿图4.4 平面图5 无向树6 生成树1 图的基本概念
无向图#xff1a; 简而言之#xff0c;边不带方向的图就是无向图。 有向图#xff1a; 简而言之#xff0c;边带方向的图就…
文章目录1 图的基本概念2 图的连通性3 图的矩阵表示4 几种特殊的图4.1 二部图4.2 欧拉图4.3 哈密顿图4.4 平面图5 无向树6 生成树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 二部图
二部图定义 二部图如果能将一个图的所有顶点分为两份图中的所有边的两个端点一个再一份里一个在另一份里这样的图就叫做二部图。完全二部图就是图中每一个顶点都跟另一份中的所有顶点相邻的二部图。 二部图的判别定理充要条件 证明如下 染色法判断二部图 染色法从图的一个顶点开始将它染成红色所有与它邻接的顶点染成白色所有与刚刚染成红色的顶点相邻的顶点染成红色如此反复如果能不冲突地将图中所有点都染上色说明这个图是二部图举例如下 匹配 匹配在二部图中选一部分互不相邻的边这些边就是原二部图的一个匹配。 极大匹配如果在已经选好的匹配中再加任意一条边都不再是匹配那么这个匹配就是极大匹配。 最大匹配一个图中边数最多的匹配(最大匹配是极大匹配)。 完备匹配如果V1V2图中一个匹配的边数与V1相等这个匹配叫做完备匹配。 完美匹配V1V2匹配中的边数与V1,V2相等。 存在完备匹配的条件 Hall定理有完备匹配当且仅当任取V1中K个顶点这K个顶点至少和V2中的K个顶点相邻。(充分必要条件 t条件二部图中能找到这样的正整数t使得V1中每个顶点至少关联t条边V2中每个顶点至多关联t条边则有完备匹配。充分非必要条件 二部图的应用 (完备性问题) 可以将匹配、完备问题建模成二部图问题然后使用Hall定理或者t条件来解决例 本题是一个完备性问题化成二部图以后找完备匹配即可。 1可用t条件找到t22找不到t但是满足相异性条件(3)找不到t且不满足相异性条件。
4.2 欧拉图
欧拉图定义 图中能找到一个经过所有边仅一次且经过所有顶点的回路这个图就是欧拉图。欧拉回路是简单回路但不一定是初级回路也就是说同一顶点可以多次经过)。 无向图的欧拉图判定定理 无向图是连通的而且没有奇度顶点就有欧拉回路就是欧拉图。图是连通的且仅有两个奇度顶点就有欧拉通路但没有欧拉回路。 有向图的欧拉图判定定理 有向图是连通的而且所有顶点入度等于出度就有欧拉回路是欧拉图。是连通且一个顶点入度比出度大1一个顶点出度比入度大1其余入度等于出度就有欧拉通路。 欧拉图的应用一笔画问题 戈尼斯堡七桥不能不重复的走完因为有BCD三个奇度顶点所以无欧拉通路。
4.3 哈密顿图
哈密顿图定义 图中能找到过所有顶点且仅过一次的回路那么这个图就是哈密顿图对边无要求 显然哈密顿通路是初级通路哈密顿回路是初级回路特别的定义平凡图是哈密顿图。 哈密顿图的必要条件 如果一个图是哈密顿图那么删去这个图中n个顶点后所得图的连通分支数一定pn。该定理是哈密顿图的必要条件一般用来证明一个图不是哈密顿图即找到一个有n个顶点的点集删去以后剩下的图的连通分量数大于n那么这个图一定不是哈密顿图如下图中: a删去红色点后有两个连通分量不是哈密顿图实际上有割点的图不是哈密顿图b删去5个红点以后有6个连通分量不是哈密顿图。一般来说使用该定理时优先删去度数大的顶点。 哈密顿回路通路的充分条件 简单无向图中任两个不相邻的顶点度数和n-1则有哈密顿通路n则有哈密顿回路。如果简单无向图的最小度n/2则是哈密顿图如果一个有向图略去方向以后所得无向图中含有子图Knn阶完全图则有哈密顿通路。 哈密顿图的应用周游问题 先将本题转化成图论问题将每个人看作点如果两个人能交谈就连上边画出图以后如果能找到哈密顿回路那么就能坐成一圈。
4.4 平面图
平面图的定义 平面图的概念比较抽象如果一个图可以边不相交地画在平面上那么就是平面图。如果无论怎么话都无法使边不相交就不是平面图如下图 (1)虽然有边相交但是一个图并没有规定画成什么样子只要顶点个数边的个数顶点和边之间的关联不变那么两个图就是同构的1的一种同构为2边不相交所以图1是平面图2是1的平面嵌入。34)同理。 平面图的面和次数 对于面的边界的判断容易出错如下 注意到外部面R0的边界中d应该记作两次因为面的边界是以回路定义的两个不同的回路之间要用逗号隔开。 平面图面的次数和与边数的关系 极大平面图 简单平面图中任意再加一条边就不是平面图了这个平面图就是极大平面图。 极大平面图的充分必要条件 一个图是极大平面图的充要条件是它的所有面的次数都是3注意外部面的次数也应该是3. 平面图欧拉公式 一个连通的平面图里顶点数-边数面数2。 更一般地在有多个连通分支时顶点数-边数面数连通分支数1。 注意此处的l是面次最小值。利用该定理可以证明不是平面图例如 平面图的充要条件库拉图斯基定理 首先说明什么是同胚和收缩 同胚就是两个图同构或者经过反复插入消去二度顶点后同构。 收缩就是将两个点之间的边删掉然后将这两个点“捏”到一起变成一个点。 库拉图斯基定理就是图是平面图当且仅当这个图不与K5,K3,3同胚也无可收缩为K5K3,3的子图。库拉图斯基定理比较难理解通过如下 实例可便于理解 一般来说如果一个图含与K5,K3,3同胚的子图那么也含能收缩到K5K3,3的子图。因为收缩比同胚要直观所以这里用收缩来解释这两道例题 第一个图可以先删除图中所有黑色的边之所以可以删除是因为我们要找的是可以收缩为K5或K33的子图然后最上和最下两个顶点可以收缩到左边相邻的顶点也可以理解成删除这个点最后就得到了K3,3所以不是平面图第二个图同理删除两条黑边然后收缩最下面的两个点到相邻的点也可以理解成删除这个点最后收缩成了K5所以不是平面图。 对偶图 简而言之对偶图就是原图的点变成面面变成点。为了实现这个变换将原图中的每个面包括外部面中画一个点如果两个面原来相邻那就通过每一条相邻边都画一条新的线来连接新的两个点最后画出来的图就是对偶图如下图所示 实线和空心点是原图红色虚线和实心点是对偶图。 对偶图的性质 桥变环环变桥边数不变顶点数和面数互换面的次数对应点的度数。
5 无向树
无向树的定义 如果一个图是连通的而且没有回路这个图就是树。 无向树的性质 以下三条任意满足两条图就是树 1.连通 2.无回路 3.mn-1
6 生成树
生成树的定义 一个无向连通图的生成子图删边不删点如果是树这个树就是这个点的生成树。 生成树的存在性 无向连通图都有生成树可用破圈法证明。 最小生成树 总权值最小的生成树就是最小生成树。找最小生成树的方法如下 克鲁斯卡尔算法 简而言之从权最小的边开始按从小到大开始选择如果不与已经选好的边构成回路就选择这条边直到对所有边的选择结束就找到了最小生成树。例 红色为选择的黑色是不选择的注意环不选择如果有权值一样的边则随便选择一个然后选择另一个。
