河内图

在图论和娱乐数学，河内图是一种无向图，它的顶点代表河内塔谜题的可能状态，而它的边代表两个状态间，可行的移动。

一个

H_{3}^{7}

的河内图

建构

一个

H_{3}^{5}

的河内图 (黑色圆圈) 由杨辉三角形推得

此谜题包含一堆不同大小的圆盘，放置杆上的圆盘，依照愈下面愈大的顺序。谜题对应 $n$ 圆盘在 $k$ 根杆上的河内图，记做 $H_{k}^{n}$ 。^[1]^[2]每一个状态表示每一个杆子上的圆盘，所以每一个河内图有 $k^{n}$ 顶点。^[2]

^ Hinz, Andreas M.; Klavžar, Sandi; Petr, Ciril, 2.3 Hanoi Graphs, The tower of Hanoi—myths and maths 2nd, Cham: Birkhäuser: 120, 2018, ISBN 978-3-319-73778-2, MR 3791459, doi:10.1007/978-3-319-73779-9
^ ^2.0 ^2.1 Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F., 2.2 Hanoi Graphs, Topics in Graph Theory: Graphs and their Cartesian Product, Wellesley, MA: A K Peters: 13–15, 2008, ISBN 978-1-56881-429-2, MR 2468851