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



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

  

user avatar    网友的相关建议: 
      

(反证)

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

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


user avatar   timosky 网友的相关建议: 
      

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

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


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




  

相关话题

  如何求解满足条件的映射的个数? 
  是否存在将中国大陆部分一分为二的铁路路线? 
  我好像证明了四色猜想,各位怎么看? 
  如何证明这个图的染色问题? 
  如何用组合数学证明 (n²)! 能被 (n!)^(n+1) 整除? 
  N个互异数随机组成的数组的逆序数的分布公式是什么? 
  如何估计这个级数? 
  为什么离 n!/e 最近的整数是 n-1 的倍数? 
  给定正整数 n,将 1 拆分为 n 个互不相同的单位分数之和,不计次序,有几种拆法? 
  如何证明下面这个图论问题? 

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





© 2025-03-30 - tinynew.org. All Rights Reserved.
© 2025-03-30 - tinynew.org. 保留所有权利