Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А
9.Бинарное отношение задано матрицей. Как получить матрицу инверсии отношения?
10.Можно ли проверить бинарное отношение на эквивалентность с помощью операции композиция и отношения включения?
ЛАБОРАТОРНАЯ РАБОТА № 3
ПРЕДСТАВЛЕНИЕ ГРАФОВ В ЭВМ
Цель работы: изучение основных алгоритмов теории графов и получение практических навыков их программной реализации.
Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.
Теоретические сведения
Основу теории графов составляет совокупность методов и представлений, сформировавшихся при решении конкретных задач.
Граф есть совокупность точек и линий, соединяющих эти точки. Эти соединения могут обладать различными характеристиками. Теория графов занимается изучением этих характеристик.
Пусть задано некоторое конечное множество X, элементы которого будем называть вершинами, и множество U , состоящее из пар элементов (xi,xj ) множества X. Упорядоченная па-
ра множеств G=(X,U) называется графом.
Если в определении графа существенно в каком порядке выбираются вершины то есть пара(xi,xj ) отлична от пары
(xj,xi), то такой граф называют ориентированным или оргра-
19
фом, а пару (xi,xj ) - дугой, при этом считается, что xi - на-
чальная вершина, a xj - конечная. В геометрической интерпре-
тации дуге соответствует направленный отрезок. Если в определении графа не существенен порядок вершин при образовании пары (xi,xj ), то граф называют неориентированным или
неорграфом, а пару (xi,xj ) - ребром .
Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Для неорграфа такая последовательность ребер называется цепью.
Две вершины xi и xj называются смежными, если суще-
ствует соединяющее их ребро (дуга), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) - ин- цидентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину.
Если граф ориентированный, то говорят, что дуга (xi,xj )
исходит из вершины xi и заходит в вершинуxj . Число дуг, ко-
торые имеют вершину xi своей начальной вершиной, называют полустепенью исхода вершины xi и обозначают d (xi). Число дуг, которые имеют вершинуxi своей конечной вершиной, на-
зывают полустепенью захода вершины xi и обозначают d (xi).
Для неорграфа число ребер, инцидентных данной вершине xi
называется степенью (валентностью) вершины xi , и обознача-
ется d(xi).
Подграфом графа G=(X,U) называется граф G (X ,U),
для которого X X,U U.
Остовным подграфом графа G=(X,U) называется граф
Go=(Xo,Uо), для которого Хо=Х, Uo U.
20
Порожденным подграфом графа G=(X,U) называется граф
Gs=(Xs,Us), для которого Xs X и для
xi XS (ГS (xi ) Г(xi) XS ).
Если в графе G существует путь, идущий от вершины xi к
вершине хj то говорят, что вершина xj достижима из вершины
хi.
Если для любой пары вершин существует цепь их соединяющая, то такой граф называется связным. Иначе граф назы-
вается несвязным.
Матрицей достижимости графа G=(X,U), |X|=n называется матрица R = [ rij ]nxn , элементы которой определяются следующим образом:
1, если вершина xj достижима из хi;
rij=
0 в противном случае.
Матрицей контрдостижимости графа G = (X, U), |Х| = n называется матрица Q = [ qij ]nxn , элементы которой определяются следующим образом:
1, если вершина хi достижима из x
qij=
0 в противном случае. |
|
Множество достижимости вершины хi R(xi) |
состоит из |
таких вершин xj , для которых rij=1, определяется формулой: |
|
R(хi) = { хi } Г(хi) Г2(хi) ... Гp(хi), |
р < n. |
21
Множество контрдостижимости вершины хi Q(хi) состоит из таких вершин xj, для которых qij=l, определяется формулой:
Q(xij) = { хi } Г-1(хi) Г-2 (хi) ... Г-p(хi), р <n.
Основные операции над графами
1.Объединение графов. Объединением графовG1 (X1,U1)
иG2 (X2,U2) называется граф G3 (X1 X2,,U1 U2).
2. Пересечение графов. Пересечением графов G1 (X1,U1)
иG2 (X2,U2) называется граф G3 (X1 X2,,U1 U2).
3.Удаление вершины. При удалении вершины из графа
удаляются и все инцидентные ей ребра (дуги).
4.Удаление ребра (дуги). При удалении ребра (дуги) его концевые вершины не удаляются. Операцией, являющейся обратной к удалению ребра, является добавление ребра.
5.Слияние или отождествление вершин. Говорят, что
вершины xi и xj в графе G отождествляются (сливаются), ес-
ли они заменяются такой новой вершиной xk , что все ребра
(дуги) графа, инцидентные xi и xi , становятся инцидентными новой вершине xk .
6. Стягивание ребра. Эта операция означает удаление ребра и отождествление его концевых вершин. Граф G называется стягиваемым к графу Н, если граф Н может быть получен из G в результате некоторой последовательности стягиваний ребер.
22
Представление графов в ЭВМ
Очевидно, что наиболее понятный и полезный для человека способ представления графа – изображение графа на плоскости в виде точек и соединяющих их линий – будет совершенно бесполезным, если решать задачи, связанные с графами, с помощью ЭВМ. Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов.
В теории графов классическим способом представления графа служит матрица инциденций. Это матрица В с n строками, соответствующими вершинам, и т столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (х, у) U, содержит –1 в строке, соответствующей вершине х, 1 в строке, соответствующей вершине у, и нули во всех остальных строках (петлю, т. е. дугу вида (х, х) удобно представлять иным значением в строке х, например, 2). В случае неориентированного графа столбец, соответствующий ребру (х, у), содержит 1 в строках, соответствующих х и у, и нули в остальных строках. Это проиллюстрировано на рис. 2. С алгоритмической точки зрения матрица инциденций является, вероятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, он требует пт ячеек памяти, причем большинство этих ячеек вообще занято нулями. Неудобен также доступ к информации. Ответ на элементарные вопросы типа «существует ли дуга (х, у)?», «к каким вершинам ведут ребра из х?» требует в худшем случае перебора всех столбцов матрицы, а следовательно, т шагов.
Лучшим способом представления графа является матрица смежности, определяемая как матрица А =[аij] размера n n, где аij = 1, если существует ребро, идущее из вершины х в вершину у, и аij = 0 в противном случае. Здесь мы подразумеваем, что ребро (х, у) неориентированного графа идет как от х к у, так и от у к х, так что матрица смежности такого графа всегда является симметричной. Это проиллюстрировано на рис. 3.
23