首页 > 其他分享 >qbxt day1

qbxt day1

时间:2023-04-30 20:11:27浏览次数:54  
标签:度数 连通 个点 哈密顿 dfrac day1 qbxt 回路

数学知识

现有奇数个人,两两间可能认识或不认识,请证明永远存在一个认识偶数个人的人。

将其转化成更强的问题: 给定一张奇数个点的图 \(G\) ,证明度数为偶数的点的个数为
奇数。
继续考虑它的相反的问题: 给定一张奇数个点的图 \(G\) ,证明度数为奇数的结点的个数为偶数
考虑所有点的度数和,由于一条边会被计算到两个结点的度数上,故其必定为偶数。

证明一个 \(n\) 个点和至少 \(\dfrac{(n - 1)(n - 2)}{2}\) 条边的图是连通图。

有 \(n - 1\) 个点的连通图至多有 \(\dfrac{(n - 2)(n - 1)}{2}\) 个点,所以可以证得 \(n\) 个点和至少 \(\dfrac{(n - 1)(n - 2)}{2}\) 条边的图是连通图。


欧拉回路:点的度数都为偶数的图存在欧拉回路。
欧拉通路:不存在或存在 \(2\) 个度数为奇数的图存在欧拉通路。
哈密顿回路:每个点只经过一次的回路。

若每个点的度数大于等于 \(\dfrac{n}{2}\),则必定存在哈密顿回路。
若两个不相邻的点的度数和大于 \(n\),则必定存在哈密顿回路。

