Связанные понятия
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно...
Экспандер ы — это класс графов, изучение которых первыми начали московские математики М. С. Пинскер, Л. А. Бассалыго и Г. А. Маргулис в семидесятые годы XX века.
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Симплициальный компле́кс , или симплициальное пространство, — топологическое пространство с заданной на нём триангуляцией, то есть, неформально говоря, склеенное из топологических симплексов по определённым правилам.
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Подробнее: Циркулянтный граф
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Проективная группа — группа преобразований проективного пространства, индуцируемых линейными преобразованиями соответствующего векторного пространства. Её элементы называются проективными преобразованиями — они обобщают проективные преобразования проективной плоскости. С матричной точки зрения проективная группа — это группа всех невырожденных матриц с точностью до скалярных матриц.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение...
Систе́ма корне́й (корнева́я систе́ма) в математике — конфигурация векторов в евклидовом пространстве, удовлетворяющая определённым геометрическим свойствам.
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.
Подробнее: Компонента сильной связности в орграфе
n-Мерная
целочисленная решётка (или кубическая решётка), обозначается Zn, — это решётка в евклидовом пространстве Rn, точки которой являются n-кортежами целых чисел. Двумерная целочисленная решётка называется также квадратной решёткой. Zn является наиболее простым примером решётки корней. Целочисленная решётка является нечётной унимодулярной решёткой.
В теории графов графами Пэли (названы в честь Раймонда Пэли) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства...
Подробнее: Граф Пэли
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
Плоскость Фано — конечная проективная плоскость порядка 2, имеющая наименьшее возможное число точек и прямых (7 точек и 7 прямых), с тремя точками на каждой прямой и с тремя прямыми, проходящими через каждую точку. Названа по имени итальянского математика Джино Фано.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
В общей алгебре, термин кручение относится к элементам группы, имеющим конечный порядок, или к элементам модуля, аннулируемым регулярным элементом кольца.
Подробнее: Кручение (алгебра)
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Если дано топологическое пространство и группа действий на нём, образы отдельной точки под действием группы действий образуют орбиты действий. Фундаментальная область — это подмножество пространства, которое содержит в точности по одной точке из каждой орбиты. Она даёт геометрическую реализацию абстрактного множества представителей орбит.
Подробнее: Фундаментальная область
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов.
Конечная геометрия — это любая геометрическая система, имеющая конечное количество точек. Например, евклидова геометрия не является конечной, так как евклидова прямая содержит неограниченное число точек, а точнее говоря, содержит ровно столько точек, сколько существует вещественных чисел. Конечная геометрия может иметь любое конечное число измерений.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Коммутант в общей алгебре — подсистема алгебр, содержащих групповую структуру (подгруппа, подкольцо, в наиболее общем случае — подгруппа мультиоператорной группы), показывающая степень некоммутативности групповой операции.
Алгебраическая комбинаторика — это область математики, использующая методы общей алгебры, в особенности теории групп и теории представлений, в различных комбинаторных контекстах и, наоборот, применяющая комбинаторные техники к задачам в алгебре.
В математическом анализе, и прилегающих разделах математики, ограниченное множество — множество, которое в определенном смысле имеет конечный размер. Базовым является понятие ограниченности числового множества, которое обобщается на случай произвольного метрического пространства, а также на случай произвольного частично упорядоченного множества. Понятие ограниченности множества не имеет смысла в общих топологических пространствах, без метрики.
Подробнее: Ограниченное множество
В теории графов
глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...
Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски...
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Обобщённый четырёхугольник — это структура инцидентности, главное свойство которой — отсутствие треугольников (однако структура содержит много четырёхугольников). Обобщённый четырёхугольник является по определению полярным пространством ранга два. Обобщённые четырёхугольники являются обобщёнными многоугольниками с n = 4 и почти 2n-угольниками с n = 2. Они являются также в точности частичными геометриями pg(s,t,α) с α = 1.
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
В математике свободная абелева группа (свободный Z-модуль) — это абелева группа, имеющая базис, то есть такое подмножество элементов группы, что для любого её элемента существует единственное его представление в виде линейной комбинации базисных элементов с целыми коэффициентами, из которых только конечное число являются ненулевыми. Элементы свободной абелевой группы с базисом B называют также формальными суммами над B. Свободные абелевы группы и формальные суммы используются в алгебраической топологии...
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Произведение топологических пространств — это топологическое пространство, полученное, как множество, декартовым произведением исходных топологических пространств, и снабжённое естественной топологией, называемой топологией произведения или тихоновской топологией. Слово «естественная» здесь употребляется в смысле теории категорий и означает, что эта топология удовлетворяет некоторому универсальному свойству.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной...
Группа классов идеалов дедекиндова кольца — это, грубо говоря, группа, позволяющая сказать, насколько сильно в данном кольце нарушается свойство факториальности. Эта группа тривиальна тогда и только тогда, когда дедекиндово кольцо является факториальным. Свойства дедекиндова кольца, касающиеся умножения его элементов, тесно связаны с устройством этой группы.
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Подробнее: Мультиграф