Инструкция

1. Для добавления новой вершины выберите соответствующую фигуру и нажмите левой кнопкой мыши на графическом полотне.
2. Чтобы соединить вершины, их необходимо предварительно выбрать (один щелчок мыши по каждой вершине), а затем нажать на кнопку Соединить.

Создание графа

С помощью данной программы можно онлайн нарисовать любой граф (ориентированный, неориентированный, с петлями), сетевой график, дерево, граф состояний или блок-схему. Во вкладке Примеры графов можно ознакомиться с возможностями онлайн сервиса.
Граф можно нарисовать или задать в виде матрицы (меню Операции).
Нумерация вершин с №1 ?
Дуги с одинаковыми весами: ?
Выберите нужный тип вершины и нажмите левой кнопкой мыши на графическом полотне
?

Размеры графического полотна

Ширина Высота

Созданный граф можно сохранить в форматах docx и png (меню Действия).

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

Граф состояний кредитной карты

KП PSCashBack

Здесь объектом анализа выступает такой банковский продукт как кредитная карта K. На графе состояний операций по кредитной карте отмечены следующие события: начисления процентов на остаток счета (P - петля), покупка П на сумму S, возврат CashBack в виде бонусных баллов на счет карты.

Сетевой график получения кредитной истории

1 2 3 4 5 6

1 - устройство на работу с трудовой книжкой; 2,3 - получение кредитной карты с минимальным кредитным лимитом. Некоторые банки выдают кредиты уже после 3-х месячного трудового стажа, другие банки устанавливают этот срок от 1 года; 4,5 - продвинутый уровень, получение кредитных карт с большим cashback-ом; 6 - хорошая кредитная история, полученная с выгодой от использования кредитных карт.

Схема транспортной сети

3 8 10 B 159 км 134 км 190 км 67 км 81 км

На схеме показаны взаимное расположение пунктов, длинны звеньев, потребность грузов в развозочной системе.

Задача календарного планирования с заданной технологией

НачалоКонец 14,B14,A 14,C14,D 10,A10,B

Здесь показан пример ориентированного графа

Схема канала распределения

ФирмаОптовая продажа Розничная продажаПотребитель

Товар после изготовления поступает в оптовую продажу, далее доходит либо до потребителя, либо следует в розничную продажу, а затем уже к потребителю. По данной схеме работают и продуктовые рынки.

Инструкция к сервису по рисованию графа

Для добавления вершины на графическое полотно необходимо использовать соответствующую фигуре кнопку Добавить. Если название вершины не задано, будет показан ее номер. По умолчанию, нумерация начинается с номера 1. Чтобы нумерация начиналась с 0, необходимо снять отметку с пункта Нумерация вершин с №1.
Чтобы соединить вершины, их необходимо предварительно выбрать (один клик мыши по объекту), а затем нажать на кнопку Соединить. Если выбрана одна вершина, то будет создана петля. У выбранных элементов (вершин или дуг) можно изменить свойства или удалить их.
Построенный граф можно сохранить в формате docx или png.

Основные определения

В математической теории графов и информатике граф представляет собой совокупность объектов со связями между ними. Граф G задается множеством точек (вершин) X={x1,…,xn} и множеством линий (ребер) A={a1,…,am}, соединяющих между собой все или часть этих точек. На данный момент в сервисе для графического отображения вершин используются следующие фигуры: круг, квадрат и треугольник. Каждая вершина может иметь собственный вид: цвет и толщина линии, фон и размеры. Для изменения характеристик вершины необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.

Ребра графа – линии, соединяющие вершины. Чтобы соединить вершины, необходимо выбрать одну или две из них. Каждое ребро графа имеет собственные свойства: цвет и толщина линии, значение (отображается поверх ребра).

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не принимается во внимание. Ребро графа называется ориентированным, если этот порядок существенен. Ориентированное ребро называют также дугой графа. Две вершины, соединённые дугой или ребром называются смежными. Для задания дуги необходимо при соединении вершин отметить пункт концевой маркер →. Для изменения типа дуги необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.

С каждым ребром можно связать число или символ — вес ребра. Для задачи коммивояжера это может быть расстояние между городами, а для транспортной сети - стоимость проезда. Такой граф называется взвешенным.

Для каждого графа G(Х) существует обратный граф G-1(Х), полученный изменением ориентации каждого из ребер графа G(Х) на противоположную.

Петлей называется ребро g(xi,xi), у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной. Для создания петли необходимо выделить только одну вершину и нажать на кнопку Соединить.

Ребра ориентированного графа с одинаковыми весами могут быть представлены в разном виде. Для настройки отображения используйте пункт Дуги с одинаковыми весами.

В неизменном виде: отображается каждая дуга с весом.
12345372032724184120181

Представить как неориентированные: отображается неориентированная дуга с общим весом.
12345372420181

Соединять в одну: две ориентированные дуги с общим весом соединяются в одну.
12345372420181

Область применения

Поскольку граф очень удобная математическая модель, с его помощью можно решать различные задачи из разных областей. С другой стороны, граф – это и информационная модель, с помощью его удобно представлять информацию графически. Посмотреть примеры графов можно в этом разделе.

Сеть это граф, в котором вершины связаны между собой по принципу «многие ко многим».

Примером ориентированного графа являются блок-схемы алгоритмов.

Задача о кратчайшем пути между парой вершин

Требуется найти кратчайший путь из заданной вершины s в заданную вершину d. Для этого необходимо будет выделить вершины s и d, а затем выполнить команду Разрез сети. Используется алгоритм Дейкстры (Dijkstra’s algorithm, 1959). Для более подробного решения по шагам, используйте вкладу Параметры графа.

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

  1. Кориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.
  2. Оре О. Теория графов. – М.: Наука, 1980. – 352 с.
  3. Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.
  4. Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.
  5. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
  6. Кузин Л.Т. Основы кибернетики.: В 2 т. Т.2. Основы кибернетических моделей. – М.: Энергия, 1979. – 584 с.
  7. Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.
Задать вопрос или оставить комментарий Помощь в решении Поиск