反证法,假设 \(G\) 没有哈密顿回路。
我们由图 \(G\) 构造出一个新的没有哈密顿回路的图 \(G'\),具体的,令 \(G' = G\) ,对于每条不在图 \(G\) 中的边,如果加入 \(G'\) 后不会产生哈密顿回路,则加入,该构造的顺序不重要。
此时我们得到了一个图 \(G\) ,再加入任何一条边都会得到一条哈密顿回路,并且由于我们仅加入了新的边,所有结点的度数任然大于等于 \(\dfrac{n}{2}\) 。
假设 \((v_1, v_n)\) 这条边不在 \(G'\) 中,我们知道必定存在一条哈密顿路径 \(v_1, v_2, v_3, \cdots, v_n\),考虑 \((v_1, v_i)\) 有一条边,则 (v_{i - 1}, v_n) 必定不能有边,否则可以构造出一条哈密顿回路。
因为这样的 \(v_i\) 至少有 \(\dfrac{n}{2}\) 个,从而这样的 \(v_{i - 1}\) 也至少有 \(\dfrac{n}{2}\) 个,又由于 \(v_n\) 不能和自己连边,故而它至多与 \(n - \dfrac{n}{2} - 1\) 个点连边,但 \(deg(v_n) \ge \dfrac{n}{2}\) ,矛盾。

Posa 12岁的时候, 他在餐桌上花费了半分钟证明出了这个问题。现有 \(n + 1\) 个小于等于 \(2n\) 的正整数,证明存在两个数互质。

两个相邻的数一定互质,根据鸽巢原理,一定有至少两个数是相邻的,所以存在两个数互质。

证明 \(G\) 或者 \(G\) 的补图至少有一个是连通的。

将点分成 \(k\) 个连通块,补图就是将不同连通块的点之间相互连边,由于原来连通块里的点都连接到了相同的点上(这个点在其他连通块上),这个可以保证原来的连通块里的点依然联通,所以,补图是联通的。

连通图 \(G\) 满足任意两条边至少有一个点是重合的,证明 \(G\) 要么是 \(3\) 个点的完全图,要么是星星。

假设 \(G\) 不是三个点的完全图,

image

如图,若要加入一个新的点,要想满足条件,只能将边连向 \(x\) 点构成菊花,否则这个点会与 \(y\) 或 \(z\) 重合,同时连边构成三个点的完全图。

房间里有 \((m - 1)n + 1\) 个人,证明要么存在 \(m\) 个人两两不认识,要么存
在一个人认识至少 \(n\) 个人。

假设不存在一个人至少认识 \(n\) 个人,则每个联通块的点数最大为 \(n - 1\)。
原式可以转化为 \((n - 1)(m - 1) + m\),可以看做有 \(m\) 个连通块,第 \(m\) 个连通块有 \(m\) 个点,每次从不同连通块中取一个人,则存在 \(m\) 个人两两不认识。

证明任意连通图 \(G\) 存在一个点 \(x\),删掉后剩下的图依旧是连通图。

若图中有度数为 \(1\) 的点,则删掉这个点即可;没有度数为 \(1\) 的,任选一个点,删掉距离它最远的点即可。

现在有一张 \(4 \times n\) 的棋盘上有一个马(中国象棋),证明不存在一条经过所有格子恰好一次并回到起点的路径。

将棋盘染色,同种颜色的不能挨着(就是染成像国际象棋的棋盘那样),马每走一步都要换色,同时将第一行、第四行染成蓝色,第二行、第三行染成红色,则蓝色下一步一定到红色,但红色下一步不一定到蓝色,为了保证走过所有的点,且每个点只走一遍,我们让红色下一步就到蓝色,则跳的顺序就是:黑蓝 \(\rightarrow\) 白红 \(\rightarrow\) 黑蓝。。。
但是,只有 \(2n\) 个点是黑蓝或白红,一共有 \(4n\) 个点,矛盾,证得。

图的存储

  • 邻接矩阵
  • 链式前向星
  • vector

二分图

称一张图 \(G = (V, E)\) 是二分图当且仅当点集 \(V\) 可以分为两半 \(A, B\) ,使得所有边都可以写成 \((a, b) \in E, a \in A, b \in B\)。
若存在一种办法使得所有点集 \(A, b\) 的点两两匹配,则称二分图 \(G\) 存在完美匹配。

二分图 \(G\) 存在完美匹配的必要条件是 \(|A| = |B|\)。

一个二分图 \(G\) 存在完美匹配,当且仅当 \(A\) 的任意子集 \(S\), \(B\) 中至少有 \(|S|\) 个不同的点与 \(S\) 相邻。

标签:度数,连通,个点,哈密顿,dfrac,day1,qbxt,回路
From: https://www.cnblogs.com/yifan0305/p/17365715.html

相关文章

  • JOISC 2014 Day1
    T1巴士走读考虑在每个节点\(u\)维护\(f_u(x)\)表示在时刻\(x\)到达节点\(u\)时的最晚出发时间,显然这个函数单调递增。考虑进行转移,将所有巴士按照\(Y\)进行排序,依次枚举每辆巴士,设巴士出发节点为\(A\),终止节点为\(B\),发车时间为\(X\),到达时间为\(Y\),由于我们......
  • 完整实现React day10
    update流程与mount流程的区别。对于beginWork:需要处理ChildDeletion的情况需要处理节点移动的情况(abc->bca)对于completeWork:需要处理HostText内容更新的情况需要处理HostComponent属性变化的情况对于commitWork:对于ChildDeletion,需要遍历被删除的子树对于Update,需......
  • Day14
      3.代码示例#include<iostream>usingnamespacestd;intmain(){inta,b,num=0;cout<<""<<"白球"<<""<<"红球"<<""<<"黑球"<<endl;......
  • Day13
      3.代码示例#include<iostream>usingnamespacestd;intjudge(int*c){inti,s=0;for(i=2;i<11;i++){if(c[1]!=c[i])s=1;}returns;}intmain(){intsweet[12]={20,10,2,8,22,16,4,10,6,14,20,0};inti,j=1;......
  • Day11
     2.代码示例#include<iostream>usingnamespacestd;intmain(){intn;doubles=0;cout<<"请输入您的个人收入:";cin>>n;cout<<"应缴纳税额为:";if(n<3500){s=0;}elseif(n<5000){......
  • mysql主从-day1——mysql主从搭建、django中使用多数据库做读写分离
    目录一、mysql主从5django使用多数据库做读写分离一、mysql主从#之前做过redis的主从,很简单#mysql稍微复杂一些,搭建mysql主从的目的是? -读写分离-单个实例并发量低,提高并发量-只在主库写,读数据都去从库#mysql主从原理步骤一:主库db的更新事件......
  • Day1,MarkDown基础
    一级标题二级标题以此类推字体字体粗体字体斜体字体加粗斜体字体删除引用引用内容分割线---或***图片![图片名字](图片路径)eg:![02]("C:\Users\86178\Pictures\SavedPictures\R-C.jfif")超链接名字列表1、a2、b或ab*表格第一种:右键插入第二种......
  • 【Java基础】day16
    day16一、switch-case和if-else谁更快?switch-case在switch-case中,case的值是连续的话,会生成一个TableSwitch来进行优化,这样的情况下,只需要在表中进行判断即可。这里使用0-4的连续值来进行测试如果说多加几个Case的值,但是范围控制在比较小的范围时:这里使用0......
  • 【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 |
    DAY16共3题:奇♂妙拆分(简单数学)区区区间间间(单调栈)小AA的数列(位运算dp)......
  • day1
    Markdown标题三级标题四级标题 字体hello,worldhello,worldhello,worldhello,world引用自信巅分割线图片超链接狂神说java列表abcabc表格mzxbsr 代码​hello ......