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

关于一笔画问题的一些思考(欧拉路Fleury算法、逐步插入回路法、以及另一种可能的解法)

前言

这是一个经典的图论问题了

最近复习离散的时候又恰好看到了,发现自己以前的解法似乎有点bug

然后开始出反例卡自己,结果发现卡不掉?

然后再好好想了想,发现这个看起来有问题的做法可能确实没问题。

注意:欧拉路、欧拉回路、欧拉图、半欧拉图四个概念的区别

Fleury算法

这是离散数学书上的经典求解欧拉路的算法之一

非常好理解,只不过如何快速判断正在删边的图的桥实现起来比较麻烦,如果没有好的数据结构的支持,时间复杂度将会多乘一个(n+m),所以正常情况下我们不用Fleury算法来求解欧拉路

逐步插入回路法

这个方法离散数学书上并没有细讲,而仅仅只用一句话带过了

我们可以先来看看定理15.1(欧拉回路的判定定理)的充分性证明

充分性:G是无向连通图且没有奇度顶点=>G中存在欧拉回路(G是欧拉图)

大致意思就是

(1)G中必定存在圈

书中用可以证明四个字带过了

这个可以用极大路径法证明

因为δ(G)≥2,那么找一条图中的极大路径,路径的端点一定存在一条边连向路径中的点(否则路径就可以继续延长,与极大路径矛盾),这样就会构成一个圈。

(2)删掉这个圈后,剩下的连通分支都是欧拉图(由归纳法假设可得)

(3)以这个大圈上的一点为出发点,走到与删掉后的连通分支上的点后,先把子欧拉回路走完,然后再继续向前走。

证明过程如此,那么如何将其转换为算法呢?

可以利用归纳法的思想,对图G进行分治,先任意找圈,然后删圈,判连通性,在各个连通分支递归,答案返回后再一起整合……反正写起来巨麻烦,而且没必要

另一种可能的解法

为什么说是可能呢,因为我也感觉自己不能很严谨的证明这个做法的正确性

先上代码:

这里省略了对图进行(半)欧拉图判定的过程以及选起始点的过程

只保留了计算的主体部分

可以说是非常诡异,初看时觉得有点道理,细想之后发现完全不对劲,但是它却AC了

于是我开始举反例

8

0 1 1 1 1 0 1 1

1 0 1 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 0 0 1 1 0 0

1 0 0 1 0 1 0 0

0 0 0 1 1 0 0 0

1 0 0 0 0 0 0 1

1 0 0 0 0 0 1 0

可以发现程序的dfs过程确实时错误的,但是最后输出的结果确实对的

关键就是在于保存答案的位置和输出答案的顺序。

dfs输出的位置是入栈的位置,而保存答案的位置是出栈的位置

Fluery算法告诉我们,我们在做一笔画时出错的原因是,在不必要的时候先走了桥,导致没办法走回来

也就是说,我们应该最后走桥

虽然这个做法中我们并不能保证我们最后走的是桥

但是我们知道

先走桥的肯定会先出栈(因为会走不通,导致退栈回溯)

所以过桥的答案一定会被先统计到

而且最后又是倒序输出,这样就间接地保证了过桥之后的答案最后输出

也就间接地保证了这个做法的正确性。

这个做法是OI中比较普遍的欧拉路求解算法,然而我的这个证明是很不严谨的,希望有识之士可以补充更加严谨的证明。

完结撒花~~~~( •̀ ω •́ )y

相关文章:

关于一笔画问题的一些思考(欧拉路Fleury算法、逐步插入回路法、以及另一种可能的解法)

前言这是一个经典的图论问题了最近复习离散的时候又恰好看到了,发现自己以前的解法似乎有点bug然后开始出反例卡自己,结果发现卡不掉?然后再好好想了想,发现这个看起来有问题的做法可能确实没问题。注意:欧拉路、欧拉回…...

vlookup怎么用详细步骤,看这一篇就够了

