Geodesic
Solving puzzles by O. Ore's method
Daghestan Electronic Mathematical Reports, no. 13 (2020), pp. 22-30 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, oriented graph, path.
Mots-clés : arc, node 
@article{DEMR_2020_13_a1,
     author = {A. M. Magomedov and S. Lawrencenko},
     title = {Solving puzzles by {O.} {Ore's} method},
     journal = {Daghestan Electronic Mathematical Reports},
     pages = {22--30},
     year = {2020},
     number = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DEMR_2020_13_a1/}
}
TY  - JOUR
AU  - A. M. Magomedov
AU  - S. Lawrencenko
TI  - Solving puzzles by O. Ore's method
JO  - Daghestan Electronic Mathematical Reports
PY  - 2020
SP  - 22
EP  - 30
IS  - 13
UR  - http://geodesic.mathdoc.fr/item/DEMR_2020_13_a1/
LA  - ru
ID  - DEMR_2020_13_a1
ER  - 
%0 Journal Article
%A A. M. Magomedov
%A S. Lawrencenko
%T Solving puzzles by O. Ore's method
%J Daghestan Electronic Mathematical Reports
%D 2020
%P 22-30
%N 13
%U http://geodesic.mathdoc.fr/item/DEMR_2020_13_a1/
%G ru
%F DEMR_2020_13_a1
A. M. Magomedov; S. Lawrencenko. Solving puzzles by O. Ore's method. Daghestan Electronic Mathematical Reports, no. 13 (2020), pp. 22-30. http://geodesic.mathdoc.fr/item/DEMR_2020_13_a1/

[1] Ore O., Teoriya grafov, 2-e izd., Nauka. Glavnaya redaktsiya fiziko-matematicheskoi literatury, M., 1980, 336 pp.

[2] Gashkov S.B., Sistemy schisleniya i ikh primenenie, Izdatelstvo MTsNMO, M., 2012, 68 pp.

[3] Sharygin I.F., Matematicheskii vinegret, Agentstvo «ORION», M., 1991

[4] Magomedov A.M., Sharapudinov T.I., Programma resheniya zadachi ob optimalnykh perelivaniyakh s ogranicheniyami dlya sluchaya trekh sosudov, Svidetelstvo o gosudarstvennoi registratsii programmy dlya EVM # 2019664676 ot 12.11.2019

[5] Arsak Zh., Programmirovanie igr i golovolomok, Izdatelstvo «Nauka», M., 1990, 224 pp.