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

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

news 2026/2/3 23:01:02

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

css实现圆环展示百分比，根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

编程新知 2026/1/26 22:27:53

vscode（仍待补充）

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用侧边栏 vscode还能连接ssh？ debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

编程新知 2026/1/24 13:04:10

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯第三方负载均衡（如 HAProxy、AWS NLB、阿里 SLB）发起上游连接时，将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后，ngx_stream_realip_module 从中提取原始信息…...

编程新知 2026/1/4 5:02:00

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码注：文档 https://developers.weixin.qq…...

编程新知 2026/1/29 8:41:55

跨链模式：多链互操作架构与性能扩展方案

跨链模式：多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石一、跨链架构的核心范式演进 1. 分层协议栈：模块化解耦设计现代跨链系统采用分层协议栈实现灵活扩展（H2Cross架构）： 适配层&#xf…...

编程新知 2026/1/31 9:33:35

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

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

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

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列？2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

编程新知 2026/1/23 10:10:53

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ；并安装。基础操作不再赘述。打开 macOS 终端，开始 docker 安装mysql之旅第一步 docker search mysql 》〉docker search mysql NAME DE…...

编程新知 2026/1/24 12:29:11

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

编程新知 2026/1/25 13:33:35

Redis：现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发，其初衷是为了满足他自己的一个项目需求，即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源，Redis凭借其简单易用、…...

编程新知 2025/11/15 1:41:43