社区讨论

关于图论的一个问题

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo20po5m
此快照首次捕获于
2023/10/23 06:05
2 年前
此快照最后确认于
2023/11/03 06:29
2 年前
查看原帖
在一个有向无环图 GG 中,给节点分别标上 1,2,,n1,2,\dots,n 的编号。然后我们有一些小球。小球的移动是有规则的。每个节点都有一个“记忆”,表示上一次小球通过了这个节点去向了几号节点。如果没有小球通过过,“记忆”为 1-1。如果某个“时刻” ii 号节点有小球,那么下一个“时刻”小球会去向比“记忆”中的节点编号大的且存在一条有向边 iji \to jjj 号节点。如果没有比“记忆”中的节点编号大的可到达的节点,就重新从可到达的编号最小的节点开始。如果当前节点有小球,且没有可到达的节点。那么小球视为被此节点“接受”。小球从第 11 “时刻”开始,每个“时刻”都会在 11 号节点放置一个小球。
可以举个例子,即一个简单的图 121 \to 2。从第 11 时刻开始,每一个时刻 11 号节点上都有一个小球。同时从第 22 个“时刻”开始,每一个“时刻” 22 号节点都会“接受”一个来自 11 号节点的小球。
再比如说一个图 12,131 \to 2,1 \to 3,这个时候 11 号节点给出的球会在 22 号节点和 33 号节点之间“反复横跳”,并被“接受”。如果是图 12,13,231 \to 2,1 \to 3,2 \to 3,可以得到 33 号节点从第 22 个“时刻”开始,每奇数个“时刻”会“接受” 22 个小球,偶数个时刻不接受小球。
我的问题是,能否编写比较快速的程序,能够预测第 TT 时刻每个节点“接受”的小球数量?或者有没有数学方法可以得到答案?如果有这样的题目(不要类似,要一模一样),我也可以去看题解的。

回复

2 条回复,欢迎继续交流。

正在加载回复...