Ядро (теория графов)

Ядро графа — это понятие, описывающее поведение графа в отношении гомоморфизмов графа.

Определение

Граф $C$ является ядром, если любой гомоморфизм $f:C\to C$ является изоморфизмом, то есть это биекция вершин $C$ .

Ядро графа $G$ — это граф $C$ , такой, что

существует гомоморфизм из $G$ в $C$
существует гомоморфизм из $C$ в $G$
с этими свойствами граф $C$ минимален.

Говорят, что два графа гомоморфно эквивалентны, если они обладают изоморфными ядрами.

Ядро графа, если оно существует, является одновременно минимальным внешне и максимальным внутренне устойчивым множеством ее вершин.^[1]

Примеры

Любой полный граф является ядром.
Цикл нечётного порядка является своим же ядром.
Любые два цикла чётного порядка, и более обще, любые два двудольных графа гомоморфно эквивалентны. Ядром любого такого графа является граф K₂.
Ядро графа, представляющего задачу потребительского выбора, является решением задачи выбора по Нейману-Моргенштерну.^[1]
Если граф не содержит циклов, а множество предпочтений транзитивно, то ядро такого графа дает множество недоминируемых альтернатив.^[1]

Свойства

Любой граф имеет единственное (с точностью до изоморфизма) ядро. Ядро графа G всегда является порождённым подграфом графа G. Если $G\to H$ и $H\to G$ , то графы $G$ и $H$ обязательно гомоморфно эквивалентны.

Вычислительная сложность

Задача проверки, имеет ли граф гомоморфизм в собственный подграф, является NP-полной, и ко-NP-полной задачей является проверка, является ли граф своим собственным ядром (то есть что не существует гомоморфизмов в собственные подграфы)^[2].

Примечания

↑ ¹ ² ³ 15. 3. Внутренняя устойчивость (рус.). StudFiles. Дата обращения: 27 февраля 2024.
↑ Hell, Nešetřil, 1992.

Литература

Chris Godsil, Gordon Royle. Chapter 6 section 2 // Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics). — ISBN 0-387-95241-1.
Pavol Hell, Jaroslav Nešetřil. The core of a graph // Discrete Mathematics. — 1992. — Т. 109, вып. 1-3. — С. 117–126. — doi:10.1016/0012-365X(92)90282-K.
Jaroslav Nešetřil, Patrice Ossona de Mendez. Proposition 3.5 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — С. 43. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4..

Похожие исследовательские статьи

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.

В теории графов изоморфизмом графов $\text{[math]}$ и $\text{[math]}$ называется биекция между множествами вершин графов $\text{[math]}$ такая, что любые две вершины $\text{[math]}$ и $\text{[math]}$ графа $\text{[math]}$ смежны тогда и только тогда, когда вершины $\text{[math]}$ и $\text{[math]}$ смежны в графе $\text{[math]}$ . Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как $\text{[math]}$ .

Пло́тный граф — граф, в котором число рёбер $\text{[math]}$ близко к максимально возможному у полного графа с числом вершин $\text{[math]}$ :

В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.

Базис циклов неориентированного графа — множество простых циклов, которые образуют базис пространства циклов графа. Таким образом, это минимальный набор циклов, который позволяет любой эйлеров подграф представить как симметрическую разность базисных циклов.

Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом.

Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина графа — наименьшее число полуплоскостей для всех книжных вложений графа. Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницы и книжное число скрещиваний.

Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

Минор в теории графов — граф $\text{[math]}$ для заданного графа $\text{[math]}$ , который может быть образован из $\text{[math]}$ удалением рёбер и вершин и стягиванием рёбер.

В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков. Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды.

Два графа $\text{[math]}$ и $\text{[math]}$ гомеоморфны, если существует изоморфизм некоторого подразделения графа $\text{[math]}$ и некоторого подразделения графа $\text{[math]}$ . Если рёбра графа понимать как отрезки, соединяющие вершины, то два графа гомеоморфны в контексте теории графов, когда они гомеоморфны в топологическом смысле.

Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.

Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H. Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.

Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа.

Факторграф Q графа G — граф, вершины которого являются блоками разбиения вершин графа G, а блок B смежен блоку C, если некоторая вершина в B смежна некоторой вершине в C. Другими словами, если G имеет набор рёбер E и набор вершин V и R является отношением эквивалентности, порождённым разбиением, то факторграф имеет набор вершин V/R и набор рёбер $\text{[math]}$ .

Косое разбиение графа — разбиение его вершин на два подмножества в виде несвязного порождённого подграфа и дополнения; играет важную роль в теории совершенных графов.

Пространство циклов неориентированного графа — линейное пространство над полем $\text{[math]}$ , состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.