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

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

В теории графов смежной вершиной вершины[en] 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 (Hell 1978, Sedlacek 1983). Например, в графе октаэдра, показанном на рисунке, каждая вершина имеет окрестность, изоморфную циклу из четырёх вершин, так что октаэдр является локально C4.

Например:

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

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

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

Смотрите также[править | править исходный текст]

Ссылки[править | править исходный текст]