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



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

  

user avatar    网友的相关建议: 
      

(反证)

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

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


user avatar   timosky 网友的相关建议: 
      

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

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


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




  

相关话题

  如何求解满足条件的映射的个数? 
  数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗? 
  如何用组合数学证明 (n²)! 能被 (n!)^(n+1) 整除? 
  对于 3 和 4 之间的整数 Bleem,你怎么看? 
  请教拓扑排序中的一点疑问? 
  如何解决这个图的特征值问题? 
  如何证明任意一个有偶数个顶点的图,一定存在两个点拥有偶数个共同邻居? 
  哪些看似与图论无关的问题可用图论模型解决? 
  从0,2 中选一个数字,从1,3,5中选两个数字,组成无重复数字的三位数,构成奇数的概率是多少? 
  逆拓扑排序是拓扑排序的逆序嘛? 

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





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