Практическая работа №1
Представление графов в ЭВМ
1. Цель работы
Изучение представления графов в ЭВМ при помощи матрицы смежности, множества пар вершин и массива структур. Визуализация графов.
2. Необходимые теоретические сведения
Граф – это объект, состоящий из элементов двух типов: узел (вершина)
и ребро.
Граф называется ориентированным (направленным), если каждому ребру данного графа присвоено направление.
Граф называется взвешенным, если каждому ребру данного графа поставлено в соответствие некое значение – вес ребра.
Ребро является инцидентным вершине, если это ребро либо заканчивается, либо начинается в этой вершине.
Основными структурами данных, которые используются для представления графов в компьютерных программах, являются матрица смежности и список ребер.
Для графа с конечным числом вершин n (пронумерованных числами от
1 до n), матрица смежности — это квадратная матрица A размера n, в
которой значение элемента aij равно числу рёбер (или сумме весов рёбер),
соединяющих i-ую и j-ую вершины графа (или исходящих из i-ой вершины графа и входящих в j-ую вершину).
Матрица смежности неориентированного графа симметрична (т.е. все элементы данной матрицы являются симметричными относительно главной диагонали).
Список ребер представляет собой список, в котором указаны все пары соединенных ребрами вершин с указанием веса данных ребер. Порядок указания вершин является важным, сначала указывают вершину, из которой выходит ребро, а затем вершину, в которую ребро входит. В случае неориентированного графа каждая пара вершин дублируется и записывается в обратном порядке.
3. Порядок выполнения работы
1.Выбрать согласно варианту граф из таблицы 1.1.
2.Для выбранного графа выписать матрицу смежности. Ввести в ЭВМ матрицу смежности в явном виде.
3.Написать подпрограмму для построения списка ребер из заданной матрицы смежности.
4.Визуализировать заданный граф. Убедиться в том, что он совпадает с исходным графом.
5.Написать подпрограмму, позволяющую представить граф в виде массива записей, основываясь на заданной матрице смежности. Каждой вершине графа соответствует запись. В каждой такой записи обязательным является вывод следующих параметров вершины графа:
№ вершины, подпись/имя вершины, количество детей / родителей /
соседей, номера вершин детей / родителей / соседей, веса исходящих / входящих / инцидентных ребер. Для удобства и наглядности можно добавить в запись дополнительные параметры. Вывести полученный массив записей в понятном пользователю виде (например, таблица, список и т.д.).
6.Для каждого из представлений (матрица смежности, список ребер,
массив записей) написать подпрограммы поиска и вывода на экран:
▪всех соседей заданной вершины графа;
▪ответа, образует ли заданная последовательность вершин цепь;
▪номеров вершин, сумма весов инцидентных ребер которых больше заданной величины;
▪количества ребер в графе.
Для каждой подпрограммы организовать диалог с пользователем
(запрос параметра – вывод результата). Данные для представления результатов выполнения данных подпрограмм подобрать самостоятельно.
7.Для каждого из представлений (матрица смежности, список ребер,
массив записей) вывести на экран размер содержащего их объекта в байтах.
8.Каждую подпрограмму, реализующую выполнение пункта 6 п/р (в том числе и для каждого представления графа), повторить 106 раз при постоянных входных параметрах. Засечь время выполнения каждой подпрограммы и оценить среднее время ее выполнения. Вывести полученные результаты на экран.
4. Содержание отчета
1.Цель работы.
2.Запись матрицы смежности согласно выбранному варианту.
3.Описание (список использованных переменных, листинг,
комментарии) и результаты выполнения разработанных программ,
реализующих пункты 3, 5, 6 порядка выполнения п/р.
4.Изображения графов, полученные в пункте 4 порядка выполнения п/р.
5.Результаты выполнения пунктов 7 и 8 порядка выполнения п/р.
6.Выводы о целесообразности хранения структуры графа в рассмотренных в п/р представлениях, исходя из рассмотренных параметров.
Номер
варианта
1
2
3
Таблица 1.1 – Варианты к п/р № 1
Граф
|
|
|
B |
|
|
1 |
|
|
|
2 |
|
A |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
|
|
4 |
|
|
3 |
|
|
|
C |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
D |
|
|
|
2 |
G |
|
|
|
|
||
|
|
|
|
|
|
|
3 |
|
E |
|
|
|
|
|
|
|
|
|
X |
|
|
|
|
1 |
|
|
|
|
4 |
|
1 |
|
|
|
|
|
|
X |
|
|
|
|
4 |
|
|
|
|
|
1 |
|
X |
|
|
|
|
3 |
2 |
|
2 |
|
1 |
3 |
X |
2 |
||
|
3 |
|
|
|
X |
|
|
|
|
|
|
|
|
|
8 |
|
|
5 |
|
|
|
|
|
|
|
|
2 |
|
|
|
X |
|
|
X6 |
|
7 |
5 |
12 |
|
|
|
|||
|
|
X |
|
|
|
|
5 |
|
|
|
|
Sun |
|
|
5 |
|
1 |
|
|
|
|
Sat |
|
|
|
|
|
4 |
Mon |
|
|
|
|
|
2 |
Tue |
3 |
|
|
||
|
|
|
|
3 |
|
|
2 |
|
|
|
|
|
|
6 |
|
Fri |
7 |
8 |
Thr |
|
Wed
4
5
6
|
Oct |
|
|
|
|
|
|
|
|
3 |
2 |
|
Aug |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Jan |
|
|
|
|
|
6 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jul |
|
|
|
|
|
|
|
|
3 |
4 |
|
Mar |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
Feb |
3 |
|
|
|
|
|
|
|
|
Nov |
||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Sep |
3 |
|
5 |
|
2 |
|
|
|
7 |
|
|
|
|||
|
|
|
|
|
|
||
|
2 |
|
|
|
|
4 |
|
|
|
|
|
|
|
||
|
Jun |
7 |
8 |
|
Apr |
|
|
|
|
|
|
Dec |
|||
|
|
|
|
|
|
1 |
|
|
|
|
May |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
1 |
|
|
|
|
|
|
|
|
|
III |
3 |
|
|
|
|
|
|
II |
|
|
4 |
|
|
|
|
|
1 |
2 |
|
|
|
|
|
3 |
|
||
|
|
3 |
|
|
|
VII |
|
|
|
4 |
|
|
1 |
|
|
||
|
2 |
|
|
|
|
2 |
2 |
IV |
|
|
|
|
|
|
VI |
||
|
|
|
|
1 |
|
|
|
|
|
|
V
|
1 |
John |
|
4 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
|
Tommy |
2 |
Stuart |
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
1 |
Paul |
|
|
|
6 |
|
4 |
|
1 |
|
Norman |
|
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
Chas |
4 |
Pete |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
George |
|
|
|
2 |
|
|
|
3 |
Ringo |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
7
8
9
10
Rector
|
1 |
|
2 |
|
3 |
4 |
|
|
|
Vice- |
2 |
|
Vice- |
|
4 |
Vice- |
1 |
Vice- |
|
Rector 1 |
Rector 2 |
Rector 3 |
Rector 4 |
||||||
|
|
|
|||||||
5 |
1 |
2 |
|
|
|
2 |
|
4 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
||
3 |
|
|
4 |
|
|
|
|
|
|
Dean 1 |
Dean 2 |
Dean 3 |
Dean 4 |
|
|||||
|
|
|
|
|
King |
|
7 |
|
1 |
|
|
|
|
|
Pawn |
|
Queen |
|
|
7 |
|
5 |
3 |
3 |
4 |
|
|||
|
|
4 |
|
|
|
|
|
Rook |
Knight |
1 |
Bishop |
|
2 |
|
Grandpa |
|
Grandma |
Grandpa |
|
Grandma |
1 |
2 |
1 |
2 |
2 |
2 |
|
|
|
|
||
1 |
|
1 |
1 |
|
1 |
|
Mother |
|
2 |
Father |
|
|
|
1 |
1 |
|
|
|
1 |
|
|
1 |
|
|
|
Son |
Daughter |
|
|
|
|
|
|
Niko- |
|
|
5 |
|
lai II |
|
4 |
|
2 |
|
Ekate- |
Petr III |
|
9 |
|
|
4 |
|||
rina II |
|
|
||
|
|
Alek- |
||
|
|
|
||
|
|
|
|
|
|
|
|
|
sandr |
5 |
|
34 |
|
III |
|
Pevel I |
2 |
|
8 |
6 |
|
6 |
|
Alek- |
|
|
sandr II |
||
|
|
7 |
|
|
|
|
|
|
|
Alek- |
|
Niko- |
|
|
sandr I |
|
lai I |
|
|
11
12
13
14
|
|
Assistant |
|
6 |
|
|
6 |
|
|
|
|
Secre- |
|
2 |
Secre- |
|
|
||
tary2 |
|
|
tary1 |
10 |
|
|
10 |
|
|
Chief |
|
4 |
|
|
4 |
|
|
|
|
10 |
|
|
10 |
Manager |
2 |
|
Manager |
1 |
|
2 |
|
|
|
||
4 |
|
|
4 |
|
|
|
|
|
|
Worker |
|
|
|
|
|
Hawk |
|
|
|
1 |
|
1 |
1 |
|
|
|
|
|
|
|||
|
Snake |
Lizard |
||||
|
2 |
|
1 |
|
1 |
|
|
|
|
|
|
||
|
Mouse |
|
|
Hare |
|
Grig |
Sun- |
|
2 |
2 |
|
||
2 |
|
|
1 |
|||
light |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Green |
|
|
|
|
|
|
plants |
|
|
|
|
|
|
|
15 |
Birth |
|
10 |
Youth |
|
|
||
|
|
|
|
|
|
|
Maturity |
|
|
|
|
|
|
|
55 |
|
|
65 |
|
80 |
|
|
|
|
|
||
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
Old age |
|
|
Death |
|
|
|
|
|
|
35 |
|
|
|
|
|
|
Metro |
|
|
|
1 |
|
Station 2 |
|
1 |
|
|
|
|
|
|
|
|
Univer- |
|
|
1 |
|
|
|
sity1 |
|
|
|
|
Metro |
|
|
|
|
|
|
||
|
|
|
Metro |
|
Station 3 |
|
|
|
|
|
|
||
|
8 |
Station 1 |
|
|
||
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
Home |
|
|
10 |
|
Univer- |
|
|
|
|
|
sity2 |
|
|
|
|
|
|
|
15
16
17
Kinder- |
|
|
garten |
|
|
7 |
|
|
School |
|
|
|
9 |
|
11 |
|
|
9 |
|
|
Univer |
3 |
|
College |
||
-sity |
||
|
||
6 |
|
|
|
3 |
|
Work |
|
|
40 |
|
|
Pension |
|
|
|
|
Work- |
|
|
|
|
|
stantion |
|
|
|
1 |
|
1 |
1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
3 |
|
Work- |
|
|
2 |
|
Work- |
stantion |
|
|
|
stantion |
|
2 |
|
|
|
||
6 |
|
|
|
2 |
|
|
|
|
|
||
|
|
|
Token- |
|
|
|
|
|
ring |
|
1 |
1 |
|
|
|
2 |
|
Work- |
|
2 |
|
|
Work- |
|
|
2 |
|
||
stantion |
|
|
|
stantion |
|
|
|
|
|
||
5 |
|
|
|
|
3 |
|
1 |
|
Work- |
|
1 |
|
|
|
stantion |
|
|
|
|
|
4 |
|
|
Lava |
|
Dust |
2 |
Dirt |
|
|
|
||||
|
|
1 |
|
|
|
2 |
|
|
|
2 |
1 |
|
|
1 |
|
|
|
Fire |
|
Air |
|
Earth |
Water |
|
2 |
|
2 |
|
1 |
1 |
|
|
|
||
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
Energy |
2 |
Steam |
|
Swamp |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
Storm |
|
|
18
19
20
|
|
X |
|
|
Y |
|
|
|
|
|
2 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
Plus |
|
|
|
|
|
|
|
|
|
|
|
|
|
Div |
|
9 |
|
|
Z |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Multi |
8 |
|
|
|
|
3 |
|
|
|
|
|
|
|
3 |
plic |
|
|
|
|
|
|
|
|
|
|
|
||
|
K |
|
72 |
|
|
|
|
|
|
3 |
|
|
24 |
|
|
|
|
Div |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
24 |
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
Idea |
1 |
|
Plan |
|
|
|
|
|
|
|
|||
|
1 |
|
2 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
Produce |
|
|
|
|
Calcula |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
-tions |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
Model |
|
|
|
|
|
|
|
Metis |
|
|
|
|
|
|
1 |
|
|
|
|
2 |
|
Euro- |
|
Negroid |
|
Mongo- |
||
|
pean |
|
|
loid |
|||
|
|
|
|
|
|
||
|
2 |
1 |
2 |
|
|
1 |
2 |
|
|
|
|
|
|
|
|
Quad- |
1 |
Mulatto |
|
|
|
Sambo |
|
|
|
|
|
|
|
|
|
roon |
|
|
|
|
|
|
|
Приложение 1
Примеры использования встроенных функций MATLAB для работы с графами.
>>N = 6; %количество вершин графа
>>W = [.41 .99 .51 .32 .15 .45 .38 .32]; %массив весов ребер
%функция для отображения разреженной матрицы
>> DG = sparse([6 1 2 2 3 4 4 5],[2 6 3 5 4 1 6 3],W, N, N)
%результат выполнения функции sparse DG =
(4,1) |
0.4500 |
(6,2) |
0.4100 |
(2,3) |
0.5100 |
(5,3) |
0.3200 |
(6,3) |
0.2900 |
(3,4) |
0.1500 |
(5,4) |
0.3600 |
(1,5) |
0.2100 |
(2,5) |
0.3200 |
(1,6) |
0.9900 |
(4,6) |
0.3800 |
%функция отображение графа
>> view(biograph(DG,{'A','BB','c','OL','dfg','d3'}, 'ShowWeights','on','ShowArrows', 'off'))
% Создание массива записей (структуры)
S(N,1) = struct('<имя_поля1>',<значение>, '<имя_поля2>',<значение>,…)
Приложение 2
Примеры работы с графами и создание словарей в Python 3.X.
#Работа с графами при помощи пакета igraph
import igraph |
|
|
G = igraph.Graph(directed = True) |
#создание ориентированного графа |
|
G.add_vertices(N) |
#добавление вершин в граф |
|
G.vs["label"] = ['A', 'B', 'C', …] |
#подписи вершин |
|
G.add_edges([(0,1),(0,2),(1,3), …]) |
#добавление ребер в граф |
G.es["weight"] = [2,4,5,…] |
#задание |
весов ребрам |
G.es["label"] = range(m) |
#подписи |
ребер |
#Построение графа
igraph.plot(G, bbox = (300,300), vertex_label_color = 'black', vertex_label_size = 10, vertex_size = 20, vertex_color = 'white', edge_width = [edge for edge in G.es['weight']])
#---------------------------------------------------------------------
#Работа с графами при помощи пакета networkx
import networkx as nx
G = nx.Graph() #Создание объекта пустого графа без ребер и узлов
#DG = nx.DiGraph(directed=True) # Создание объекта пустого ориентированного графа
G.add_nodes_from([0, 1, 2, …]) #Добавление вершин в виде списка
# G.add_nodes_from(['A', 'B', …]) #Добавление вершин в виде списка имен