Справка программы Графоанализатор 1.3 - http://grafoanalizator.unick-soft.ru
Справка по программе Графоанализатор 1.3
Официальный сайт:
http://grafoanalizator.unick-soft.ru
2010 год
Графоанализатор 1.3 что это? 4
Визуализация графов и алгоритмов. 4
20 алгоритмов для работы с графом 5
Для чего можно использовать программу 11
Поиск минимального пути проезда 11
Поиск минимальных затрат на прокладку проводки или компьютерной сети 14
Поиск минимальных затрат при найме сотрудников 14
Расчет пропускной способности компьютерной или дорожной сети 18
Распределение работы между несколькими работниками 20
Пример решения задач: Проверка возможности соединения электронных элементов на плате 26
Пример решения задач: Поиск метода раскраски карты минимальным числом краски 27
Пример решения задач: Решение задачи коммивояжёра 28
Сохранения визуального представления 31
Редактирование матрицы смежности 33
Настройка внешнего вида вершин, дуг и текста 35
Настройка внешнего вида вершин 36
Настройка внешнего вида дуг 36
Настройка внешнего вида надписей 36
Настройка фонового изображения 36
Алгоритмы поиска эйлеровых и гамильтоновых маршрутов 40
Алгоритм нахождения эйлерового пути и цикла 40
Алгоритм нахождения гамильтонова пути и цикла 41
Определение хроматического числа 41
Определение минимального оставного дерева 41
Определение максимального потока 41
Поиск пропускной способности для одного истока и стока 41
Поиск пропускной способности для нескольких истоков и стоков 42
Поиск эксцентриситета вершины 42
Нахождение радиуса и диаметра графа 42
Проверка является ли граф деревом 42
Графоанализатор – визуальная среда для работы с графами. Графоанализатор не только предоставляет возможность создавать и обрабатывать графы, но визуально отображать результаты работы алгоритмов. Среда поддерживает работу с ориентированными и простыми графами, нагруженными и ненагруженными. Программа реализует множество алгоритмов для обработки графов, начиная от поиска пути и заканчивая проверкой на планарность. Графоанализатор – это незаменимый помощник для решения задач с помощью графов.
|
Процесс создания и изменения графа интуитивно понятен. Визуальное представление графа является очень понятной формой представления графа, также можно увидеть результат работы алгоритма в визуальной форме. Визуальное представление можно сохранить в файле изображения. Для большей наглядности вы можете добавлять подписи к элементам граф, изменять фон, настраивать внешний вид элементов графа.
|
|
|
Для редактирования графа можно использовать различные методы: визуально редактировать граф или редактировать матрицу смежности графа.
|
|
|
|
|
Среда Графоанализатор предоставляет пользователю множество вспомогательных функций для облегчения работы: возможность сохранения и загрузки графа с поддержкой сохранения визуального представления, возможность создания графа из матрицы смежности, быстрое преобразование графа, настройка вида графа, обозначения вершин, загрузка подложки графа, режим создания карты с заданием масштаба, режим конструктора.
Графоанализатор 1.3, далее в соглашении «программа».
Программа является абсолютно бесплатной и поставляется «как есть». Пользователь не имеет права зарабатывать деньги путём продажи программы или сдачи её в аренду. При размещении программы на электронных носителях или страницах Интернет, необходимо указать ссылку на официальный сайт программы http://grafoanalizator.unick-soft.ru.
Производитель программы не несёт ответственности за вред или убытки, причиненные в результате использования программы и за косвенный вред или убытки, к которым привело использование программы.
Запрещено использовать программу с целью, нарушающую законодательство РФ или другой страны, на территории которой используется программа.
При попытки использовать программу после 1 октября 2010 года включительно, необходимо бесплатно регистрировать копии программы по адресу: http://grafoanalizator.unick-soft.ru/registration/.
Для
начала необходимо создать
граф, выбрав его тип (программа поддерживает как
нагруженные графы так и нет, как ориентированные так и
неориентированные) и тип нумерации вершин.
Можно загрузить
граф из файла.
После необходимо добавить вершины и дуги. Для редактирования веса дуг можно использовать матрицу смежности или делать это визуальным методом. Если вы строите граф на основе карты, вы можете использовать режим карты. Для упрощения создания графа можно использовать режим конструктора.
Вы можете настроить внешний вид вершины и дуг, или загрузить задний фон рабочей области. Также вы можете настроить размер вершины.
После создания графа вы можете применить один из алгоритмов:
Результат алгоритма можно увидеть визуально или в окне вывода результата алгоритма, отчёт можно просмотреть в формате HTML и текстовом формате.
После работы с графом его можно сохранить. Если вы нашли в программе недостатки, или вам необходимо добавить какую-то функциональность, то можете написать об этом автору.
Для использования программы после 1 октября 2010 года необходимо зарегистрироваться. Регистрация абсолютно бесплатная. Подробно о регистрации вы можете узнать в разделе «Регистрация».
Главная форма программы представлена ниже:
1 — главное меню программы;
2 — рабочая область;
3 — окно матрицы смежности;
4 — поле вывода результата работы;
5 — кнопки быстрого доступа.
Рисунок 3.1 — Главное окно программы
Описание остальных диалоговых окон находится в соответствующих разделах.
Остальные функции программы описаны в разделах «Задание графа» и «Алгоритмы».
Программу Графоанализатор 1.2 можно использовать для решения множества задач, которые можно свести к математической модели графов. Ниже приведён список типичных задач:
поиск минимальных затрат на прокладку проводки или компьютерной сети;
расчет пропускной способности компьютерной или дорожной сети;
проверка возможности соединения электронных элементов на плате;
Решение всех задач сводится к поиску минимального маршрута в нагруженном графе.
Нам необходимо проехать от дома до магазина, причём путь должен быть минимальный. Предположим, мы имеем карту улиц.
Рисунок 3.2 — Карта города
Для начала загружаем карту улиц как задний фон для рабочей области.
Рисунок 3.3 — Загруженный задний фон
Затем устанавливаем масштаб (сколько метров в 10 пикселях карты)
Рисунок 3.4 — Задание масштаба
Затем чертим граф на основе карты.
Рисунок 3.5 — Граф на основе карты
А теперь находим кратчайший путь, используя один из методов (Форда-Беллмана, Дейкстры или Флойда). После поиска кратчайшего пути мы увидим оптимальный путь.
Рисунок 3.6 — Граф с найденным минимальным путём
Как мы видим, кратчайший путь равен 460.
Задача решается подобно той, что была рассмотрена выше, только необходимо использовать карту всех возможных методов прокладки сети.
Задача о найме сотрудников сводится к нахождению минимального пути.
Предположим, нам необходимо нанять сотрудников, отвечающих на телефонные звонки с 8 часов утра до 20 часов. У нас есть список сотрудников, которые согласны работать в различное время за различную плату:
Дядя Петя:
С 8 до 10 – 200 рублей.
С 14 до 18 – 500 рублей
С 19 до 20 – 50 рублей
Наталья Ивановна
С 8 до 12 – 350 рублей
С 15 до 20 – 700 рублей
Мальчик Вова
С 9 до 12 – 290 рублей
С 14 до 16 – 190 рублей
С 18 до 20 – 250 рублей
Робот
С 10 до 14 – 350 рублей
С 16 до 19 – 250 рублей
Василий Иванович
С 10 до 15 – 700 рублей
С 18 до 19 – 70 рублей
Данные в таком виде выглядят очень непонятно, тогда представим их виде временной диаграммы.
|
Время
Работники |
С 8 до 9 |
С 9 до 10 |
С 10 до 11 |
С 11 до 12 |
С 12 до 13 |
С 13 до 14 |
С 14 до 15 |
С 15 до 16 |
С 16 до 17 |
С 17 до 18 |
С 18 до 19 |
С 19 до 20 |
|
Дядя Петя |
200 р |
|
|
|
|
500 р |
|
50 р |
||||
|
Наталья Ивановна |
350 р |
|
|
|
700 р |
|||||||
|
Мальчик Вова |
|
290 р |
|
|
190 р |
|
|
250 р |
||||
|
Робот |
|
|
350 р |
|
|
250 р |
|
|||||
|
Василий Иванович |
|
|
700 р |
|
|
70 р |
|
|||||
Как видно из диаграммы, альтернатив найма несколько, хотя их количество не велико, но это только пример, в реальной жизни может быть всё сложнее.
Теперь на основе этих данных строим граф. Вершинами графа будут временные метки через каждый час, а дугами, варианты оплаты разных работников.
Рисунок 3.7 — Граф на основе графика работы
Теперь, найдя наикратчайший путь из первой вершины в последнюю, мы определим минимальные затраты и метод найма.
Рисунок 3.8 — Найденный минимальный маршрут
В результате правильным решением будет следующее, выделенное зелёным цветом:
|
Время
Работники |
С 8 до 9 |
С 9 до 10 |
С 10 до 11 |
С 11 до 12 |
С 12 до 13 |
С 13 до 14 |
С 14 до 15 |
С 15 до 16 |
С 16 до 17 |
С 17 до 18 |
С 18 до 19 |
С 19 до 20 |
|
Дядя Петя |
200 р |
|
|
|
|
500 р |
|
50 р |
||||
|
Наталья Ивановна |
350 р |
|
|
|
700 р |
|||||||
|
Мальчик Вова |
|
290 р |
|
|
190 р |
|
|
250 р |
||||
|
Робот |
|
|
350 р |
|
|
250 р |
|
|||||
|
Василий Иванович |
|
|
700 р |
|
|
70 р |
|
|||||
Решение обоих задач сводится к нахождению максимального потока. Только задачу о распределение работы между несколькими работниками необходимо свести к ней.
Предположим, у нас есть участок сети дорог, представленный на рисунке ниже.
Рисунок 3.9 — Карта дорог
Нам необходимо просчитать пропускную способность сети дорог в одном из направлений. Например, слева на право. Мы строим ориентированный граф, и задаём веса дуг равные пропускной способности. Все правые и левые дороги соединяем с истоком и стоком. В результате получим граф:
Рисунок 3.10 — Граф на основе карты дорог
Осталось только просчитать пропускную способность. В результате получаем такое распределение потока.
Рисунок 3.11 — Максимальная пропускная способность дорог
Распределение работ между работниками тоже сводится к поиску пропускной способности. Пусть мы имеем список работников:
Дядя Петя;
Наталья Ивановна;
Мальчик Вова;
Робот;
Василий Иванович;
Петров;
Иванов;
Сидоров.
Также имеется список работ, необходимых для выполнения:
копать;
пилить;
решать уравнения;
готовить;
убирать;
делать уроки;
составлять отчёт;
готовить кофе;
спать;
петь;
тратить деньги;
зевать;
чинить.
Каждый из работников может выполнять различные типы работ. Ниже приведён список, кто какие виды работы может выполнять.
Дядя Петя:
копать;
пилить;
зевать;
чинить;
Наталья Ивановна:
готовить;
убирать;
готовить кофе;
Мальчик Вова:
делать уроки;
составлять отчёт;
копать;
Робот:
пилить;
решать уравнения;
готовить;
Василий Иванович:
составлять отчёт;
копать;
решать уравнения;
петь;
Петров:
тратить деньги;
зевать;
чинить;
Иванов:
готовить кофе;
спать;
петь;
Сидоров:
убирать;
делать уроки.Как мы видим, разные виды работ могут выполнять разные работники, и по условию одна работа может выполняться одним работником.
Нам необходимо распределить работников так, что бы максимальное количество работ выполнялось. Сделать это вручную трудоёмкая задача, если число работников велико.
Для решения представим нашу задачу в виде графа. Левый столбик вершин графа – это работники, правый – это типы работ. Также мы добавили сток и исток.
Теперь соединим каждого работника с тем типом работ, который он может выполнять. Вес дуги графа равны 1.
Рисунок 3.12 — Граф на основе работников и видов работ
После соединяем исток со всеми работниками, а сток соединяем с видами работ. Вес также равен 1.
Рисунок 3.13 — Граф на основе работников и видов работ
Теперь ищем пропускную способность.
Рисунок 3.14 — Способ распределения работников
Пропускная способность нам показала, какой работник должен выполнять какую работу. Например, Петров должен тратить деньги, Дядя Петя должен копать.
При строительстве дорог или при прокладке кабелей может существовать несколько путей соединения города или компьютера, но необходимо это сделать одним определённым способом. Причём, желательно, чтобы выбранный способ был наиболее экономичным с точки зрения временных или денежных затрат.
Пусть мы имеем несколько городов и возможные способ соединения их.
Нам необходимо соединить все города и затратить на это наименьшие количество денег. Преобразуем нашу карту в граф.
Рисунок 3.15 — Карта городов
А теперь осталось найти наименьшее оставное дерево.
Рисунок 3.16 — Минимальная стоимость постройки дорог
В результате мы затратим всего 73 условные единицы.
При соединении элементов на электронной плате, необходимо чтобы соединения не пересекались. Для этого эклектическую цепь необходимо представить в виде графа. Если граф является планарным, то можно соединить все элементы цепи без пересечений.
Если существует карта, на которой находятся страны, и необходимо найти такой метод раскраски чтобы две соседние страны имели разные цвета.
Пусть имеется карта:
Рисунок 3.17 — Карта стран
Для представления карты в виде графа, страны будут являться вершинами графа, а границы дугами. Тогда граф будет выглядеть так:
Рисунок 3.18 — Граф на основе карты стран
После ищем хроматическое число графа, и получаем такой результат:
Рисунок 3.19 — Способ раскраски графа
Предположим, у фирмы или курьера, или коммивояжёра имеются клиенты, и необходимо посетить всех клиентов только один раз.
Представим наших клиентов в виде графа.
Рисунок 3.20 — Карта расположения клиентов
Для поиска необходимого пути, выбираем алгоритм поиска Гамильтоновой цепи.
Рисунок 3.21 — Маршрут обхода клиентов
Первая операция, которую необходимо выполнить – это задать граф, с которым вы будете работать. Основные этапы задания графа:
Для создания графа сначала необходимо выбрать его тип. На рисунке 4.1 приведена форма создания графа.
Рисунок 4.1 — Форма создания графа
Если установить галочку «Орграф», тогда граф будет ориентированным. Если установить галочку «Нагруженный граф», граф будет нагруженным.
Для того, что бы создать граф необходимо вызвать меню «Создать».
Рисунок
4.2 — Меню программы «Граф»
Для сохранения графа с целью его дальнейшего использования необходимо выбрать пункт меню «Файл» – «Сохранить граф».
Рисунок 4.3 — Изображение меню «Файл»
В результате, в файле будет сохранён граф, его тип, позиция вершин, позиции и значения надписей. Также в меню сохраняются последование файлы графа, с которыми вы работали.
Для сохранения визуального представления графа, необходимо выбрать пункт меню «Граф» — «Сохранить изображение». В результате в файле будет сохранено, то что вы ведите в рабочей области.
Для возобновления работы с ранее сохраненным графом необходимо загрузить граф, используя меню «Файл» – «Загрузить граф».
Рисунок
4.4 — Изображение меню «Файл»
Все данные о графе, которые ранее были использованы, будут утеряны.
Добавление вершины можно произвести несколькими методами:
И
спользовать
горячую клавишу «F3».
Кнопку на панели.
И
спользовать
пункт из меню Граф.
Стоит отметить, что вершина будет добавлена в случайную позицию рабочей области. Если в виде нумерации вершин выбрана нумерация, задаваемая пользователем, то также будет необходимо ввести название вершины.
Добавление дуги можно произвести несколькими методами:
И
спользовать
пункт меню из меню «Граф». После необходимо ввести
номер вершины, из которой будет идти дуга и в какую. Также можно
использовать горячую клавишу «F4».
В
торой
метод – это графический. Сначала необходимо выделить вершину,
кликнув на неё левой клавишей мышки, потом
кликнуть правой кнопкой по второй вершине, и из контекстного меню
выбрать «Чертить дугу». Для упрощения можно
использовать режим конструктора.
Редактировать матрицу смежности, вводом значения в соответствующую клетку.
Д
ля
создания поясняющих надписей существует возможность добавления
текста. Для добавления текста необходимо выбрать соответствующий
пункт из меню «Граф» или нажать кнопку на панели
быстрого доступа. После этого необходимо выбрать место для
расположения надписи, а потом ввести текст надписи.
Д
ля
удаления объектов (вершин графа, дуг или надписей) необходимо их
выделить, кликнув на них правой кнопкой мышки, а потом выбрать пункт
из меню «Граф» или нажать кнопку на панели.
Для перемещения объектов (вершин графа, дуг или надписей) необходимо нажать на объект левой кнопкой мышки, и не отпуская её, произвести перемещение мыши.
Для переименования вершин, изменения веса дуг и переименования надписей, необходимо выбрать интересующий элемент. Зайти в пункт меню Изменить и выбрать один из пунктов:
- для редактирования название вершины, в режиме названий, задаваемых
пользователем.
- для редактирования веса дуг, для нагруженных графов.
- для изменения текста надписи.
Редактирование матрицы смежности можно осуществить 2 различными методами.
Первый метод заключается в использовании панели матрицы смежности для редактирования весов дуг.
Рисунок 4.5 — Окно редактирования матрицы смежности
При редактировании неорграфа второе значение будет добавлено автоматически. При введении некорректных значений, будет выведено сообщение.
В
торой
метод редактирования – это задание матрицы смежности.
Для этого необходимо выбрать пункт меню Граф –
Редактировать матрицу смежности. В появившемся окне можно ввести
новую или редактировать старую матрицу смежности. Значения в матрице
смежности разделяются знаком «,». После применения
матрицы смежности, если она была корректна, будет создан граф,
положение всех вершин будет случайно.
Режим обработки мыши определяет обработку правого клика мышки. Существует 2 режима обработки мышки:
В режиме конструктора при клике правой кнопкой мышки по вершине, автоматически создастся дуга.
В режиме поиска пути при клике правой кнопкой мышки по вершине появляется контекстное меню с выбором метода поиска пути или для создания дуги.
Режим карты предназначен для создания графа на основе карты. Режим поддерживается только для нагруженных графов. При создании дуги её вес будет заполняться автоматически исходя из масштаба.
Рисунок 4.6 — Меню режима карты
Для настройки создания карты необходимо вызвать элемент меню Режим работы — Режим карты — Настроить масштаб.
Р
исунок
4.7 — Диалог настройки масштаба
В диалоговом окне можно ввести сколько веса дуги будет в 10 пикселях карты.
Для активирования режима необходимо вызвать элемент меню Режим работы — Режим карты — Включить. После создания дуги вес будет добавляться автоматически. Этот режим лучше использовать вместе с фоновым изображением.
Для улучшения визуального восприятия существует возможность настройки вида вершин, дуг и текста. Каждая из настроек состоит из 2 типов: настройка нормального и активного вида.
Нормальный тип это то, как выглядит элемент в нормальном состоянии. Активный тип это то, как выглядит элемент, когда он выделен.
Для настройки внешнего вида необходимо выбрать пункт меню Вид — Настроить...
Рисунок 4.8 — Диалог настройки внешнего вида
Для вершин можно настроить цвет линий, цвет заливки, цвет текста и размер вершин. Изменить атрибуты можно, кликнув на соответствующий кружок.
Для дуг можно настроить цвет линий, цвет текста и толщину линии.
Для настройки надписей можно настроить цвет текста, цвет фона и атрибуты шрифта.
Для загрузки фонового изображения необходимо выбрать элемент меню Вид — Загрузить фон.
Для удаления фонового изображения необходимо выбрать элемент меню Вид — Очистить фон.
Преобразование графа используется для изменения типа графа. Для преобразования графа необходимо использовать пункты меню «Граф»- «Преобразование графа»:
«...в
неорграф» - преобразует граф в не ориентированные;
«...в орграф» - преобразовать граф в ориентированный граф;
«...в нагруженный» - преобразовать граф в нагруженный граф;
«...в не нагруженный» - преобразовать граф в не нагруженный граф.
Для изменения типа графа необходимо выбрать меню Граф — Свойство графа.
Рисунок
4.9 — Настройка свойства графа
Используя диалог можно изменить тип графа и тип нумерации.
Доступ к алгоритмам можно осуществить через меню Алгоритмы, Особые алгоритмы или контекстное меню.
Приведём сводную таблицу алгоритмов и их ограничений.
|
Название алгоритма |
Поддерживает неорграфы |
Поддерживает орграфы |
Поддерживает ненагруженные графы |
Поддерживает нагруженные графы |
|
Да |
Да |
Нет |
Да |
|
|
Да |
Да |
Нет |
Да |
|
|
Да |
Да |
Нет |
Да |
|
|
Да |
Да |
Да |
Нет |
|
|
Да |
Да |
Да |
Нет |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Да |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Нет |
Да |
Нет |
Да |
|
|
Нет |
Да |
Нет |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
|
|
Нет |
Да |
Нет |
Да |
|
|
Да |
Да |
Да |
Да |
|
|
Да |
Нет |
Да |
Да |
Поиск пути включает в себя несколько алгоритмов, для поиска пути и поиска кратчайшего пути в нагруженный и ненагруженный графы.
Алгоритм Терри служит для нахождения не кратчайшего пути. Другими словами, для проверки достижимости.
Алгоритм обходит граф пока не дойдёт до конечной вершины или не обойдёт все вершины.
Служит для поиска кратчайшего пути в нагруженном графе.
На каждой шаге алгоритм обновляет расстояние от начальной вершины до всех остальных. Сначала рассматриваются вершины соседние с начальной, потом соседние с соседней.
Алгоритм служит для нахождения пути в нагруженном графе.
Кратно описать алгоритм можно следующим образом:
Обозначим через МинРс(1, f, к) наименьшее расстояние между 1 вершиной и вершину с номером f менее чем через k вершин. Для поиска остальных значений прибегнем к формуле:
МинРс (1, f, k+1) = наименьшему из чисел МинРс(1, f, k) и МинРс(1, i, k) + a[i][f] (i=1..n).
Алгоритм находит все кратчайшие расстояния в графе.
Алгоритм основан на том предположении, что расстояние между вершинами А и Б, может быть больше, чем расстояние от А до В + от В до Б.
В виде псевдокода изобразить алгоритм можно следующим образом:
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
Алгоритм фронта волны подходит для не нагруженных графов.
Алгоритм помечает расстояния от начальной вершины. Ответом будет являться число, которое было записано в конечную вершину.
Эйлеровым считается путь, который проходит по всем дугам графа равно 1 раз. Гамильтоновым считается путь, который проходит через 1 вершину только один раз.
Для нахождения эйлеровго цикла в графе должны быть все вершины чётной степени. При нахождении пути в графе должны быть 2 вершины не чётной степени, и соединив, их задача сведётся к нахождению эйлерового цикла.
Для нахождения эйлерового цикла необходимо найти последовательно циклы и удалять из графа дуги этих циклов.
Для нахождения гамильтонова пути и цикла используется поиск методом перебора. В связи с этим, для больших графов поиск может занять много времени.
Хроматическое число – это минимальное число цветов для раскраски графа.
Для поиска хроматического числа используется 2 алгоритма. Первый из них из меню Алгоритмы — Определение Хроматического числа:
Найдем вершину с максимальным количество дуг. Данная вершина раскрашивается в первый цвет. Берётся одна из соседних вершин и раскрашивается в цвет 2, ещё одна соседняя – в минимальный цвет его соседний плюс 1.
Второй алгоритм из меню Особые Алгоритмы — Определение хроматического числа альтернатив алгоритмам:
Все вершины сортируются по числу дуг и раскраска начинается от вершины с максимальным количеством дуг.
Стоит отметить что оба алгоритма не идеальны и могут не всегда выдавать корректный результат.
Минимальное оставное дерево – подграф с минимальной суммой дуг, соединяющий все вершины.
Для нахождения минимального оставного дерева сначала необходимо найти дугу с минимальным весом, включить его в результирующий подграф, затем включить в подграф соседнею дугу с минимальным весом. И так далее пока все вершины не будут соединены.
Поток в графе, если его величина максимальна, называется максимальным. В программе реализовано 2 метода поиска максимального потока: поиск максимального потока для одного истока и стока и для нескольких истоков и стоков.
Поиск производится по алгоритму Форда-Фалкерсона. На графе визуализируется поток.
Для начала граф преобразуется к виду, когда все истоки соединяются с псевдо истоком, вес дуг при этом равен 30000 (условная бесконечность). Также исток соединяется с псевдо истоком.
После, поиск потока производится по алгоритму Форда-Фалкерсона.
Проверка выдаёт как результат связный граф или нет. Алгоритм использует метод заливки.
Эксцентриситет вершины – расстояние до наиболее удаленной вершины. Для поиска необходимо выбрать вершину, применить к ней алгоритм. Результатом будет значение эксцентриситета. Данный алгоритм можно применять только к связным графам.
Радиус графа – это наименьший эксцентриситет, а максимальный эксцентриситет называется диаметром. Результатом алгоритма будет 2 значения радиуса и диаметра.
Дерево – связный граф, не имеющий циклов.
Для проверки является ли граф деревом необходимо проверить граф на связность и найти циклы в графе, если их нет то граф — дерево.
Граф является планарным если его можно расположить на плоскости, чтобы его дуги не пересекались.
Алгоритм работает исходя из необходимого условия и достаточного условия.
Поиск критического пути графа для нагруженного орграфа. Алгоритм поддерживает множество начальных точек и множество конечных, при этом считается что все начальные точки происходят в одно и тоже время, как и все конечные.
Алгоритм проверки на ацикличность, при это программа выведен один из найденных циклов. Поиск циклов проводиться путём поиска в глубину.
Поиск максимального полного подргафа с использованием алгоритма Брона-Кербоша.
Программа «Графоанализатор 1.3» протестирована под операционными системами Windows XP, Windows Vista, Windows 7.
Официальный сайт программы: http://grafoanalizator.unick-soft.ru.
Написать автору можно по адресу soft_support@list.ru.
В программу встроена форма обратной связи, для открытия формы необходимо вызвать пункт меню «Справка» — «Обратная связь».
Если в программе найдены ошибки или необходимо расширить её функционал, то пишете об этом автору.
Для отключения окна регистрации или использования программы после 1 октября 2010 года необходимо зарегистрировать свою копию программы. Для этого необходимо зайти на страницу регистрации: http://grafoanalizator.unick-soft.ru/registration/
Заполнить форму и ввести полученный код активации в форму регистрации: Справка — Регистрация.
Регистрация помогает нам в сборе статистики о пользователях программы и улучшению нашей программы.
Что было нового в версии 1.3
Изменение интерфейса:
Добавлена возможность выбора типа индексации вершин.
Добавлена возможность переименовывать вершин, надписей и изменения веса дуг.
Добавлена настройка шрифта и толщины рёбер.
Улучшена форма отчётов.
Добавлены элементы меню последних файлов.
Изменён формат сохранения графов.
Изменения алгоритмов:
Исправлена ошибка при поиске радиуса.
Добавлен поиск критического пути.
Добавлен алгоритм поиска циклов.
Добавлен алгоритм поиска максимального полного подграфа.
Улучшен алгоритм проверки на планарность.
Другие улучшения:
Добавлена возможность отмены действий.
Добавлен интерфейс на английском языке.
Добавлена регистрация.
Что было нового в версии 1.2:
Изменения интерфейса:
Добавлена панель изменения матрицы смежности
Добавлен диалог задания матрицы смежности
Добавить подсказки для основных элементов управления
Добавлено возможность добавления текста.
Улучшена визуализация дуг графа
Улучшено меню программы
Изменён диалог настройки размера вершины.
Изменения алгоритмов:
Добавлен алгоритм поиска макс потока для нескольких истоков и стоков
Добавлен алгоритм проверки дерево или нет
Добавлен режим задания графа карта.
Добавлен алгоритм проверки на планетарность
Добавлена возможность преобразования графа
Улучшены алгоритмы нахождения эйлерового цикла и пути
Другие улучшения:
Добавлено возможность оставлять мнение о программе
Уменьшена нагрузка на компьютер при перемещение объектов
В файл сохранения графа также добавляется его тип
Переделать справку
Что было нового в версии 1.1:
При сохранение графа сохраняется также расположение вершин на рабочем поле.
Добавлена возможность изменять размер рабочей области.
Добавлена возможность изменять размер вершин графа.
Можно ставить фоновый рисунок на рабочую область.
Настройки программы также сохраняются в файле.
