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