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

[图论]哈尔滨工业大学(哈工大 HIT)学习笔记23-31

视频来源:4.1.1 背景_哔哩哔哩_bilibili

目录

1. 哈密顿图

1.1. 背景

1.2. 哈氏图

2. 邻接矩阵/邻接表

3. 关联矩阵

3.1. 定义

4. 带权图


1. 哈密顿图

1.1. 背景

(1)以地球为建模,从一个大城市开始遍历其他大城市并且返回,每个顶点只能被通过一次

1.2. 哈氏图

(1)定义:如果G中有生成圈,则称G为哈氏图

(2)和欧拉图的区别:欧拉图是一个顶点可以通过多次,只要把边画完就好。但哈密顿图一个顶点只能经过一次

(3)染色:

        ①同一条边的两个顶点染上不同的颜色

        ②每个顶点都需染色

        ③一共只能染两种颜色

        ④特例1:不能成功染色但是是哈密顿图,可以在哈密顿圈上补点

        ⑤特例2:不是哈密顿图但是可以成功染色(因此一定要判断是不是圈):

        ⑥⭐若能染,但是染完两个颜色个数不一样多,一定不是哈密顿图

(4)必要条件:G=\left ( V,E \right )S\subseteq V,设 w\left ( \right ) 为求支,若是哈密顿则有:

w\left ( G-S \right )\leq \left | S \right |

(5)充分条件:

        ①定理1:顶点大于3时,任何一个顶点的度都大于p/2

证明:若一个图G不是哈密顿图,则存在有u,v不邻接的。则一直加边,加到是哈密顿图为止。这时去掉一条边,G变成哈密顿路,形似1.2.(3)⑤。

        ②定理2:若不相邻两顶点度数之和大于等于p,则G是哈密顿图

        ③定理3:若不相邻两顶点度数之和大于等于p-1,则G中有哈密顿路

2. 邻接矩阵/邻接表

(略)数据结构学过了

3. 关联矩阵

3.1. 定义

(1)纵轴为顶点,横轴为边,关联则标1。

(2)重视顶点和边之间的关系

(3)示例

4. 带权图

略。老师只抛出了问题,没有说求解办法。

相关文章:

[图论]哈尔滨工业大学(哈工大 HIT)学习笔记23-31

视频来源:4.1.1 背景_哔哩哔哩_bilibili 目录 1. 哈密顿图 1.1. 背景 1.2. 哈氏图 2. 邻接矩阵/邻接表 3. 关联矩阵 3.1. 定义 4. 带权图 1. 哈密顿图 1.1. 背景 (1)以地球为建模,从一个大城市开始遍历其他大城市并且返回…...

Nginx+Keepalived实现服务高可用

Nginx 和 Keepalived 是常用于构建高可用性(High Availability)架构的工具。Nginx 是一款高性能的Web服务器和反向代理服务器,而Keepalived则提供了对Nginx服务的健康状态监测和故障切换功能。 下载Nginx 在服务器1和服务器2分别下载nginx …...

picodet onnx转其它芯片支持格式时遇到

文章目录 报错信息解决方法两模型精度对比 报错信息 报错信息为: Upsample(resize) Resize_0 not support attribute coordinate_transformation_mode:half_pixel. 解决方法 整个模型转换过程是:paddle 动态模型转成静态,再用paddle2onnx…...

【学习笔记】CF704B Ant Man

智商不够啊,咋想到贪心的😅 非常经典的贪心模型🤔 首先,从小到大将每个 i i i插入到排列中,用 D P DP DP记录还有多少个位置可以插入,可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注…...

SQLines数据迁移工具

Data and Analytics Platform Migration - SQLines Tools SQLines提供的工具可以帮助您在不同的数据库平台之间传输数据、转换数据库模式(DDL)、视图、存储过程、包、用户定义函数(udf)、触发器、SQL查询和SQL脚本。 SQLines SQL Converter OverviewCommand LineConfigurati…...

pkl文件与打开(使用numpy和pickle)

文章目录 1. 什么是pkl文件2. 如何打开?Reference 1. 什么是pkl文件 1)python中有一种存储方式,可以存储为.pkl文件。 2)该存储方式,可以将python项目过程中用到的一些暂时变量、或者需要提取、暂存的字符串、列表、…...

3d渲染农场全面升级,好用的渲染平台值得了解

什么是渲染农场? 渲染农场是专门从事 3D 渲染的大型机器集合,称为渲染节点,这些机器组合在一起执行一项任务(渲染 3D 帧和动画)。通过将渲染工作分配给数百台机器,可以显着减少渲染时间,从而使…...

