【平面图理论】平面图学习笔记

【平面图理论】平面图学习笔记我为什么现在要学平面图因为顺切HNOI2010遇到了平面图判定…————————————–线割分是我>w首先是一些定义:什么是平面图?对于一个图G=,如果能把G画在一个平面上,且画出的图的任意两条边除了V中的节点没有其他交点,则图G为平面图.平面图的面:对于一个平面图,由如果存在一些边围成的区域,且这个区域内不包含这个图的点和边,那么我们称这个区域为该平面图的一个面

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

我为什么现在要学平面图
因为顺切HNOI2010遇到了平面图判定…

————————————–线割分是我>w<————————————————–

首先是一些定义:

什么是平面图?
对于一个图G=< V,E >,如果能把G画在一个平面上,且画出的图的任意两条边除了V中的节点没有其他交点,则图G为平面图.
平面图的:
对于一个平面图,由如果存在一些边围成的区域,且这个区域内不包含这个图的点和边,那么我们称这个区域为该平面图的一个面.
比如这里面的红色区域:
这里写图片描述
对于包围这个区域的那些边构成的圈,我们称之为这个面的边界.边界的长度,称为这个面的.
我们定义一个面的集合F,于是对于平面图我们可以将其表示为G=< V,E,F >
平面图的性质(具体内容及证明见国家集训队2003论文刘才良《平面图在信息学中的应用》):

1.若图G=< V,E,F >为连通平面图, fF d(f)  =2|E|
2.若图G=< V,E,F >为连通平面图, |V||E|+|F|=2

当然,对于不连通的平面图,我们可以把它分解成几个联通块,然后对每个联通块这两个性质都成立(这是很显然的),所以就可以得到对不连通的平面图的一些性质.这里我不再赘述.
从上面两个性质又可以得到如下推论:

对于给定的连通简单平面图G=< V,E,F >,若|V|>=3,则|E|<=3|V|-6,|F|<=2|V|-4

原文的第二个推论我觉得好像有问题我不贴了,反正第二个好像也没用
第一个推论的作用就是告诉我们E的数量级是O(|V|)的…

平面图的判定(才不会说我就是因为这个才学平面图的):
做法转自这里

哈密顿回路会连成一个环,这个图必定被分成两部分,如果两条边相交无论同时在内还是在外都会相交,只有一条在环内一条在外才行——二分图!首先判断出那些边不再回路上然后把有矛盾的边连边利用染色法判断能否构成二分图,二分图的成立决定了平面图的成立。

接下来是重点:平面图与对偶图
定义:对于一个平面图,如果它有源点汇点,我们称之为s-t平面图.
每个平面图都能建出相应的对偶图.
对于一个平面图G,其对偶图为G*.G*中的一个点,对应原图G中的一个面.
对于G中的每条边e,如果e属于两个面 f1,f2 ,那么我们在G*中对点 f1,f2 连一条边;
如果e只属于一个面f,那么在G*中对点 f,f 连一条自环边.
此时有定理:

1.G的面数等于G*的点数,G与G*的边数相等.
2.对于一个s-t平面图,其对偶图中的一个环对应原图中的一个割.

此时就可以看出我们引入平面图与对偶图有什么作用了.
我们都知道求最大流的算法与最短路算法在效率上有不小的差距.
当我们看到一个题数据范围极大但是像是最大流,却又担心单纯的写最大流会TLE的时候
如果原图满足是平面图,我们不妨先转化为求最小割,然后再建出其对偶图然后求解.
对对偶图跑一遍Heap-Dijkstra,利用它求出的距离来做距离标号,构造最大流.
具体题目我好像只知道BeiJing2006 狼与兔子QAQ
之后单独写题解

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

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

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

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

(0)


相关推荐

  • native DRAMAtical Murder_project diablo 2

    native DRAMAtical Murder_project diablo 2投影投影是JMESPath的关键特性之一。它允许您将表达式应用于元素集合。有五种投影:列表投影切片投影对象投影展平投影过滤投影处理投影需要注意的点投影分为两个步骤。左侧(LHS)创建一

  • 浏览器主页被劫持成360导航.每次打开都是360导航https://hao.360.cn/?src=lm&ls=n36a7f6a197

    浏览器主页被劫持成360导航.每次打开都是360导航https://hao.360.cn/?src=lm&ls=n36a7f6a197这里有个误区:(本人亲测有效)大家都以为是篡改了主页,其实你去IE的设置里去看,主页没变化,或者说已经被锁定不能修改了。问题出在启动项的参数上—你试试在桌面IE的图标点击属性,看目标下边,正常的只有EXE文件的路径,但是很可能你的EXE文件路径后边跟上了一串网址字符,我的就是这样:"C:\ProgramFiles\InternetExplorer\iexplore.exe" htt…

  • 实现一个单向链表_java链表添加

    实现一个单向链表_java链表添加链表是常用的一种数据结构,如何创建链表、增、删、查找等功能是本文讨论的内容。首先,链表需要两个指针,一个是头指针是固定不变的,一个是移动变化的指针。(1)为什么要头指针?原因是单向列表中的数据结构包含的只有下一个数据的指针,这样就说明了,单向链表是不可逆向进行操作。所有的操作都需要正向去操作。这时我们必须要知道第一个数据的地址,才能从第一个数据往后访问其他数据。(2)可移动的指针的作用有两个,一个…

    2022年10月25日
  • 数据分析sql面试必会6题经典_数据分析师SQL面试必备50题[通俗易懂]

    数据分析sql面试必会6题经典_数据分析师SQL面试必备50题[通俗易懂]以下是SQL面试必备的经典的50道题目,每道题都有博主本人的解题思路和对应的SQL语句。每道题的思路与答案均为博主本人主观理解,仅供参考。环境:MySQL8.0可视化工具:Navicat1、查询课程编号为01的课程比02的课程高的所有学生的学号和成绩解题思路:(1)先把课程为01的学号和成绩找出来as表a(2)再把课程为02的学号和成绩找出来as表b(3)用innerjoin将表a…

  • 有什么优质的计算机专业书籍?操作系统、计算机网络、计算机组成、数据结构、数据库…..「建议收藏」

    有什么优质的计算机专业书籍?操作系统、计算机网络、计算机组成、数据结构、数据库…..「建议收藏」大家好,我是小林哥。平日里,大家都喊程序员加班多很辛苦,动不动就掉头发,但干的还是很香的,毕竟大多数公司钱还是给的很到位的,今年毕业应届生的我见到好多动不动就月薪20K~30K的,真让人两眼泪酸酸,当然这离不开他们大学期间的努力。讲真,没什么家庭背景的人,选择当程序员确实是比较好的选择了,原因有二:首先,当今互联网、AI人工智能、大数据等都是高速发展的行业,自然人才需求很多,薪资也相对其他传统行业高;第二,纯粹看你技术能力,只要自己愿意付出努力,技术能力肯定会慢慢提高上来,而且现在比起几十年

  • kubernetes简介

    kubernetes简介Kubernetes简介初识KubernetesKubernetes(K8s)是一个用于自动化部署、扩展和管理容器化应用程序的开源系统2014年6月7日Google推出了Borg的开源版本2

发表回复

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

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