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

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

news 2025/7/2 21:41:58

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

浏览器访问 AWS ECS 上部署的 Docker 容器（监听 80 端口）

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义（Task Definition&…...

编程新知 2025/6/30 3:36:38

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章传送阵>> 点我查看说明：假设每台服务器已…...

编程新知 2025/7/1 18:03:13

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

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

编程新知 2025/6/27 2:57:24

Java-41 深入浅出 Spring - 声明式事务的支持事务配置 XML模式 XML+注解模式

点一下关注吧！！！非常感谢！！持续更新！！！ 🚀 AI篇持续更新中！（长期更新） 目前2025年06月05日更新到： AI炼丹日志-28 - Aud…...

编程新知 2025/7/2 15:27:51

SpringCloudGateway 自定义局部过滤器

场景： 将所有请求转化为同一路径请求（方便穿网配置）在请求头内标识原来路径，然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

编程新知 2025/6/26 22:36:32

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

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

编程新知 2025/6/25 0:03:21

学习STC51单片机32（芯片为STC89C52RCRC）OLED显示屏2

每日一言今天的每一份坚持，都是在为未来积攒底气。案例：OLED显示一个A 这边观察到一个点，怎么雪花了就是都是乱七八糟的占满了屏幕。。解释 ： 如果代码里信号切换太快（比如 SDA 刚变，SCL 立刻变&#…...

编程新知 2025/6/26 10:08:51

基于Java Swing的电子通讯录设计与实现：附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘一、系统概述本电子通讯录系统采用Java Swing开发桌面应用，结合SQLite数据库实现联系人管理功能，并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能，同时可以最小化到系统…...

编程新知 2025/6/15 22:59:29

NXP S32K146 T-Box 携手 SD NAND（贴片式TF卡）：驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中，车辆不再仅仅是传统的交通工具，而是逐步演变为高度智能的移动终端。这一转变的核心支撑，来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒（T-Box）方案：NXP S32K146 与…...

编程新知 2025/6/26 6:57:08

Python Ovito统计金刚石结构数量

大家好，我是小马老师。本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构，但是无法直接输出结构的变化情况。本文使用python调用ovito包的方法，可以持续统计各步的金刚石结构，具体代码如下： from ovito…...

编程新知 2025/6/22 11:10:58