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

ВЕРШИННАЯ И РЕБЕРНАЯ НЕЗАВИСИМОСТИ

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

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

Множество вершин графа называется независимым (внутренне устойчивым), если никакие две вершины из этого множества несмежны. Независимое множество вершин называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности из максимальных независимых множеств называется наибольшим. Число вершин в наибольшем независимом множестве графа G называется числом независимости (числом внутренней устойчивости, неплотностью) и обозначается через ( G).

На рис.6 показан граф G, у которого число независимости ( G ) = 4. Множества вершин { v₁, v₂, v₃, v₇}; { v₁, v₂, v₃, v₈};{ v₂, v₃, v₅, v₇} и { v₂, v₃, v₅, v₈} являются наибольшими независимыми множествами. Множество вершин { v₄, v₇} максимальным независимым множеством, но не наибольшим.

Рис. 6 Граф G с числом независимости, равным четырем вершинам реберного графа L(G), т. е. (G) = [L(G)].

Произвольное подмножество попарно несмежных ребер графа называется паросочетанием (независимым множеством ребер). Паросочетание графа G называется максимальным оно не содержится в паросочетании с большим числом ребер. Паросочетание является наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа G. Число ребер в наибольшем паросочетании называется числом паросочетания и обозначается через ( G ).

Независимые множества ребер графа G находятся во взаимно однозначном соответствии с независимым множеством

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

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

2. Определите наибольшее независимое множество вершин и вершинное число внутренней устойчивости ( G) графов G и G.

3. Определите наибольшее независимое множество ребер и число паросочетаний ( G) графов G и G .

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

1. Матричное и графическое представление графа G ( G ).

2. Схемы алгоритмов вычисления чисел внутренней устойчивости ( G) и паросочетаний ( G) графов G и G.

3. Протоколы вычислений чисел внутренней устойчивости и паросочетаний графов G и G .

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

1. Верно ли утверждение, что любое паросочетание графов содержится в наибольшем паросочетании?

2. Если G - дерево, содержащее n вершин, то выполняется ли для него соотношение ( G ?

3. Каким образом можно определить наибольшее независимое множество вершин в графе Петерсена?