离散数学 --- 图论基础 --- 子图和补图，握手定理

8月前作者：Metallic Cat 分类：Toy博客阅读(26) 违法举报

这篇具有很好参考价值的文章主要介绍了离散数学 --- 图论基础 --- 子图和补图，握手定理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第一部分 --- 子图和补图

1.生成子图：点集合不变，边集合是原图的边集合的子集

2.导出子图：点集合是原图点集合的非空子集V，然后再在原图的边集合中找到两个端点均在点集合V中的边元素，并将这些边元素称成一个新的边集合，得到的这个边集合就是导出子图的边集合

（点集合V和得到的新的边集合组成的新图是原图G的子图，被称为V导出的原图的子图，简称为V的导出子图）离散数学 --- 图论基础 --- 子图和补图，握手定理

1.一个图G可以是自身的子图，生成子图和导出子图

2.判断一个原图的子图是否是导出子图的方法：将子图中缺少的点在原图中删去，然后再将由于删去了点后少掉了一个端点的线给去掉，如果子图和这个修改后的原图相等的话，则这个子图就是原图的导出子图，否则就不是

3.一个集合的子集可以是自身，一个图的真子集除了不能是自身外盒子集没区别

离散数学 --- 图论基础 --- 子图和补图，握手定理

完全图就是图中的任意两个结点之间都有边相连

1.简单图是无环非多重图（无环：没有自己和自己连环状线，非多重图：两个结点间没有平行边（也可以没有边））

补充：简单图的邻接矩阵的主对角线（矩阵的左上角和右下角连线）上的元素都为0，因为简单图是没有结点自己和自己连接环状线的，所以根据定义对应位置上的元素为0

2.对于有序图而言两个端点之间没有平行边意味着一个方向上只有一条边 --- 比如A，B结点之间没有平行边意味着A指向B只有一条边，B指向A也只有一条边

3.对于无序图而言没有平行边意味着两个端点之间只有一条边离散数学 --- 图论基础 --- 子图和补图，握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

1.一个图的补图的点集合和原图一样，且边集合与原图的边集合并起来后等价于以原图的点集合为基础得到的完全图的边集合，也就是说完全图的边集合 - 原图的边集合 = 原图的补图的边集合（三个图的点集合都一样）离散数学 --- 图论基础 --- 子图和补图，握手定理

上面红色的就是补图

离散数学 --- 图论基础 --- 子图和补图，握手定理

注意原图的补图的点集合是和原图的点集合一样的，在画补图的时候，千万不要漏画点了离散数学 --- 图论基础 --- 子图和补图，握手定理

第二部分 --- 握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

1.对于有向图而言边的端点分为两种：一种是始点，一种是终点。结点作为一次始点时算作一次端点，作为一次终点时算作一次端点

而对于无向图而言边的端点就是占据边的两个边缘的点（两个边缘可以同时别一个点占据（环状线），此时这个点做了两次端点） --- 结点作为占据一次边的边缘时算作一次端点

2.注意悬挂结点要求的是总度数为1，而不只是出度或入度单独为1

离散数学 --- 图论基础 --- 子图和补图，握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

1.在无向图中，如果结点和结点自己以环状线相连的话，则这个结点同时占据了一个边的两个边缘，所以这个结点作为端点的次数要算两次

离散数学 --- 图论基础 --- 子图和补图，握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

握手定理：图中所有结点的度数和等于图中所有边的边数的两倍离散数学 --- 图论基础 --- 子图和补图，握手定理

离散数学 --- 图论基础 --- 子图和补图，握手定理

1. 偶数 + 奇数 = 奇数；奇数 * 偶数 = 偶数；偶数 * 偶数 = 偶数；奇数 * 奇数 = 奇数 ---> 这些关系就是上面那个推论的基础离散数学 --- 图论基础 --- 子图和补图，握手定理

注意是有向图中所有结点的出度和 = 所有结点的入度和 = 有向图的边数

离散数学 --- 图论基础 --- 子图和补图，握手定理

文章来源地址https://www.toymoban.com/news/detail-401070.html

到了这里，关于离散数学 --- 图论基础 --- 子图和补图，握手定理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

离散数学-图论-树（13）

定义1：连通无回路的无向图称为无向树,简称树.每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点. 定义2 设G=V,E是n阶m条边的无向图，则下面各命题是等价的: (1)G是树 (2)G中任意两个顶点之间存在惟一的

