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

       Сочленения и мосты являются "узкими местами" в графе и отражают
в графовой модели чувствительность физической системы к разрушению
её элементов и соединений. Например, если δ (G ) - минимальная степень
вершин графа G, то λ (G ) ≤ δ (G ) . Это следует из того, что удаление всех
ребер, инцидентных данной вершине, приводит к увеличению компонент
графа. Для любого графа G верно неравенство χ (G ) ≤ λ (G ) ≤ δ (G ) .
       Если χ (G ) ≥ k , граф называется k-связным, и, если λ (G ) ≥ k , то
реберно k-связным.
       Маршрутом              в      орграфе          называется           чередующаяся
последовательность вершин и дуг S = (v0 , u 0 , v1 , u1 , v2 , u 2 ,..., vn , u n ) . Вершина
vj достижима из вершины vi если существует маршрут (vi, vj). Любая
вершина считается достижимой из себя самой.
       Орграф называется сильносвязным, если любые две его вершины
достижимы друг из друга. Орграф называется односторонне-связным, если
для любой пары его вершин, по меньшей мере, одна достижима из другой.
Орграф называется слабосвязным, если любые две его вершины соединены
полупутем.       Поскольку         любая    вершина       достижима        из    себя,    то
одновершинный          граф       одновременно      сильносвязный,         односторонне-
связный и слабосвязный.
                                  Лабораторное задание
 1. Выполните генерацию матрицы смежности M(G) неориентированного
помеченного графа G. Порядок графа п определяется преподавателем.
Определите вершинную χ (G ) и реберную λ (G ) связности графа G.
 2. Построите из графа G, выполняя последовательно операции удаления
вершин и ребер, граф Q, содержащий точку сочленения и мост.
 3. По согласованию с преподавателем, выполните удаление рёбер из
графа G и определите компоненты связности в графе G.




                                             19