Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: LIX Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 27 ноября 2017 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Редькина М.В., Вдовенко С.Г. ГРАФЫ В СИСТЕМЕ КОМПЬЮТЕРНОЙ МАТЕМАТИКИ MAXIMA // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. LIX междунар. студ. науч.-практ. конф. № 11(58). URL: https://sibac.info/archive/technic/11(58).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 12 голосов
Дипломы участников
У данной статьи нет
дипломов

ГРАФЫ В СИСТЕМЕ КОМПЬЮТЕРНОЙ МАТЕМАТИКИ 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, g2)

создает произведение графов g1 и ш

grid_graph (n, m)

создает сетку

cube_graph (n)

создает граф n-мерного куба

complement_graph (g)

создает дополнение графа g

 

Выводы. В статье дано описание команд пакета graph системы компьютерной алгебры Maxima. Рассмотрены способы решения некоторых типичных задач теории графов в Maxima. Используя рассмотрены команды пакета Maxima можно иллюстрировать решения задач на занятиях по курсу дискретной математики.

 

Список литературы:

  1. Красильников В.В. Использование системы компьютерной алгебры MAPLE в булевой алгебре [Текст] / В.В. Красильников, А.А. Оленев, В.С. Тоискин, К.Т. Тынчеров // Актуальные вопросы инженерного образования-2016: сборник научных трудов Международной научно-методической конференции, посвященной 60-летию филиала УГНТУ в г. Октябрьском / ред. кол. В.Ш. Мухаметшин. [и др.]. – Уфа: Изд-во УГНТУ, 2016. - С. 303-310.
  2. Малиатаки В.В. Совершенствование математической подготовки учителя в вузе на основе использования СКА Maple [Текст] / В.В. Малиатаки, Л.М. Медведева, А.А. Оленев // Актуальные вопросы инженерного образования – 2015: сборник научных трудов Международной научно-методической конференции (Октябрьский, 27 ноября 2015 г.) / отв. ред. К.Т. Тынчеров. – Уфа: Альфа Принт, 2016. – С. 129-134.
  3. Оленев А.А. Использование системы компьютерной алгебры MAPLE при изучении дискретной математики [Текст] / В.В. Красильников, А.А. Оленев, В.С.Тоискин, К.Т. Тынчеров // Актуальные вопросы инженерного образования-2016: сборник научных трудов Международной научно-методической конференции, посвященной 60-летию филиала УГНТУ в г. Октябрьском / ред. кол. В.Ш. Мухаметшин. [и др.]. – Уфа: Изд-во УГНТУ, 2016. -С. 310-319.
  4. Оленев А.А. Логические элементы и схемы в СКА MAPLE [Текст] / А.А. Оленев, В.В. Малиатаки, К.Т. Тынчеров // Современные технологии в нефтегазовом деле – 2017: сборник трудов международной научно-технической конференции в 2-х томах./ отв. ред. В.Ш. Мухаметшин. – Уфа: Изд-во УГНТУ, 2017. - С. 280-283.
  5. Оленев А.А Создание MAPLET для решения простейших комбинаторных задач [Текст] /А.А. Оленев, В.В. Малиатаки // Наука сегодня: Проблемы и перспективы развития: сборник (материалы) международной научно-практической конференции: в 2 частях. Научный центр «Диспут». – Вологда: Изд-во: ООО «Маркер», 2016. - С. 135-137.
  6. Уилсон Р. Введение в теорию графов/Р. Уилсон, -М.: Мир, 1977.-135 с.
  7. Чичкарёв Е. А. Компьютерная математика с Maxima: Руководство для школьников и студентов / Е. А. Чичкарёв — М.: ALT Linux, 2012. — 384 с.: ил. — (Библиотека ALT Linux).
Проголосовать за статью
Конференция завершена
Эта статья набрала 12 голосов
Дипломы участников
У данной статьи нет
дипломов

Комментарии (3)

# Игнат 08.12.2017 18:29
Я считаю, что это лучшая статья, которую я читал в своей жизни!
# Олег 08.12.2017 18:48
Афтар жжот пиши истчо)0)0
# ayana 15.03.2019 08:55
супер

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.