Шарнир (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Шарниром в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».

Определения[править | править вики-текст]

Вершина Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v графа называется шарниром, если подграф Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): G_{1} , полученный из графа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): G удалением вершины Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://ru.wikipedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): v и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://ru.wikipedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): G .

Граф, содержащий два шарнира (вершины 2 и 5) и три блока (12, 2345, 56).

С понятием шарнира также связано понятие двусвязности. Связный граф, не содержащий шарниров, называется двусвязным. Максимальный двусвязный подграф графа называется компонентой двусвязности. Компоненты двусвязности иногда называют блоками.

Рёберным аналогом шарнира является мост. Мостом называется такое ребро графа, в результате удаления которого количество компонент связности в графе возрастает.

Поиск шарниров[править | править вики-текст]

Эффективное решение задачи поиска всех шарниров графа основано на алгоритме поиска в глубину.

Пусть дан граф Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): G . Через Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Adj(v)} обозначим множество всех вершин графа, смежных с Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v . Предположим, что мы просмотрели граф в глубину, начав с некоторой произвольной вершины. Занумеруем все вершины графа в том порядке, в котором мы в них вошли, и каждой вершине Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v припишем соответствующий номер Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle n(v)} . Если в вершину мы впервые попали из вершины Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://ru.wikipedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): v , то вершину Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): u будем называть потомком Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v , а Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v — предком Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): u . Множество всех потомков вершины Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v обозначим через Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Ch(v)} . Через Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(v)} обозначим минимальный номер среди всех вершин, смежных с Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v и с теми вершинами, в которые мы пришли по пути, проходящем через Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v .

Ясно, что величину Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://ru.wikipedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle Low(v)} можно вычислить рекурсивно, непосредственно в процессе обхода в глубину: если в настоящий момент рассматривается вершина Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v , и из неё нельзя перейти в ещё не посещённую вершину (т.е. нужно вернуться к предку Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v , или прекратить обход, если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v — стартовая вершина), то для всех её потомков Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://ru.wikipedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle Low} уже посчитано, а значит, и для неё можно можно провести соответствующие вычисления по формуле

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(v) = \min \left\{\min_{x \in Ch(v)}Low(x), \min_{y \in Adj(v)/Ch(v)}n(y) \right\}.}

Зная величину Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(v)} для всех вершин графа, можно однозначным образом определить все его шарниры согласно следующим двум правилам:

  1. Стартовая вершина (т.е. та, с которой мы начали обход) является шарниром тогда и только тогда, когда у неё больше одного потомка.
  2. Вершина Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): v , отличная от стартовой, является шарниром тогда и только тогда, когда у неё есть потомок u такой, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(u)=n(v)} .

В качестве примера рассмотрим применение описанного алгоритма к графу, изображённому на рисунке справа. Числа, которыми помечены вершины, соответствуют одному из возможных вариантов обхода в глубину. При таком порядке у каждой из вершин ровно один потомок, за исключением вершины 6, у которой потомков нет. Стартовая вершина 1 имеет единственного потомка, следовательно, шарниром она не является. Для остальных вершин вычислим значения интересующей нас функции:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(6)=5, Low(5)=2, Low(4)=2, Low(3)=2, Low(2)=1} .

У вершины 2 есть потомок 3, а у 5 потомок 6 — в обоих случаях выполнено искомое соотношение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «/mathoid/local/v1/»:): {\displaystyle Low(u)=n(v)} . Следовательно, 2 и 5 являются шарнирами. Других шарниров в этом графе нет.

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

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

  • В. Е. Алексеев, В. А. Таланов. Графы и алгоритмы. Структуры данных. Модели вычислений. — М.: БИНОМ. Лаборатория знаний, 2006. — ISBN 5-94774-543-7.