Анализ графов на ЭВМ - 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