Дискретная математика

Калькулятор теории графов

Интерактивный редактор графов с визуализацией алгоритмов. Кратчайший путь (Дейкстра), обходы BFS/DFS, минимальное остовное дерево (Краскал, Прим) и анализ свойств графа.

Ориентированный

Добавить вершину

Добавить ребро

1736

Эйлер, Кёнигсберг

Год рождения теории графов

O(V+E)

BFS / DFS

Линейная сложность обхода

O(E log V)

Дейкстра

С двоичной кучей

Цвета достаточно

Теорема о четырех красках для планарных графов

Что такое граф

Граф — одна из ключевых структур дискретной математики, которая моделирует связи между объектами. Вершины (узлы) представляют объекты, а ребра — связи между ними. Теория графов лежит в основе маршрутизации сетей, социальных сетей, GPS-навигации и множества других систем.

📊

Основные понятия

Граф G = (V, E) состоит из множества вершин V и множества ребер E. Каждое ребро соединяет пару вершин. Степень вершины — количество инцидентных ей ребер. Путь — последовательность вершин, соединенных ребрами. Цикл — путь, начинающийся и заканчивающийся в одной вершине.

➡️

Типы графов

Неориентированный граф — ребра не имеют направления (дружба в соцсети). Ориентированный (орграф) — ребра направлены (подписки в Telegram). Взвешенный граф — каждому ребру назначен вес (расстояние между городами). Полный граф — каждая пара вершин соединена ребром.

📝

Представление графов

Матрица смежности — квадратная таблица 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, prev

BFS (обход в ширину)

