Связанные понятия
Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов...
Подробнее: Ограниченное расширение графа
При визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой) или общее число изломов на рисунке. Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величины.
Подробнее: Минимизация изломов
В визуализации графов и геометрической теории графов число наклонов графа — это минимальное возможное число различных коэффициентов наклона рёбер в рисунке графа, в котором вершины представляются точками евклидовой плоскости, а рёбрами являются отрезки, которые не проходят через вершины, неинцидентные этим рёбрам.
Подробнее: Число наклонов графа
Веер Кнастера — Куратовского — пример такого связного подмножества плоскости, удаление из которого одной точки делает его вполне несвязным.
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Говорят, что ориентированный
граф апериодичен, если нет целого числа k > 1, делящего длину любого цикла графа. Эквивалентно, граф апериодичен, если наибольший общий делитель длин его циклов равен единице. Этот наибольший общий делитель для графа G называется периодом графа G.
В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.
Блоковый многогранник — это (многомерный) многогранник, образованный из симплекса путём многократного приклеивания другого симплекса к одной из его фасет.
Гипотеза Тёплица , также известная как гипотеза о вписанном квадрате — нерешённая проблема геометрии. Формулировка гипотезы...
В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.
Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...
Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению...
Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).
Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Для ориентированного графа G термины converse (обратный), transpose (транспонированный) или reverse (противоположный) используются для обозначения другого ориентированного графа с тем же набором вершинам и с теми же дугами, но ориентация дуг этого графа противоположна ориентации дуг графа G. То есть, если граф G содержит дугу (u,v), то обратный/транспонированный/противоположный граф графу G содержит дугу (v,u) и наоборот.
Подробнее: Транспонированный граф
Преобразование треугольник-звезда — способ эквивалентного преобразования пассивного участка линейной электрической цепи — «треугольника» (соединения трёх ветвей, которое имеет вид треугольника, сторонами которого являются ветви, а вершинами — узлы), в «звезду» (соединение трёх ветвей, которые имеют один общий узел). Эквивалентность «треугольника» и «звезды» обусловлена тем, что при одинаковых напряжениях между одноименными выводами электрической цепи токи, которые втекают в одноименные выводы, а...
В математике константой
Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий). Названа в честь математика Джефа Чигера...
Теорема об обратной функции даёт достаточные условия для существования обратной функции в окрестности точки через производные от самой функции.
Неориентированный
граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно...
В теории графов
доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра).
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
В теории категорий, понятие элемента (или точки) обобщает обычное понятие элемента множества на объект произвольной категории. Иногда оно позволяет переформулировать свойства морфизмов (например, свойство мономорфизма), которые обычно описываются при помощи универсальных свойств в более привычных терминах действия отображения на элементах. Этот подход к теории категорий (и особенно его использование в лемме Йонеды) был предложен Гротендиком.
Подробнее: Элемент (теория категорий)
Важнейшими с точки зрения приложений характеристических функций к выводу асимптотических формул теории вероятностей являются две предельные теоремы — прямая и обратная. Эти теоремы устанавливают, что соответствие, существующее между функциями распределения и характеристическими функциями, не только взаимно однозначно, но и непрерывно.
Подробнее: Прямая и обратная предельная теорема
Срединный граф — граф, представляющий рёбра смежности внутри граней заданного планарного графа.
Направленное множество в математике — непустое множество A с заданным на нем рефлексивным транзитивным отношением ≤ (то есть предпорядком), обладающее дополнительным свойством: у любой пары элементов из A есть верхняя грань в A.
Симплициальная (или комбинаторная) d-сфера — это симплициальный комплекс, гомеоморфный d-мерной сфере. Некоторые симплициальные сферы появляются как границы выпуклого многогранника, однако в более высоких размерностях большинство симплициальных сфер не может быть получено таким образом.
В геометрии правильный косой многогранник — это обобщение множества правильных многогранников, которое включает возможность непланарных граней или вершинных фигур. Коксетер рассматривал косые вершинные фигуры, которые создавали новые четырёхмерные правильные многогранники, а много позднее Бранко Грюнбаум рассматривал правильные косые грани.
Алгори́тм Ка́ргера (англ. Karger's algorithm) — в информатике и теории графов является вероятностным алгоритмом, позволяющим найти минимальный разрез связного графа. Алгоритм изобретен Девидом Каргером и опубликован в 1993 году.
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
Говорят, что частичный
порядок или линейный порядок < на множестве X плотный, если для всех x и y из X, для которых выполняется x < y, существует элемент z в X, такой что x < z < y.
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
Сглаживающий сплайн (англ. smoothing spline) это метод сглаживания (аппроксимации кривой набора зашумлённых исходных данных) с использованием сплайн-функций.
В теории колец,
простой модуль (также используется название «неприводимый модуль») над кольцом R — это модуль над R, не имеющий ненулевых собственных подмодулей. Эквивалентно, модуль является простым тогда и только тогда, когда любой циклический модуль, порожденный одним его элементом (ненулевым элементом), совпадает со всем модулем. Простые модули служат для построения модулей конечной длины, в этом смысле они похожи на простые группы.
Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.
Флаг в геометрии многогранников — последовательность граней (различной размерности) абстрактного многогранника, в которой каждая предыдущая грань содержится в последующей и последовательность содержит ровно по одной грани каждой размерности.
Апейрогон (от др.-греч. ἄπειρος — бесконечный или безграничный и др.-греч. γωνία — угол) — обобщённый многоугольник со счётно-бесконечным числом сторон.
Фуксова модель — это представление гиперболической римановой поверхности R как факторповерхности верхней полуплоскости H по фуксовой группе. Любая гиперболическая риманова поверхность позволяет такое представление. Концепция названа именем Лазаря Фукса.
Слабая сходимость в функциональном анализе — вид сходимости в топологических векторных пространствах.
Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.
Полупростые модули (вполне приводимые модули) — общеалгебраические модули, которые можно легко восстановить по их частям. Кольцо, являющееся полупростым модулем над самим собой, называется артиновым полупростым кольцом. Важный пример полупростого кольца — групповое кольцо конечной группы над полем характеристики ноль. Структура полупростых колец описывается теоремой Веддербёрна — Артина: все такие кольца являются прямыми произведениями колец матриц.
Подробнее: Полупростой модуль
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
В коммутативной алгебре, дробный идеал — это обобщение понятия идеала целостного кольца, особенно полезное при изучении дедекиндовых колец. Условно говоря, дробные идеалы — это идеалы со знаменателями. В случаях, когда одновременно обсуждаются дробные и обычные идеалы, последние называют целыми идеалами.
Нормальная форма Чибрарио — нормальная форма дифференциального уравнения, не разрешённого относительно производной, в окрестности простейшей особой точки. Название предложено В. И. Арнольдом в честь итальянского математика Марии Чибрарио, установившей эту нормальную форму для одного класса уравнений.