介于可观测与可检测之间的随机图模型，刻画了在概率意义下通过顶点颜色序列确定初始或当前位置的最小着色的计算复杂性。
Zhu, Shiyong · 曹进德 · Lin, Lin · Rutkowski, Leszek · Lu, Jianquan · 陆国平
IEEE Transactions on Automatic Control 2023
对于给定的着色图，可以在多项式时间内判定是否具有可观测性或可检测性，便于实际系统设计时快速检查。
提供了任意顶点对之间可观测性和可检测性概率的隐式计算公式，无需模拟即可分析。
证明了随机可观测性最小着色是 NP-hard，而确定性可检测性最小着色多项式时间可解，揭示了问题的难易分界。