Связанные понятия
В проективной геометрии
конфигурация на плоскости состоит из конечного множества точек и конечной конфигурации прямых, таких, что каждая точка инцидентна одному и тому же числу прямых и каждая прямая инцидентна одному и тому же числу точек.
Плоскость Фано — конечная проективная плоскость порядка 2, имеющая наименьшее возможное число точек и прямых (7 точек и 7 прямых), с тремя точками на каждой прямой и с тремя прямыми, проходящими через каждую точку. Названа по имени итальянского математика Джино Фано.
Отношение инцидентности — это бинарное отношение между двумя различными типами объектов. Это включает понятия, которые можно выразить такими фразами как «точка лежит на прямой» или «прямая принадлежит плоскости». Наиболее существенное отношение инцидентности — между точкой P и прямой l, которое записывается как P I l. Если P I l, пара (P, l) называется флагом. В разговорном языке существует много выражений, описывающих отношение инцидентности (например, прямая проходит через точку, точка лежит на...
Подробнее: Инцидентность (геометрия)
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Проективная пло́скость — двумерное проективное пространство. Важным частным случаем является вещественная проективная плоскость.
Конечная геометрия — это любая геометрическая система, имеющая конечное количество точек. Например, евклидова геометрия не является конечной, так как евклидова прямая содержит неограниченное число точек, а точнее говоря, содержит ровно столько точек, сколько существует вещественных чисел. Конечная геометрия может иметь любое конечное число измерений.
Обобщённый четырёхугольник — это структура инцидентности, главное свойство которой — отсутствие треугольников (однако структура содержит много четырёхугольников). Обобщённый четырёхугольник является по определению полярным пространством ранга два. Обобщённые четырёхугольники являются обобщёнными многоугольниками с n = 4 и почти 2n-угольниками с n = 2. Они являются также в точности частичными геометриями pg(s,t,α) с α = 1.
В математике
абстрактный многогранник , неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
n-Мерная
целочисленная решётка (или кубическая решётка), обозначается Zn, — это решётка в евклидовом пространстве Rn, точки которой являются n-кортежами целых чисел. Двумерная целочисленная решётка называется также квадратной решёткой. Zn является наиболее простым примером решётки корней. Целочисленная решётка является нечётной унимодулярной решёткой.
Симплициальный компле́кс , или симплициальное пространство, — топологическое пространство с заданной на нём триангуляцией, то есть, неформально говоря, склеенное из топологических симплексов по определённым правилам.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Проективная группа — группа преобразований проективного пространства, индуцируемых линейными преобразованиями соответствующего векторного пространства. Её элементы называются проективными преобразованиями — они обобщают проективные преобразования проективной плоскости. С матричной точки зрения проективная группа — это группа всех невырожденных матриц с точностью до скалярных матриц.
Многоугольник Петри для правильного многогранника в размерности n — это пространственный многоугольник, такой что любые (n-1) последовательных ребра (но не n) принадлежат одной (n-1)-мерной грани.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
В геометрии конфигурацией Мёбиуса — Кантора называется конфигурация, состоящая из восьми точек и восьми прямых, такая что на каждой прямой лежат по три точки и через каждую точку проходят по три прямые. Невозможно изобразить точки и прямые с этой моделью инцидентности на евклидовой плоскости, однако можно изобразить на комплексной проективной плоскости.
Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
В геометрии конфигурацией
Мёбиуса или тетраэдрами Мёбиуса называется конфигурация в евклидовом пространстве или проективном пространстве, состоящая из двух взаимно вписанных тетраэдров — каждая вершина одного тетраэдра лежит на плоскости, проходящей через грань другого тетраэдра и наоборот. Таким образом, в результирующей системе восьми точек и восьми плоскостей каждая точка лежит на четырёх плоскостях (три плоскости определяют вершину тетраэдра, а четвёртая плоскость — это плоскость, проходящая...
Нера́венство треуго́льника в геометрии, функциональном анализе и смежных дисциплинах — это одно из интуитивных свойств расстояния.
Если дано топологическое пространство и группа действий на нём, образы отдельной точки под действием группы действий образуют орбиты действий. Фундаментальная область — это подмножество пространства, которое содержит в точности по одной точке из каждой орбиты. Она даёт геометрическую реализацию абстрактного множества представителей орбит.
Подробнее: Фундаментальная область
Правильные четырёхмерные многогранники являются четырёхмерными аналогами правильных многогранников в трёхмерном пространстве и правильных многоугольников на плоскости.
Подробнее: Правильный четырёхмерный многогранник
Диэдральная группа (группа диэдра) — группа симметрии правильного многоугольника, включающая как вращения, так и осевые симметрии. Диэдральные группы являются простейшими примерами конечных групп и играют важную роль в теории групп, геометрии и химии. Хорошо известно и совершенно тривиально проверяется, что группа, образованная двумя инволюциями с конечным числом элементов в области определения является диэдральной группой.
Алгебраическая теория графов — это ветвь математики, в которой применяются алгебраические методы к задачам с графами. Другие подходы к задачам с графами — это геометрический, комбинаторный и алгоритмический. Существует три основные ветви алгебраической теории графов — две ветви используют линейную алгебру и теорию групп, а одна ветвь изучает инварианты графа.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви, который описал их в 1942 году.
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Подробнее: Циркулянтный граф
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Си́мплекс или n-мерный тетра́эдр (от лат. simplex ‘простой’) — геометрическая фигура, являющаяся n-мерным обобщением треугольника.
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Подробнее: Граф пересечений
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка {1, 2, 3, 4}, переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка, переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.
В математике свободная абелева группа (свободный Z-модуль) — это абелева группа, имеющая базис, то есть такое подмножество элементов группы, что для любого её элемента существует единственное его представление в виде линейной комбинации базисных элементов с целыми коэффициентами, из которых только конечное число являются ненулевыми. Элементы свободной абелевой группы с базисом B называют также формальными суммами над B. Свободные абелевы группы и формальные суммы используются в алгебраической топологии...
Два-граф ы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Подробнее: Мультиграф
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Подробнее: Рёберный граф
Однородные координаты ―
система координат , используемая в проективной геометрии, подобно тому, как декартовы координаты используются в евклидовой геометрии.
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)