首页 > 其他分享 >关于环的一些证明

关于环的一些证明

时间:2023-11-07 09:55:32浏览次数:41  
标签:题意 返祖 插边 极小 证明 BFS 关于 一些 任意

DFS搜索树上有返祖边,等价于图中至少存在一个环。

充分性显然,必要性。

如果是无向图,那就只有树边和返祖边,不存在横插边,没有返祖边那就是一棵树,与图中有环矛盾。

有向图多了横叉边,但是这样不是环,是个DAG,也矛盾。

这个结论常用于深搜判环。

Fish Graph一题中,dfs只能找到一个任意环,但是因为我们有保证环上至少有一个度数不小于4的点(起点),所以这个环要么满足题意,要么一定可以调整得到一个新的符合题意的环,而且这个新环必然在回溯的过程中被更新到,所以这样dfs是正确的。

这个做法毫无一般性。

AlexWEI的BFS的做法值得研究一下。

下面证明,BFS中找出的环,一定是极小环。

注意,只是极小的环,不是最小的环,BFS也只能找出任意环,但是可以保证任意环是一个极小的环。

假设它不是极小的环。

那么环内就还有一条边,而且由于BFS树中的非树边只能在同一层或者相邻两层,所以里面的更小的环必然更早被搜到,那么这个任意环就不是被搜到的环了。

BFS树上没有返祖边,只有横插边,而且层数不能相差超过1,如果没有走到横插边,那么就是树,就没有环了,矛盾。(所以也是等价于至少存在一个环,而且一定走到的是极小环)。

标签:题意,返祖,插边,极小,证明,BFS,关于,一些,任意
From: https://www.cnblogs.com/zhangchenxin/p/17814344.html

相关文章

  • 关于找环
    voiddfs(intu,intfrom){ printf("%d->%d\n",~from?e[from^1]:-1,u); ins[u]=true; st[u]=true; if(~from)fa[u]=e[from^1]; for(inti=h[u];~i;i=ne[i]){ if(i==(from^1))continue; intv=e[i]; if(!st[......
  • 关于嵌入式QT QML 竖屏屏幕显示为横屏
    硬件平台:全志的A40I-H(从淘宝一家广州卖家买的开发板)软件平台:Linux内核版本3.10.65QT版本:5.9.0当时遇到的问题,在PC上运行一个qml的demo,是正常的横屏显示的。但是交叉编译过后,烧录到开发板子上面,发现是旋转了90度显示大致如下图所示: 当时非常的头大,如果按照文档上面,使用QT......
  • 关于用逆序数求解行列式的知识都在这里啦
    利用逆序求n阶行列式的值你知道怎么判断一组数字的逆序数吗?你会使用逆序计算这个行列式吗?这个四阶行列式千万不要展开求解......
  • #18搞OI不要会证明
    KarenandCards题面设符合条件的三元组为\((x,y,z)\)。枚举\(x\),可以将\(n\)个三元组分为两类:\(a_i\gex\)和\(a_i<x\)。对于\(i\in[1,n],a_i\gex\),需要满足的条件为\(b_i<y\)且\(c_i<z\);对于\(i\in[1,n],a_i<x\),需要满足的条件为\(b_i<y\)或者\(c_i<z\)。令......
  • 一些工具
    批量造数据板子点击查看代码#include<bits/stdc++.h>usingnamespacestd;charcommand[100000];stringcvs1(intnum){stringres="";dores+=num%10+'0',num/=10;while(num>0);reverse(res.begin(),res.end());r......
  • 关于对iOS企业签名的类型如何选择,分别有什么优势
    了解过苹果签名的都知道苹果签名的方式有好几种,其中企业签名是其中使用最广泛,性价比最高的一种签名方式,企业签名还分以下三种签名方式,共享企业签名,稳定版企业签名,超稳版企业签名。大家可能还不太了解这三种签名方式的区别,今天大家就一起了解如何选择签名方式,选择哪一种签名方式......
  • 一些可能用得上的板子
    复数模板点击查看代码structComplex{doubler,i;//realpart,imaginarypartComplex(doubler=0,doublei=0):r(r),i(i){}//abc怎么你了?Complexoperator+(constComplex&other)const{returnComplex(r+other.r,i+other.i);}Comp......
  • 一些测试数据记录汇总
     //这段代码耗费时间150us 波特率256000//GpioDataRegs.GPBSET.bit.GPIO54=1;//上电配置输出高电平/* ScicRegs.SCITXBUF=0x00; while(ScicRegs.SCICTL2.bit.TXRDY!=1){} ScicRegs.SCITXBUF=0x00;......
  • 关于中断的分类和优先级(优先级由高到低排序)
    1.机器校验中断:高速程序发生了设备故障,比如电源故障,主存出错等2.访管中断:用户程序需要操作系统接入,调用操作系统服务等3.程序性中断:包括指令和数据的格式错误,程序执行中出现异常等4.外部中断:来自机器外部,包括定时器中断、外部信号中断、中断键中断等5.IO中断:由IO控制器产生,用......
  • 关于文件夹权限不够,引起的安装错误的处理方法
      文件夹没有权限,在更改文件夹的权限的时候会报各种错误,很多人在一报错的情况下,都不知道如何设置了。今天给大家带来一个用命令来处理这个问题的方法:假设文件路径为:C:\Windows\System32\en-US  比如:在安装软件的时候,报这个错误:用上面的设置文件权限的方法又报错的情况......