Связанные понятия
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Задача Вебера обобщает поиск геометрической медианы, для которой цены перевозок полагаются равными для всех точек потребления, и задачу нахождения точки Ферма, геометрической медианы трёх точек. По этой причине задачу иногда называют задачей Ферма – Вебера, хотя то же самое имя используется и для задачи нахождения невзвешенной геометрической медианы. Задача Вебера, в свою очередь, обобщается задачей притяжения – отталкивания, которая позволяет отрицательные цены, так что для некоторых точек большее...
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Голигон — это любой многоугольник, в котором все углы прямые, а длины сторон являются последовательными целыми числами (от 1 до n). Голигоны придумал (и дал им название) Ли Сэллоус, а популяризовал Александр Дьюдени в колонке 1990 года в журнале Scientific American . Вариации определения голигонов позволяют сторонам пересекаться, иметь в качестве длин сторон любые целые числа (не обязательно последовательные) и иметь углы, отличные от 90°.
Геометрический центр дискретного множества точек евклидова пространства (говоря статистическим языком — выборки) — это точка, в которой минимизируется сумма расстояний до точек множества. Геометрический центр обобщает медиану в математической статистике, которая минимизирует расстояния в одномерной выборке данных. Таким образом, геометрический центр отражает центральную тенденцию в пространствах высокой размерности. Понятие известно также по названиям 1-медиана , пространственная медиана, или точка...
Контактное число (иногда число Ньютона, в химии соответствует координационному числу) — максимальное количество шаров единичного радиуса, которые могут одновременно касаться одного такого же шара в n-мерном евклидовом пространстве (предполагается, что шары не проникают друг в друга, то есть объём пересечения любых двух шаров равен нулю).
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Подробнее: Задача о принадлежности точки многоугольнику
Пло́щадь — численная характеристика двумерной (плоской или искривлённой) геометрической фигуры, неформально говоря, показывающая размер этой фигуры. Исторически вычисление площади называлось квадратурой. Фигура, имеющая площадь, называется квадрируемой. Конкретное значение площади для простых фигур однозначно вытекает из предъявляемых к этому понятию практически важных требований (см. ниже). Фигуры с одинаковой площадью называются равновеликими.
Алгоритм Гилберта — Джонсона — Кёрти (англ. Gilbert — Johnson — Keerthi algorithm, сокращённо GJK) — алгоритм для определения минимального расстояния между двумя выпуклыми множествами (объектами). В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом (с помощью итераций) генерирует ближайшие симплексы для корректного...
Решение треугольников (лат. solutio triangulorum) — исторический термин, означающий решение главной тригонометрической задачи: по известным данным о треугольнике (стороны, углы и т. д.) найти остальные его характеристики. Существуют также обобщения этой задачи на случай, когда заданы другие элементы треугольника (например, медианы, биссектрисы, высоты, площадь и т. д.). Треугольник может располагаться на плоскости или на сфере. Данная задача часто встречается в тригонометрических приложениях, например...
В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.
Подробнее: Медианный граф
Гипотеза Хивуда , или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....
В геометрии гипотеза Келлера — это высказанная Отт-Генрихом Келлером гипотеза о том, что в любой мозаике в евклидовом пространстве, состоящей из однинаковых гиперкубов, найдутся два куба, соприкасающиеся грань-к-грани. Например, как показано на рисунке, в любой мозаике на плоскости из одинаковых квадратов, какие-то два квадрата должны соприкасаться ребро-к-ребру. Перрон доказал, что это верно в размерностях до 6. Однако для больших размерностей это неверно, как показали Лагарис и Шор для размерностей...
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.
Теорема Бека — это один из нескольких результатов комбинаторной геометрии, два из которых приведены ниже.
Приближение с помощью кривых — это процесс построения кривой или математической функции, которая наилучшим образом приближается к заданным точкам с возможными ограничениями на кривую . Для построения такого приближения может использоваться либо интерполяция , где требуется точное прохождение кривой через точки, либо сглаживание, когда «сглаживающая» функция проходит через точки приближённо. Связанный раздел — регрессионный анализ, который фокусируется, главным образом, на вопросах статистического...
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
Полимино , или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами.
Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы...
Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.
Зада́ча о кратча́йшем пути ́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
Теорема об уголках — доказанный результат в области аддитивной комбинаторики, утверждающий присутствие некой упорядоченной (в арифметическом смысле) структуры, называемой уголком, в достаточно больших двумерных множествах любой фиксированной плотности.
Задача о наибольшем пустом прямоугольнике или задача о максимальном пустом прямоугольнике — это задача поиска прямоугольника максимального размера, который следует разместить среди препятствий на плоскости. Существует несколько вариантов задачи, в зависимости от особенностей формулировки, в частности, от способов измерения «размера», области (типы препятствий) и ориентации прямоугольника.
Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в логике графов второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан Брюно Курселем в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.
Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом...
Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение...
Метод неделимых — возникшее в конце XVI века наименование совокупности приёмов, предназначенных для вычисления площадей геометрических фигур или объёмов геометрических тел.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Эта математика изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Окружности Мальфатти — три окружности внутри заданного треугольника, такие, что каждая окружность касается двух других и двух сторон треугольника. Окружности названы именем Джанфранческо Мальфатти, который начал исследовать задачу построения этих окружностей с ошибочным убеждением, что они в сумме дают максимальную возможную площадь трёх непересекающихся окружностей внутри треугольника. Задача Мальфатти относится к обеим задачам — как к построению окружностей Мальфатти, так и к задаче нахождения...
Задача трёх тел (в астрономии) — одна из задач небесной механики, состоящая в определении относительного движения трёх тел (материальных точек), взаимодействующих по закону тяготения Ньютона (например, Солнца, Земли и Луны). В отличие от задачи двух тел, в общем случае задача не имеет решения в виде конечных аналитических выражений. Известно лишь несколько точных решений для специальных начальных скоростей и координат объектов.
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Интегральное исчисление — раздел математического анализа, в котором изучаются понятия интеграла, его свойства и методы вычислений.
Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определеиня наилучшего расположения охраны в картинных галереях.
Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
В проективной геометрии
конфигурация на плоскости состоит из конечного множества точек и конечной конфигурации прямых, таких, что каждая точка инцидентна одному и тому же числу прямых и каждая прямая инцидентна одному и тому же числу точек.