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

平面图,对偶图,「建议收藏」平面图定义:图存在一种形式,所有的边只在顶点处相交,那么这个图就是平面图。对偶图定义:对于每一个平面图,都有与其相对应的对偶图.我们假设上面的例图是图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)


相关推荐

  • Centos7 下安装tomcat7

    Centos7 下安装tomcat7一、安装jdk1、检查jdk版本信息,输入“rpm-qa|grepjava”查看2、用命令“rpm-e–nodepsXXXXXXXX”删除已经安装的java版本,其中XXXXXXX表示上面查询到的Java信息。如下图3、下载JDKJDK下载:http://www.oracle.com/technetwork/java/javase/downloads/jdk7-do…

  • DeviceIoControl解读

    DeviceIoControl解读设备驱动程序可以被当作内核模式函数包来看待,I/O控制代码就是用来指定访问其中的哪个函数的。DeviceIoControl函数的dwIoControlCode参数就是这个代码,它指出了我们需要进行的操作,以及如何进行操作。 控制代码是32位数字型常量,可以CTL_CODE宏来定义,它们定义在winioctl.inc和ntddk.inc文件中。 控制代码中各数据位字段的含义如下: ◎

  • origin画图怎么拟合曲线_origin拟合平滑曲线

    origin画图怎么拟合曲线_origin拟合平滑曲线需要用到matlab的拟合曲线中的smoothingspline功能,同时origin画的图又比较好看且可以后续做多条切线,因此记录下matlab与origin联合使用的方法,并加上用origin的tangent插件做曲线多条切线的方法。

  • Linux将一个文件夹复制到另一个文件夹

    Linux将一个文件夹复制到另一个文件夹下面命令是将上一级目录里面的package1复制当前目录里面,用的是相对路径,也可以用绝对路径,cp-r…/packge1./

  • pycharm2020.2.3专业版安装教程(python开发cad插件)

    下面通过三种方法给大家介绍Pycharm2020.1安装中文语言插件的方法,大家可以参考下:方法一(在搜索不到插件):1.安装好Pycharm并打开Pycharm2.打开File,找到Settings并打开3.打开Settings中的Pulgins,选择Marketplace,搜索chinese出现下图这个就可以在线安装,不出现离线安装(方法二)方法二(推荐):1.查看Pycharm版本help–…

发表回复

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

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