近年来，使用神经网络执行图算法引起了极大的兴趣，因为其展现出令人鼓舞的实证进展。这促使我们进一步了解神经网络如何复制关系数据的推理步骤。在本研究中，我们从理论角度研究了 Transformer 网络模拟图上算法的能力。我们使用的架构是一个带有额外注意力头的循环 Transformer，这些注意力头与图交互。我们通过构造证明了该架构可以模拟单个算法，如 Dijkstra 最短路径算法、广度优先搜索、深度优先搜索和 Kosaraju 强连通分量算法，以及同时模拟多个算法。网络中的参数数量不会随着输入图大小的增加而增加，这意味着网络可以模拟任何图上的上述算法。尽管具有此特性，但我们证明了由于有限精度，我们的解决方案存在模拟的局限性。最后，我们证明了当使用额外注意力头时，在恒定宽度的情况下，图灵完备性结果。