О задачах обхода графа
Авторы: Бояринцева Т.Е., Мастихина А.А.
Опубликовано в выпуске: #5(17)/2013
DOI: 10.18698/2308-6033-2013-5-735
Раздел: Инженерное образование
В статье рассматривается тема соотношения "наглядного" способа изложения действий на графах (с использованием рисунка) и "абстрактного" (опирающегося на представление графа посредством матрицы). Такого рода проблема (изложение наглядных действий при помощи инструмента дискретной математики) нередко возникает в преподавании предмета. Для задачи построения матрицы достижимости и определения количества и состава компонент связности даются два алгоритма решения. В качестве примера описания графом системы с различными возможными состояниями приводится задача о переливании. Для другого примера графической задачи дается решение, которое обосновывается уже с применением булевых функций. Также рассматривается задача о построении гамильтонова цикла, связанного с обходом полей шахматной доски фигурой коня.
Литература
[1] Белоусов А.И., Ткачев С.Б. Дискретная математика. Москва, Изд-во МГТУ им. Н.Э. Баумана (серия математика в техническом университете, 2001, вып. XIX)
[2] Уилсон Р. Введение в теорию графов. Москва, Мир, 1977
[3] Яблонский С.В. Введение в дискретную математику. Москва, Наука, 1979
[4] Нефедов В.Н., Осипова В.А. Курс дискретной математики. Москва, Изд-во МАИ, 1992
[5] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Теория графов. Москва, Наука, 1990
[6] Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. Москва, Наука, 1992
[7] Оре О. Теория графов. Москва, Наука, 1968
[8] Панов В.Н. Шахматы и мнемотехника. Наука и жизнь, 1969, № 5