论文标题
部分同步着色
A Partially Synchronizing Coloring
论文作者
论文摘要
鉴于有限的有向图，其边缘的着色将图形变成有限状态自动机。确定性自动机的k同步单词是其边缘颜色字母中的一个单词，至少在K-元素子集上映射自动机的状态集。如果颜色将图形变成具有k同步词的确定性有限自动机，则有针对性超级（任何顶点的恒定超级）的均匀超级（恒定超级）的有限有限图的边缘的颜色是k同步。 对于K = 1，一个有众所周知的道路着色问题。道路着色问题的最新积极解决方案意味着Beal和Perrin首先考虑的优雅概括：有限连接的均匀分类的有限图是k同步的IFF，如果FF是其所有周期的最大长度的最大共同分裂，则是k。 提出了对任意有限挖掘的着色的某些后果。 我们描述了包装中实现的K同步的道路着色的次级算法。一个新的线性可视化程序演示了所获得的着色。提出了任意有限挖掘和这种均匀超级的颜色的某些后果。
Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its edges that maps the state set of the automaton at least on k-element subset. A coloring of edges of a directed strongly connected finite graph of a uniform outdegree (constant outdegree of any vertex) is k-synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a k-synchronizing word. For k=1 one has the well known road coloring problem. The recent positive solution of the road coloring problem implies an elegant generalization considered first by Beal and Perrin: a directed finite strongly connected graph of uniform outdegree is k-synchronizing iff the greatest common divisor of lengths of all its cycles is k. Some consequences for coloring of an arbitrary finite digraph are presented. We describe a subquadratic algorithm of the road coloring for the k-synchronization implemented in the package TESTAS. A new linear visualization program demonstrates the obtained coloring. Some consequences for coloring of an arbitrary finite digraph and of such a graph of uniform outdegree are presented.
