Связанные понятия
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...
Подробнее: Граф гиперкуба
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа.
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Граф многоугольников на окружности можно задать «чередующейся последовательностью». Такую последовательность можно получить разорвав окружность в произвольном месте и перечислив вершины многоугольников, идя вдоль окружности. Такая последовательность единственна.
Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника (в размерностях 3 и выше). В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной...
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
k-Смежностный многогранник — это выпуклый многогранник, в котором любое k-элементное подмножество его вершин является множеством вершин некоторой грани этого многогранника.
Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.
Комплексный многогранник — это обобщение многогранника в вещественном пространстве на аналогичную структуру в комплексном гильбертовом пространстве, где к каждой вещественной размерности добавляется мнимая.
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
Полуикосаэдр — это абстрактный правильный многогранник, содержащий половину граней правильного икосаэдра. Он может быть реализован как проективный многогранник (мозаика проективной плоскости 10 треугольниками), который можно представить себе путём построения проективной плоскости как полусферы, противоположные точки которой вдоль границы соединены и делят полусферу на три равные части.
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба...
Подробнее: Граф Клебша
В геометрии политоп (многогранник, многоугольник или замощение, например) изогонален или вершинно транзитивен, если, грубо говоря, все его вершины эквивалентны. Отсюда следует, что все вершины окружены одним и тем же видом граней в том же самом (или обратном) порядке и с теми же самыми углами между соответствующими гранями.
Подробнее: Изогональная фигура
Многоугольник Петри для правильного многогранника в размерности n — это пространственный многоугольник, такой что любые (n-1) последовательных ребра (но не n) принадлежат одной (n-1)-мерной грани.
Хромати́ческое число ́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
В геометрии однородный многогранник — это многогранник, грани которого являются правильными многоугольниками, и он вершинно транзитивен (транзитивен относительно вершин, а также изогонален, то есть имеется движение, переводящее вершину в любую другую). Отсюда следует, что все вершины конгруэнтны, и многогранник имеет высокую степень зеркальной и вращательной симметрии.
Подробнее: Список однородных многогранников
Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви, который описал их в 1942 году.
Многогранник, двойственный (или дуальный) к заданному многограннику — многогранник, у которого каждой грани исходного многогранника соответствует вершина двойственного, каждой вершине исходного — грань двойственного и каждому ребру исходного — ребро двойственного. Многогранник, двойственный двойственному, гомотетичен исходному.
Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства. В этой ветви изучаются также погружения графов.
Символ Шлефли — комбинаторная характеристика правильного многогранника, применяется для описания правильных многогранников во всех размерностях. Назван в честь швейцарского математика Людвига Шлефли, который внёс значительный вклад в геометрию и другие области математики.
В геометрии вершина — это вид точки, в которой две кривые, две прямые либо два ребра сходятся. Из этого определения следует, что точка, в которой сходятся два луча, образуя угол, является вершиной, а также ею являются угловые точки многоугольников и многогранников.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.
Лемма Шпернера — комбинаторный аналог теоремы Брауэра о неподвижной точке, один из основных результатов комбинаторной топологии. Утверждает, что при любой Шпернеровской раскраске вершин в триангуляции n-мерного симплекса найдётся ячейка триангуляции, вершины которой покрашены во все цвета. Первый результат подобного типа был доказан Эмануэлем Шпернером.
Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.
Подробнее: Алгоритм Киркпатрика
Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.
Многогранник или полиэдр — обычно замкнутая поверхность, составленная из многоугольников, но иногда так же называют тело, ограниченное этой поверхностью.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
Многогранник Кли выпуклого многогранника P в пространстве любой размерности — это другой многогранник PK, образованный заменой каждой фасеты многогранника P невысокой пирамидой. Многогранники названы по имени американского математика Виктора Кли (Victor Klee)
Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Подробнее: Циркулянтный граф
В математике
абстрактный многогранник , неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нила Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
Теорема Грёча — это утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках, для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета. По теореме же Грёча достаточно лишь три цвета для планарных графов, которые не содержат трёх связанных друг с другом вершин.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Многогранник, многоугольник или мозаика является изотоксальным или рёберно транзитивным, если его симметрии действуют транзитивно на его рёбрах. Неформально это означает, что имеется только один вид рёбер у объекта — если даны два ребра, существует параллельный перенос, вращение и/или зеркальное отражение, переводящее одно ребро в другое, не меняя область, занимаемую объектом.
Подробнее: Изотоксальная фигура