Н.Э. Баумана, Москва, 105005, Россия
В статье рассматривается тема соотношения «наглядного» способа изложения
действий на графах (с использованием рисунка) и «абстрактного» (опирающегося
на представление графа посредством матрицы). <...> Такого рода проблема (изложение наглядных действий при помощи инструмента дискретной математики) нередко возникает в преподавании предмета. <...> Для задачи построения матрицы достижимости и определения количества и состава компонент связности даются
два алгоритма решения. <...> В качестве примера описания графом системы с различными возможными состояниями приводится задача о переливании. <...> Для другого
примера графической задачи дается решение, которое обосновывается уже с
применением булевых функций. <...> Также рассматривается задача о построении гамильтонова цикла, связанного с обходом полей шахматной доски фигурой коня. <...> Преподавание дискретной математики студентам технических специальностей зачастую связано с определенными трудностями. <...> А все сужающиеся временные
границы не позволяют как следует освоить эту область уже в рамках
дискретной математики. <...> Граф интуитивно понимается как рисунок (геометрический
граф). <...> В данной работе рассматривается соотношение наглядного и абстрактного способов представления действий с графами в области
задач, связанных с обходами. <...> Т.Е. Бояринцева, А.А. Мастихина
(вершины — состояния, ребра — возможные переходы), то достижимость означает, что можно попасть из одного фиксированного состояния в другое. <...> Напомним,
что цикл в графе называется эйлеровым, если он проходит через каждое
ребро ровно один раз; если такой цикл существует, то граф называется
эйлеровым. <...> В таком виде алгоритм Флери не годится для реализации на
ЭВМ. <...> Опишем матричную реализацию алгоритма Флери; она может
быть выполнена на ЭВМ. <...> Для этого построим матрицу достижимости
графа, т. е. матрицу, в которой единицы на пересечении i-й строки и
j-го столбца означают достижимость i-й вершины <...>