В статье описан алгоритм Кавош (Kavosh) для поиска сетевых мотивов (или статистически важных подграфов). Приведены зависимости скорости работы, полученные в результате апробации данного алгоритма на языке программирования Python. Разработанный прототип веб-приложения Motif App применим как для анализа ориентированных, так и неориентированных графов.
Обсуждаются взаимосвязи курса «Теория графов», «Алгебра и геометрия» и «Математическая логика». Отмечается значение методов теории графов в общей и линейной алгебре и особая роль метода математической индукции.
В статье обсуждается методика использования пакета математических символьных вычислений Maple при изучении вузовского курса «Теория графов». В работе демонстрируется применение подпакетов «Теория графов» и «Линейная алгебра» для нахождения и проверки связи между тремя основными матрицами, задающими граф (матрицей смежности, матрицей инцидентности и матрицей Кирхгофа). Эти же подпакеты Maple используются для нахождения числа остовных деревьев графа связного графа. Одновременно с машинным нахождением матриц демонстрируется связь между этими матрицами, причем машинный иллюстрирующий эксперимент может продолжаться сколь угодно долго. Компьютерная иллюстрация также без ограничения на число опытов предложена и для теоремы Кирхгофа о деревьях, а также для экспериментальной проверки свойств матрицы Кирхгофа.
Предлагается алгоритм построения всех наибольших паросочетаний в произвольном связном графе, основанный на предварительном представлении графа специальной матрицей с последующей процедурой комбинаторного построения паросочетаний. Алгоритм использует способ кодирования элементов графа с помощью простых чисел. Тем самым, реализуется идея цифровизации графа. Такой подход позволяет работать с графом как с числовым объектом, не теряя взаимно однозначного соответствия с его геометрической структурой. Изложенный материал может быть использован как при решении конкретных задач теории графов, так и в учебном процессе.
В статье обсуждается методика использования пакета математических символьных вычислений Maple при изучении вузовского курса «Теория графов». Рассматриваются особенности применения подпакета with (GraphTheory). Показана методика компьютерного исследования и нахождения основных параметров графа. Отмечено, что при машинном решении задачи об изоморфизме двух графов можно использовать, кроме команд подпакета with (GraphTheory), команды подпакета with (LinearAlgebra). При проверке, изоморфны два графа или нет, естественным образом возникают вопросы об устройстве графа, его параметров, сохраняющихся при изоморфизме. Окончательная проверка связи матриц сопряженности проверяемых графов проводится лишь после удачно прошедших проверку неполных инвариантов графов.
На элементарном уровне изложены важнейшие понятия теории
графов, причем основной материал посвящен именно обыкно-
венным (не ориентированным) графам. Подробно рассмотрен ал-
горитм Дейкстры, позволяющий находить кратчайшие маршруты
во взвешенном графе, в общих чертах разобран так называемый му-
равьиный алгоритм, предназначенный для решения известной задачи
коммивояжера. Во втором издании исправлены замеченные неточно-
сти и опечатки, добавлен ряд новых задач, расширен материал, отно-
сящийся к свойствам многогранников.
Книжка адресована старшим школьникам, интересующимся мате-
матикой, а также студентам педвузов – будущим учителям математи-
ки и информатики.
На элементарном уровне изложены важнейшие понятия теории графов, причем основной материал посвящен именно обыкновенным (не ориентированным) графам. Подробно рассмотрен алгоритм Дейкстры, позволяющий находить кратчайшие маршруты во взвешенном графе, в общих чертах разобран так называемый муравьиный алгоритм, предназначенный для решения известной задачи коммивояжера. Во втором издании исправлены замеченные неточности и опечатки, добавлен ряд новых задач, расширен материал, относящийся к свойствам многогранников. Книжка адресована старшим школьникам, интересующимся математикой, а также студентам педвузов - будущим учителям математики и информатики.
Теория графов составляет существенную часть математических методов, применяемых в экономике для решения самых разнообразных задач. Из этого многообразия следует выделить задачи построения оптимальных подграфов определенного вида в заданном связном графе. В последние десятилетия все более актуальными становятся многокритериальные варианты указанных задач. Однако широкому практическому распространению алгоритмов их решения препятствуют имеющиеся сведения об экспоненциальном росте мощности множества Парето-оптимальных решений с ростом размерности задачи, в результате чего наблюдается преждевременное исчерпание вычислительных ресурсов. Чтобы научиться бороться с этой проблемой, надо получить «хорошую», желательно достижимую оценку мощности множества Парето. Это должно способствовать созданию метода диагностирования неконтролируемого роста числа эффективных решений многокритериальных задач и в дальнейшем помочь в разработке методов борьбы с этим ростом. С практической точки зрения среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив (ПМА). Поэтому построению оценки мощности именно ПМА посвящена настоящая работа. В результате проведенных исследований были найдены две универсальных оценки мощности ПМА для произвольных подграфов и доказаны теоремы об их корректности. Отдельно были рассмотрены подграфы двух видов - пути и остовные деревья. Для них приведены примеры достижимости одной из оценок в случае двух критериев. Получены асимптотические оценки вычислительной сложности двух алгоритмов поиска Парето-оптимальных путей в графе. Из полученной оценки следует, что при ограниченности значений весов ребер графа эти алгоритмы относятся к классу псевдополиномиальных, т.е. при определенных условиях их вычислительная сложность ниже экспоненциальной.
Искусственные нейронные сети можно представить в виде графовой модели. Теория графов выступает основой для разработки технологий искусственного интеллекта, которые строятся на алгоритмах и архитектурах моделирования искусственных нейронных сетей
Данная работа посвящена алгебраической теории автоматов, являющейся одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, возникающие во многих прикладных задачах. В зависимости от исследуемых задач рассматриваются автоматы, у которых основные множества наделены дополнительными математическими структурами, согласованными с функциями автомата. В настоящей работе исследуются автоматы над графами — графовые автоматы, множество состояний и множество выходных сигналов которых наделены математическими структурами графов.