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

В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.

Граф, состоящий из 6 вершин и 7 рёбер

Окрестность часто обозначается как N_G(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как N_G[v]. Если не указано явно, окрестность предполагается открытой.

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

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

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

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

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

Например:

• Любой полный граф K_n является локально графом K_n-1. Единственные графы, которые локально полны — это несвязное объединение полных графов.
• Граф Турана T(rs,r) локально эквивалентен T((r-1)s,r-1). То есть, любой граф Турана локально является графом Турана.
• Любой планарный граф локально внешнепланарен. Однако не всякий локально внешнепланарный граф является планарным.
• Граф является графом без треугольников в том и только в том случае, если он локально независим.
• Любой k-хроматический граф локально (k-1)-хроматичен. Любой локально k- хроматический граф имеет хроматическое число $O({\sqrt {kn}})$.
• Если семейство графов F замкнуто относительно операции взятия порождённых подграфов, то любой граф в F локально тоже F. Например, любой хордальный граф локально хордален, любой совершенный граф локально совершенен, любой граф сравнимости является графом сравнимости.
• Граф локально цикличен, если любая окрестность является циклом. Например, граф октаэдра является единственным локально C₄ графом, граф икосаэдра является единственным локально C₅ графом, а граф Пэли порядка 13 локально равен C₆. Локально циклические графы, отличные от K₄, — это в точности графы, лежащие в основе триангуляции Уитни, осуществляющей вложение графов в поверхность таким образом, что грани при внедрении соответствуют кликам графа. Локально циклические графы могут до $n^{2-o(1)}$ рёбер.
• Графы без клешней — это графы, локально кo-свободные от треугольников. То есть, для всех вершин, дополнение графа окрестности вершины не содержит треугольников. Граф, являющийся локально графом H, не содержит клешней тогда и только тогда, когда число независимости графа H не больше двух. Например, граф правильного икосаэдра не содержит клешней, поскольку он локально C₅ и число независимости C₅ равно двум.

Множество соседей

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

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

См. также

• Окрестность Мура
• Окрестность фон Неймана
• Вершинная фигура, похожее понятие в геометрии многогранников.

Литература

• Nora Hartsfeld, Gerhard Ringel.  Clean triangulations // Combinatorica. — 1991. — Vol. 11, no. 2. — P. 145—155. — doi:10.1007/BF01206358.
• Pavol Hell. . Graphs with given neighborhoods I // Problèmes Combinatoires et Théorie des Graphes. — Paris: Éditions du Centre national de la recherche scientifique, 1978. — xiv + 443 p. — (Colloques internationaux C.N.R.S., vol. 260). — ISBN 2222020700. — P. 219—223.
• F. Larrión, V. Neumann-Lara, M. A. Pizaña.  Whitney triangulations, local girth and iterated clique graphs // Discrete Mathematics. — 2002. — Vol. 258. — P. 123—135. — doi:10.1016/S0012-365X(02)00266-2.
• Aleksander Malnič, Bojan Mohar.  Generating locally cyclic triangulations of surfaces // Journal of Combinatorial Theory, Series B. — 1992. — Vol. 56, no. 2. — P. 147—164. — doi:10.1016/0095-8956(92)90015-P.
• J. Sedlacek. . On local properties of finite graphs // Graph Theory, Lagów. — Springer-Verlag, 1983. — (Lecture Notes in Mathematics, vol. 1018). — ISBN 978-3-540-12687-4. — doi:10.1007/BFb0071634. — P. 242—247.
• Ákos Seress, Tibor Szabó.  Dense graphs with cycle neighborhoods // Journal of Combinatorial Theory, Series B. — 1995. — Vol. 63, no. 2. — P. 281—293. — doi:10.1006/jctb.1995.1020. Архивировано 30 августа 2005 года.
• Avi Wigderson.  Improving the performance guarantee for approximate graph coloring // Journal of the ACM. — 1983. — Vol. 30, no. 4. — P. 729—735. — doi:10.1145/2157.2158.