Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 18 стр.

                         Лабораторная работа №5
        ВЕРШИННАЯ И РЕБЕРНАЯ СВЯЗАННОСТЬ ГРАФОВ
      Цель работы — исследование свойств связности ориентированных и
неориентированных графов. Приобретение практических навыков анализа
структур технических систем с использованием элементов теории графов.
                   Основные понятия и определения
      Граф G = (V, U) называется связным, если любые две его
несовпадающие вершины соединены маршрутом (цепью, простой цепью).
Всякий максимально связный подграф графа G называется компонентой
связности (компонентой). Определение "максимальный'" означает, что
подграф не содержится в другом связном подграфе с большем числом
элементов.   Множество    вершин   компоненты     связности   называется
областью связности графа. Каждый граф G представляется в виде
дизъюнктивного объединения своих компонент связности.
      Вершинной связностью (святостью) χ (G ) графа G отзывается
наименьшее число вершин, удаление которых делает граф несвязным или
одновершинным. Для любого несвязного графа           χ (G ) =0. Реберной
связностью λ (G ) называется наименьшее число ребер, удаление которых
приводит к несвязному графу. Для несвязного или одновершинного графа
χ (G ) =0.
      Удаление вершины из графа G приводит к подграфу G - v,
содержащему все вершины графа G, кроме v, и ребра графа G,
неинцидентные v. Вершины v, графа G называются точкой сочленения
(разделяющей вершиной), если граф G - v, имеет больше компонент, чем G.
Следовательно, если граф G связен и v точка сочленения, то граф G - v не
связен. Ребро графа называется мостом, если его удаление увеличивает
число компонент.




                                   18