数学知识
现有奇数个人,两两间可能认识或不认识,请证明永远存在一个认识偶数个人的人。
将其转化成更强的问题: 给定一张奇数个点的图 \(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\) 不是三个点的完全图,
如图,若要加入一个新的点,要想满足条件,只能将边连向 \(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|\)。
标签:度数,连通,个点,哈密顿,dfrac,day1,qbxt,回路 From: https://www.cnblogs.com/yifan0305/p/17365715.html一个二分图 \(G\) 存在完美匹配,当且仅当 \(A\) 的任意子集 \(S\), \(B\) 中至少有 \(|S|\) 个不同的点与 \(S\) 相邻。