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

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

news 2026/2/8 8:43:26

视频来源：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）伪图：包含多重图和带环图

相关文章：

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

视频来源：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）…...

编程日记 2023/10/7 22:22:08

使用关键字abstract 声明抽象类-PHP8知识详解

抽象类只能作为父类使用，因为抽象类不能被实例化。抽象类使用关键字abstract 声明，具体的使用语法格式如下： abstract class 抽象类名称{ //抽象类的成员变量列表 abstract function 成员方法1(参数); //抽象类的成员方法 abstract functi…...

编程日记 2023/10/7 22:18:02

Java中使用正则表达式

正则表达式正则表达式（Regular Expression）是一种用于匹配、查找和替换文本的强大工具。它由一系列字符和特殊字符组成，可以用来描述字符串的模式。在编程和文本处理中，正则表达式常被用于验证输入、提取信息、搜索和替换文本等…...

编程日记 2023/10/7 22:16:00

Python之字符串分割替换移除

Python之字符串分割替换移除分割 split(sepNone, maxsplit-1) -> list of strings 从左至右sep 指定分割字符串，缺省的情况下空白字符串作为分隔符maxsplit 指定分割的次数，-1 表示遍历整个字符串立即返回列表 rsplit(sepNone, maxsplit-1) -> …...

编程日记 2023/10/7 22:15:00

ubuntu增加内存

文章目录 1、硬盘操作步骤第二步：点击【扩展】（必须关闭ubuntu电源才能修改）第三步：修改【最大磁盘容量大小】1、硬盘操作步骤最近发现Ubuntu空间不足，怎么去扩容呢？第一步：点击【硬盘】第二步：点击【扩展】（必须关闭ubuntu电源才能修改）第三步：修改【最大磁…...

编程日记 2023/10/7 22:12:58

黑客都是土豪吗？真实情况是什么？

黑客的利益链条真的这么大这么好么,连最外围的都可以靠信息不对称赚普通人大学毕业上班族想都不敢想的金钱数目,黑客们是不是基本都是土豪网络技术可以称为黑客程度的技术是不是真的很吃香？如果大部分大学生的智力资源都用在学习网络技术，会不会出现僧…...

编程日记 2023/10/7 22:10:54

企业想过等保，其中2FA双因素认证手段必不可少

随着信息技术的飞速发展，网络安全问题日益凸显。等保2.0时代的到来，意味着企业和组织需要更加严格地保护自身的信息安全。而在这个过程中，双因素认证的重要性逐渐得到广泛认可。本文将探讨 2FA 双因素认证的重要性。在了解 2FA 双因素认证的…...

编程日记 2023/10/7 22:08:51

Combination Lock

题目描述新学期开学，您又回到了学校。您需要记住如何操作储物柜上的组合锁。一个组合锁的常见设计如图 1 所示。组合锁有一个圆形刻度表盘，在表盘上，有 40 个编号为从 0 至 39 的刻度，正上方有一个刻度指针。一个组合由这些数字…...

编程日记 2023/10/7 22:07:50

SpringBoot解决LocalDateTime返回数据为数组问题

现象： 在SpringBoot项目中，接口返回的数据出现LocalDateTime对象被转换成了数组原因分析： 默认序列化情况下会使用SerializationFeature.WRITE_DATES_AS_TIMESTAMPS。使用这个解析时就会打印出数组。解决方法： 在配置类中…...

编程日记 2023/10/7 22:06:49

【数字人】2、MODA | 基于人脸关键点的语音驱动单张图数字人生成（ICCV2023）

文章目录一、背景二、方法2.1 问题描述和数据预处理2.2 Mapping-Once network with Dual Attentions2.3 Facial Composer Network2.4 使用 TPE 来合成人像图片三、效果3.1 训练细节3.2 数据3.3 测评指标3.4 结果比较四、代码4.1 数据前处理4.2 训练4.3 推理论文&#xff1a…...

编程日记 2023/10/7 22:03:45

群狼调研（长沙物业第三方评优）开展房地产市场调查内容设计

湖南房地产市场近年来表现出多元化的发展趋势。为了在竞争激烈的市场中获得更好的发展，房地产企业需要密切关注市场变化，合理规划开发项目，同时提高产品质量和服务水平，以满足消费者的需求和期望。群狼调研(长沙神秘顾客调查)在房…...

编程日记 2023/10/7 22:01:43

计算机网络-计算机网络体系结构-物理层

目录一、通信基础通信方式传输方式码元传输率 *二准则 2.1奈氏准则(奈奎斯特定理) 2.2香农定理三、信号的编码和调制 *数字数据->数字信号数字数据->模拟信号模拟数据->数字信号模拟数据->模拟信号 *四、数据交换方式电路交换报文交换…...

编程日记 2023/10/7 22:00:42

微信小程序wxs标签在wxml文件中编写JavaScript逻辑

PC端开发可以在界面中编写JavaScript脚本 vue/react这些框架更是形成了一种常态因为模板引擎和jsx语法本身就都是在js中的我们小程序中其实也有类似的奇妙写法不过先声明这东西不是很强大我们可以先写一个案例代码 wxml代码参考 <view><wxs module"wordSt…...

编程日记 2023/10/7 21:59:40

C++设计模式-工厂模式（Factory Method）

目录 C设计模式-工厂模式（Factory Method） 一、意图二、适用性三、结构四、参与者五、代码 C设计模式-工厂模式（Factory Method） 一、意图定义一个用于创建对象的接口，让子类决定实例化哪一个类。Factory…...

编程日记 2023/10/7 21:58:39

八大排序算法

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N1e510; int q[N]; int w[N],s[N]; int n,sz; //直接插入排序 ,对于某一个元素加入到一个有序的序列中，将该元素依次从该位置开始 //从后往前比较&…...

编程日记 2023/10/7 21:51:29

机器学习笔记 - 两个静态手势识别的简单示例

一、关于手势识别手势识别方法通常分为两类：静态或动态。静态手势是那些只需要在分类器的输入处处理单个图像的手势，这种方法的优点是计算成本较低。动态手势需要处理图像序列和更复杂的手势识别方法。进一步了解可以参考下面链接。静态手势识别和动态手势识别的区别和技…...

编程日记 2023/10/7 21:48:26

2023年，有哪些好用的互联网项目管理软件？

项目管理是为了使工作项目能够按照预定的需求、成本、进度、质量顺利完成，而对人员、产品、过程和项目进行分析和管理的活动。一直以来，项目管理被企业管理人员和各级人员所重视，项目管理是一个项目的灵魂，只有做好了项目管理&am…...

编程日记 2023/10/7 21:45:19

python 按照文件大小读取文件

返回一个list，每个list里面是一个元组(filename, file_size)，按照file_size从小到大排序的 import osdef get_sorted_files(dir_path):# 存储最后的文件路径files []# 便利dir_path下面的文件或者文件夹for file in os.listdir(dir_path):file_path o…...

编程日记 2023/10/7 21:44:19

黑客帝国代码雨

黑客帝国代码雨奉上,之前一直想写,但一直没抽出时间来,今天把他写了,也算了了装心事效果图如下原理就不讲了,代码写的很清楚而且不长有不懂的评论区问我就好 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8">&l…...

编程日记 2023/10/7 21:43:18

基于SpringBoot的植物健康系统

目录前言一、技术栈二、系统功能介绍系统首页咨询专家普通植物检查登记珍贵植物检查登记植物救治用料登记植物救治材料管理植物疾病案例管理三、核心代码 1、登录模块 2、文件上传模块 3、代码封装前言随着信息技术在管理上越来越深入而广泛的应用&am…...

编程日记 2023/10/7 21:40:16

网络编程（Modbus进阶）

思维导图 Modbus RTU（先学一点理论） 概念 Modbus RTU 是工业自动化领域最广泛应用的串行通信协议，由 Modicon 公司（现施耐德电气）于 1979 年推出。它以高效率、强健性、易实现的特点成为工业控制系统的通信标准。包…...

编程新知 2026/2/7 23:18:34

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤： 1）请求大小调整：首先，malloc 需要调整用户请求的大小，以适应内部数据结构（例如，可能需要存储额外的元数据）。通常，这包括对齐调整，确保分配的内存地址满足特定硬件要求（如对齐到8字节或16字节边界）。 2）空闲…...

编程新知 2025/11/1 5:21:39

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装（Encapsulation） 定义：将数据（属性）和操作数据的方法绑定在一起，通过访问控制符（private、protected、public）隐藏内部实现细节。示例： public …...

编程新知 2025/10/6 4:03:40

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件，常用于在两个集合之间进行数据转移，如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。核心特性与用法基本属性 v-model：绑定右侧列表的值&…...

编程新知 2026/2/4 4:25:40

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06（十亿美元）。漏洞扫描服务市场行业预计将从 2024 年的 3.48（十亿美元）增长到 2032 年的 9.54（十亿美元）。预测期内漏洞扫描服务市场 CAGR（增长率&…...

编程新知 2026/2/4 12:43:08

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

编程新知 2025/12/14 11:45:25

【Java_EE】Spring MVC

目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递注意事项编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据编辑RequestBody …...

编程新知 2026/2/1 16:32:53

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

编程新知 2025/10/3 17:30:30

【HarmonyOS 5 开发速记】如何获取用户信息（头像/昵称/手机号）

1.获取 authorizationCode： 2.利用 authorizationCode 获取 accessToken：文档中心 3.获取手机：文档中心 4.获取昵称头像：文档中心首先创建 request 若要获取手机号，scope必填 phone，permissions 必填 …...

编程新知 2025/9/17 2:39:21

【 java 虚拟机知识第一篇】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍内存模型主要分…...

编程新知 2026/1/31 8:12:12