Соседство (теория графов) - Neighbourhood (graph theory)

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

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

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

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

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

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

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

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

Например:

• Любой полный граф K _n локально K _n-1 . Единственные графы, которые являются локально полными, - это непересекающиеся объединения полных графов.
• Турана граф Т ( RS , г ) локально Т (( г - 1) с , г -1). В более общем смысле любой граф Турана является локально Тураном.
• Каждый плоский граф локально внешнепланарный . Однако не всякий локально внешнепланарный граф является плоским.
• Граф свободен от треугольников тогда и только тогда, когда он локально независим .
• Каждый к - хроматический граф локально ( к -1) -хроматическому. Каждый локально k -хроматический граф имеет хроматическое число ( Wigderson, 1983 ).${\ displaystyle O ({\ sqrt {kn}})}$
• Если граф семейства Р замкнуто относительно операции взятия индуцированных подграфов, то каждый граф в F также локально F . Например, каждый хордовый граф локально хордовый; каждый совершенный граф локально совершенен; каждый граф сопоставимости локально сопоставим.
• Граф является локально циклическим, если каждая окрестность является циклом . Например, октаэдр - это единственный связный локально C ₄ граф, икосаэдр - единственный связный локально C ₅ граф, а граф Пэли порядка 13 - локально C ₆ . Локально циклические графы, отличные от K _4, являются в точности базовыми графами триангуляций Уитни , вложения графов на поверхности таким образом, что грани вложения являются кликами графа ( Hartsfeld & Ringel 1991 ; Larrión, Neumann-Lara & Pizaña 2002 ; Malnič & Mohar 1992 ). Локально циклические графы могут иметь сколько угодно ребер ( Seress & Szabó, 1995 ).${\ Displaystyle п ^ {2-о (1)}}$
• Графы без клешней - это графы, которые локально свободны от треугольников ; то есть для всех вершин дополнительный граф окрестности вершины не содержит треугольника. Граф, локально Н является зубчатым свободно тогда и только тогда , когда число независимости от Н не более двух; например, граф правильного икосаэдра не имеет клешней, потому что он локально C _5, а C ₅ имеет независимость номер два.
• В локально линейные графики являются графиками , в которых каждая окрестность представляет собой индуцированное соответствие ( Fronček 1 989 ).

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

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

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

Смотрите также

• Марковское одеяло
• Окрестности Мура
• Район фон Неймана
• Вторая проблема соседства
• Фигура вершины , связанное понятие в геометрии многогранника

использованная литература

• Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz / 136481 , MR  1016323
• Хартсфельд, Нора; Рингель, Gerhard (1991), "Чистые триангуляции", Combinatorica , 11 (2): 145-155, DOI : 10.1007 / BF01206358.
• Ад, Павол (1978), «Графы с заданными окрестностями I», Problèmes combinatoires et théorie des graphes , Colloques internationaux CNRS, 260 , стр. 219–223..
• Ларрион, Ф .; Нойман-Лара, В .; Pizaña, MA (2002), "Уитня триангуляция, локальная обхват и итерация кружковых граф" , Дискретная математика , 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.
• Седлачек, J. (1983), «О локальных свойствах конечных графов», Теория графов, Лагув , Конспект лекций по математике, 1018 , Springer-Verlag, стр. 242–247, doi : 10.1007 / BFb0071634 , ISBN 978-3-540-12687-4.
• Seress, Ákos; Сабо, Тибор (1995), "Плотные графы с циклическими окрестностями" , Журнал комбинаторной теории, серия B , 63 (2): 281–293, doi : 10.1006 / jctb.1995.1020 , архивировано с оригинала 30 августа 2005 г..
• Wigderson, Avi (1983), "Повышение производительности гарантии для приблизительного раскраски графа", Журнал ACM , 30 (4): 729-735, DOI : 10,1145 / 2157,2158.