论文部分内容阅读
s-图的路由数源自于网格上行走的机器人的坐标规则问题.Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题:平面图上的路由数是否一定存在仅由半径为参数构成的界?本文引入有向s-图的路由数这一概念并证明该数等于其周长.这一结果表明无向s-图的路由数等于该图所有定向图的最小周长,同时也对上面的问题给出了一个反例.做为一个应用.我们证明乘积图的路由数等于其半径.