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



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

  

user avatar    网友的相关建议: 
      

(反证)

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

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


user avatar   timosky 网友的相关建议: 
      

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

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


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




  

相关话题

  是否存在连续函数,使得每个数都被取到n次? 
  有n级台阶,每次可以走1~(n-1)的任意阶数,那么一共有多少种走法? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  如果有人想走遍中国所有的省级行政区(含港澳台),总路程最小可以是多长? 
  母函数都是用幂级数吗?三角级数可以构造母函数吗? 
  为什么正方体有十一种展开图? 
  从 1~100 这 100 个数,按照怎样的顺序排列是最混乱的? 
  如何统计拓扑排序的个数? 
  我好像证明了四色猜想,各位怎么看? 
  博弈论+图论,博士有哪些方向可以选择? 

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





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