Лабораторная работа №5

ВЕРШИННАЯ И РЕБЕРНАЯ СВЯЗАННОСТЬ ГРАФОВ

Цель работы — исследование свойств связности ориентированных и неориентированных графов. Приобретение практических навыков анализа структур технических систем с использованием элементов теории графов.

Основные понятия и определения

Граф G = (V, U ) называется связным, если любые две его несовпадающие вершины соединены маршрутом (цепью, простой цепью). Всякий максимально связный подграф графа G называется компонентой связности (компонентой). Определение "максимальный'" означает, что подграф не содержится в другом связном подграфе с большем числом элементов. Множество вершин компоненты связности называется областью связности графа. Каждый граф G представляется в виде дизъюнктивного объединения своих компонент связности.

Вершинной связностью (святостью)  графа G отзывается наименьшее число вершин, удаление которых делает граф несвязным или одновершинным. Для любого несвязного графа =0. Реберной связностью  называется наименьшее число ребер, удаление которых приводит к несвязному графу. Для несвязного или одновершинного графа =0.

Удаление вершины из графа G приводит к подграфу G - v , содержащему все вершины графа G, кроме v, и ребра графа G, неинцидентные v. Вершины v, графа G называются точкой сочленения (разделяющей вершиной), если граф G - v, имеет больше компонент, чем G. Следовательно, если граф G связен и v точка сочленения, то граф G - v не связен. Ребро графа называется мостом, если его удаление увеличивает число компонент.

Сочленения и мосты являются "узкими местами" в графе и отражают в графовой модели чувствительность физической системы к разрушению её элементов и соединений. Например, если  - минимальная степень вершин графа G, то . Это следует из того, что удаление всех ребер, инцидентных данной вершине, приводит к увеличению компонент графа. Для любого графа G верно неравенство .

Если , граф называется k -связным, и, если , то реберно k -связным.

Маршрутом в орграфе называется чередующаяся последовательность вершин и дуг . Вершина v_j достижима из вершины v_i если существует маршрут ( v_i , v_j ). Любая вершина считается достижимой из себя самой.

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

Лабораторное задание

1. Выполните генерацию матрицы смежности M( G) неориентированного помеченного графа G. Порядок графа п определяется преподавателем. Определите вершинную  и реберную  связности графа G.

2. Построите из графа G, выполняя последовательно операции удаления вершин и ребер, граф Q, содержащий точку сочленения и мост.

3. По согласованию с преподавателем, выполните удаление рёбер из графа G и определите компоненты связности в графе G.

4. Осуществите преобразование матрицы M( G) в матрицу смежности  M( R) орграфа R( n 6).

5. Определите, является ли орграф R связным, односторонне-связным или слабосвязным.

6. Отождествляя каждую вершину орграфа с одним из элементов на рис. 7, постройте функциональную схему электронного узла, представленного в форме графа R. Свободные входы элементов, соответствующих вершинам с номерами 1,2 являются входами всего узла. Выходы элементов, соответствующих вершинам с номерами n, n-1, являются выходами всего узла.

Рис. 7. Элементы функциональной схемы

Содержание отчета

7. Матричные и графические представления графов G, R, K, H, Q.

8. Схемы алгоритмов вычисления компонент связности неориентированного графа K, сильной, односторонней и слабой связности графа R.

9.  Протоколы анализа характеристик графов K, R, с использованием системы MathCAD.

Контрольные вопросы

1. Имеют ли общую вершину две простые цепи максимальной длины в связном графе?

2. Является ли граф G, исследованный в лабораторной работе №1, связным?

3. Является ли граф G, связным, если ?