百科问答小站 logo
百科问答小站 font logo



如何证明这个图的染色问题? 第1页

  

user avatar    网友的相关建议: 
      

(反证)

如果存在一种颜色 ,使任意染成该颜色的点 ,它的邻域 至多有其他 种颜色,不妨记未出现的,与 不同的颜色为 。

注意到,对每个 ,将 的颜色由 改为 ,仍是一种合理的染色,此时只使用 种颜色,与 矛盾。


user avatar   timosky 网友的相关建议: 
      

如果某个颜色(比如颜色a)的一个点(比如点A)邻域里不包含其他所有颜色的点,也就是说至少还有一个其他颜色(比如颜色b)不与它相邻,那就把点A改成颜色b。

如果颜色a不存在“邻域里包含所有其他颜色的点”,那么如此操作,每个颜色a的点都将被改为其他颜色……而且依旧满足相邻点颜色不同。于是点色数--,矛盾了。


换句话来说就是:用最少颜色使得相邻两点颜色不同的染法,就是你所要求的这个染法……否则我们将可以使用更少的颜色实现相邻两点不同,从而导致矛盾。




  

相关话题

  如何证明以下式子? 
  如何证明n+1~2n最大奇因子之和等于n²? 
  数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗? 
  为什么规定 0 的阶乘为 1? 
  如何证明任意一个有偶数个顶点的图,一定存在两个点拥有偶数个共同邻居? 
  图论里的图用什么软件画比较好? 
  有n级台阶,每次可以走1~(n-1)的任意阶数,那么一共有多少种走法? 
  能解释下怎么从这个有向图生成如图的集合链?(数字电路并行全入度拓扑排序优化算法)? 
  有限个人,任意两个人有且只有1个公共朋友,那么一定存在1个人是所有人的朋友,这是什么数学问题? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 

前一个讨论
数学的所有内容都是基于一些无法证明的公理和无法定义的概念(比如集合、直线),那么数学有没有可能是假的?
下一个讨论
如何证明子集族上界?





© 2025-04-26 - tinynew.org. All Rights Reserved.
© 2025-04-26 - tinynew.org. 保留所有权利