平面图学习

news/2024/2/29 3:55:54

空调管道的设计:某景区有6个景点,位置分布如下图。
在这里插入图片描述
分析者认为:(1) A1与A4, (2) A2与A5, (3) A3与A6间人流较少,其它景点之间人流量大,必须投资铺设空调管道,但要求空调管道间不能交叉。如何设计?

把每个景点分别设为一个点,景点间连线当且仅当两景点间要铺设空调管道。
则原问题的图对应为:
在这里插入图片描述
问题转化为:能否把上图画在平面上,使得边不会相互交叉。

若图G可画在一个平面上使除顶点外边不交叉,则称 G可嵌入平面,或称G为可平面图。可平面图G的边不交叉的一种画法称为G的一个平面嵌入,G的平面嵌入表示的图称为平面图。
在这里插入图片描述
设G是一个平面图,G将所嵌入的平面划分为若干个区域,每个区域的内部连同边界称为G的面,无界的区域称为外部面或无限面。G的面组成的集合用Φ表示。

每个平面图有且仅有一个外部面。

对于平面图来说,割边就是只属于一个面的边。

f是G的一个面,构成f的边界的边数(割边计算2次)称为面f的次数,记为deg(f)

在这里插入图片描述
deg(f1)=1
deg(f2)=2
deg(f3)=3
deg(f4)=6
deg(f5)=10
相加为22,正好是边数11的2倍。

设G是具有m条边的平面图,则
在这里插入图片描述
对G的任意一条边e,如果e是某面的割边,那么由面的次数定义,该边给G的总次数贡献2次;如果e不是割边,那么它必然属于是某两个面的公共边,由面的次数定义知,它也给总次数贡献2次。

设G是具有n个点,m 条边,φ个面的连通平面图,则有
n–m+φ=2。


https://www.jiucaihua.cn/news/show-4628144.html

相关文章

2.项目中的文件

项目的路径是这样的 目录 1 pages 1.1 json 1.2 wxml 1.3 wxss 1.4 js 2 utils 3 .eslintrc.js 4 app.js 5 app.json 6 app.wxss 7 project.config.json 8 project.private.config.json 9 sitemap.json 1 pages pages 用来存放所有小程序的页面&am…

随机数发生器设计(三)

随机数发生器设计(三)- 熵估计和健康测试 熵估计健康测试 熵估计 考虑都熵源的多样性,建立一个通用的熵估计模型比较困难。本文采用nist.sp.800-90B推荐的Markov评估。详见 https://doi.org/10.6028/NIST.SP.800-90B。 执行Markov评估时&am…

Netty之EventLoop 解读

是什么 EventLoop (事件循环对象)本质是一个单线程执行器(同时维护了一个 Selector),里面有 run 方法处理 Channel 上源源不断的 io 事件。 它的继承关系比较复杂 一条线是继承自 j.u.c.ScheduledExecutorService 因…

【JavaEE】Tomcat-Servelet第一个helloworld程序

Tomcat & Servelet第一个程序helloworld! 文章目录 JavaEE & Tomcat & 第一个Servelet程序1. HTTP服务器 - Tomcat1.1 Tomcat的目录结构:1.2 启动Tomcat1.3 Tomcat的优点 2. Servelet框架2.1 创建Maven项目2.2 引入依赖2.3 创建目录2.4 写代…

AutoHotKey脚本初步:判断和选择

文章目录 脚本基础连击识别setTimer判断和选择 脚本基础 尽管通过窗口识别与按键映射,就可以胜任很多工作了,但AutoHotKey仍提供了一些简单的编程功能,对一些稍微复杂的任务,也可以做到得心应手。但要注意一点,AHK的V…

Payroll工资单中英文对照明细

不知道大家的工资单是中文的还是英文的,如果是英文的,刚开始看有些看不懂(我就是),那么可以在这里找到对应的翻译。如果中文的,而你又想知道对应英文怎么写的话,也欢迎查阅以下表格。ps.个人所得…

Linux 实操篇-网络配置

Linux 实操篇-网络配置 Linux 网络配置原理图 查看网络IP 和网关 查看虚拟网络编辑器和修改IP 地址 查看网关 查看windows 环境的中VMnet8 网络配置(ipconfig 指令) 查看linux 的网络配置ifconfig ping 测试主机之间网络连通性 基本语法 ping 目的主机(功能描述…

Java企业级信息系统开发学习笔记14 Spring Boot(使用Spring Initializr方式构建Spring Boot项目)

文章目录 一、使用Spring Initializr方式构建Spring Boot项目(一)创建Spring Boot项目(二)创建控制器(三)运行入口类(四)访问Web页面(五)修改访问映射路径 一…

Java面向对象程序开发——基础

文章目录 前言类和对象类对象 构造方法匿名对象变量作用域this关键字总结 前言 提示:这里可以添加本文要记录的大概内容: Java 是一种以面向对象编程为基础的编程语言 在 Java 编程中,一切皆为对象 每个对象都有其自己的属性和方法 对象可以…

二叉树的链式结构 - C语言(含有大量递归)

目录: 🍔前言 🍔二叉树链式结构的实现 🍟基本构架 😍代码: 🍔二叉树的遍历 🍟前序遍历 🍟中序遍历 🍟后序遍历 🍟层序遍历 &#x1f53…