什么是平面图? 平面图的定义就是所有的边只在顶点处相交， 这里就是一个例子.
文章图片
你看， 边与边之间没有相交吧~.
其实这是论文PPT的图， 本人画的太丑就不挂出来了.
So…对偶图? 对于每一个平面图， 都有与其相对应的对偶图. 我们假设上面的例图是图G， 与其对应的对偶图G*， 那么对于G*来说， G*上面的每一个点， 对应的是G里面的每一个面. 比如说下面就是G*.
文章图片
上面的点就是对偶图G里的点.
那么关于对偶图G*里的边呢 ? 对于G中本来的每条边e， 他是两个面(比如说面f1和f2)的交边， 那么在对偶图里， 我们对这两个面(f1， f2)所映射在G*里的点连线(f1* 连向f2*). 如果f1 == f2(比如说G中5， 6这条边， 边的两侧都是同一个面， 那我们就建一条回边.
图就长这样(回边在5， 6那里).
文章图片
这个就是对偶图了.
平面图与对偶图之间的关系 1.G*中的环与G中的割一一对应.(割就是一些边， 如果割掉这些边使图分成两个互不连通的子图的话， 就称之为割).
举例: 1*-2*-3*-4*这个G*里的环， 对应的是G中1-3， 2-3， 3-4， 3-5这个割.
TIPS:这个性质对于平面图的最小割有巨大的作用.
【关于平面图到对偶图的转化】2.G的面数等于G*的点数， G与G*的边数相同.
推荐阅读
- AIoT(人工智能+物联网)|程序员的数学【线性代数基础】
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- HDU 5184 Brackets (卡特兰数)
- 高斯消元
- 水题纪念|【51nod - 1098】 最小方差（基础数学，公式化简，前缀和，积的前缀和）
- 扩展欧几里德算法（gcd扩展使用）
- 数学|CF 514D.Nature Reserve 几何,二分,交集
- codeforces|Codeforces Round #665 (Div. 2) C. Mere Array(数学)
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维，数学)
- 数论|Codeforces Global Round 10 B. Omkar and Infinity Clock(数学)