Связанные понятия
В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два реберно непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров.
Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов...
Подробнее: Ограниченное расширение графа
Преобразование треугольник-звезда — способ эквивалентного преобразования пассивного участка линейной электрической цепи — «треугольника» (соединения трёх ветвей, которое имеет вид треугольника, сторонами которого являются ветви, а вершинами — узлы), в «звезду» (соединение трёх ветвей, которые имеют один общий узел). Эквивалентность «треугольника» и «звезды» обусловлена тем, что при одинаковых напряжениях между одноименными выводами электрической цепи токи, которые втекают в одноименные выводы, а...
В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.
Упоминания в литературе
Созревание ягод
и плодов происходит не одновременно у каждого вида, и сбор их проводят ежедневно или через 1…4 дня, в зависимости от погодных условий и хода созревания. При сборе необходимо избегать повреждения ягод и плодов. Особенно осторожно собирают лесную землянику, малину, чернику, ежевику, голубику.
Связанные понятия (продолжение)
Срединный граф — граф, представляющий рёбра смежности внутри граней заданного планарного графа.
Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графа. Эти задачи могут быть решены либо точно (как задача алгебраического перечисления) или асимптотически.
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок.
Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.
Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.
Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик. Тривиально совершенные графы первым изучал Волк, но название дал Голумбик. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев, древовидные графы сравнимости и квазипороговые графы...
В теории графов рёберно-транзитивным графом называется граф G такой, что для любых двух рёбер e1 и e2 графа G, существует автоморфизм графа G, который отображает e1 в e2.
Подробнее: Рёберно-транзитивный граф
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
(Топологический)
индекс Хосойи , известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.
Флаг в геометрии многогранников — последовательность граней (различной размерности) абстрактного многогранника, в которой каждая предыдущая грань содержится в последующей и последовательность содержит ровно по одной грани каждой размерности.
Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...
Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению...
В геометрии правильный косой многогранник — это обобщение множества правильных многогранников, которое включает возможность непланарных граней или вершинных фигур. Коксетер рассматривал косые вершинные фигуры, которые создавали новые четырёхмерные правильные многогранники, а много позднее Бранко Грюнбаум рассматривал правильные косые грани.
Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
В теории графов
укрытие — это определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец, чтобы выиграть игру преследование-уклонение на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти. Укрытия были впервые введены Сеймуром и Томасом как средство характеризации древесной ширины графов. Другие приложения этого понятия — доказательство существования малых сепараторов...
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
В теории графов
глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...
В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций...
Геометрический род — это базовый бирациональный инвариант pg алгебраических многообразий и комплексных многообразий.
В теории графов параллельно-последовательные графы — это графы с двумя различными вершинами, которые называются терминальными, образованные рекурсивно с помощью двух простых операций. Эти графы могут быть использованы для моделирования последовательного и параллельного соединения электрических цепей.
Подробнее: Параллельно-последовательный граф
Вну́тренность множества в общей топологии — это совокупность всех внутренних точек. Обычно обозначается Int, вероятно, от англ. Interior. Иногда внутренность множества называют ядром.
Апейрогон (от др.-греч. ἄπειρος — бесконечный или безграничный и др.-греч. γωνία — угол) — обобщённый многоугольник со счётно-бесконечным числом сторон.
В теории графов древесная декомпозиция — это отображение графа в дерево, которое может быть использовано для определения древесной ширины графа и ускорения решения определённых вычислительных задач на графах.
В математике константой
Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий). Названа в честь математика Джефа Чигера...
Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Многогранник, многоугольник или мозаика является изотоксальным или рёберно транзитивным, если его симметрии действуют транзитивно на его рёбрах. Неформально это означает, что имеется только один вид рёбер у объекта — если даны два ребра, существует параллельный перенос, вращение и/или зеркальное отражение, переводящее одно ребро в другое, не меняя область, занимаемую объектом.
Подробнее: Изотоксальная фигура
Гусеница или гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии 1 от центрального пути.
Направленное множество в математике — непустое множество A с заданным на нем рефлексивным транзитивным отношением ≤ (то есть предпорядком), обладающее дополнительным свойством: у любой пары элементов из A есть верхняя грань в A.
В общей алгебре,
поле k называется совершенным если выполняется одно из следующих эквивалентных условий...
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
Единичный отрезок — величина, принимаемая за единицу при геометрических построениях. При изображении декартовой системы координат, единичный отрезок обычно отмечается на каждой из осей.
Блоковый граф (кликовое дерево) — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
Дискре́тное простра́нство в общей топологии и смежных областях математики — это пространство, все точки которого изолированы друг от друга в некотором смысле.