Создание графа
С помощью данной программы можно онлайн нарисовать любой граф (ориентированный, неориентированный, с петлями), сетевой график, дерево, граф состояний или блок-схему. Во вкладке Примеры графов можно ознакомиться с возможностями онлайн сервиса.Граф можно нарисовать или задать в виде матрицы или схемы (меню Действия).
Также доступно:
- Поиск кратчайшего пути с помощью алгоритма Дейкстры, задача о кратчайшем пути (см. вкладку Параметры графа).
- Построить дерево.
- Построить дерево по коду Прюфера (затем можно будет найти его инверсию).
Размеры графического полотна
Созданный граф можно сохранить в форматах docx и png (меню Действия).
Далее можно найти характеристики графа (матрица смежности, матрица инциденций, матрица расстояний).Инструкция к сервису по рисованию графа
Чтобы соединить вершины, их необходимо предварительно выбрать (один клик мыши по объекту), а затем нажать на кнопку Соединить. Если выбрана одна вершина, то будет создана петля. У выбранных элементов (вершин или дуг) можно изменить свойства или удалить их.
Кнопка Auto выравнивает размеры полотна по содержимому.
Граф состояний кредитной карты
Здесь объектом анализа выступает такой банковский продукт как кредитная карта K. На графе состояний операций по кредитной карте отмечены следующие события: начисления процентов на остаток счета (P - петля), покупка П на сумму S, возврат CashBack в виде бонусных баллов на счет карты.
Сетевой график получения кредитной истории
1 - устройство на работу с трудовой книжкой; 2,3 - получение кредитной карты с минимальным кредитным лимитом. Некоторые банки выдают кредиты уже после 3-х месячного трудового стажа, другие банки устанавливают этот срок от 1 года; 4,5 - продвинутый уровень
, получение кредитных карт с большим cashback-ом; 6 - хорошая кредитная история, полученная с выгодой от использования кредитных карт.
Схема транспортной сети
На схеме показаны взаимное расположение пунктов, длинны звеньев, потребность грузов в развозочной системе.
Задача календарного планирования с заданной технологией
Здесь показан пример ориентированного графа
Схема канала распределения
Товар после изготовления поступает в оптовую продажу, далее доходит либо до потребителя, либо следует в розничную продажу, а затем уже к потребителю. По данной схеме работают и продуктовые рынки.
Еще один пример построения схемы классификации аннуитетных платежей можно посмотреть здесь.
Видеоинструкция
Основные определения
В математической теории графов и информатике граф представляет собой совокупность объектов со связями между ними. Граф G задается множеством точек (вершин)X={x1,…,xn} и множеством линий (ребер) A={a1,…,am}, соединяющих между собой все или часть этих точек. На данный момент в сервисе для графического отображения вершин используются следующие фигуры: круг, квадрат и треугольник. Каждая вершина может иметь собственный вид: цвет и толщина линии, фон и размеры. Для изменения характеристик вершины необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.
Ребра графа – линии, соединяющие вершины. Чтобы соединить вершины, необходимо выбрать одну или две из них. Каждое ребро графа имеет собственные свойства: цвет и толщина линии, значение (отображается поверх ребра).
Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не принимается во внимание. Ребро графа называется ориентированным, если этот порядок существенен. Ориентированное ребро называют также дугой графа. Две вершины, соединённые дугой или ребром называются смежными. Для задания дуги необходимо при соединении вершин отметить пункт концевой маркер →. Для изменения типа дуги необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.
С каждым ребром можно связать число или символ — вес ребра. Для задачи коммивояжера это может быть расстояние между городами, а для транспортной сети - стоимость проезда. Такой граф называется взвешенным.
Для каждого графа G(Х) существует обратный граф G-1(Х), полученный изменением ориентации каждого из ребер графа G(Х) на противоположную.
Петлей называется ребро g(xi,xi), у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной. Для создания петли необходимо выделить только одну вершину и нажать на кнопку Соединить.
В неизменном виде: отображается каждая дуга с весом.
Представить как неориентированные: отображается неориентированная дуга с общим весом.
Соединять в одну: две ориентированные дуги с общим весом соединяются в одну.
Область применения
Поскольку граф очень удобная математическая модель, с его помощью можно решать различные задачи из разных областей. С другой стороны, граф – это и информационная модель, с помощью его удобно представлять информацию графически. Посмотреть примеры графов можно в этом разделе.Сеть это граф, в котором вершины связаны между собой по принципу «многие ко многим».
Примером ориентированного графа являются блок-схемы алгоритмов.
Матрица Кирхгофа
На главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца (i≠j) стоит −1, если вершины с номерами i и j смежны, и 0 в противном случае.Число остовов в связном неодноэлементном обыкновенном графе G равно алгебраическому дополнению любого элемента матрицы Кирхгофа B(G). Найти алгебраическое дополнение можно здесь.
Задача о кратчайшем пути между парой вершин
Требуется найти кратчайший путь из заданной вершины s в заданную вершину d. Для этого необходимо будет выделить вершины s и d, а затем выполнить команду Разрез сети. Используется алгоритм Дейкстры (Dijkstra’s algorithm, 1959). Для более подробного решения по шагам, используйте вкладу Параметры графа.Пример. Задан обыкновенный граф с 7 вершинами и рёбрами: (1,3), (1,4), (2,6), (3,6), (4,5), (5,6), (5,7), (6,7). Вычислить и записать кратчайший путь (через 1 пробел) от вершины 1 до вершины 2.
Построение дерева
Для преобразования созданного графа в дерево (организационная диаграмма), используйте командуПреобразовать в дерево. Также можно создать дерево заново, использую следующий сервис. Для этого в каждой строке укажите вершины в формате:v1-v2. Текст к вершине задается командой v1=name.
Отображать индексы вершин
1-2 1-3 2-4 1=Директор 2=Финансовый директор 3=Бухгалтер 4=Экономистбыло нарисовано следующее дерево.
| Директор | |||||||||||||
| Финансовый директор | Бухгалтер | ||||||||||||
| Экономист | |||||||||||||
Построение дерева по коду Прюфера
Код Прюфера представляет собой последовательность вершин.Цифры кода разделяются пробелом, например 1 5 2. В некоторых случаях, дерево строится не полностью из-за особенностей работы алгоритма. В этом случае можно вручную поправить полученные вершины и нажать на кнопку Построить дерево. Чтобы получить подробное нахождение списка вершин, используйте кнопку Решение.
Пример восстановления дерева по коду Прюфера
Код: 152Число вершин в графе, n=3
Список вершин (n+2=5): 1 2 3 4 5
Шаг №1
Код Прюфера: 1 5 2
Массив вершин дерева: 1 2 3 4 5
Минимальная вершина, не содержащаяся в коде Прюфера – это 3.
Список ребер: 1 3.
Шаг №2
Код Прюфера: 1 5 2
Массив вершин дерева: 1 2 3 4 5
Минимальная вершина, не содержащаяся в коде Прюфера – это 1.
Список ребер: 1 3, 5 1.
Шаг №3
Код Прюфера: 1 5 2
Массив вершин дерева: 1 2 3 4 5
Минимальная вершина, не содержащаяся в коде Прюфера – это 4.
Список ребер: 1 3, 5 1, 2 4.
Шаг №5
Код Прюфера: 1 5 2
Массив вершин дерева: 1 2 3 4 5
Добавляем остаточные вершины: 2 5
Итого:
Список ребер: 1 3, 5 1, 2 4, 2 5
Поиск кратчайшего пути во взвешенном графе
Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом.Для отыскания всех путей выберите исходную вершину.
Для решения задач динамического программирования, условие может выглядеть так.
На данной сети дорог имеется несколько маршрутов, по которым можно доставлять груз из пункта 1 в пункт 10. Известны стоимости сij перевозки единицы груза между пунктами сети.
Требуется:
- методом динамического программирования найти за сети наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты;
- выписать оптимальные маршруты перевозки груза из всех остальных пунктов сети в пункт 10 и указать отвечающие им минимальные затраты на доставку.
Для решения необходимо задать сеть (удобнее в виде схемы через меню Действия) и отметить пункт задача о кратчайшем пути из вершины 10.
Задача о максимальном потоке
Алгоритм Форда-Фалкерсона позволяет найти максимальный поток в сети. При выполнении каждой итерации метода Форда-Фалкерсона определяется увеличивающий путь р, и поток f вдоль каждого ребра данного пути увеличивается на величину остаточной пропускной способности сf(р).Список литературы
- Кориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.
- Оре О. Теория графов. – М.: Наука, 1980. – 352 с.
- Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.
- Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.
- Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
- Кузин Л.Т. Основы кибернетики.: В 2 т. Т.2. Основы кибернетических моделей. – М.: Энергия, 1979. – 584 с.
- Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.
- Восстановление дерева по коду Прюфера