Статья опубликована в рамках: LIX Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 27 ноября 2017 г.)
Наука: Информационные технологии
Скачать книгу(-и): Сборник статей конференции
дипломов
ГРАФЫ В СИСТЕМЕ КОМПЬЮТЕРНОЙ МАТЕМАТИКИ MAXIMA
В последнее время наблюдается активное проникновение систем компьютерной алгебры в образовательный процесс, позволяющий формировать инновационные технологии обучения, в частности математического обучения в институтах и университетах [1], [3], [4], [5], [6], [7]. Одной из самых популярных систем компьютерной алгебры является система Maxima. Maxima является свободной системой компьютерной алгебры, написанной на языке Common Lisp. Произошла от системы Macsyma, которую разрабатывали в MIT с 1968 по 1982 годы. Система успешно сочетает символьные манипуляции, вычислительную математику, имеет мощную графику. В настоящее время технологии сопровождения математического моделирования, несмотря на свою эффективность и наглядность, в силу различных причин, еще недостаточно распространены в учебном процессе, что не способствует интеграции системы высшего образования России в мировое пространство высшего образования.
Целью данной статьи является популяризация систем компьютерной алгебры, использование СКА Maxima для изучения основных типов графов [2]. Начальные навыки работы в системе компьютерной алгебры Maxima, подробно рассмотрены в [1]. Данная статья является альтернативой (с точки зрения используемой системы компьютерной алгебры) [3], [4], [5], [6], [7].
Создание графов. Для работы с графами в Maxima предназначен специализированный пакет graphs, который вызывается командой load(graphs). Под графами создатели пакета понимают только конечные простые (обыкновенные) графы и орграфы, т. е. конечные графы без петель и кратных ребер. Это можно объяснить тем, что в приложениях теории графов обычно встречаются именно эти виды графов и орграфов. Кратко опишем основные функции, входящие в данный пакет. Он представляет собой набор процедур для создания графов, изображения графов, манипуляций с ними и проверки их свойств. Пакет поддерживает как ориентированные и неориентированные, так взвешенные и не взвешенные графы.
Для подключения пакета необходимо в рабочей строке Maxima после символа приглашения ввода команды “>” набрать командную строку следующего вида:
Основной командой для создания неориентированного графа является команда Graph <список параметров>. В списке параметров указываются множества вершин графа, множества ребер, которые задаются парой упорядоченных элементов, матрица инцидентности и другие параметры.
Простейшим списком параметров может служить множество, элементами которого являются пары инцидентных вершин, к примеру:
Если граф уже задан, то команды vertices (G) и edges (G) выдают списки вершин графа и список его ребер соответственно, например, для созданного выше графа имеем:
Команда random_graph (g,p) создает граф из g вершин соединенных ребрами с вероятностью p:
Для того чтобы добавить новую вершину или новое ребро в граф используем команды add_vertex и add_edge, например:
В предыдущем графе добавлена вершина, произведено соединение ребром вершин 1 и 4 и произведена проверка правильности выполнения действий.
Для того чтобы удалить ребро из графа используется команда remove_edge (e, gr) с аналогичным синтаксисом.
Также в качестве параметра можно указать матрицу инцидентности графа, предварительно определив ее:
Характеристический многочлен графа, то есть характеристический многочлен его матрицы инцидентности, находится при помощи команды CharacteristicPolynomial (G, переменная):
Изображение графов. Для изображения графов служит команда DrawGraph (G). Для определенного выше графа имеем
Рисунок 1. Граф G = {[1, 2], [2, 3], [3, 1], [3, 2], [3, 3], [4, 1], [4, 4]}
Эта команда позволяет строить достаточно сложные графы, которые имеют до 1000 вершин.
Ниже приведены команды для создания и изображение случайного графа с четырьмя вершинами:
Рисунок 2. Случайный граф
Свойства графов. Пакет позволяет находить и оценивать основные свойства графов, в частности такие как: проверка на связность, планарность, гамильтоновость, регулярность, находить компоненты связности. Проиллюстрируем основные команды на конкретном примере.
Рисунок 3. Граф G = {{1,2}, {1,3}, {2,3}, {3,4}, {4,5}, {5,6}}
Проверка графа на связность и нахождение компонентов связности:
Проверка графа на связность и находим компоненты связи:
Находим расстояние диаметр графа:
Специальные графы. Maxima обеспечивает работу с несколькими десятками хорошо известных графов, в частности с графами Дезарга, Петерсена, Клебш, Коксетер, Пели и другими.
Рисунок 4. Граф Петерсена.
Перечень и описание всех типов специальных графов есть в справочной системе
http://maxima.sourceforge.net/docs/manual/de/maxima_50.html.
Таблица 1 содержит перечень основных команд пакета graph, которые могут быть полезными при работе с графами. В первой колонке представлены название и синтаксис команды Maxima, а во второй колонке дано описание функций этой команды.
Таблица 1
|
Список команд пакета пакета graph. Создание и визуализация графов и орграфов |
|
|
create_graph (v_list, e_list) |
создает граф со списком вершин v_list и списком ребер e_list. |
|
create_graph (v_list, e_list, directed), |
n – число вершин (вершины пронумерованы целыми числами от 0 до n ), v_list – список вершин [v1, v2, ..., vn] или список вершин вместе с метками вершин [[v1, l1], [v2, l2]..., [vn, ln]], e_list – список ребер [e1, e2, ..., em] или список ребер вместе с весами ребер [[e1, w1], ..., [em, wm]] |
|
print_graph( ) |
Вывод информации о созданном графе используется функция По умолчанию установлено directed=false, если directed=true, то будет создан орграф |
|
Операции над графами |
|
|
remove_vertex (v, gr) |
удаляет вершину v из графа gr вместе с инцидентными ей ребрами |
|
remove_edge (e, gr) |
удаляет ребро e из графа gr |
|
add_vertex (v, gr) |
добавляет вершину v в граф gr; |
|
add_vertices (v_list, gr) |
добавляет все вершины из списка v_list в граф gr |
|
connect_add_edge (e, gr) |
добавляет ребро e в граф gr |
|
add_edges (e_list, gr)
|
добавляет все ребра из списка e_list в граф gr |
|
contract_edge (e, gr) |
стягивает ребро e в графе gr |
|
connect_vertices (v_list, u_list, gr) |
соединяет все вершины из списка v_list с вершинами в списке u_list в графе gr (v_list и u_list могут быть одиночными вершинами). |
|
induced_subgraph (V, g)
|
создает подграф графа g на подмножестве вершин |
|
Операции над самими графами |
|
|
graph_union (g1, g2) |
создает объединение графов g1 и g2 |
|
graph_product |
создает произведение графов g1 и ш |
|
grid_graph (n, m) |
создает сетку |
|
cube_graph (n) |
создает граф n-мерного куба |
|
complement_graph (g) |
создает дополнение графа g |
g1, g2)
Выводы. В статье дано описание команд пакета graph системы компьютерной алгебры Maxima. Рассмотрены способы решения некоторых типичных задач теории графов в Maxima. Используя рассмотрены команды пакета Maxima можно иллюстрировать решения задач на занятиях по курсу дискретной математики.
Список литературы:
- Красильников В.В. Использование системы компьютерной алгебры MAPLE в булевой алгебре [Текст] / В.В. Красильников, А.А. Оленев, В.С. Тоискин, К.Т. Тынчеров // Актуальные вопросы инженерного образования-2016: сборник научных трудов Международной научно-методической конференции, посвященной 60-летию филиала УГНТУ в г. Октябрьском / ред. кол. В.Ш. Мухаметшин. [и др.]. – Уфа: Изд-во УГНТУ, 2016. - С. 303-310.
- Малиатаки В.В. Совершенствование математической подготовки учителя в вузе на основе использования СКА Maple [Текст] / В.В. Малиатаки, Л.М. Медведева, А.А. Оленев // Актуальные вопросы инженерного образования – 2015: сборник научных трудов Международной научно-методической конференции (Октябрьский, 27 ноября 2015 г.) / отв. ред. К.Т. Тынчеров. – Уфа: Альфа Принт, 2016. – С. 129-134.
- Оленев А.А. Использование системы компьютерной алгебры MAPLE при изучении дискретной математики [Текст] / В.В. Красильников, А.А. Оленев, В.С.Тоискин, К.Т. Тынчеров // Актуальные вопросы инженерного образования-2016: сборник научных трудов Международной научно-методической конференции, посвященной 60-летию филиала УГНТУ в г. Октябрьском / ред. кол. В.Ш. Мухаметшин. [и др.]. – Уфа: Изд-во УГНТУ, 2016. -С. 310-319.
- Оленев А.А. Логические элементы и схемы в СКА MAPLE [Текст] / А.А. Оленев, В.В. Малиатаки, К.Т. Тынчеров // Современные технологии в нефтегазовом деле – 2017: сборник трудов международной научно-технической конференции в 2-х томах./ отв. ред. В.Ш. Мухаметшин. – Уфа: Изд-во УГНТУ, 2017. - С. 280-283.
- Оленев А.А Создание MAPLET для решения простейших комбинаторных задач [Текст] /А.А. Оленев, В.В. Малиатаки // Наука сегодня: Проблемы и перспективы развития: сборник (материалы) международной научно-практической конференции: в 2 частях. Научный центр «Диспут». – Вологда: Изд-во: ООО «Маркер», 2016. - С. 135-137.
- Уилсон Р. Введение в теорию графов/Р. Уилсон, -М.: Мир, 1977.-135 с.
- Чичкарёв Е. А. Компьютерная математика с Maxima: Руководство для школьников и студентов / Е. А. Чичкарёв — М.: ALT Linux, 2012. — 384 с.: ил. — (Библиотека ALT Linux).
дипломов
Комментарии (3)
Оставить комментарий