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