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