О задачах обхода графа

графы обходы матрица смежности достижимость эйлеров цикл булевы функции

Работа многоступенчатого компрессора при наполнении емкости, Алгоритм моделирования рабочих процессов в трубопроводах сложной пространственной конфигурации и его программная реализация, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт