Виталий Печенкин, профессор, д.с.н., к.ф.-м.н.,
pechenkinvv@grin-software.net
Саратовский государственный технический университет имени Гагарина Ю.А.
GRaph INterface
На этом сайте вы можете загрузить программу Grin (GRaph INterface) для MS Windows (NT . . . 10), которая позволит лучше понять задачи теории графов и сетей, увидеть решение этих задач прямо на графе. Работая с программой, можно совершить виртуальное путешествие по интересным разделам дискретной математики. Результаты работы многих алгоритмов можно будет сразу увидеть, что позволяет оценить полученное решение, понять существо задачи.
Grin является полезной для студентов и преподавателей университетов компьютерной программой, которую могут использовать не только математики (дискретная математика, теория графов, исследование операций), но и экономисты (математические модели в экономике), социологи (анализ социальных сетей), все те, кто так или иначе интересуется дискретными моделями. Программа легка в освоении, если пользователь имеет навыки работы с компьютером, работа с ней не вызовет трудностей.
С помощью программы Grin можно создавать, интерактивно редактировать и исследовать графы. Графы сохраняются на диск и легко могут быть загружены. Справочная система (в формате hlp, требует установки и использования WinHlp32.exe) содержит информацию не только по самой программе, но и подробную справку по теории графов и оптимизационным задачам теории сетей. Для преподавателей будут полезны методические материалы, которые содержат специальные задания студентам для работы с Grin на практических занятиях по курсу «Прикладные аспекты теории графов»
Команды редактирования графа
- Добавить элементы графа (вершины и ребра)
- Удалить элементы графа (вершины, ребра, компоненты связности, весь граф целиком)
- Переместить элементы графа (вершины, компоненты связности и весь граф целиком)
- Изменить размер всего графа или его выделенных частей: увеличить, уменьшить, автозаполнение видимого пространства окна)
- Редактировать атрибуты элементов графа (имя, цвет, вес и некоторые другие)
- Изменить тип графа (Ориентированный или неориентированный)
- Программа поддерживает стандартные операции с буфером обмена (копировать, вставить, вырезать, удалить, выделить). Буфер обмена поддерживается на уровне самого приложения. Вы можете копировать в буфер и вставлять из буфера программы графы целиком или их частями. Кроме этого, программа позволяет скопировать в буфер обмена MS Windows изображение графа в растровом (bmp) или векторном (wmf) форматах. Эта возможность позволяет скопировать изображения графа непосредственно в офисное приложение
- Вы можете осуществлять декомпозицию модели (дуг графа). Это полезно при построении сложных многоуровневых моделей проектов при решении задачи о критическом пути. Любая дуга (работа) проекта может быть рассмотрена как самостоятельный проект. В этом случае при решении задачи для текущей модели будет осуществляться рекурсивное вычисление критических путей для всех входящих в него работ, имеющих декомпозицию
Алгоритмы решения задач
- Метрические характеристики графа (радиус, диаметр, плотность, неплотность, наименьшее вершинное покрытие и некоторые другие)
- Пути и циклы (эйлеровы и гамильтоновы)
- Мосты и точки сочленения
- Вершинная раскраска (минимальная вершинная раскраска и эвристические алгоритмы раскраски)
- Группа автоморфизмов
- Минимальное стягивающее дерево
- Кратчайшие пути
- Путь максимальной пропускной способности
- К кратчайших путей
- Задача коммивояжера (классическая постановка и ее обобщение на несколько коммивояжеров)
- Задача о максимальном потоке
- Задача о критическом пути (с вычислением резервов времени для событий и работ проекта, представленного ориентированной сетью)
- Построение иерархии доминирования в социальной сети (алгоритм построения иерархии доминирования Линтона Фримена)
- Алгоритмы вычисления характеристик центральности для социальных сетей
- Стохастическое моделирование работы сетей Петри. В процессе случайным образом выбирается живой переход в соответствии заданными приоритетами. Моделирование выполняется до тех пор пока жив хотя бы один переход.
Пользователь может сохранить информацию из окна результатов в файле отчета графа. Просмотр этого файла тоже вызывается вызовом одной команды. Альтернативный способ хранения информации о графе — в описании самого графа, которое сохраняется в файл вместе с ним и в любой момент доступно на закладке «Описание» окна графа.
Программа поддерживает несколько форматов сохранения и загрузки информации о графе. Для операции экспорта и импорта можно использовать установленную на машине пользователя программу MS Excel. Кроме этого, можно конвертировать описание графа в простое текстовое (формат программы KrackPlot представления графа), которое можно просматривать и редактировать в обычном редакторе текста.
Стандартный файл программы, в котором хранится информация о графе, представляет собой файл формата XML, структура которого описывается оригинальными авторскими тегами. Структура файла достаточно проста и ее можно просмотреть и понять в блокноте. Пользователь может просто отредактировать файл в текстовом редакторе (при наличии определенной осторожности).
Граф можно сохранять в некоторых стандартных графических форматах (bmp или wmf). Для этого нужно воспользоваться командой «Сохранить как…» и выбрать соответствующий формат. При вставке изображения в текстовом редакторе лучше воспользоваться командой копирования изображения в соответствующем формате в буфер обмена.