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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф, состоящий из 6 вершин и 7 рёбер

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

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

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

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

Локальные свойства графа[править | править вики-текст]

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

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

Например:

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

Множество соседей[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]