Калькулятор теории графов
Что такое граф
Граф — одна из ключевых структур дискретной математики, которая моделирует связи между объектами. Вершины (узлы) представляют объекты, а ребра — связи между ними. Теория графов лежит в основе маршрутизации сетей, социальных сетей, GPS-навигации и множества других систем.
Основные понятия
Граф G = (V, E) состоит из множества вершин V и множества ребер E. Каждое ребро соединяет пару вершин. Степень вершины — количество инцидентных ей ребер. Путь — последовательность вершин, соединенных ребрами. Цикл — путь, начинающийся и заканчивающийся в одной вершине.
Типы графов
Неориентированный граф — ребра не имеют направления (дружба в соцсети). Ориентированный (орграф) — ребра направлены (подписки в Twitter). Взвешенный граф — каждому ребру назначен вес (расстояние между городами). Полный граф — каждая пара вершин соединена ребром.
Представление графов
Матрица смежности — квадратная таблица n x n, где a[i][j] = вес ребра (или 1/0). Занимает O(V^2) памяти, быстрая проверка наличия ребра. Список смежности — для каждой вершины хранится список соседей. Занимает O(V+E) памяти, эффективен для разреженных графов.
Сложность алгоритмов/ справочник
Сравнение временной и пространственной сложности основных алгоритмов на графах. Выбор алгоритма зависит от типа графа (разреженный или плотный), наличия отрицательных весов и конкретной задачи.
Таблица сложностей
| Алгоритм | Время | Память | Применение |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Кратчайший путь (невзвешенный) |
| DFS | O(V + E) | O(V) | Топологическая сортировка, циклы |
| Дейкстра | O((V+E) log V) | O(V) | Кратчайший путь (неотр. веса) |
| Беллман-Форд | O(V * E) | O(V) | Кратчайший путь (отрицательные веса) |
| Краскал | O(E log E) | O(V) | MST (разреженные графы) |
| Прим | O((V+E) log V) | O(V) | MST (плотные графы) |
Алгоритм Дейкстры (псевдокод)
Находит кратчайший путь от источника до всех вершин. Работает только с неотрицательными весами.
function Dijkstra(G, source):
dist[source] = 0
for each vertex v in G:
if v != source: dist[v] = INF
prev[v] = NULL
add v to Q (priority queue)
while Q is not empty:
u = vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
return dist, prevBFS (обход в ширину)
Использует очередь (FIFO). Обходит граф «уровнями» — сначала все соседи, затем соседи соседей. Гарантирует кратчайший путь в невзвешенном графе.
- + Кратчайший путь в невзвешенном графе
- + Поиск компонент связности
- + Проверка двудольности
- - Требует O(V) дополнительной памяти
DFS (обход в глубину)
Использует стек (LIFO) или рекурсию. Идет «вглубь» насколько возможно, затем возвращается. Обнаруживает циклы через обратные ребра.
- + Топологическая сортировка
- + Обнаружение циклов
- + Поиск мостов и точек сочленения
- - Не гарантирует кратчайший путь
Сравнение MST-алгоритмов
Оба алгоритма находят одно и то же минимальное остовное дерево (MST), но подходят для разных ситуаций.
Краскал
Сортирует все ребра по весу и добавляет минимальные, не создающие цикл. Использует Union-Find (система непересекающихся множеств). Лучше для разреженных графов (E близко к V).
Прим
Растет из одной вершины, на каждом шаге добавляя минимальное ребро, ведущее к новой вершине. Использует приоритетную очередь. Лучше для плотных графов (E близко к V^2).
Совет: для графов с отрицательными весами ребер используйте алгоритм Беллмана-Форда вместо Дейкстры. Дейкстра может дать неверные результаты при наличии отрицательных весов.
Практика: для невзвешенного графа не нужен Дейкстра — достаточно простого BFS, который работает за O(V+E) и гарантирует кратчайший путь по числу ребер.
Знаменитые задачи теории графов
Многие задачи теории графов имеют важное практическое значение и интересную историю. Некоторые из них до сих пор остаются открытыми или NP-трудными.
Задача коммивояжера (TSP)
NP-труднаяНайти кратчайший маршрут, проходящий через все города ровно по одному разу и возвращающийся в начальный. Точное решение требует перебора n! вариантов. На практике используются эвристики: ближайший сосед, 2-opt, генетические алгоритмы, муравьиный алгоритм.
Раскраска графа
NP-полная (для k ≥ 3)Назначить цвета вершинам так, чтобы никакие две смежные вершины не имели одинаковый цвет. Минимальное число цветов — хроматическое число. Для планарных графов достаточно четырех цветов (теорема, доказанная компьютером в 1976 году).
Максимальный поток
P (полиномиальная)Найти максимальный поток из источника в сток в сети с пропускными способностями. Решается алгоритмами Форда-Фалкерсона, Эдмондса-Карпа, Диница. Применяется в логистике, телекоммуникациях, распределении ресурсов. Связан с теоремой о максимальном потоке и минимальном разрезе.
Эйлеров и гамильтонов путь
Эйлеров — P, Гамильтонов — NP-полныйЭйлеров путь проходит по каждому ребру ровно один раз. Существует тогда и только тогда, когда не более двух вершин имеют нечетную степень. Гамильтонов путь проходит через каждую вершину ровно один раз. Проверка его существования — NP-полная задача.
Практические советы
Рекомендации по выбору алгоритмов и представления данных для решения реальных задач на графах.
1Выбор алгоритма кратчайшего пути
Для невзвешенных графов используйте BFS. Для графов с неотрицательными весами — Дейкстру. При отрицательных весах (без отрицательных циклов) — Беллмана-Форда. Для поиска кратчайших путей между всеми парами — Флойда-Уоршелла.
2Разреженные vs плотные графы
Разреженный граф (E приблизительно V) — храните списком смежности, используйте Краскала для MST. Плотный граф (E приблизительно V^2) — матрица смежности может быть эффективнее, Прим с матрицей за O(V^2). Большинство реальных графов (соцсети, дорожные) — разреженные.
3Отрицательные веса и Беллман-Форд
Алгоритм Дейкстры не работает с отрицательными весами ребер. Алгоритм Беллмана-Форда корректно обрабатывает отрицательные веса за O(V*E) и может обнаружить отрицательные циклы. Применяется в арбитраже валют и сетевой маршрутизации (RIP-протокол).
4Кратчайший путь в DAG
В направленном ациклическом графе (DAG) кратчайший путь можно найти за O(V+E): выполните топологическую сортировку, затем релаксируйте ребра в полученном порядке. Работает и с отрицательными весами. Применяется в планировании проектов (метод критического пути).
5Графовые базы данных
Neo4j, Amazon Neptune, ArangoDB хранят данные в виде графа. Запросы на языке Cypher или SPARQL выполняют обходы, поиск паттернов и вычисление метрик центральности. Идеальны для социальных сетей, рекомендательных систем, систем обнаружения мошенничества.
6Применение в реальных проектах
В коммерческих проектах графы используются для рекомендаций (Amazon, Netflix), маршрутизации (Uber, Delivery Club), анализа зависимостей (npm, pip), обнаружения мошенничества (PayPal, Сбербанк), а также в поисковых движках (PageRank Google).
Как пользоваться калькулятором
Пошаговая инструкция для работы с интерактивным редактором графов и запуска алгоритмов.
Постройте граф
Добавьте вершины и ребра вручную или загрузите один из готовых пресетов (K5, цикл, дерево, решетка). Укажите веса ребер для взвешенного графа. Перетаскивайте вершины для удобного расположения.
Выберите алгоритм
Перейдите на вкладку «Алгоритмы» и выберите нужный: Дейкстра, BFS, DFS, Краскал или Прим. Для большинства алгоритмов укажите начальную вершину.
Запустите и изучите
Нажмите «Запустить». Результаты отобразятся на графе с подсветкой ребер и вершин. Используйте пошаговый режим, чтобы проследить каждый шаг алгоритма.
Анализируйте свойства
На вкладке «Свойства графа» посмотрите характеристики: связность, двудольность, степени вершин, наличие эйлерова/гамильтонова пути, хроматическое число.
Часто задаваемые вопросы
Лиана Арифметова
Миссия: Демократизировать сложные расчеты. Превратить страх перед числами в ясность и контроль. Девиз: «Любая повторяющаяся задача заслуживает своего калькулятора».
Отказ от ответственности
Только для информационных целей. Все расчёты, результаты и данные, предоставляемые данным инструментом, носят исключительно ознакомительный и справочный характер. Они не являются профессиональной консультацией — медицинской, юридической, финансовой, инженерной или иной.
Точность результатов. Калькулятор основан на общепринятых формулах и методиках, однако фактические результаты могут отличаться в зависимости от индивидуальных условий, исходных данных и применяемых стандартов. Мы не гарантируем полноту, точность или актуальность приведённых расчётов.
Медицинские, финансовые и профессиональные решения должны приниматься исключительно на основании консультации с квалифицированными специалистами — врачом, финансовым советником, инженером или другим профессионалом в соответствующей области. Не используйте результаты данного инструмента как единственное основание для принятия важных решений.
Ограничение ответственности. Авторы и разработчики сервиса не несут никакой ответственности за прямой или косвенный ущерб, возникший в результате использования данных расчётов. Пользователь принимает на себя всю ответственность за интерпретацию и применение полученных результатов.
Похожие инструменты
Калькулятор анионного промежутка (AG)
Рассчитайте анионный промежуток по формуле Na-(Cl+HCO3). Коррекция по альбумину, дельта-дельта соотношение. Диагностика ацидоза.
Калькулятор теории относительности: время и длина
Расчет релятивистского замедления времени и сокращения длины (СТО). Лоренц-фактор, парадокс близнецов и эффекты при околосветовых скоростях.
Калькулятор обработки аудио: sample rate, сжатие, латентность, FFT, LUFS
Профессиональный калькулятор аудиообработки: размер WAV/AIFF по sample rate и bit depth, сжатие MP3/AAC/FLAC/Opus, латентность буфера ASIO/CoreAudio, конвертер частот и нот (MIDI), громкость LUFS для стриминга и оценка DSP-нагрузки (FFT).
Калькулятор амортизации кредита (график платежей)
Рассчитайте аннуитетные и дифференцированные платежи по кредиту. График погашения, переплата, досрочное погашение.
Калькулятор даты родов и срока беременности
Точный расчет даты родов (ПДР) и текущего срока беременности по дате последней менструации, дате зачатия или узи.
Калькулятор градиентов и интерполяции цветов
Генератор плавных переходов между цветами. Создайте CSS градиент онлайн, получите коды цветов (HEX/RGB) и настройте количество шагов.
Калькулятор деревьев для компенсации CO₂
Рассчитайте, сколько деревьев нужно посадить для компенсации углеродного следа. Экологический калькулятор лесовосстановления.
Калькулятор штрихкода (EAN/UPC) и упаковки
Проверка контрольной цифры штрихкодов (EAN-13, EAN-8, UPC) и расчет параметров упаковки (объем, вес).
Калькулятор площади и объёма фигур
Расчет площади, периметра, объёма и поверхности для 2D и 3D фигур. Формулы Герона, эллипсы, торы, инженерные задачи.
Калькулятор проверки гипотез (Z-test, t-test, χ², ANOVA)
Статистическая проверка гипотез онлайн. Z-тест, t-критерий Стьюдента, Хи-квадрат и дисперсионный анализ (ANOVA) с расчетом P-value.
Калькулятор гидрологии
Расчёт стока, формула Маннинга, закон Дарси, метод кривых CN, водный баланс, эвапотранспирация, паводок.
Калькулятор химии полимеров
Степень полимеризации, молекулярная масса Mn/Mw/PDI, уравнение Марка-Хаувинка, температура стеклования Tg, сополимеризация.
Ипотечный калькулятор онлайн
Рассчитать ипотеку онлайн: аннуитетные и дифференцированные платежи, досрочное погашение, график выплат.
Калькулятор таможенных пошлин и платежей
Расчёт таможенной пошлины, НДС при ввозе, таможенного сбора для юридических и физических лиц. Параллельный импорт, беспошлинный порог ЕАЭС.
Калькулятор соотношения талии к бедрам (WHR)
Рассчитайте индекс талия/бедра (WHR) для оценки типа фигуры и рисков метаболического синдрома.