ЛР / ЛР1 / Графы_ПР №1

Практическая работа №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 порядка выполнения п/р.

%результат выполнения функции sparse DG =

%функция отображение графа

>> view(biograph(DG,{'A','BB','c','OL','dfg','d3'}, 'ShowWeights','on','ShowArrows', 'off'))

% Создание массива записей (структуры)

S(N,1) = struct('<имя_поля1>',<значение>, '<имя_поля2>',<значение>,…)

Приложение 2

Примеры работы с графами и создание словарей в Python 3.X.

#Работа с графами при помощи пакета igraph

#Построение графа

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', …]) #Добавление вершин в виде списка имен