Использует очередь (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Применение в реальных проектах

В коммерческих проектах графы используются для рекомендаций (Яндекс.Маркет, Кинопоиск), маршрутизации (Яндекс.Такси, Delivery Club), анализа зависимостей (npm, pip), обнаружения мошенничества (Сбербанк, Тинькофф), а также в поисковых движках (PageRank Яндекса и Google).

Как пользоваться калькулятором

Пошаговая инструкция для работы с интерактивным редактором графов и запуска алгоритмов.

Постройте граф

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

Выберите алгоритм

Перейдите на вкладку «Алгоритмы» и выберите нужный: Дейкстра, BFS, DFS, Краскал или Прим. Для большинства алгоритмов укажите начальную вершину.

Запустите и изучите

Нажмите «Запустить». Результаты отобразятся на графе с подсветкой ребер и вершин. Используйте пошаговый режим, чтобы проследить каждый шаг алгоритма.

Анализируйте свойства

На вкладке «Свойства графа» посмотрите характеристики: связность, двудольность, степени вершин, наличие эйлерова/гамильтонова пути, хроматическое число.

ЧАСТЫЕ ВОПРОСЫ

Часто задаваемые вопросы

Граф — это математическая структура, состоящая из множества вершин (узлов) и множества ребер (связей между вершинами). Формально граф G = (V, E), где V — множество вершин, E — множество ребер. Граф моделирует попарные связи между объектами: города и дороги, люди и знакомства, компьютеры и каналы связи.

В неориентированном графе ребро {u, v} не имеет направления — связь работает в обе стороны (дружба в VK). В ориентированном графе (орграфе) ребро (u, v) имеет направление от u к v (подписка в Telegram: вы подписаны, но на вас не обязательно). У вершин орграфа есть входящая и исходящая степень.

Алгоритм Дейкстры находит кратчайшие пути от одной вершины-источника до всех остальных. Он работает жадно: на каждом шаге выбирает непосещенную вершину с минимальным текущим расстоянием, отмечает её посещенной и обновляет расстояния до её соседей (релаксация). С приоритетной очередью (бинарной кучей) работает за O((V+E) log V). Требует неотрицательных весов.

BFS (обход в ширину) находит кратчайший путь в невзвешенном графе за O(V+E) — все ребра имеют одинаковый «вес». Если ребра имеют разные неотрицательные веса, необходим алгоритм Дейкстры. При отрицательных весах — Беллман-Форд. BFS проще в реализации и быстрее на невзвешенных графах.

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

Оба находят MST, но работают по-разному. Краскал: сортирует все ребра по весу и добавляет минимальные, не создающие цикл (Union-Find). Лучше для разреженных графов, O(E log E). Прим: растет из одной вершины, добавляя минимальное ребро к новой вершине (приоритетная очередь). Лучше для плотных графов, O((V+E) log V) или O(V^2) с массивом.

Матрица смежности — двумерный массив n×n, где элемент a[i][j] содержит вес ребра или 0/1. Занимает O(V^2) памяти, проверка ребра за O(1). Список смежности — массив списков, где для каждой вершины хранятся её соседи. Занимает O(V+E) памяти, обход соседей за O(degree). Список смежности предпочтительнее для разреженных графов (большинство реальных).

Эйлеров путь проходит по каждому ребру графа ровно один раз. Существует, если не более двух вершин имеют нечетную степень. Эйлеров цикл (замкнутый путь) — если все вершины имеют четную степень. Проверка и нахождение — за O(E). Гамильтонов путь проходит через каждую вершину ровно один раз. Проверка существования — NP-полная задача (нет известного полиномиального алгоритма).

Граф двудольный, если его вершины можно разбить на два множества так, что все ребра идут между множествами (нет ребер внутри одного множества). Эквивалентно: граф не содержит циклов нечетной длины. Проверяется за O(V+E) с помощью BFS или DFS: пытаемся «раскрасить» граф в два цвета. Если встречаем конфликт — граф не двудольный.

Хроматическое число χ(G) — минимальное число цветов, необходимое для правильной раскраски графа (смежные вершины имеют разные цвета). Нахождение точного значения — NP-трудная задача. Жадный алгоритм дает верхнюю оценку. Для планарных графов χ ≤ 4 (теорема о четырех красках). Для полного графа K_n хроматическое число равно n.

Неориентированный граф связный, если существует путь между любой парой вершин. Если граф не связный, он распадается на компоненты связности — максимальные связные подграфы. Для ориентированных графов различают сильную связность (путь есть в обоих направлениях) и слабую (связный при игнорировании направлений). Проверка — BFS или DFS за O(V+E).

Калькулятор оптимизирован для учебных и демонстрационных целей — графов до 20-30 вершин. Для больших графов (тысячи и миллионы вершин) рекомендуются специализированные библиотеки: NetworkX (Python), JGraphT (Java), igraph (C/Python/R), а также графовые базы данных Neo4j и Amazon Neptune.

Был ли этот калькулятор полезен?

ревизия · 9 мая 2026

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ

Инструмент справочный — не заменяет эксперта

Только для информационных целей. Все расчёты, результаты и данные, предоставляемые инструментом, носят исключительно ознакомительный и справочный характер. Они не являются профессиональной консультацией — медицинской, юридической, финансовой, инженерной или иной.

Точность результатов. Калькулятор основан на общепринятых формулах и методиках, однако фактические результаты могут отличаться в зависимости от индивидуальных условий, исходных данных и применяемых стандартов. Мы не гарантируем полноту, точность или актуальность приведённых расчётов.

Профессиональные решения — медицинские, финансовые, инженерные — должны приниматься только после консультации с квалифицированным специалистом. Не используйте автоматический расчёт как единственное основание для важных решений.

Ограничение ответственности. Авторы и разработчики сервиса не несут ответственности за прямой или косвенный ущерб, возникший из-за использования данных расчётов. Пользователь принимает на себя всю ответственность за интерпретацию результатов.

СМЕЖНЫЕ ИНСТРУМЕНТЫ

Калькулятор теории графов

Добавить вершину

Добавить ребро

Что такое граф

Основные понятия

Типы графов

Представление графов

Сложность алгоритмов/ справочник

Таблица сложностей

Алгоритм Дейкстры (псевдокод)

BFS (обход в ширину)

DFS (обход в глубину)

Сравнение MST-алгоритмов

Знаменитые задачи теории графов

Задача коммивояжера (TSP)

Раскраска графа

Максимальный поток

Эйлеров и гамильтонов путь

Практические советы

1Выбор алгоритма кратчайшего пути

2Разреженные vs плотные графы

3Отрицательные веса и Беллман-Форд

4Кратчайший путь в DAG

5Графовые базы данных

6Применение в реальных проектах

Как пользоваться калькулятором

Постройте граф

Выберите алгоритм

Запустите и изучите

Анализируйте свойства

Часто задаваемые вопросы

Лиана Арифметова

Инструмент справочный — не заменяет эксперта

Похожие калькуляторы

Калькулятор тригонометрии

Калькулятор оптимизации: симплекс, рюкзак, генетика

Калькулятор дробей (смешанные и неправильные)

Калькулятор НОД и НОК

Калькулятор матриц

Калькулятор комбинаторики

Калькулятор комплексных чисел

Калькулятор производных и интегралов

Калькулятор чисел Фибоначчи

Калькулятор золотого сечения

Калькулятор сумм рядов

Калькулятор Монте-Карло симуляции: оценка рисков

Калькулятор процентов

Калькулятор научной нотации

Калькулятор интерполяции (Лагранж, сплайн)

Добавить вершину

Добавить ребро