Онлайн редактор графов

Обзор сервиса "Онлайн редактор графов" для педагогов. Пригодится при подготовке к урокам вероятности и статистики, например, в 10 классе.

Онлайн редактор графов и его интерфейс

С 2021 года работает онлайн редактор графов. Он позволяет создавать графическое представление набора объектов, где некоторые пары объектов соединены связями. 

Как только вы открыли редактор перед вами появляется меню управления и поле для рисунка.

Поле имеет сетку (при желании её можно отключить с помощью сочетания клавиш Ctrl+G), для более удобного выравнивания вершин. С помощью меню (можно свернуть с помощью сочетания Ctrl+M) вы можете добавлять элементы графа, выполнять сохранения и загрузку получившегося графа и выполнять пошаговые алгоритмы с вашим рисунком.

Редактор хранит историю всех выполненных действий, так что в случае ошибки можно отменить последние действия с помощью сочетания клавиш Ctrl+Z. Чтобы повторить отменённое действие, достаточно нажать сочетание Ctrl+Y.

Построение и изменение графа

Само собой вы можете добавлять основные элементы: вершины, рёбра и их редактировать.

Более подробно можно узнать в инструкции, которая открывается прямо при запуске самого сервиса.

Сохранение графа

Редактор позволяет сохранить граф в одном из следующих форматов:

• .graph — собственный формат редактора, по своей природе являющийся JSON'ом
• .png — растровое изображения, качество напрямую зависит от текущего масштаба редактора.
• .svg — векторное изображение
• .dot — распространённый текстовый формат, наиболее известный благодаря редактору graphviz
• .tgf — самый простой текстовый формат
• .graphml — основанный на XML формат хранения графов

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

Примеры графов

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

Можно сгенерировать случайный граф.

Алгоритмы на графах

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

• Алгоритмы обхода графа
  • в глубину (DFS)
  • в ширину (BFS)
• Поиск путей
  • алгоритм Дейкстры (кратчайший путь от одной вершины до всех остальных)
  • алгоритм Беллмана-Форда (кратчайший путь от одной вершины до всех остальных, допускает рёбра отрицательного веса)
  • алгоритм Флойда-Уоршелла (кратчайшие пути между всеми парами вершин)
  • поиск всех возможный путей между парой вершин
• Размещение графа (перемещение вершин для придания более эстетического вида)
  • силовой алгоритм Фрюхтермана-Рейнгольда
  • энергетический алгоритм Камада-Кавай
• Построение минимального остовного дерева
  • алгоритм Прима
  • алгоритм Краскала
• Связность
  • компоненты слабой связности
  • компоненты сильной связности
  • поиск точек сочленения
  • поиск мостов
• Нахождение максимального потока
  • алгоритм проталкивания предпотока
  • алгоритм Диница
• Прочее
  • Эйлеров путь
  • Эйлеров цикл
  • Гамильтонов цикл
  • поиск любого цикла
  • разбиение на две доли
  • проверка двух графов на изоморфизм
  • центр, радиус и диаметр
  • топологическая сортировка
  • раскраска
  • расчёт степеней вершин