[图论]哈尔滨工业大学(哈工大 HIT)学习笔记16-22

news/2025/3/14 22:11:58/

视频来源:2.7.1 补图_哔哩哔哩_bilibili

目录

1. 补图

1.1. 补图

2. 双图

2.1. 双图定理

3. 图兰定理/托兰定理

4. 极图理论

5. 欧拉图

5.1. 欧拉迹

5.2. 欧拉闭迹

5.3. 欧拉图

5.4. 欧拉定理

5.5. 伪图


1. 补图

1.1. 补图

(1)补图示例:其中G为母图,G'为其补图

(2)定义:设 G=\left ( V,E \right ) , 则 G 的补图 G{}'=\left ( V,E{}' \right ) , 其中 E{}'=\mathbb{P}_{2}\left ( V \right )\setminus E (所有顶点关联边二元集不包含E的子集)

(3)推论:G和它的补图G{}'有可能同构,即G\cong G{}'

(4)例题:六个人的团体中,或有三个人互相认识,或有三个人互相不认识。可用图和补图来做。

(5)拉姆齐定理:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识

\begin{aligned} &R\left(1,k\right) =1 \\ &R\left(2,k\right) =k \\ &R\left(p,q\right) =R\left(q,p\right) \\ &R\left(p,q\right) \leq R\left(p-1,q\right)+R\left(p,q-1\right)\textit{ if }p,q\geq2 \\ &R\left(p,q\right) \leq\binom{p+q-2}{p-1} \end{aligned}

2. 双图

2.1. 双图定理

(1)只用一刀切开所有边就好了,看边的两边是否在不同子图中。

(2)定理1:双图也称2部图,其中圈的度数一定为偶数(充分必要条件)。

证明:圈可以表示成 v_{1},v_{2},v_{3},...,v_{n},v_{1} ,若 v_{1}\in V ,则v_{2}\in V{}' 。因此单数顶点都属于 V, 偶数顶点都属于 V{}'

(2)定理2:有 G= \left ( V,E \right ) ,\exists v\in Vdeg\, v> 0\forall v\in Vdeg\, v为偶数,则图中一定有圈

3. 图兰定理/托兰定理

(1)定理:设 G= \left ( V,E \right ) 是一个\left ( p,q \right ) 图,如其中没有三角形,则 q\leq \left [ \frac{p^{2}}{4} \right ] 。其中中括号为求整符号

(2)证明:显然,对于p=1,2,3时结论都成立。则分别证明p为奇数(p=2n-1)和偶数(p=2n)的情况;

假设p=2n-1时成立,则需证p=2n+1时成立

设p=2n-1的图G’,p=2n+1的图为G,有G-u-v=G';(u和v为两个顶点,若u,v连接,则它们一定没有公共邻接点,否则构成三角形;若它们不邻接,则可能存在公共邻接点。视频中老师应该是使他们邻接的,这样可以使第一个顶点u的邻接边假设到最大)

知G'是一个(2n-1,q')图,知 q{}'\leq \left [\frac{\left ( 2n-1 \right )^{2}}{4} \right ]=n^{2}-n;

deg\, u=k,deg\, v\leq p-k (u和v邻接,且无公共邻接点的情况)

q\leq q{}'+p \Rightarrow q\leq q{}'+2n\Rightarrow q\leq n^{2}+n\Rightarrow q\leq\left [ \frac{\left ( 2n+1 ^{2}\right )}{4} \right ]

4. 极图理论

(1)找到边最多的图,但不含K_{n}

5. 欧拉图

5.1. 欧拉迹

(1)定义:包含图的每一条边的迹

5.2. 欧拉闭迹

(1)定义:包含图的所有顶点的闭迹

5.3. 欧拉图

(1)定义:包含欧拉闭迹的图称为欧拉图

5.4. 欧拉定理

(1)定理1:G是欧拉图⇔G连通且每个顶点度为偶数

(2)定理2:图中有一条欧拉开迹⇔G中恰有2个奇度顶点

(3)定理3:设G有2n个奇度顶点,则G至少有n条迹

5.5. 伪图

(1)多重图定义:两个顶点可以之间有多条边

(2)带环图定义:存在顶点到自身的边

(3)伪图:包含多重图和带环图


http://www.ppmy.cn/news/1138163.html

相关文章

基于SSM的校园二手物品交易平台设计与实现

末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用Vue技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…

数据分析篇-数据认知分析

一简介 数据认知分析,实际是对数据的整体结构和分布特征进行分析,是对整个数据外在的认识,也是数据分析的第一步。对于数据认知的分析,一般会考虑分散性、位置特性、变量的相关性等,一般会考虑平均数、方差、极差、峰…

1027 打印沙漏

一.问题: 本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”,要求按下列格式打印 ************ *****所谓“沙漏形状”,是指每行输出奇数个符号;各行符号中心对齐;相邻两行符号数差2;符…

探秘布隆过滤器:高效数据查找与去重利器

探秘布隆过滤器:高效数据查找与去重利器 引言 在现代计算机科学中,数据的查找与去重是一个至关重要的问题。本文将介绍一种高效的数据结构——布隆过滤器,它能够在海量数据中快速判断某个元素是否存在,同时具有出色的空间效率。…

Python常用功能的标准代码

后台运行并保存log 1 2 3 4 5 6 7 8 9 nohup python -u test.py > test.log 2>&1 & #最后的&表示后台运行 #2 输出错误信息到提示符窗口 #1 表示输出信息到提示符窗口, 1前面的&注意添加, 否则还会创建一个名为1的文件 #最后会把日志文件输出到test.log文…

PDF中跳转到参考文献后,如何回到原文

在PDF中,点击了参考文献的超链接可以直接跳至参考文献的位置。 如果想从当前参考文献在回到正文中对应位置时,可以通过 Alt \red{\text{Alt}} Alt ← \red{\leftarrow} ← 实现。

SCROLLINFO scrollInfo; 2023/10/5 下午3:38:53

2023/10/5 下午3:38:53 SCROLLINFO scrollInfo;scrollInfo.cbSize = sizeof(SCROLLINFO);scrollInfo.fMask = SIF_ALL;//scrollInfo.nMin = 0; // 最小位置//scrollInfo.nMax = nRowCountToShow; // 最大位置//scrollInfo.nPage = nRowCountToShow; // 页面大小//scrollInf…

直线导轨坏了可以维修吗?

直线导轨是工业自动化设备中常用的零部件,其性能和使用寿命对设备的稳定运行和产能有着直接的影响,在生产中,由于各种原因,直线导轨会出现各种问题,那么,直线导轨的维修方法究竟是怎样的呢?我们…