河內圖

在圖論和娛樂數學，河內圖是一種無向圖，它的頂點代表河內塔謎題的可能狀態，而它的邊代表兩個狀態間，可行的移動。

一個${\displaystyle H_{3}^{7}}$的河內圖

建構

一個${\displaystyle H_{3}^{5}}$的河內圖 (黑色圓圈) 由楊輝三角形推得

此謎題包含一堆不同大小的圓盤，放置杆上的圓盤，依照愈下面愈大的順序。謎題對應${\displaystyle n}$圓盤在${\displaystyle k}$根杆上的河內圖，記做${\displaystyle H_{k}^{n}}$。^[1][2]每一個狀態表示每一個杆子上的圓盤，所以每一個河內圖有${\displaystyle k^{n}}$頂點。^[2]

參考文獻

1. 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. 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