平面图,对偶图,「建议收藏」

平面图,对偶图,「建议收藏」平面图定义:图存在一种形式,所有的边只在顶点处相交,那么这个图就是平面图。对偶图定义:对于每一个平面图,都有与其相对应的对偶图.我们假设上面的例图是图G,与其对应的对偶图G*,那么对于G*来说,G*上面的每一个点,对应的是G里面的每一个面.比如说下面就是G*.上面的点就是对偶图G里的点. 那么关于对偶图G*里的边呢?对于G中本来的每条边e,他是两个面…

大家好,又见面了,我是你们的朋友全栈君。

平面图定义:

图存在一种形式,所有的边只在顶点处相交,那么这个图就是平面图。

平面图,对偶图,「建议收藏」

对偶图定义:

对于每一个平面图, 都有与其相对应的对偶图. 我们假设上面的例图是图G, 与其对应的对偶图G*, 那么对于G*来说, G*上面的每一个点, 对应的是G里面的每一个面. 比如说下面就是G*.

这里写图片描述

上面的点就是对偶图G里的点.  
那么关于对偶图G*里的边呢 ? 对于G中本来的每条边e, 他是两个面(比如说面f1和f2)的交边, 那么在对偶图里, 我们对这两个面(f1, f2)所映射在G*里的点连线(f1* 连向f2*). 如果f1 == f2(比如说G中5, 6这条边, 边的两侧都是同一个面, 那我们就建一条回边. 
图就长这样(回边在5, 6那里).

这里写图片描述

求网络流的最小割或最大流时,如果时平面图,就可以转化成对偶图,然后对对偶图求s’,t’的最短路,就是原网络的最大流和最小割。就是对偶图的点需要自己对应好。。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/141340.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 大数据教程,大数据学习线路图

    大数据教程,大数据学习线路图前言先引用一下马云大大的话:很多人还没搞清楚什么是PC互联网,移动互联网来了,我们还没搞清楚移动互联的时候,大数据时代又来了。马云深度解析大数据“大数据”是近年来IT行业的热词,并广泛的应用在各行各业。特别是近年来随着社交网络、物联网、云计算以及多种传感器的广泛应用,以数量庞大,种类众多,时效性强为特征的非结构化的数据不断涌现,数据的重要性愈发凸显,传统的数据存储、分析技术难以实时处…

  • for循环的执行顺序

    一边回顾基础一边记录记录做个整理,这篇关于for循环的执行顺序:for(表达式1;表达式2;表达式3){循环体}第一步,先对表达式1赋初值;第二步,判别表达式2是否满足给定条件,若其值为真,满

    2021年12月25日
  • 安装tcping

    安装tcpingcping在windows和linux系统中都不是内建的命令,需要我们自己去下载下载命令wgethttps://sources.voidlinux.eu/tcping-1.3.5/tcping-1.3.5.tar.gzsudoyuminstallepel-releaseyuminstalltcpingtcpingwww.baidu.com443详细见图…

  • 页面返回顶部代码_网页回到顶部代码

    页面返回顶部代码_网页回到顶部代码网站添加返回顶部有好几种,下面我简单介绍下:1使用文字添加方法最简单的是:最简单的“返回顶部”代码就是“返回顶部”(不包括引号),(0,0)代表座标,第一位是水平,第二位是垂直,(0,0)就表示网页左上角,文字部分(返回顶部)可以自由替换成自己需要的内容,比如也可以用“TOP”都可以。

  • gpsgate 配置过程

    gpsgate 配置过程gpsgate是一个虚拟串口的软件。通过gpsgate虚拟出来的串口可以同时连接N个应用程序。举个例子来说,QIGI智能手机的gps通讯端口是com3,波特率手是9600。我们通过gpsgate虚拟出

  • Oracle 语法

    Oracle 语法

    2021年12月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号