ГРАФОВ СВЯЗНОСТЬ

— одно из основных свойств графов, выражающееся в следующем. На мн-ве вершин графа L отношение «вершины х и у соединены хотя бы одной цепью» есть эквивалентность; классы этой эквивалентности порождают подграфы, называемые компонентами (связности) графа L. Если к-во компонент

, то граф связным. В графов теории фундаментальную роль играет теорема Менгера: для существования в графе L системы из к цепей соединяющих две заданные вершины х и у и попарно не имеющих других общих элементов, необходимо и достаточно, чтобы никакое удаление к (или менее) элементов, представляющих собой отличные от х и у вершины или соединяющие ребра, не превращало L в такой граф, где х и у принадлежат разным компонентам. «Реберный» вариант этой теоремы (теорема Коцига) отличается тем, что удаляемыми к элементами служат только ребра, а А; цепей, соединяющих , не должны иметь общих ребер (но могут иметь общие вершины, отличные от ). Граф вершинно (соответственно реберно), если любые две его вершины х, у соединены по крайней мере к цепями попарно без общих элементов, кроме х и у (соответственно попарно без общих ребер). Максимальный -связный (вершинно) подграф графа его блоком, а вершина, принадлежащая более чем одному блоку, — точкой сочленения; последняя характеризуется тем, что ее удаление приводит к увеличению к-ва компонент графа.

Учитывая ориентацию ребер, получают понятие достижимости. Так, в Бержа графе вершина у достижима из если существует ориентированная цепь с началом и концом у. Граф, в котором всякие две вершины достижимы друг из друга, наз. бисвязным (или сильно связным). Бикомпоненты графа — это его макс. бисвязные подграфы, база вершин — такое подмн-во Z X, что никакие две различные вершины из Z не достижимы друг из друга, а всякая вершина достижима хотя бы из одной вершины, входящей в Z. Проблема полного обзора без вершин графа решается так: выявляют все те бикомпоненты, в которые не заходит извне ни одна дуга, тогда всевозможными базами вершин служат мн-ва, получаемые выбором по одной вершине из всех выявленных бикомпонент. Проблема обзора и нахождения баз дуг — таких миним. суграфов, которые обеспечивают ту же достижимость вершин, что и в исходном графе, — гораздо сложнее, но и она в некотором смысле решена.

Лит.: Зыков А. Теория конечных графов, т. 1. Новосибирск, 1969 [библиогр. с. 515—542].

А. А. Зыков.