九天中文网

手机浏览器扫描二维码访问

第89章 路染色猜想（第1页）

路染色猜想最早是由Adler，Goodwyn和Weiss在1977年研究符号动力系统问题时提出的。

路染色猜想：所有的非周期的、出度k正则的强连通有向图，都存在一个同步的确定k染色。

这个猜想难度要远超张尧做的任何一道题。

张尧在解它的第一个问，强连通（stronglyconnected）：

有向图Gu003d（V，E）称为强连通的，如果对于G中任意两个顶点u和v，有一条起点为"

终点为v的路径（walk）。

他在解这个问题前准备了大量的资料，可以说所有相关的证明过程他一一翻阅过。

但这个问题由于不同教授研究的方向不同，有些是研究图论的，有些是自动机方向的，还有一些符号动力学上做研究的。

张尧一一把这些学者的论文吃透，认真思考着每一种研究方法的原理。

但还是得不出太多有用的东西来。

他甚至觉得自己是不是那一步出了问题，还是说这个难度对他现在来说还是大了点。

继续了每天的深思时间后，张尧觉得不能再这样下去了。

他一定是在哪里遇到了误区。

为此张尧花了大量时间把目前和这个猜想沾边的理论都找了出来，一步一步重头来。

等价猜想:任意的强连通、非周期、各点出度相等的有向图，都存在一个健壮的染色。

每天他都会花固定的时间在这上面，每一天解到自己没有灵感为止。

一个月后，

假设Gu003d（V，E）中存在简单环C，，p素数，且p＜n，则G是可同步的。

两个月，

设映射H:Z，→Z，不是到上的且F2（r）（i）u003d（i+1）modn，iu003d1，2..n.则存在一个常映射fE＜F（r）。

三个月后，

....

一直解到过年前，这个问题依然只解了一半出来。