Материал: Дискретная математика. методические указания к выполнению лабораторных работ для студентов направления подготовки «Информатика и вычислительная техника». Собенина О.В., Пак А.А

следовательность степеней является графической. Искомый граф получается в результате выполнения шагов, соответствующих порядку изъятия степеней;

б) одна из остаточных степеней отрицательна - это означает, что последовательность {d1,... ,dn} не является графической, т. е. не существует простого графа, который ее реализует.

2. Алгоритм проверки связности неорграфа

3. Алгоритм нахождения сильных компонент графа

Шаг 1. G = ( X, U ) - данный граф. Определение сильных компонент

сильные компоненты определены.

ПРАКТИЧЕСКАЯ ЧАСТЬ Задания

1.Написать программу, позволяющую осуществлять переход от матрицы смежности к матрице инциденций для ориентированного графа.

2.Написать программу, позволяющую осуществлять переход от матрицы смежности к матрице инциденций для неориентированного графа.

3.Написать программу, позволяющую строить простой граф с заданной последовательностью степеней, если он существует.

4.Написать программу, позволяющую для произвольного графа определять количество путей заданной длины из каждой вершины в каждую.

5.Написать процедуру для определения, является ли данный граф связным.

6.Написать программу, позволяющую находить сильные компоненты связного графа.

7.Написать программу, позволяющую получать матрицы достижимости и контр достижимости для произвольного графа.

16

8.Написать программу, реализующую алгоритм определения уровней графа без контуров.

11.Написать программу, которая переводит матрицу смежности в список ребер и список инцидентности для ориентированного графа

12.Написать программу, которая переводит матрицу инцидентности в список ребер и список инцидентности для неориентированного графа.

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

1.Номер и тема лабораторной работы.

2.Цель выполнения работы.

3.Схема алгоритма.

4.Исходные данные и результаты вычислений.

5.Анализ полученных результатов и вывод по работе.

ЛАБОРАТОРНАЯ РАБОТА № 6 ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФЕ

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

Практическая часть

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.

17

18

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

1.Номер и тема лабораторной работы.

2.Цель выполнения работы.

3.Условия задач приводятся полностью.

4.Решения излагаются подробно, объясняются все действия по ходу ре-

шения.

5.Анализ полученных результатов и вывод по работе.

ЛАБОРАТОРНАЯ РАБОТА № 7

ДЕРЕВЬЯ. ОСТОВЫ. КРАТЧАЙШИЕ ОСТОВЫ

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

Алгоритм построения остова неорграфа

Замечание. Процедура основана на просмотре в произвольном порядке ребер исходного графа и может быть представлена как процесс окрашивания ребер. При этом синий цвет используется для окраски ребер, включаемых в остов, а красный – для окраски ребер, не включаемых в остов. При рассмотрении ребра осуществляется проверка того, не образует ли данное ребро в совокупности с ребрами, уже включенными в остов, цикл. Эта проверка осуществляется следующим образом. Ребра, включенные в остов, составляют граф, имеющий одну или несколько компонент связности. Вершины, принадлежащие отдельно взятой компоненте, объединяются в совокупность, которую будем называть «букетом». Некоторое ребро образует цикл с ребрами, уже включенными в остов, если обе его концевые вершины принадлежат одному и тому же букету.

Результаты работы алгоритма удобно записывать в таблицу:

19

Шаг 1. Выбрать любое ребро, не являющееся петлей. Окрасить его в синий цвет и сформировать букет, включив в него концевые вершины окрашенного ребра.

Шаг 2. Выбрать любое неокрашенное ребро, не являющееся петлей. Если в графе такого ребра нет, то останов – исходный граф не содержит остова. Иначе перейти к шагу 3.

Шаг 3. а) Если обе концевые вершины выбранного ребра принадлежат одному букету, то окрасить выбранное ребро в красный цвет. б) Если одна из концевых вершин выбранного ребра принадлежит некоторому букету, а другая концевая вершина не принадлежит ни одному букету, то окрасить выбранное ребро в синий цвет и включить его концевую вершину, не принадлежавшую ранее ни одному букету, в тот же букет, которому принадлежит другая концевая вершина рассматриваемого ребра.

в) Если ни одна из концевых вершин не принадлежит ни одному букету, то окрасить рассматриваемое ребро в синий цвет и сформировать новый букет из его концевых вершин.

г) Если концевые вершины выбранного ребра принадлежат различным букетам, то окрасить ребро в синий цвет, а оба букета, которым принадлежат его концевые вершины, соединить в один букет.

Шаг 4. Если все вершины графа вошли в один букет, то останов - синие ребра образуют остов. Иначе перейти к шагу 2.

b [a,5], e [a,14], f [a,8], c [0, ], d [0, ].

Выбираем вершину с минимальной пометкой, т.е. вершину b. Добавляем эту вершину к TS , а соответствующее ребро к

AS .TS a, b , AS (a, b) .

20