Покрытие множества

Покры́тие в математике — семейство множеств, таких, что их объединение содержит заданное множество.

Обычно покрытия рассматривается в общей топологии, где наибольший интерес представляют открытые покрытия — семейства открытых множеств.

В комбинаторной геометрии важную роль играют покрытия выпуклыми множествами.

Источник: Википедия

Связанные понятия

Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно...

Откры́тое мно́жество — это множество, каждый элемент которого входит в него вместе с некоторой окрестностью (в метрических пространствах и, в частности, на числовой прямой). Например, внутренность шара (без границы) является открытым множеством, а шар вместе с границей - не является открытым.

В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в минимальном доминирующем множестве G.

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

Конфигурация — это разбиение d-мерного линейного, аффинного или проективного пространства на связные открытые ячейки, порождённые конечным набором геометрических объектов. Иногда эти объекты имеют один и тот же тип, такой как гиперплоскости или сферы. Интерес к изучению конфигураций вызван успехами в вычислительной геометрии, где конфигурации были объединяющими структурами для многих задач. Успехи в изучении более сложных объектов, таких как алгебраические поверхности, отвечали нуждам приложений...

Размерность Вапника — Червоненкиса или VC-размерность — это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь Владимира Вапника и Алексея Червоненкиса.

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

Если дано топологическое пространство и группа действий на нём, образы отдельной точки под действием группы действий образуют орбиты действий. Фундаментальная область — это подмножество пространства, которое содержит в точности по одной точке из каждой орбиты. Она даёт геометрическую реализацию абстрактного множества представителей орбит.

Подробнее: Фундаментальная область

Произведение топологических пространств — это топологическое пространство, полученное, как множество, декартовым произведением исходных топологических пространств, и снабжённое естественной топологией, называемой топологией произведения или тихоновской топологией. Слово «естественная» здесь употребляется в смысле теории категорий и означает, что эта топология удовлетворяет некоторому универсальному свойству.

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

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

Подробнее: Комбинаторная схема

В теории графов и комбинаторной оптимизации двудольная размерность или число бикликового покрытия графа G = (V, E) — это минимальное число биклик (то есть полных двудольных подграфов), необходимых, чтобы покрыть всё рёбра E. Набор биклик, покрывающих все рёбра в G, называется бикликовым покрытием рёбер, или просто бикликовым покрытием. Двудольная размерность графа G часто обозначается символом d(G).

Подробнее: Двудольная размерность

В геометрии подстановки плиток — это метод построения мозаик. Наиболее важно, что некоторые подстановки плиток образуют апериодические мозаики, то есть замощения, протоплитки которых не образуют какую-либо мозаику с параллельным переносом. Наиболее известные из них — мозаики Пенроуза. Подстановочные мозаики являются специальными случаями правил конечного подразделения, когда не требуется геометрическое равенство плиток.

Мно́жество — одно из ключевых понятий математики; это математический объект, сам являющийся набором, совокупностью, собранием каких-либо объектов, которые называются элементами этого множества и обладают общим для всех их характеристическим свойством. Изучением общих свойств множеств занимаются теория множеств, а также смежные разделы математики и математической логики.

В общей топологии локальная конечность является свойством семейства подмножеств топологического пространства. Это понятие является естественным обобщением понятия конечного семейства и играет ключевую роль при изучении паракомпактности и топологической размерности.

Подробнее: Локально конечное семейство подмножеств

Четырёхмерная топология — раздел топологии, который исследует топологические и гладкие четырёхмерные многообразия.

А́лгебра (от араб. الْجَبْر‎, «аль-джабр» — восполнение) — раздел математики, который можно нестрого охарактеризовать как обобщение и расширение арифметики. Слово «алгебра» также употребляется в общей алгебре в названиях различных алгебраических систем. В более широком смысле под алгеброй понимают раздел математики, посвящённый изучению операций над элементами множеств произвольной природы, обобщающий обычные операции сложения и умножения чисел.

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

Синглетон — множество с единственным элементом. Например, множество {0} является синглетоном.

В геометрии домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.

Алгебраическая комбинаторика — это область математики, использующая методы общей алгебры, в особенности теории групп и теории представлений, в различных комбинаторных контекстах и, наоборот, применяющая комбинаторные техники к задачам в алгебре.

Прямое или декартово произведение двух множеств — это множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств.

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

Гру́ппа в математике — множество, на котором определена ассоциативная бинарная операция, причём для этой операции имеется нейтральный элемент (аналог единицы для умножения), и каждый элемент множества имеет обратный. Ветвь общей алгебры, занимающаяся группами, называется теорией групп.

Алгебраическая поверхность — это алгебраическое многообразие размерности два. В случае геометрии над полем комплексных чисел алгебраическая поверхность имеет комплексную размерность два (как комплексное многообразие, если оно неособо), а потому имеет размерность четыре как гладкое многообразие.

Суперквадрики — семейство геометрических поверхностей, определяемых уравнением эллипсоида и других поверхностей второго порядка, где показатели степени 2 заменены произвольным числом. Их можно считать трёхмерными аналогами кривых Ламе (суперэллипсов).

Фракта́л (лат. fractus — дроблёный, сломанный, разбитый) — множество, обладающее свойством самоподобия (объект, в точности или приближённо совпадающий с частью себя самого, то есть целое имеет ту же форму, что и одна или более частей). В математике под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность (в смысле Минковского или Хаусдорфа), либо метрическую размерность, отличную от топологической, поэтому их следует отличать от прочих геометрических...

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

Теорема Сарда — одна из теорем математического анализа, имеющих важные приложения в теории катастроф и теории динамических систем.Названа в честь американского математика Артура Сарда.

Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.

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

Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.

Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.

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

Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.

Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.

В геометрии гипотеза Келлера — это высказанная Отт-Генрихом Келлером гипотеза о том, что в любой мозаике в евклидовом пространстве, состоящей из однинаковых гиперкубов, найдутся два куба, соприкасающиеся грань-к-грани. Например, как показано на рисунке, в любой мозаике на плоскости из одинаковых квадратов, какие-то два квадрата должны соприкасаться ребро-к-ребру. Перрон доказал, что это верно в размерностях до 6. Однако для больших размерностей это неверно, как показали Лагарис и Шор для размерностей...

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

Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.

Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.

Нерв покрытия — конструкция в топологии, дающая симплициальный комплекс по произвольному покрытию.

Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.

В математике константой Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий). Названа в честь математика Джефа Чигера...

Симплициальное множество (в ранних источниках — полусимплициальный компле́кс) — теоретико-категорная конструкция, обобщающая понятие симплициального комплекса и в определённом смысле моделирующая понятие топологического пространства с «хорошими» свойствами: теория гомотопий для симплициальных множеств эквивалентна классической теории гомотопий для топологических пространств. За счёт того, что является чисто алгебраической конструкцией, обеспечивает практически полный параллелизм с геометрическими...

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

Общая топология, или теоретико-множественная топология, — раздел топологии, в котором изучаются понятия «непрерывности» и «предела» в наиболее общем смысле.

Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в логике графов второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан Брюно Курселем в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.

Род многообразия — гомоморфизм кольца кобордизмов замкнутых многообразий в некоторое кольцо, обычно кольцо рациональных чисел.

Топологический анализ данных — новая область теоретических исследований для задач анализа данных (Data mining) и компьютерного зрения.

В математике термин матрица Картана имеет три значения. Все они названы по имени французского математика Эли Картана. Фактически, матрицы Картана в контексте алгебр Ли впервые исследовал Вильгельм Киллинг, в то время как форма Киллинга принадлежит Картану.

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я