1、vlookup函数:使用方法 以下便是vlookup函数,功能、语法和参数用法: excel函数vlookup 2、vlookup函数:查询参数 首先,选中F2单元格,然后在编辑栏输入函数公式:VLOOKUP(E2,B&…...

雅思经验(9)之小作文常用词汇总结

写作:关于趋势的上升和下降在小作文中,真的是非常常见的,所以还是要积累一下。下面给出了很多词,但是在雅思写作中并不是词越丰富,分数就越高的。雅思写作强调的是准确性:在合适的地方用合适的词和句法。不…...

【Python语言基础】——Python NumPy 数组创建

Python语言基础——Python NumPy 数组创建 文章目录 Python语言基础——Python NumPy 数组创建一、Python NumPy 数组创建一、Python NumPy 数组创建 创建 NumPy ndarray 对象 NumPy 用于处理数组。 NumPy 中的数组对象称为 ndarray。 我们可以使用 array() 函数创建一个 NumP…...

【大数据】Hadoop-Kms 安装及相关详细配置,看完你就会了

简介 Hadoop KMS是基于Hadoop的KeyProvider API的加密密钥管理服务器,它提供了使用REST API通过HTTP进行通信的客户端和服务器组件。 客户端是一个KeyProvider实现,使用KMS HTTP REST API与KMS交互。 KMS及其客户端具有内置的安全性,它们支…...

SpringCloud分布式框架

SpringCloud分布式框架 SpringCloud框架 Spring Cloud 是一个用于创建分布式系统的开源框架。它基于 Spring Boot 和 Spring Framework,提供了一整套关于分布式系统的工具和技术。 Spring Cloud 是微服务架构的一种实现方式,它提供了一整套完整的技术…...

Csss属性display,visibility区别,对渲染页面的影响

display: none; 与 visibility: hidden; 的区别 相同: 它们都能让元素不可见 区别:display:none;会让元素完全从渲染树中消失,渲染的时候不占据任何空间; visibility: hidden;不会让元素从渲染树消失,渲染时元素继续…...

怎么给笔记本电脑外接两台显示器?

我们在办公室会看见不少同事的电脑不止一台显示器,多屏确实可以提高工作效率。有的游戏党也会选择给电脑外接显示器,带来绝佳的体验。 不过要怎么把将外部显示器连接到笔记本电脑上?驱动人生在这里教给大家给笔记本外接显示器的做法。 一、…...

生成树协议 — STP

目录 一、环路的出现 1、广播风暴: 2、MAC地址表翻滚: 二、生成树 1、定义: 2、生成树使用的算法: 三、802.1D 1、BPDU: 2、TCN—拓扑变更消息(也是BPDU): 3、部分名词&am…...

git必会的知识点

注:本文参考https://www.liaoxuefeng.com/wiki/896043488029600 原文非常值得一读,作者学识渊博,补充了很多有意思的知识。我仅仅是拾人牙慧。 git是最先进的分布式版本控制系统。 版本控制系统——自动记录系统中文件的改动情况&#xff0…...

【hello, world】计算机系统漫游

文章目录hello程序信息就是位 上下文程序被其他程序翻译成不同的格式预处理阶段编译阶段汇编阶段链接阶段了解编译系统如何工作是大有益处的优化程序性能理解链接时出现的错误避免安全漏洞处理器读并解释储存在内存中的指令系统的硬件组成总线I/O设备主存处理器运行hello程序高…...

1. SpringMVC 简介

文章目录1. SpringMVC 概述2. SpringMVC 入门案例2.1 入门案例2.2 入门案例工作流程3. bean 加载控制4. PostMan 工具1. SpringMVC 概述 SpringMVC 与 Servlet 功能等同,均属于 Web 层开发技术。SpringMVC 是 Spring 框架的一部分。 对于 SpringMVC,主…...

《解谜三星堆:开启中华文明之门》-范勇 笔记

甲篇 应重视民间流传的疑似三星堆的文物,对其展开充分的研究,以发现更多关于三星堆的秘密,并且避免“敦煌窘境”,让我国的三星堆学术研究处于世界领先地位!(书中就讲到了在民间首次发现了圆形玉器&#xf…...

锐捷(十四)mpls vxn optionc的关键问题所在和具体问题分析

用锐捷的设备搭建mpls vxn optionc的基础版和带RR的版本,在控制平面和转发平免上分析mpls vxn optionc的关键问题所在和具体问题分析。一 基础mpls vxn optionc:核心:两pe之间之间建立MP EBGP邻居,从而直接传递路由解放了ASBR。关…...

Python语言零基础入门教程(十四)

Python 日期和时间 Python 程序能用很多方式处理日期和时间,转换日期格式是一个常见的功能。 Python 提供了一个 time 和 calendar 模块可以用于格式化日期和时间。 时间间隔是以秒为单位的浮点小数。 每个时间戳都以自从1970年1月1日午夜(历元&…...

Https 协议超强讲解(一)

都说Https协议非常安全,那为什么还是会被抓包呢?抓包后会影响什么吗? HTTPS协议 随着 HTTPS 建站的成本下降,现在大部分的网站都已经开始用上 HTTPS 协议。大家都知道 HTTPS 比 HTTP 安全,也听说过与 HTTPS 协议相关…...

5.Redis 实现点赞 优化登陆(验证码 token..)

Redis(1)简介Redis 是一个高性能的 key-value 数据库原子 – Redis的所有操作都是原子性的。多个操作也支持事务,即原子性,通过MULTI和EXEC指令包起来。非关系形数据库数据全部存在内存中,性能高。(2&#…...

scscanner:一款功能强大的大规模状态码扫描工具

关于scscanner scscanner是一款功能强大的大规模状态码扫描工具,该工具可以帮助广大研究人员从一个URL列表文件中批量读取目标网站的状态码响应信息。除此之外,该工具还可以过滤出指定的状态码,并将结果存储到一个文件中以供后续深入分析使用…...

Word 和 LaTeX 文档相互转换

Word 和 LaTeX 文档相互转换 目前可以找到两种工具完成将 LaTeX\LaTeXLATE​X 文档向 Word 文档的转换, 分别为 Tex2Word和LaTeX-to-Word。 Tex2Word 安装Tex2Word后, 启动 Word, 打开你要转换的 LaTeX\LaTeXLATE​X 源文件 (注意,如果没有成功安装 Tex2Word,那么你无法读取…...

python自动发送邮件实现

目录1 前言2 准备工作2.1 电子邮件的基础知识。2.2 python邮件库2.3 邮箱设置3 python实现邮件自动发送3.1 SMTP()和send()方法介绍3.2 python实现实例参考信息1 前言 python功能强大,可以实现我们日常办公的很多任务。诸如批量处理word,excel,pdf等等文件&#xf…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...