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

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

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

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

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

Если все вершины в 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. Любой граф имеет уникальное рекурсивное разложение на модули, его модульное разложение , которое может быть построено из графа за линейное время ; алгоритмы модульного разложения имеют приложения в других алгоритмах графов, включая распознавание графов сравнимости .

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

• Cohen, Arjeh M. (1990), «Локальное распознавание графов, зданий и связанных с ними геометрий» (PDF) , в Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (ред.), Конечные геометрии, здания и связанные с ними темы: доклады с конференции по зданиям и связанным с ними геометриям, состоявшейся в Pingree Park, Colorado, 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.