МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АНАЛИЗ ГРАФОВ НА ЭВМ
Методические указания к выполнению лабораторных работ по курсу "Дискретная математика"
ПЕНЗА 2004
УДК 519.17
А 64
Приведены сведения об основных понятиях и терминологии теории графов, необходимые для выполнения цикла лабораторных работ. Темы лабораторных работ связаны с исследованием унарных и бинарных операция над графами, анализом метрических свойств, связности, независимости, паросочетаний, покрытий и циклов неориентированных и ориентированных графов с применением ЭВМ. Указан порядок выполнения лабораторных работ, даны темы заданий и ссылки на известные алгоритмы анализа графов, изложены требования к содержанию отчета.
Методические указания "подготовлены на кафедре "Вычислительная техника" и предназначены для студентов специальности 22.01.00, изучающих курс "Дискретная математика".
Ил. 11, табл. 2, библиогр. 14 назв.
Составители: П.П. Макарычев, Д.В. Пащенко
Под ред. д-ра техн. наук, профессора Н.П. Вашкевича
Р е ц е н з е н т: С.А. Зинкин, канд. техн. наук
Введение
Задачи теории графов имеют важное практическое значение. Особый интерес для научной и инженерной деятельности представляют алгоритмические аспекты таких задач.
На практике, при проектировании сложных технических систем, важно уметь построить модели этих систем в виде графов, а затем вычислить их характеристики, такие, как наибольшее паросочетание, наибольшее независимое множество вершин и ребер, остовное дерево и т, д. Таким образом, для решения практических задач проектирования и исследования технических систем надо иметь соответствующие алгоритмы, в конечном счете, программы для ЭВМ.
Основной задачей проведения лабораторных работ по курсу "Дискретная математика" является закрепление знаний по основам теории графов, приобретение практических навыков решения прикладных задач и построение эффективных алгоритмов для автоматизации математических расчетов.
В данных лабораторных работах в качестве инструмента для таких вычислений студентам предлагается система MathCAD, которая содержит текстовый редактор, мощный вычислитель и графический процессор. Язык общения с пользователем в системе MathCAD идеально приближен к обычному математическому языку. Поэтому центр тяжести расчетов перемещается с вопросов программирования на естественное математическое описание алгоритмов. Сведения по расширению функциональных возможностей MathCAD с использованием динамически подключаемых библиотек, приведены в приложении.
Лабораторная работа № 1
МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ И ХАРАКТЕРИСТИКИ ГРАФОВ
Цель работы -
изучение форм представления графов на основе матриц и вычисление их характеристик на ЭВМ.
Основные понятия и определения
Пусть G
-
связный помеченный граф, содержащий непустое множество вершин V
и множество ребер U
.
Вершинам графа присвоены метки из подмножества натуральных чисел {1,2,…}.
Выделим в графе G
две несовпадающие вершины vi
; и vj
.
Длина кратчайшего маршрута (простой цепи) между vi
; и vj
называется расстоянием между вершинами
и обозначается через l
(
vi
;
vj
).
Для фиксированной вершины vi
; величина
называется эксцентриситетом вершины vi
.
Максимальный среди всех эксцентриситетов эксцентриситет вершины называется диаметром графа G
и обозначается через D
(
G
).
Следовательно, вершина vi
называется периферийной,
если e
(
vi
) =
d
(
G
).
Простая цепь длины d
(
G
)
называется диаметральной цепью.
Минимальный из эксцентриситетов вершин связного графа G
называется его радиусом
и обозначается через r
(
G
).
Вычисление значения радиуса осуществляется по формуле
Вершина vi
называется центральной,
если e
(
vi
) =
r
(
G
).
Множество всех центральных вершин графа называется его центром.
Граф G
может иметь единственную центральную вершину или несколько центральных вершин.
Степенью вершины графа G
называется число инцидентных ей ребер. Степень вершины vi
: обозначается через deg
(
vi
).
Максимальная и минимальная степени вершиy графа G
обозначаются символами Δ(
G
)
, δ(
G
)
соответственно:
.
Список степеней вершин графа называется его степенней последовательностью.
Порядок членов в последовательности роли не играет. Вершина степени 0 называется изолированной,
степени 1 — концевой (висячей).
Ребро, инцидентное концевой вершине, также называется концевым.
Вершина графа, смежная с каждой другой его вершиной, называется доминирующей.
Лабораторное задание
1. Осуществите генерацию матрицы смежности M(
G)
неориентированного графа G,
где n -
порядок помеченного графа.
2. Определите радиус и диаметр графа G,
используя матрицу смежности графа M(
G)
и алгоритм вычисления эксцентриситета вершины.
3. Определите подмножества периферийных и центральных вершин графа G,
используя матрицу смежности M(
G)
4. Определите список степеней вершин графа, изолированные, концевые и доминирующие вершины.
5. Постройте для графа G
матрицу инцидентности A(
G).
Выполните п.4, используя представление графа и форме матрицы инцидентности.
6. Постройте для графа G
матрицу Кирхгофа B(
G).
Содержание отчета
Протокол решения задач по всем пунктам лабораторного задания средствами системы MathCAD.
Контрольные вопросы
1. Чему равна сумма степеней всех вершин графа?
2. Докажите, что матрица смежности и матрица Кирхгофа для графа без петель связаны соотношением
3. Bi,j
= Ii,j
.
M2
i,j
(G) - Mi,j
(G)
4. где I —
единичная матрица.
5. Покажите на примерах, что расстояние между вершинами l(
vi
,
vj
)
удовлетворяет следующим аксиомам метрики:
a) l(vi
,vj
)
>= 0;
б)
l
(
vi
,
vj
)
= 0, тогда и только тогда,
когда vi
=
vj
;
в) l
(
vi
,
vj
)
= l
(
vj
,
vi
)
г) l
(
vi
,
vk
)
+ l
(
vk
,
vj
)
>= l
(
vi
,
vj
)
(неравенство треугольника).
7. Пусть G —
граф, множество вершин которого совпадает с отрезком натурального ряда {
1,2,...5},
а множество ребер определяется следующим условием: несовпадающие вершины vi
,
и vj
смежны тогда, когда числа i
и j
взаимно просты. Какой вид имеют:
— матрица смежности графа G;
— матрица инциденций G
;
— матрица Кирхгофа графа G.
Лабораторная работа №2
УНАРНЫЕ И БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ
Цель работы
— исследование унарных, бинарных операций над графами и приобретение практических навыков решения задач с использованием основ теории графов.
Основные понятия и определения
Все унарные операции над графами можно объединить в две группы. Первую группу составляют операции, с помощью которых из исходного графа G
1
,
можно построить граф G
2
с меньшим числом элементов. В группу входят операции удаления ребра или вершины, отождествления вершин, стягивание ребра. Вторую группу составляют операции, позволяющие строить графы с большим числом элементов. В группу входят операции расщепления вершин, добавления ребра.
Отождествление вершин.
В графе G
1
выделяются вершины и,
v
.
Определяют окружение Q
1
вершины u
, и окружение Q
2
вершины v
,
вычисляют их объединение Q
= Q
1
Q
2
.
Затем над графом G
1
выполняются следующие преобразования:
— из графа G
1
удаляют вершины u
,
v
(
H
1
=
G
1
-
u
- v);
— к графу Н
1
присоединяют новую вершину z
(
H
1
=
H
1
+
z
);
— вершину z
соединяют ребром с каждой из вершин w
1
Q
(G
2
= H
1
+ zwi
, i =
1,2,3,…).
Стягивание ребра.
Данная операция является операцией отождествления смежных вершин и, v
в графе G
1
.
Наиболее важными бинарными операциями являются: объединение, пересечение, декартово произведение и кольцевая сумма.
Объединение.
Граф G
называется объединением или наложением графов G
1
и G
2
, если VG
=
V
1
V
2
;
UG
=
U
1
U
2
(рис. 1).
Рис. 1. Объединение графов G
1
, G
2
Объединение графов G
1
и G
2
называется дизъюнктным, если V
1
V
2
=
. При дизъюнктном объединении никакие два из объединяемых графов не должны иметь общих вершин.
Пересечение.
Граф G
называется пересечением графов G
1
, G
2
, если VG
=
V
1
V
2
и UG
=
U
1
U
2
(риc.2). Операция "пересечения" записывается следующим образом: G
=
G
1
G
2
.
Рис.2. Пересечение графов G
1
, G
2
.
Декартово произведение.
Граф G
называется декартовым произведением графов G
1
и G
2
если VG
= V
1
V
2
—декартово произведение множеств вершин графов G
1
, G
2
, а множество ребер U
c
задается следующим образом: вершины (zi
, vk
) и (zj
, vl
) смежны в графе G
тогда и только тогда, когда zi
= zj
(i
= j
), a v
k
и vl
смежны в G
2
или vk
= vl
(k
= l
), смежны в графе G
1
(см. рис.3).
Рис. 3. Декартово произведение графов G
1
, G
2
Кольцевая сумма
графов представляет граф, который не имеет изолированных вершин и состоит из ребер, присутствующих либо в первом исходном графе, либо во втором. Кольцевая сумма определяется следующим соотношением: G
= G
1
G
2
(рис.4).
Рис.4. Кольцевая сумма графов G1
,
G2
Лабораторное задание
1. Выполните генерацию матриц M
1
, М
2
смежности неориентированных помеченных графой G
1
, G
2
. Метки вершин выберите из подмножества натуральных чисел {
1, 2, …,
n}
. Порядок графов, определяется преподавателем. Вычислите матрицу смежности дополнительного графа (дополнения) G1
. Порядок графа п
определяется преподавателем.
2. Вычислите матрицы смежности подграфов Н,
Q
графа G
1
(
G
1
).
Например:
H
= G
1
- vi
, i
= 1, 2,..., n
;
Q
= G
1
- vi
- vj
, i
= 1, 2,..., n
, i
j
.
3. Выполните операцию отождествления вершин (стягивания ребра, расщепления вершины) в графе G1
(
G1
),
Номера выбираемых для выполнения операции двух вершин (вершины) согласуйте с преподавателем.
4. Выполните операцию объединения (пересечения, кольцевой суммы) графов G
= G
1
G
2
(G
= G
1
G
2
, G
= G
1
G
2
).
5. Выполните операцию декартова произведения графов G =
G
1
X G
2
, i =
1,2
Содержание отчета
1. Матричные и графические представления графов G1
(
G1
),Н,
Q,,
G
2
, G
3
.
2. Протоколы и результаты выполнения операций отождествления вершин (стягивания ребра), расщепления вершины объединения, пересечения, кольцевой суммы, декартова произведения графов в матричной и графической формах.
Контрольные вопросы
1. Задан неориентированный граф G
. В графе удаляются вершина и два ребра. Существенна ли последовательность выполнения операций?
2. Как выглядит колода P(
G) п —
вершинного графа G
, если все подграфы, входящие в колоду, выписать следующим образом:
G
1
= G
- vi
, i
= 1, 2, ..., n
?
3. К = {{
1, 2}; {
1, 2}} —
полный двухвершинный граф, Q = ({{
1,2,3,4};
{{1, 2}; {
2, 3}; {
3, 4}; {
4, 1}} -
двумерный куб. Верно ли, что граф R
= К
Q -
трехмерный куб?
4. Графы H
= H
1
H
2
и Q
являются подграфами полного n
-вершинного графа. Выполняется ли для них соотношение
HQ = (H
1
H
2
)Q = H
1
QH
2
Q?
Лабораторная работа № 3
АНАЛИЗ СВОЙСТВ СЕТЕЙ ПЕТРИ
Цель работы
- изучение форм представления сетей Петри и их анализ в среде системы компьютерной математики Mathcad.
Основные понятия и определения
Cеть Петри представляется четверткой , где – конечное множество позиций , – конечное множество переходов , – отображение множества переходов в комплекты входных позиций (входная функция), – отображение множества переходов в комплекты выходных позиций (выходная функция). Множество позиций и переходов не пересекаются . Позиция является входной позицией перехода , если . Позиция является выходной позицией перехода , если . Входы и выходы переходов представляют собой комплекты позиций. Запись обозначает число появлений позиции в комплекте . Для сети, приведенной на рис. 5, и . Входная и выходная функции имеют вид:
| ; |
; |
| ; |
; |
| ; |
; |
| ; |
. |
Маркировка сети Петри есть процесс присвоения фишек (маркеров) позициям. Маркировка задается функцией, отображающей множество позиций в множество неотрицательных целых чисел . Маркировка может быть определена как вектор . На графе фишки изображаются маленькими точками в кружке позиции. Состояние сети Петри определяется её маркировкой. Запуск разрешенного перехода изменяет состояние сети Петри посредством изменения маркировки.
Рис. 5. Граф сети Петри
При выполнении сети Петри получается две последовательности: маркировок и запущенных переходов , которые связаны соотношением . Имея последовательность запущенных переходов (маркировок) и несложно получить последовательность маркировок (запущенных переходов). Переход может запускаться только в том случае, когда является разрешенным. Переход считается разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу входных дуг.
Функции входов и выходов могут быть представлены матрицами инцидентности соответственно. Каждая матрица имеет – строк и – столбцов. Элементы матрицы определяются следующим образом:
, .
Пусть – вектор размерности , содержащий нули везде, за исключением – компоненты. Переход в маркировке разрешен, если выполняется условие . Результат запуска перехода в маркировке определяется формулой:
,
где – составная матрица изменений маркировок. Для последовательности запусков переходов вектор запусков определяется соотношением: . Элемент вектора – число запусков перехода в последовательности . При этом смена маркировки определяется соотношением:
.
Множество всех маркировок сети Петри, обладающей – позициями, есть множество всех – векторов . Это множество может быть бесконечным, но всегда счетным.
Позиция маркированной сети называется -ограниченной, если для любой маркировки , достижимой из , . Если , то позиция называется безопасной. Принято считать, что сеть структурно ограничена, если она ограничена для любой первоначальной маркировки .
Сеть Петри консервативна, или S
- инвариантна, если существует положительное целое число , связанное с каждой позицией , такое, что сумма маркеров постоянна для любой маркировки , достижимой из :
.
Сеть Петри повторяема, если существуют последовательность срабатываний переходов из такая, что каждый переход срабатывает бесконечное число раз в .
Сеть Петри непротиворечива, или - инвариантна, если существуют последовательность срабатываний из в такая, что переход в последовательности запускается по крайней мере один раз.
Лабораторное задание
1. Согласуйте с преподавателем вариант структуры и начальной маркировки сети Петри. Постройте граф сети в документе.
2. Определите входную и выходную функции сети Петри, матрицы инцидентности , вектор начальной маркировки .
3. Постройте дерево достижимости сети Петри с использованием матричного способа описания.
4. Определите достижимость маркировки из начальной маркировки и последовательность запусков переходов .
5. Исследуйте структурные свойства сети Петри: ограниченность, консервативность, повторяемость и непротиворечивость.
Содержание отчета
Протокол формализованного задания и анализа сети Петри по всем пунктам лабораторного задания средствами системы MathCAD.
Контрольные вопросы
1. Какие используются способы аналитического и графического представления маркированных сетей Петри?
2. Каким образом выполняется смена маркировки и определяется пространство состояний сети Петри?
3. Каким образом осуществляется матричный способ описания выполнения маркированной сети Петри?
4. По каким правилам и в какой последовательности строится дерево достижимости маркированной сети Петри?
5. Какие структурные свойства сети Петри зависят только от топологии и не зависят от начальной маркировки?
Лабораторная работа № 4
ВЕРШИННАЯ И РЕБЕРНАЯ НЕЗАВИСИМОСТИ
Цель работы
— исследование внутренней устойчивости ориентированных и неориентированных графов, приобретение практических навыков исследования структур технических систем.
Основные понятия и определения
Множество вершин графа называется независимым (внутренне устойчивым),
если никакие две вершины из этого множества несмежны. Независимое множество вершин называется максимальным,
если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности из максимальных независимых множеств называется наибольшим.
Число вершин в наибольшем независимом множестве графа G
называется числом независимости (числом внутренней устойчивости, неплотностью)
и обозначается через (
G).
На рис.6 показан граф G
, у которого число независимости (
G
) = 4.
Множества вершин {
v
1
, v
2
, v
3
, v
7
};
{
v
1
, v
2
, v
3
, v
8
};{
v
2
, v
3
, v
5
, v
7
}
и {
v
2
, v
3
, v
5
, v
8
}
являются наибольшими независимыми множествами. Множество вершин {
v
4
, v7
} максимальным независимым множеством, но не наибольшим.
Рис. 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(
n6)
.
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
.
Другими словами, каждая вершина графа находится на расстоянии не более единицы от доминирующего множества. Доминирующее множество называется минимальным
, нет другого доминирующего множества, содержащегося в нем. Минимальных доминирующих множеств в графе может быть несколько, и они не обязательно содержат одинаковое количество вершин. Минимальное доминирующее множество, имеющее наименьшую мощность называется наименьшим
.
Подмножество вершин графа, являющееся одновременно независимым и доминирующим, называется ядром графа
.
Понятие доминирующего множества переносится и на случай ориентированных графов. Подмножество S
вершин орграфа называется доминирующим, если для любой вершины существует такая вершина , что где А
- множество дуг орграфа Подмножество вершин S
, являющееся одновременно и независимым, и доминирующим называется ядром орграфа
. Например, орграф на рис. 8, а имеет два ядра
Орграф, изображенный на рис. 8, б, не имеет ядра.
Pис. 8. Ориентированные графы
Вершина и ребро графа покрывают друг друга, если они инцидентны. Ребро (
vi
, vj
)
покрывает вершины vi
, и vj
, а каждая из этих вершин покрывает это ребро. Подмножество называйся покрытием (вершинным покрытием, опорой)
графа G
, если каждое ребро из U
инцидентно хотя бы одной вершине из S
. Покрытие графа G
называется минимальным
, если оно не содержит покрытия с меньшим числом вершин, и наименьшим
, если число вершин в нем — наименьшее среди всех покрытий графа G
. Число вершин в наименьшем покрытии графа G
называется числом покрытия (числом вершинного покрытия)
графа G
и обозначается через .
Реберным покрытием
графа G
называется такое подмножество ребер , которое скрывает все вершины графа. При этом каждая вершина в G
инцидентна по крайней мере одному ребру из W
. Реберное покрытие графа называется минимальным
, если в нем не содержится покрытий с меньшим числом ребер, и наименьшим
, если число ребер в нем — наименьшее среди всех покрытий. Число ребер в наименьшим реберном покрытии графа G
называется числом реберного
покрытия и обозначается через .
Лабораторное задание
1. Выполните генерацию матрицы смежности M(
G)
неориентированного помеченного графа G
порядка . Метки графа выберите из подмножества натуральных чисел {
1,2,…,
n}
.
2. Выберите множество внешне устойчивых вершин S1
графа G
. Определите является ли множество S
1
ядром графа.
3. Вычислите числа вершинного и реберного покрытия графа G
.
4. Осуществите генерацию матрицы смежности М
ориентированного помеченного графа Н
порядка . Метки графа выберите из подмножества натуральных чисел {
1,2,…,
n}
.
5. Вычислите доминирующее множество вершин S
2
графа Н
. Определите является ли множество S
2
ядром орграфа.
Содержание отчета
1. Матричные и графические представления графов G, H.
2. Схема алгоритмов вычисления множества внешне устойчивых вершин графа G
, чисел вершинного и реберного покрытия графа G
, доминирующего множества вершин графа Н.
3. Протоколы вычислений S
1, S
2, , в системе MathCAD.
Контрольные вопросы
1. Существует ли граф G
порядка , в котором наименьшее доминирующее множество вершин не является независимым?
2. Чему равно число вершинного графа, если оно максимально для всех графов порядка n
?
Лабораторная работа № 7
ЦЕПИ И ЦИКЛЫ В ГРАФАХ
Цель работы
— исследование цепей и циклов в ориентированных и неориентированных графах.
Основные понятия и определения
Чередующаяся последовательность вершин и ребер графа называется маршрутом
, соединяющим вершины vi
и vi
+
1
. Маршрут (
vi
, vi
+
1
)
является цепью
, все его вершины кроме, возможно, крайних, различны. Маршрут (
vi
, vi
+
1
)
называется циклическим
, если vi
=
vi
+
1
. Циклическая цепь называется циклом
, циклическая простая цепь — простым циклом
. Число ребер в маршруте (
vi
, vi
+
1
)
определяет его длину. Простой цикл единичной длины называется единичным циклом. Длина всякого цикла в простом графе (без петель кратных ребер) и кратных ребер) минимум равна трем. Минимальная из длин циклов графа называется его обхватом
.
Любая цепь графа может рассматриваться как его подграф. В цепи Q
графа G
, заданной последовательностью вершин v
1
, v
2
,…,vn
, можно выделить две вершины vi
, vj
. Часть цепи Q
, начинающаяся в vi
и заканчивающаяся в vj
(
vi
, vi
+
1
,…,vj
-
1
, vj
)
, сама является цепью графа G
. Цепь (
vi
, vj
)
называется полуцепью
цепи Q
. На рис. 9 приведен граф G
, в котором (1,2) и (1, 2, 3, 5) - простые цепи. Цепь (1, 3, 5, 4, 3, 2) не является простой цепью. Маршрут (1, 2, 3, 5, 4, 3, 2) — не цепь. Цепь (1, 2, 3, 1) — простой цикл. Обхват рассматриваемого графа равен трем.
Рис. 9. Граф с обхватом, равным трем
В ориентированных графах маршрут ориентированный и является последовательностью вида (1). Аналогом цепи с в ориентированном графе служит путь (ориентированная цепь). Вершина vj
в ориентированном графе называется достижимой из вершины vi
, если существует путь (
vi
, vj
).
Произвольный ориентированный маршрут (
vi
, vj
)
, не являющийся простой цепью, превращается в простую цепь после устранения ''лишних звеньев''. Поэтому верны утверждения:
1. При i
, не равном j
, всякий маршрут (
vi
, vj
)
содержит простую цепь.
2. Всякий цикл содержит простой цикл.
3. Если C
, D
- два несовпадающих простых цикла, имеющих общее ребро ui
, то граф также содержит простой цикл.
Лабораторное задание
1. Выполните генерацию матрицы смежности M
(
G
)
неориентированного помеченного графа G
порядка . Метки графа выберите из подмножества натуральных чисел {
1,2,…,
n
}
. Отождествляя каждую вершину графа с одним из элементов на рис.6, постройте функциональную схему электронного узла. При этом входы элементов с номерами 1, 2 являются входами, а выходы элементов с номерами n
,
n
-
1 — выходами всего учла.
2. Вычислите остов минимального веса и базисные циклы Li
, i
=
1, 2,...,
m
в графе G
. При отсутствии базисных циклов в графе по согласованию с преподавателем осуществите добавление ребра (ребер)
3. Определите через базисные циклы все остальные циклы Lj
, j
=
m
+
1,
m
+
2,…
в графе G
. В соответствии с найденными циклами графа укажите на функциональной схеме узла все замкнутые цепи (контуры).
4. Осуществите генерацию матрицы смежности M
(
H
)
помеченного орграфа H
порядка . Определите все вершины, достижимые из вершины v
1
. Выберите достижимую вершину vj
, j
=
2,3,…,
n
, определяющую самый длинный маршрут. Определите, является ли самый длинный маршрут простой ориентированной цепью. Если маршрут не является простой ориентированной цепью, то удалите ''лишние звенья''.
Содержание отчета
1. Матричные и графические представления графов G
, H
, функциональная схема электронного узла.
2. Схема алгоритмов вычисления остова и базисных циклов графа G
и достижимых из вершины v
1
вершин графа H
.
3. Протоколы вычислений характеристик графа G
, Н
средствами системы MathCAD.
Контрольные вопросы
1. Как найти остов графа?
2. Найдите остовные деревья в графе Петерсена.
3. Верно ли, что, диаметр связного графа G
равен k
(
k
>
2)
, то в G
существует остовное дерево, диаметр которого также равен k
?
ЛИТЕРАТУРА
1. Акимов О.Е.
Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001 – 352 с.
2. Новиков Ф.А.
Дискретная математика для программистов – СПб: Питер, 2000. – 304 с.: ил.
3. Яхо, Альфред, В., Хопкрофт Джон Э., Ульман, Джеффи Д..
// Структуры данных и алгоритмы.: Пер. с англ.: Уч. пособие – М: Издательство дом «Вильямс», 2000-384 с.: ил. – Парал. тит. англ.
4. Романовский И.В.
Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – Издание 2-е, исправленное. – СПб.: Невский диалект, 2000 г. – 240 с., ил.
5. Горбатов В.А.
Основы дискретной математики: Учеб. Пособие для вузов. - М.: Высш. шк., 1986. - 312 с.
6. Нефедов В.Н., Осипова В.А.
Курс дискретной математики. - М.: Изд-во МАИ, 1992. - 264 с.
7. Лекции по теории графов / Под ред. В.А. Емеличева., О.Н. Мельникова, В.И. Сарванова, Р.И. Тышкевич
. - М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с.
8. Зыков А.А.
Основы теории графов. - М.: Наука, 1987. - 381 с.
9. Белов В.В., Воробьев Е.М., Шаталов В.Е.
Теория графов. Учеб. Пособие для вузов. - М.: Высш. шк., 1976. - 392 с.
10. Кристофиедес Н.
Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.
11. Татт У.
Теория графов. - М.: Мир, 1988. - 308 с.
12. Оре О.
Теория графов. - М.: Наука, 1980. - 336 с.
13. Евстигнеев В.
А. Применение теории графов в программировании. - М.: Наука, 1985. - 352 с.
14. Гаврилов Г.П., Сапоженко А.А.
Сборник задач по дискретной математике. - М.: Мир, 1982. - 416 с.
ПРИЛОЖЕНИЕ
Инструкция по использованию динамически подключаемой библиотеки
Функциональные возможности математической системы MathCAD могут быть существенно расширены за счёт использования динамически подключаемых библиотек (dll). Такие библиотеки могут быть легко разработаны с использованием языков высокого уровня (например С++). После получения файла соответствующей динамически подключаемой библиотеки необходимо скопировать этот файл в директорию USEREFI
Mathad’a. Кроме того, необходимо изменить файл user.xml, который находится в директории …docfuncdoc.
В этом файле регистрируются все пользовательские функции. В этот файл необходимо добавить следующий код:
<
function
> <
name
>
multiply
----- здесь указываем имя функции для вызова в
MathCAD
-е </
name
> <
params
>
a
,
M
-------указываем список аргументов функции </
params
> <
category
>
User
defined
---- Указываем категорию к которой можно отнести пользовательскую функцию
</category> <description> Returns the product of real scalar a and real array M ------
Описание
функции
для
диалогового
окна
“
Вставка
функции
” </description>
</function>
Для использования dll в MathCAD из диалогового окна “Insert Function” необходимо вызвать функцию.
Для примера возьмём задачу перемножения двух матриц (Рис. 10,11).
Рис. 10. Вставка функции
Рис. 11. Сравнение результатов
Список функций dll
Эти действия реализованы на языке С++ и храняться в динамической библиотеке, подключаемой к математическому пакету MatchCad
Таблица 1
| Имя функции
|
Описание
|
| GCreate
|
Генерация графа случайным образом |
| EccentList
|
Вычисление эксцентриситетов всех вершин графа |
| GDiametr
|
Находит диаметр графа M |
| GRadius
|
Находит радиус графа M |
| CentralList
|
Находит центральные вершины графа M |
| PeriphList
|
Находит периферийные вершины графа M |
| GraphComplement
|
Дополнение графа |
| DeleteVertex
|
Удаляет n-ую вершину графа M |
| GCreateOr
|
Генерация ориентированного графа случайным образом |
| GTranslate
|
Перевод матрицы смежности в матрицу инциденций |
| X
|
Визуализация неориентированного графа по оси Х |
| Y
|
Визуализация неориентированного графа по оси У |
| X_Or
|
Визуализация ориентированного графа по Х без стрелок |
| Y_Or
|
Визуализация ориентированного графа по У без стрелок |
| StX_Or
|
Визуализация стрелок ориентированного графа по оси Х |
| StY_Or
|
Визуализация стрелок ориентированного графа по оси У |
Пример использования некоторых функций
Таблица 2
| Размерность матрицы |
|
| Генерация |
|
| Результат |
|
| Список эксцентриситетов вершин |
|
| Вычисление диаметра |
|
| Вычисление радиуса |
|
| Вычисление вектора, содержащего центральные вершины |
|
| Визуализация неориентированного графа. |
|
| Вычисление вектора содержащего переферийные вершины |
|
СОДЕРЖАНИЕ
Введение……………………………………………..………………………… 3
Лабораторная работа №1. Матричные представления и характеристики графов………………………………………………...………………………... 4
Лабораторная работа №2. Унарные и бинарные операции над графами…. 7
Лабораторная работа №3. Анализ свойств сетей Петри…..………….….... 11
Лабораторная работа №4. Вершинная и реберная независимости……..… 15
Лабораторная работа №5. Вершинная и реберная связность графов….…. 18
Лабораторная работа №6. Вершинная устойчивость и покрытия в графах…………………………………………………………………….…... 21
Лабораторная работа №7. Цепи и циклы в графах………...………...….… 23
Литература…………………………………………………………………… 27
Приложение………………………………………………………………….. 28
Анализ графов на ЭВМ