当前位置: 首页 > 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的过期时间…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...