佛山用户网站建设,谷歌外贸seo,网站开发维护,扬州市城乡建设局招标网站视频来源#xff1a;2.7.1 补图_哔哩哔哩_bilibili 目录
1. 补图
1.1. 补图
2. 双图
2.1. 双图定理
3. 图兰定理/托兰定理
4. 极图理论
5. 欧拉图
5.1. 欧拉迹
5.2. 欧拉闭迹
5.3. 欧拉图
5.4. 欧拉定理
5.5. 伪图 1. 补图
1.1. 补图
#xff08;1#xff09;…
视频来源2.7.1 补图_哔哩哔哩_bilibili 目录
1. 补图
1.1. 补图
2. 双图
2.1. 双图定理
3. 图兰定理/托兰定理
4. 极图理论
5. 欧拉图
5.1. 欧拉迹
5.2. 欧拉闭迹
5.3. 欧拉图
5.4. 欧拉定理
5.5. 伪图 1. 补图
1.1. 补图
1补图示例其中G为母图G为其补图 2定义设 , 则 的补图 , 其中 所有顶点关联边二元集不包含的子集
3推论和它的补图有可能同构即
4例题六个人的团体中或有三个人互相认识或有三个人互相不认识。可用图和补图来做。
5拉姆齐定理要找这样一个最小的数n使得n个人中必定有k个人相识或l个人互不相识 2. 双图
2.1. 双图定理
1只用一刀切开所有边就好了看边的两边是否在不同子图中。
2定理1双图也称2部图其中圈的度数一定为偶数充分必要条件。
证明圈可以表示成 若 则 。因此单数顶点都属于 偶数顶点都属于
2定理2有 为偶数则图中一定有圈 3. 图兰定理/托兰定理
1定理设 是一个 图如其中没有三角形则 。其中中括号为求整符号
2证明显然对于p1,2,3时结论都成立。则分别证明p为奇数p2n-1和偶数p2n的情况
假设p2n-1时成立则需证p2n1时成立
设p2n-1的图G’p2n1的图为G有G-u-vG;u和v为两个顶点若u,v连接则它们一定没有公共邻接点否则构成三角形若它们不邻接则可能存在公共邻接点。视频中老师应该是使他们邻接的这样可以使第一个顶点u的邻接边假设到最大
知G是一个(2n-1,q)图知 ; u和v邻接且无公共邻接点的情况 4. 极图理论
1找到边最多的图但不含 5. 欧拉图
5.1. 欧拉迹
1定义包含图的每一条边的迹 5.2. 欧拉闭迹
1定义包含图的所有顶点的闭迹 5.3. 欧拉图
1定义包含欧拉闭迹的图称为欧拉图 5.4. 欧拉定理
1定理1G是欧拉图⇔G连通且每个顶点度为偶数
2定理2图中有一条欧拉开迹⇔G中恰有2个奇度顶点
3定理3设G有2n个奇度顶点则G至少有n条迹 5.5. 伪图
1多重图定义两个顶点可以之间有多条边
2带环图定义存在顶点到自身的边
3伪图包含多重图和带环图
