关于满足循环分区边约束的有向图的类型名称问询
关于满足循环分区边约束的有向图的类型名称问询
你好!针对你的问题,你描述的这种有向图,标准且常用的术语是 T-周期有向图(T-periodic directed graph),也可以更精准地称为循环分层有向图(cyclically layered directed graph)。
你说得非常对:普通的T-分图(T-partite graph)仅要求边不能连接同一分区内的顶点,没有限定边的方向必须遵循严格的循环层级顺序;而你提到的这类图,所有边都严格从分区$V_i$指向$V_{i+1 \textrm{ mod }T}$,是一种约束更强的特殊结构。
这种图在符号动力学(比如你正在研究的sofic移位)领域确实十分常见——你提到的带标签的实例,本质上就是sofic移位对应的转移图:每个分区$V_i$可以看作一个“相位层”或者“时间步”,严格的循环转移规则正好对应移位系统中状态的周期性转移逻辑,和这类系统的有限记忆性、周期性特征高度匹配。
另外,偶尔也会看到有人称它为循环有向分图(cyclic directed partite graph),但「T-周期有向图」是更通用、在学术文献中更广泛使用的术语,不管是图论领域还是符号动力学领域都能找到对应的定义和相关研究。
备注:内容来源于stack exchange,提问作者Nur Nordin
相关产品推荐
相关产品推荐