2024年02月03日
浏览(33)
【离散数学】4. 图论

1.数理逻辑 2. 集合论 3. 代数系统 4. 图论图：点+边+边与点的映射函数连通性与判别欧拉图与哈密尔顿图二分图和平面图与欧拉公式树及生成树单源点最短路径：Dijkstra算法对偶图 4.1.1 图一个图G是一个三重组 V ( G ) , E ( G ) , Φ G V(G),E(G),Phi_G V ( G ) , E ( G ) , Φ G V(G)是一

2024年02月10日
浏览(29)
[离散数学]图论

点相同边相同 $$ 必要条件节点数相同边相同度数相同节点数目相同 m = C n 2 = 5 ∗ 4 / 2 = 10 m=C_n^2=5*4/2=10 m = C n 2 = 5 ∗ 4/2 = 10 n = 5 n=5 n = 5 由推论 m ≤ 3 n − 6 le3n-6 ≤ 3 n − 6 得 m ≤ 9 le9 ≤ 9 相互矛盾 ∑ d e g ( v i ) = 2 e = 2 V − 2 sum deg(v_i)=2e =2V -2 ∑ d e g ( v i ) = 2 e =

2024年02月05日
浏览(192)
离散数学图论

1、V,E是一个图 2、零图：图的边集E为空集 3、平凡图：只有一个结点的零图 4、平行边： 5、多重图：有平行边的图 6、简单无向图：一个无向图( 没有平行边 )( 没有自回路 ) 7、简单有向图：一个有向图( 没有平行边 )( 没有自回路 ) 8、简单图：( 没有平行边 )( 没有自回路 )的

2024年02月08日
浏览(29)
离散数学 | 图论五色定理证明

看来一下午终于看懂了，甚至差点睡过去…… 趁热打铁记录一下自己的理解。任意一个简单的连通平面图点着色至多五色。一、设 G 为一个至少有三个结点的连通平面图，则 G 中必有一个结点 u，u 的度数 deg(u)≤5。 Step1：证明简单连通平面图 G 中一定存在一个顶点，其

2024年02月01日
浏览(26)
【离散数学】图论

目录无向图与有向图定义特殊的图顶点与边的关联与相邻无向图和有向图的度数握手定理度数列可图化最大度和最小度多重图与简单图无向完全图与有向完全图子图与补图子图生成子图补图通路与回路定义图的连通性连通图可达几种连通图的矩阵

2024年02月13日
浏览(28)
【离散数学】测试五图论

目录图论系列文章 1. n层正则m叉树一共有（）片树叶。 A. nm B. mn C. mn 正确答案： B 2. 下图是一棵最优二叉树 A. 对 B. 错正确答案： B 3. 要构造权为1，4，9，16，25，36，49，64，81，100一棵最优二叉树，则必须先构造权为5，9，16，25，36，49，64，81，100一棵最优二叉树

2024年02月09日
浏览(29)
头歌实训-离散数学-图论！

5阶无向完全图的边数为：10 设图 G 有 n 个结点， m 条边，且 G 中每个结点的度数不是 k ，就是 k+1 ，则 G 中度数为 k 的节点数是： n(k+1)-2m 若一个图有5个顶点，8条边，则该图所有顶点的度数和为多少？16 他让输出关联矩阵和邻接矩阵这不简单么？我是直接摆烂了输出个球呀

2024年02月04日
浏览(55)
离散数学——图论

图的定义现实世界中许多现象能用某种图形表示，这种图形是由一些点和一些连接两点间的连线所组成。例子：a，b，c，d 4个篮球队进行友谊比赛。为了表示４个队之间比赛的情况，我们作出图7.1.1的图形。在图中４个小圆圈分别表示这４个篮球队，称之为结点。如果两队

2024年02月02日
浏览(182)
离散数学期末复习（4）：图论（Graphs）

目录 10.1 Graphs and Graph Models (图和图模型) 10.2 Graph Terminology and Special Types of Graphs (图的术语和几种特殊图) 1.基础概念 2. 度（degree）（1）无向图中一个顶点v的度是这个点相关的边的数量，写作deg(v) （2）握手定理（3）出度和入度 3.图的分类（1）圈图（Cycles）（2）轮图

2024年02月03日
浏览(25)