О программе GRIN

Виталий Печенкин, профессор, д.с.н., к.ф.-м.н.,

pechenkinvv@grin-software.net

Саратовский государственный технический университет имени Гагарина Ю.А.

GRaph INterface

Логотип Grin

На этом сайте вы можете загрузить программу Grin (GRaph INterface) для  MS Windows (NT . . . 10), которая позволит лучше понять задачи теории графов и сетей, увидеть решение этих задач прямо на графе. Работая с программой, можно совершить виртуальное путешествие по интересным разделам дискретной математики. Результаты работы многих алгоритмов можно будет сразу увидеть, что позволяет оценить полученное решение, понять существо задачи.

Граф Петерсена

Grin является полезной для студентов и преподавателей университетов компьютерной программой, которую могут использовать не только математики (дискретная математика, теория графов, исследование операций), но и экономисты (математические модели в экономике), социологи (анализ социальных сетей), все те, кто так или иначе интересуется дискретными моделями. Программа легка в освоении, если пользователь имеет навыки работы с компьютером, работа с ней не вызовет трудностей.

С помощью программы Grin можно создавать, интерактивно редактировать и исследовать графы. Графы сохраняются на диск и легко могут быть загружены. Справочная система (в формате hlp, требует установки и использования WinHlp32.exe) содержит информацию не только по самой программе, но и подробную справку по теории графов и оптимизационным задачам теории сетей. Для преподавателей будут полезны методические материалы, которые содержат специальные задания студентам для работы с Grin на практических занятиях по курсу «Прикладные аспекты теории графов»

Команды редактирования графа

  • Добавить элементы графа (вершины и ребра)
  • Удалить элементы графа (вершины, ребра, компоненты связности, весь граф целиком)
  • Переместить элементы графа (вершины, компоненты связности и весь граф целиком)
  • Изменить размер всего графа или его выделенных частей: увеличить, уменьшить, автозаполнение видимого пространства окна)
  • Редактировать атрибуты элементов графа (имя, цвет, вес и некоторые другие)
  • Изменить тип графа (Ориентированный или неориентированный)
  • Программа поддерживает стандартные операции с буфером обмена (копировать, вставить, вырезать, удалить, выделить). Буфер обмена поддерживается на уровне самого приложения. Вы можете копировать в буфер и вставлять из буфера программы графы целиком или их частями. Кроме этого, программа позволяет скопировать в буфер обмена MS Windows изображение графа в растровом (bmp) или векторном (wmf) форматах. Эта возможность позволяет скопировать изображения графа непосредственно в офисное приложение
  • Вы можете осуществлять декомпозицию модели (дуг графа). Это полезно при построении сложных многоуровневых моделей проектов при решении задачи о критическом пути. Любая дуга (работа) проекта может быть рассмотрена как самостоятельный проект. В этом случае при решении задачи для текущей модели будет осуществляться рекурсивное вычисление критических путей для всех входящих в него работ, имеющих декомпозицию

Алгоритмы решения задач

  • Метрические характеристики графа (радиус, диаметр, плотность, неплотность, наименьшее вершинное покрытие и некоторые другие)
  • Пути и циклы (эйлеровы и гамильтоновы)
  • Мосты и точки сочленения
  • Вершинная раскраска (минимальная вершинная раскраска и эвристические алгоритмы раскраски)
  • Группа автоморфизмов
  • Минимальное стягивающее дерево
  • Кратчайшие пути
  • Путь максимальной пропускной способности
  • К кратчайших путей
  • Задача коммивояжера (классическая постановка и ее обобщение на несколько коммивояжеров)
  • Задача о максимальном потоке
  • Задача о критическом пути (с вычислением резервов времени для событий и работ проекта, представленного ориентированной сетью)
  • Построение иерархии доминирования в социальной сети (алгоритм построения иерархии доминирования Линтона Фримена)
  • Алгоритмы вычисления характеристик центральности для социальных сетей
  • Стохастическое моделирование работы сетей Петри. В процессе случайным образом выбирается живой переход в соответствии заданными приоритетами. Моделирование выполняется до тех пор пока жив хотя бы один переход.

Пользователь может сохранить информацию из окна результатов в файле отчета графа. Просмотр этого файла тоже вызывается вызовом одной команды. Альтернативный способ хранения информации о графе — в описании самого графа, которое сохраняется в файл вместе с ним и в любой момент доступно на закладке «Описание» окна графа.

Программа поддерживает несколько форматов сохранения и загрузки информации о графе. Для операции экспорта и импорта можно использовать установленную на машине пользователя программу MS Excel. Кроме этого, можно конвертировать описание графа в простое текстовое (формат программы KrackPlot представления графа), которое можно просматривать и редактировать в обычном редакторе текста.

Стандартный файл программы, в котором хранится информация о графе, представляет собой файл формата XML, структура которого описывается оригинальными авторскими тегами. Структура файла достаточно проста и ее можно просмотреть и понять в блокноте. Пользователь может просто отредактировать файл в текстовом редакторе (при наличии определенной осторожности).

Граф можно сохранять в некоторых стандартных графических форматах (bmp или wmf). Для этого нужно воспользоваться командой «Сохранить как…» и выбрать соответствующий формат. При вставке изображения в текстовом редакторе лучше воспользоваться командой копирования изображения в соответствующем формате в буфер обмена.