Окрестности (теория графов)

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

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

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

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

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

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

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

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

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

Например:

• Любой полный граф _Kn локально является Kn _-1 . Единственные графы, которые являются локально полными, — это непересекающиеся объединения полных графов.
• Граф Турана T ( rs , r ) локально T (( r -1) s , r -1). В более общем смысле любой граф Турана является локально Тураном.
• Каждый планарный граф локально внешнепланарен . Однако не каждый локально внешнепланарный граф является планарным.
• Граф свободен от треугольников тогда и только тогда, когда он локально независим .
• Каждый k - хроматический граф локально ( k -1)-хроматичен. Каждый локально k -хроматический граф имеет хроматическое число . ^[2] ${\displaystyle O({\sqrt {kn}})}$
• Если семейство графов F замкнуто относительно операции взятия индуцированных подграфов, то каждый граф из F также является локально F . Например, каждый хордальный граф является локально хордальным; каждый совершенный граф локально совершенен; каждый граф сопоставимости локально сопоставим; любой (k)-(ультра)-однородный граф локально (k)-(ультра)-однороден.
• Граф является локально циклическим, если каждая его окрестность является циклом . Например, октаэдр — это единственный связный локально граф C ₄ , икосаэдр — это единственный связный локально граф C _{5 , а} граф Пэли порядка 13 — это локально C ₆ . Локально циклические графы, отличные от 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.

Рекомендации

• Коэн, Арье М. (1990), «Локальное распознавание графиков, зданий и связанных с ними геометрий» (PDF) , в Канторе, Уильям М.; Либлер, Роберт А.; Пейн, Стэнли Э.; Шульт, Эрнест Э. (ред.), Конечная геометрия, здания и смежные темы: материалы конференции по зданиям и связанным с ними геометриям, состоявшейся в Пингри-парке, штат Колорадо, 17–23 июля 1988 г. , Oxford Science Publications, Oxford University Press, С. 85–94, МР  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..
• Ларрион, Ф.; Нойманн-Лара, В .; Пизанья, Массачусетс (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.
• Седлачек, Дж. (1983), «О локальных свойствах конечных графов», Теория графов, Лагов , Конспекты лекций по математике, том. 1018, Springer-Verlag, стр. 242–247, номер документа : 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.