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

Подграф, состоящий из всех узлов, связанных с данным узлом графа.

В этом графе вершины, смежные с 5, — это 1, 2 и 4. Окрестность 5 — это граф, состоящий из вершин 1, 2, 4 и ребра, соединяющего 1 и 2.

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

Окрестность часто обозначается ⁠ ⁠ ${\displaystyle N_{G}(v)}$ или (когда граф однозначен) ⁠ ⁠ ${\displaystyle N(v)}$ . Та же самая нотация соседства может также использоваться для обозначения множеств смежных вершин, а не соответствующих индуцированных подграфов. Описанная выше окрестность не включает в себя v и, более конкретно, является открытой окрестностью v ; также можно определить окрестность, в которую включена сама v , называемую закрытой окрестностью и обозначаемую ⁠ ⁠ . При указании без каких-либо уточнений предполагается, что окрестность является открытой. ${\displaystyle N_{G}[v]}$

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

Изолированная вершина не имеет смежных вершин. Степень вершины равна числу смежных вершин. Особый случай — петля , соединяющая вершину с собой; если такое ребро существует, вершина принадлежит своей собственной окрестности.

Локальные свойства в графиках

В графе октаэдра окрестность любой вершины представляет собой 4- цикл .

Если все вершины в G имеют окрестности, которые изоморфны одному и тому же графу H , то говорят, что G локально H , а если все вершины в G имеют окрестности, которые принадлежат некоторому семейству графов F , то говорят, что G локально F. ^[1] Например, в графе октаэдра , показанном на рисунке, каждая вершина имеет окрестность, изоморфную циклу из четырех вершин, _{поэтому} октаэдр локально  C4 .

Например:

• Любой полный граф K _n локально есть K _n-1 . Единственными графами, которые локально полны, являются несвязные объединения полных графов.
• Граф Турана T ( rs , r ) локально является графом T (( r -1) s , r -1). В более общем случае любой граф Турана локально является графом Турана.
• Каждый планарный граф локально внешнепланарен . Однако не каждый локально внешнепланарный граф является планарным.
• Граф не содержит треугольников тогда и только тогда, когда он локально независим .
• Каждый k - хроматический граф локально ( k -1)-хроматический. Каждый локально k - хроматический граф имеет хроматическое число . ^[2] ${\displaystyle O({\sqrt {kn}})}$
• Если семейство графов F замкнуто относительно операции взятия индуцированных подграфов, то каждый граф из F также локально F. Например, каждый хордовый граф локально хордальный; каждый совершенный граф локально совершенный; каждый граф сравнимости локально сравнимый; каждый (k)-(ультра)-однородный граф локально (k)-(ультра)-однородный.
• Граф локально цикличен, если каждая окрестность является циклом . Например, октаэдр является единственным связным локально графом класса C4, _{икосаэдр} является единственным связным локально графом _{класса C5} , а граф Пейли порядка 13 является локально графом _класса C6 . Локально циклические графы, отличные от K4 _, являются в точности базовыми графами триангуляций Уитни , вложений графов на поверхностях таким образом, что грани вложения являются кликами графа. ^[3] Локально циклические графы могут иметь столько же ребер. ^[4] ${\displaystyle n^{2-o(1)}}$
• Графы без клешней — это графы, которые локально не содержат треугольников ; то есть для всех вершин дополнительный граф окрестности вершины не содержит треугольника. Граф, который локально H, не содержит клешней тогда и только тогда, когда число независимости H не превышает двух ; например, граф правильного икосаэдра не содержит клешней, потому что он локально C ₅ и C ₅ имеет число независимости два.
• Локально линейные графы — это графы, в которых каждая окрестность является индуцированным паросочетанием . ^[5]
• Графы Джонсона являются локально сеточными, что означает, что каждое соседство является графом ладьи . ^[6]

Окрестность множества

Для множества вершин A окрестность вершины A представляет собой объединение окрестностей вершин, и, таким образом, это множество всех вершин, смежных хотя бы с одним  элементом A.

Множество вершин A в графе называется модулем, если каждая вершина в A имеет тот же набор соседей вне A. Любой граф имеет уникальное рекурсивное разложение на модули, его модульное разложение , которое может быть построено из графа за линейное время ; алгоритмы модульного разложения имеют приложения в других алгоритмах графов, включая распознавание графов сравнимости .

Смотрите также

• марковское одеяло
• Район Мур
• Район Фон Неймана
• Вторая проблема соседства
• Вершинная фигура , связанное понятие в многогранниках
• Ссылка (симплициальный комплекс) , обобщение соседства на симплициальные комплексы

Примечания

1. Ад 1978, Седлачек 1983
2. Вигдерсон 1983.
3. Хартсфельд и Рингель 1991; Ларрион, Нойманн-Лара и Пизанья, 2002 г.; Мальнич и Мохар, 1992 г.
4. Сересс и Сабо 1995.
5. Фрончек 1989.
6. Коэн 1990.

Ссылки

• Cohen, Arjeh M. (1990), «Локальное распознавание графов, зданий и связанных с ними геометрий» (PDF) , в Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (ред.), Finite Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries, performed in Pingree Park, Colorado, July 17–23, 1988 , Oxford Science Publications, Oxford University Press, стр. 85–94, MR  1072157; см. в частности стр. 89–90
• Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca , 39 (1): 3–6, hdl :10338.dmlcz/136481, MR  1016323
• Хартсфельд, Нора; Рингель, Герхард (1991), «Чистые триангуляции», Combinatorica , 11 (2): 145–155, doi : 10.1007/BF01206358, S2CID  28144260.
• Черт, Павол (1978), «Графы с заданными окрестностями I», Комбинированные проблемы и теория графов , Colloques internationaux CNRS, vol. 260, стр. 219–223..
• Larrión, F.; Neumann-Lara, V .; Pizaña, MA (2002), "Триангуляции Уитни, локальный обхват и итерированные кликовые графы", Discrete Mathematics , 258 (1–3): 123–135, doi : 10.1016/S0012-365X(02)00266-2.
• Малнич, Александр; Мохар, Боян (1992), «Создание локально циклических триангуляций поверхностей», Журнал комбинаторной теории, Серия B , 56 (2): 147–164, doi :10.1016/0095-8956(92)90015-P.
• Sedláček, J. (1983), "О локальных свойствах конечных графов", Теория графов, Lagów , Lecture Notes in Mathematics, т. 1018, Springer-Verlag, стр. 242–247, doi :10.1007/BFb0071634, ISBN 978-3-540-12687-4.
• Сересс, Акош; Сабо, Тибор (1995), «Плотные графы с циклическими окрестностями», Журнал комбинаторной теории, Серия B , 63 (2): 281–293, doi : 10.1006/jctb.1995.1020.
• Вигдерсон, Ави (1983), «Улучшение гарантии производительности для приблизительной раскраски графов», Журнал ACM , 30 (4): 729–735, doi : 10.1145/2157.2158 , S2CID  32214512.