On problems concerning paths in a graph
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.