expander graph&random walk的一个小应用
2024-08-28 13:39:07
此文主要总结的是一种随机算法，旨在判断一个expander图上两点是否连通。复杂度O(logn)。算法思路清奇。
expander graph博大精深，如果对expander graph的生成，family感兴趣，可以去看一下陶哲轩巨巨巨神的博客What's new，里面有篇博文讲了这些问题。
个人理解，算法可以归纳成一句话：如果expander图G是连通的，那么概率分布p在图G上随机游走l=O（logn）步后会高度逼近等概率分布。
证明见下：第一张图约定了一些符号，第二张图证明了定义的
(显然大于0)，第三张图证明了
(这里的1是向量
) 第四第五张图追加一些更精细的讨论。
啊第四第五张图待写。。Orz
最新文章
- 如何查看当前Ubuntu系统的版本
- Python Day10
- python项目在windows下运行出现编码错误的解法
- BZOJ2851 : 极限满月
- 使用Dreamweaver批量删除PHP项目中的单行注释和多行注释
- BSTR、char*和CString转换
- Sphnix
- getch()、getche()和getchar()函数
- WPF 中使slide控件拖动完成后改变变量值
- Ubuntu Mac OS主题分享
- ie8 background背景图片不显示问题
- linux一些比较重要的环境变量。配置文件
- webstorm的快捷键总结
- 看懂MSSQL执行计划，分析SQL语句执行情况
- 一道面试题（C语言）
- 易捷支付完整业务流程的lr脚本编写
- 没有上司的舞会|codevs1380|luoguP1352|树形DP|Elena
- wxPython:消息对话框MessageDialog
- .net core 问题：413 Request Entity Too Large nginx
- 主机ping不通virtualbox虚拟机的解决办法