Методические указания к выполнению лабораторных работ по курсу "Дискретная математика" пенза 2004 (стр. 4 из 6)
Рис. 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. Каким образом можно определить наибольшее независимое множество вершин в графе Петерсена?
Лабораторная работа №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-связным.Маршрутом в орграфе называется чередующаяся последовательность вершин и дуг
. Вершина vj достижима из вершины vi если существует маршрут (vi, vj). Любая вершина считается достижимой из себя самой.Орграф называется сильносвязным, если любые две его вершины достижимы друг из друга. Орграф называется односторонне-связным, если для любой пары его вершин, по меньшей мере, одна достижима из другой. Орграф называется слабосвязным, если любые две его вершины соединены полупутем. Поскольку любая вершина достижима из себя, то одновершинный граф одновременно сильносвязный, односторонне-связный и слабосвязный.
Лабораторное задание
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, связным, если
?Лабораторная работа №6
ВНЕШНЯЯ УСТОЙЧИВОСТЬ И ПОКРЫТИЯ В ГРАФАХ
Цель работы — исследование внешней устойчивости ориентированных и неориентированных графов, приобретение практических навыков исследования структур технических систем.
Основные понятия и определения
Подмножество вершин S графа G = (V,U) называется доминирующим (внешне устойчивым), если каждая вершина из V — S смежна с некоторой вершиной из S. Другими словами, каждая вершина графа находится на расстоянии не более единицы от доминирующего множества. Доминирующее множество называется минимальным, нет другого доминирующего множества, содержащегося в нем. Минимальных доминирующих множеств в графе может быть несколько, и они не обязательно содержат одинаковое количество вершин. Минимальное доминирующее множество, имеющее наименьшую мощность называется наименьшим.