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

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

news 2026/2/9 2:23:04

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

Python｜GIF 解析与构建（5）：手搓截屏和帧率控制

目录 Python｜GIF 解析与构建（5）：手搓截屏和帧率控制一、引言二、技术实现：手搓截屏模块 2.1 核心原理 2.2 代码解析：ScreenshotData类 2.2.1 截图函数：capture_screen 三、技术实现&…...

编程新知 2025/11/14 3:06:30

无法与IP建立连接，未能下载VSCode服务器

如题，在远程连接服务器的时候突然遇到了这个提示。查阅了一圈，发现是VSCode版本自动更新惹的祸！！！ 在VSCode的帮助->关于这里发现前几天VSCode自动更新了，我的版本号变成了1.100.3 才导致了远程连接出…...

编程新知 2026/1/22 21:24:01

聊聊 Pulsar：Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台，以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中，Producer（生产者） 是连接客户端应用与消息队列的第一步。生产者…...

编程新知 2026/2/5 21:34:41

ETLCloud可能遇到的问题有哪些？常见坑位解析

数据集成平台ETLCloud，主要用于支持数据的抽取（Extract）、转换（Transform）和加载（Load）过程。提供了一个简洁直观的界面，以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

编程新知 2026/2/3 12:56:31

Cloudflare 从 Nginx 到 Pingora：性能、效率与安全的全面升级

在互联网的快速发展中，高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司，近期做出了一个重大技术决策：弃用长期使用的 Nginx，转而采用其内部开发…...

编程新知 2026/1/29 21:20:51

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章参考资料源码： https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

编程新知 2026/1/31 14:55:53

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现（两者等价），用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例： 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

编程新知 2025/11/21 22:02:37

【学习笔记】深入理解Java虚拟机学习笔记——第4章虚拟机性能监控，故障处理工具

第2章虚拟机性能监控，故障处理工具 4.1 概述略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具命令：jps [options] [hostid] 功能：本地虚拟机进程显示进程ID（与ps相同），可同时显示主类&#x…...

编程新知 2026/1/15 1:34:10

Java面试专项一-准备篇

一、企业简历筛选规则一般企业的简历筛选流程：首先由HR先筛选一部分简历后，在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历例如：Boss直聘（招聘方平台） 直接按照条件进行筛选例如&#xff1a…...

编程新知 2026/1/26 19:10:48

有限自动机到正规文法转换器v1.0

1 项目简介这是一个功能强大的有限自动机（Finite Automaton, FA）到正规文法（Regular Grammar）转换器，它配备了一个直观且完整的图形用户界面，使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

编程新知 2026/1/31 13:13:32