Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

On problems concerning paths in a graph

Published: 10.10.2013

Authors: Boyarintzeva T.E., Mastikhina A.A

Published in issue: #5(17)/2013

DOI: 10.18698/2308-6033-2013-5-735

Category: Engineering education

The subject of this article is relation between "visual" way of representing operations on graph (using the schemes) and "abstract" way (based on matrix representation of graph).This kind of problem (the presentation of graphic operations with a tool Discrete Mathematics) often occurs in the teaching of the subject. There are two algorithms given for constructing reachability matrix and defining the quantity and consistency of graph's connected components. As an example of describing a system with different possible states using graph the pouring problem is displayed. For another example of a problem represented graphically a decision is given, correctness of which is proven using Boolean functions. Also the problem of finding Hamiltonian cycle is considered related with knight's tour on the chessboard.