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

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

Чтобы узнать о других значениях окрестностей в математике, см. Окрестности (математика) .

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

The neighbourhood is often denoted Район часто обозначается $N_{G}(v)$или or (when the graph is unambiguous) (когда график однозначен ) $N(v)$. . The same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. The neighbourhood described above does not include v , а точнее, является открытой окрестностью v То же обозначение окрестности можно использовать для обозначения наборов смежных вершин, а не соответствующих индуцированных подграфов. Описанная выше окрестность не включает в себя саму ; также возможно определить окрестность, в которую v входит сам , называемую замкнутой окрестностью и обозначаемую $N_{G}[v]$. Если это указано без каких-либо оговорок, предполагается, что район открыт. . When stated without any qualification, a neighbourhood is assumed to be open.

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

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

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

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

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

Например:

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

Окрестности множества

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

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

См. также

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

Ссылки

• Коэн, Арье М. (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», Комбинаторные задачи и теория графов , Международные конференции CNRS, том. 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, doi : 10.1007/BFb0071634 , ISBN.  978-3-540-12687-4 .
• Сересс, Акос; Сабо, Тибор (1995), «Плотные графы с циклическими окрестностями», Журнал комбинаторной теории, серия B , 63 (2): 281–293, doi : 10.1006/jctb.1995.1020 .
• Вигдерсон, Ави (1983), «Улучшение гарантии производительности для приблизительной раскраски графов», Journal of the ACM , 30 (4): 729–735, doi : 10.1145/2157.2158 , S2CID   32214512 .