1.5 JAVA程序运行的机制

**1.5 Java程序的运行机制** --- **简介:** Java程序的运行涉及两个主要步骤:编译和运行。这种机制确保了Java的跨平台特性。 **主要内容:** 1. **Java程序的执行过程**: - **编译**:首先,扩展名为.jav…...

基于FPGA的拔河游戏设计

基于FPGA的拔河游戏机 设计内容: (1)拔河游戏机需要11个发光二极管排成一行,开机 后只有中间一个亮点,作为拔河的中间线。 游戏双方 各持一个按键,迅速且不断地按动产生脉冲,哪方按 得快,亮点就向哪方移动, 每按一次,亮点移动一次。 移到任一方二极管的终端,该方就…...

关联规则挖掘(下):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据…...

8、【Qlib】【主要组件】预测模型:模型训练和预测

8、【主要组件】预测模型:模型训练和预测 简介基本类Example简介 预测模型(Forecast Model)旨在对股票做出预测评分。用户可以通过 qrun 在自动化工作流中使用预测模型。 由于 Qlib 中的组件设计成了松耦合方式,预测模型也可以作为一个独立模块使用。 基本类 Qlib 提供了…...

kettle安装

kettle安装 安装java环境 mkdir /data/java ln -s /data/java/ /opt/ cd /opt/javatar zxvf jdk-8u171-linux-x64.tar.gz#java export JAVA_HOME/opt/java/jdk1.8.0_171 export JRE_HOME$JAVA_HOME/jre export CLASSPATH$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH export PATH$J…...

基于生物地理学优化的BP神经网络(分类应用) - 附代码

基于生物地理学优化的BP神经网络(分类应用) - 附代码 文章目录 基于生物地理学优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.生物地理学优化BP神经网络3.1 BP神经网络参数设置3.2 生物地理学算法应用 4…...

第二证券:买基金1w一个月能赚多少?

跟着经济的开展和出资观念的改动,越来越多的人开始出资基金,购买基金已成为普遍且盛行的出资方式之一。在这个商场中,人们最重视的问题莫过于“买基金1w一个月能赚多少?”本文将从多个角度分析这一问题,协助出资者更全…...

蓝桥杯每日一题2023.10.7

跑步锻炼 - 蓝桥云课 (lanqiao.cn) 题目描述 题目分析 简单枚举&#xff0c;对于2的情况特判即可 #include<bits/stdc.h> using namespace std; int num, ans, flag; int m[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool is_ren(int n) {if((n %…...

Linux 系统为何产生大量的 core 文件?

Author&#xff1a;rab 目录 一、问题分析二、解决方案扩展 一、问题分析 上一篇刚讲到《Docker 配置基础优化》&#xff0c;这里再补充一下。就在中秋国庆这段小长假里&#xff0c;接收到了线上服务器磁盘告警通知&#xff0c;线上服务器架构是一个 Docker Swarm 集群&#x…...

Web_python_template_injection SSTI printer方法

这题挺简单的 就是记录一下不同方法的rce python_template_injection ssti了 {{.__class__.__mro__[2].__subclasses__()}} 然后用脚本跑可以知道是 71 {{.__class__.__mro__[2].__subclasses__()[71]}} 然后直接 init {{.__class__.__mro__[2].__subclasses__()[71].__i…...

TCP/IP网络江湖——江湖导航(网络层上篇)

目录 一、引言 二、IP地址与路由 三、IP协议与数据包转发 3.1 IP协议:网络江湖的规矩...

数据结构——AVL树(详解 + C++模拟实现)

文章目录 前言AVL树的概念AVL树节点的定义AVL树类框架AVL树的插入AVL树的旋转新节点插入较高子树的左侧 —— 左左: 右单旋新节点插入较高右子树的右侧——右右: 左单旋新节点插入较高左子树的右侧 —— 左右&#xff1a; 先左单旋然后再有单旋新节点插入较高右子树的左侧&…...

redis 雪崩,穿透,击穿及解决方案

一、缓存雪崩&#xff1a; 1. 原因: 缓存雪崩是指在我们设置缓存时大量采用了相同的过期时间&#xff0c;导致缓存在某一时刻同时失效&#xff0c;请求全部转发到DB&#xff0c;DB瞬时压力过重雪崩。 2. 解决方案: 将失效时间分散&#xff0c;通过生成随机数使得key的过期时间…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

MySQL中【正则表达式】用法

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

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...