Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра, метрическая задача коммивояжёра, симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Алгоритм Краскала, также алгоритм Крускала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера.
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
Алгори́тм Бору́вки — это алгоритм нахождения минимального остовного дерева в графе.
Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Задача получила своё название в честь Якоба Штейнера (1796—1863).
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
В теории графов псевдолес — это неориентированный граф, в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Наименьший разрез графа — это минимальный в некотором смысле разрез.
Алгоритм для дерева сочленений — это метод, используемый в машинном обучении для извлечения маргинализации в графах общего вида. В сущности, алгоритм осуществляет распространение доверия на модифицированном графе, называемом деревом сочленений. Основная посылка алгоритма — исключить циклы путём кластеризации их в узлы.
Евклидово минимальное остовное дерево — это минимальное остовное дерево набора из n точек на плоскости, где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам.
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа. Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути. Однако во многих случаях возможны более быстрые алгоритмы.
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня . Задача является ориентированным аналогом задачи о минимальном остовном дереве.
Алгоритм обратного удаления — это алгоритм в теории графов, использующийся для получения минимального остовного дерева из данного связного рёберно взвешенного графа. Впервые алгоритм появился в статье Краскала, но не следует его путать с алгоритмом Краскала, который появился в той же статье. Если граф не связен, этот алгоритм найдёт минимальное остовное дерево для каждой отдельной части графа. Множество этих минимальных остовных деревьев называется минимальным остовным лесом, который содержит все вершины графа.
Алгоритм Суурбалле — это алгоритм нахождения двух непересекающихся путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длину.
Минимально критичное остовное дерево во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево.
Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство . Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976, и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев.
Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети.
Примене́ние тео́рии гра́фов — использование теории графов как математического орудия в различных дисциплинах.
