图论连通性问题的对偶问题及其证明

· · 算法·理论

先给一个最经典的例题：

给一个 N \times M 的网格，有些地方是空地，有些地方是障碍。

问是否存在 (1,1) 到 (N,M) 的四连通路径。

其对偶问题为是否存在左下角到右上角的八连通障碍路径。

存在四连通路径，则等价于不存在八连通障碍路径。

来些例子：

....#.. 
....#.. 
....... 
...#... 
..#....

这个路径四连通了。

....#.. 
....#.. 
...#... 
...#... 
..#....

这个就障碍八连通了，不存在四连通路径。

那这篇文章要探讨的就是如何粗略地证明这个结论。

不存在四连通路径 \Rightarrow 存在八连通障碍

考虑提出 (1,1) 所在的路径连通块。

那么其边缘就是一个八连通障碍。

存在四连通路径 \Rightarrow 不存在八连通障碍

找到这条四连通路径，发现它把所有障碍都劈成两半了。

所以不存在八连通障碍

再逆否一下就得证了。

然后八连通路径与四连通障碍也是对偶的。

然后就是一些例题，比如 ARC214F 和 qoj9224。