Approximation theory

Daghestan Electronic Mathematical Reports: Issue 13 (2020)

Solving puzzles by O. Ore's method

UDK: 519.1

Pages: 22 - 30

In some cases, the formalisation of the puzzle in terms of graph theory allows us to solve the puzzle by finding a path in a connected acyclic digraph. We follow the approach taken in Ore's book on graph theory. In the present paper we demonstrate the approach on problems of different origins. In each case, the problem is restated in terms of a connected acyclic digraph whose nodes are certain states and whose directed arcs are transitions between states; then it is shown how to reduce the problem to finding a directed path between the nodes of the constructed digraph.

Keywords: algorithm, arc, node, oriented graph, path.

To issue content

Download full text