当前位置： 首页 > news >正文

[图论]哈尔滨工业大学（哈工大 HIT）学习笔记16-22

news 2025/7/4 11:35:42

视频来源：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）定义：设 G=\left ( V,E \right ) , 则 G 的补图 G{}'=\left ( V,E{}' \right ) , 其中 E{}'=\mathbb{P}_{2}\left ( V \right )\setminus E （所有顶点关联边二元集不包含E的子集）

（3）推论：G和它的补图G{}'有可能同构，即G\cong G{}'

（4）例题：六个人的团体中，或有三个人互相认识，或有三个人互相不认识。可用图和补图来做。

（5）拉姆齐定理：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识

\begin{aligned} &R\left(1,k\right) =1 \\ &R\left(2,k\right) =k \\ &R\left(p,q\right) =R\left(q,p\right) \\ &R\left(p,q\right) \leq R\left(p-1,q\right)+R\left(p,q-1\right)\textit{ if }p,q\geq2 \\ &R\left(p,q\right) \leq\binom{p+q-2}{p-1} \end{aligned}

2. 双图

2.1. 双图定理

（1）只用一刀切开所有边就好了，看边的两边是否在不同子图中。

（2）定理1：双图也称2部图，其中圈的度数一定为偶数（充分必要条件）。

证明：圈可以表示成 v_{1},v_{2},v_{3},...,v_{n},v_{1} ，若 v_{1}\in V ，则v_{2}\in V{}' 。因此单数顶点都属于 V， 偶数顶点都属于 V{}'

（2）定理2：有 G= \left ( V,E \right ) ，\exists v\in V，deg\, v> 0，\forall v\in V，deg\, v为偶数，则图中一定有圈

3. 图兰定理/托兰定理

（1）定理：设 G= \left ( V,E \right ) 是一个\left ( p,q \right ) 图，如其中没有三角形，则 q\leq \left [ \frac{p^{2}}{4} \right ] 。其中中括号为求整符号

（2）证明：显然，对于p=1,2,3时结论都成立。则分别证明p为奇数（p=2n-1）和偶数（p=2n）的情况；

假设p=2n-1时成立，则需证p=2n+1时成立

设p=2n-1的图G’，p=2n+1的图为G，有G-u-v=G';（u和v为两个顶点，若u,v连接，则它们一定没有公共邻接点，否则构成三角形；若它们不邻接，则可能存在公共邻接点。视频中老师应该是使他们邻接的，这样可以使第一个顶点u的邻接边假设到最大）

知G'是一个(2n-1,q')图，知 q{}'\leq \left [\frac{\left ( 2n-1 \right )^{2}}{4} \right ]=n^{2}-n;

deg\, u=k,deg\, v\leq p-k （u和v邻接，且无公共邻接点的情况）

q\leq q{}'+p \Rightarrow q\leq q{}'+2n\Rightarrow q\leq n^{2}+n\Rightarrow q\leq\left [ \frac{\left ( 2n+1 ^{2}\right )}{4} \right ]

4. 极图理论

（1）找到边最多的图，但不含K_{n}

5. 欧拉图

5.1. 欧拉迹

（1）定义：包含图的每一条边的迹

5.2. 欧拉闭迹

（1）定义：包含图的所有顶点的闭迹

5.3. 欧拉图

（1）定义：包含欧拉闭迹的图称为欧拉图

5.4. 欧拉定理

（1）定理1：G是欧拉图⇔G连通且每个顶点度为偶数

（2）定理2：图中有一条欧拉开迹⇔G中恰有2个奇度顶点

（3）定理3：设G有2n个奇度顶点，则G至少有n条迹

5.5. 伪图

（1）多重图定义：两个顶点可以之间有多条边

（2）带环图定义：存在顶点到自身的边

（3）伪图：包含多重图和带环图

http://www.lryc.cn/news/184448.html

相关文章：

  • 使用关键字abstract 声明抽象类-PHP8知识详解
  • Java中使用正则表达式
  • Python之字符串分割替换移除
  • ubuntu增加内存
  • 黑客都是土豪吗？真实情况是什么？
  • 企业想过等保，其中2FA双因素认证手段必不可少
  • Combination Lock
  • SpringBoot解决LocalDateTime返回数据为数组问题
  • 【数字人】2、MODA | 基于人脸关键点的语音驱动单张图数字人生成（ICCV2023）
  • 群狼调研（长沙物业第三方评优）开展房地产市场调查内容设计
  • 计算机网络-计算机网络体系结构-物理层
  • 微信小程序wxs标签 在wxml文件中编写JavaScript逻辑
  • C++设计模式-工厂模式（Factory Method）
  • 八大排序算法
  • 机器学习笔记 - 两个静态手势识别的简单示例
  • 2023年，有哪些好用的互联网项目管理软件？
  • python 按照文件大小读取文件
  • 黑客帝国代码雨
  • 基于SpringBoot的植物健康系统
  • Kettle连接数据库[MySQL]报错
  • Postman接口测试学习之常用断言
  • 自动化机器学习AutoML之flaml：利用flaml框架自动寻找最优算法及其对应最佳参数python
  • 支付宝sdk商户私钥 如何生成？
  • Linux之epoll理解
  • 龟速乘 - a * b爆ll且模数很大时的计算方法
  • 计算机网络笔记3 数据链路层
  • 如何实现矩阵的重采样问题
  • Spring-事务管理-加强
  • Minecraft个人服务器搭建自己的皮肤站并实现外置登录更换自定义皮肤组件
  • 解决ubuntu中没有网络连接的图标