平面图
就是放在平面上展开,存在一种画法能够使得图的边与边之间没有交点,这玩意就叫平面图。
但是一般来说吧,这个东西要配和着对偶图来使用。
对偶图
就是对于原平面图的每一条边,将与其接壤的两个面在对偶图中连一条边。特殊地,当且仅当对于一条边两边的面是同一个面,那么会出现自环。
然后不难发现,对偶图的对偶图是原图。
给出辅助用图。
(改自 百度百科,那里的图有一点点问题)
一些性质
(要求有源汇点)平面图的最小割可以转化为对偶图的最短路。
然后要保证这么一条最短路要横跨源汇点所属的两个区域
题目
海拔
狼抓兔子