Практическая работа №3
Случайные графы и их свойства
1. Цель работы
Рассмотреть различные подходы к генерации случайных графов в ЭВМ. Провести анализ свойств созданных графов.
2. Необходимые теоретические сведения
Здесь и далее в практической работе будут рассматриваться
неориентированные и невзвешенные графы.
Степень вершины – количество ребер, инцидентных этой вершине.
Спектр степеней графа – это гистограмма распределения частот степеней всех вершин графа.
Расстояние между вершинами — наименьшее число рёбер пути,
соединяющего две вершины.
Диаметр графа – это максимальное расстояние между всеми парами вершин.
Компонента связности графа – подмножество вершин графа, такое,
что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину из другого множества.
3.Порядок выполнения работы
1.Выбрать вариант из Таблицы 1.
2.Согласно выбранному варианту, реализовать функцию создания матрицы смежности случайного графа, основываясь на заданном алгоритме. Визуализировать полученный граф.
3.Реализовать функцию поиска спектра степеней графа (см. раздел 2).
Построить полученный спектр для графа, построенного по заданию пункта 2.
4.Согласно своему варианту выполнить задание из Таблицы 2. Построить соответствующие графики. (Встроенные функции, которые можно использовать для выполнения данного задания приведены в Приложении 1 и Приложении 2).
4.Содержание отчета
1.Цель работы.
2.Описание (листинг, комментарии) и результаты выполнения разработанных программ, реализующих пункты 2-4 порядка выполнения п/р.
3.Изображение графа, полученного в пункте 2 порядка выполнения п/р.
4.Изображение спектра степеней графа, полученное в результате выполнения пункта 3 порядка выполнения п/р.
5.Графики, полученные в результате выполнения пункта 4 порядка выполнения п/р.
6.Количественные и качественные выводы, полученные на основе проведенного исследования свойств случайных графов. Привести пример объекта реального мира, структуру которого может описывать полученный граф.
4. Варианты заданий
Таблица 1 – Варианты заданий (тип случайного графа)
№
Алгоритм создания графа
варианта
Деревья
На каждом шаге добавляется новая вершина, для которой выбирается только один сосед из уже существующих вершин (N = 5, 10, … 100 – количество вершин в дереве).
Вероятность выбора i-ой вершины в качестве соседа для новой
1вершины равна pi = 
tik , здесь ti – «время жизни» i-ой вершины (количество шагов, на которых вершина уже существовала),
2
3
4
5
6
коэффициент |
|
на каждом шаге выбирается так, что сумма всех |
pi равна 1.
Вероятность выбора i-ой вершины в качестве соседа для новой
вершины равна |
k |
, здесь ti |
– «время жизни» i-ой вершины |
pi = ti |
(количество шагов, на которых вершина уже существовала), коэффициент на каждом шаге выбирается так, что сумма всех pi равна 1.
Вероятность выбора i-ой вершины в качестве соседа для новой
вершины равна |
pi = |
k |
, здесь |
di |
– степень i-ой вершины, |
di |
|||||
коэффициент |
на каждом шаге выбирается так, что сумма всех |
||||
pi равна 1.
Вероятность выбора i-ой вершины в качестве соседа для новой
вершины равна |
k |
, здесь |
di |
– степень i-ой вершины, |
pi = di |
||||
коэффициент |
на каждом шаге выбирается так, что сумма всех |
|||
pi равна 1.
Вероятность выбора i-ой вершины в качестве соседа для новой
вершины равна |
k |
, здесь li – расстояние от i-ой вершины |
pi = li |
||
до корня, коэффициент |
на каждом шаге выбирается так, что |
|
сумма всех pi равна 1.
Вероятность выбора i-ой вершины в качестве соседа для новой
вершины равна |
k |
, здесь li – расстояние от i-ой вершины |
||
pi = li |
|
|||
до корня, коэффициент |
|
на каждом шаге выбирается так, что |
||
сумма всех pi равна 1.
Регулярные структуры
Дана квадратная решетка размером N на N. Закрашивание клетки такой решетки эквивалентно тому, что в граф добавляется вершина. Между двумя вершинами графа ставится ребро тогда, когда клетки решетки, соответствующие этим вершинам, прилегают друг к другу по горизонтали или вертикали (N = 10, р меняется от 0 до 1 с шагом 0.05).
7Делать обход каждой клетки решетки и принимать решение о закрашивании (p – вероятность закрашивания).
Закрасить M случайно выбранных клеток ( M = p N 2 , выбранные
8клетки могут повторяться, вершины при повторе не дублируются).
9Закрасить M случайно выбранных клеток ( M = p N 2 , выбранные клетки не должны повторяться).
Закрасить M случайно выбранных областей, имеющих форму
квадрата 2 на 2 клетки ( M = |
|
p N |
2 |
4 |
|
, расположение области |
|
|
|
||||
|
|
|
|
|
||
определяется координатами ее |
левого |
верхнего угла, квадрат |
||||
10должен целиком располагаться на решетке, области могут полностью или частично перекрывать друг друга, но вершины
при этом не |
дублируются. |
- округление вверх до целого |
числа). |
|
|
|
|
|
Делать обход |
каждой клетки |
решетки и закрашивать ее с |
11вероятностью p, если предыдущая клетка закрашена, и вероятностью 1 − p , если предыдущая клетка не закрашена.
На каждом столбце решетки случайно располагать область, имеющую форму вертикальной линии длинной M = p N
12клеток (расположение области определяется координатами ее верхней клетки, линия должна целиком располагаться на решетке, - округление вверх до целого числа).
Графы общего вида
(N = 100 – количество вершин в графе, р меняется от 0 до 1 с шагом 0.05)
13 |
Для каждого ребра полносвязного графа принимать решение об |
||
удалении этого ребра с вероятностью 1 − p . |
|||
|
|||
|
|
|
|
|
1, 2, |
. Разбить данное множество на N |
|
|
Задано множество |
||
подмножеств, следующим образом: каждый элемент исходного множества может попасть в очередное подмножество с
14вероятностью p (M = N
2, N , 2N ). Здесь номер вершины графа соответствует номеру подмножества (N штук). Ребро между двумя вершинами ставится тогда, когда в подмножествах, соответствующих данным вершинам есть общие элементы из
|
множества |
1, 2, |
. |
|
|
|
|
|
||||
|
|
|||||||||||
|
В квадратную область размером M на M помещается N точек. Две |
|||||||||||
|
точки соединяются ребром, если они находятся друг от друга на |
|||||||||||
15 |
расстоянии |
|
|
не |
|
|
большем |
чем |
R |
|||
|
|
|
|
|
||||||||
|
(R = |
|
, M = |
|
2, |
|
, N ). |
|
|
|||
|
pM 2 |
|
|
|||||||||
|
N |
N |
|
|
||||||||
|
|
|
|
|
|
|
|
|||||
16 |
Добавить |
|
M |
ребер |
между случайными |
парами |
вершин |
|||||
|
( |
) |
|
|
|
|
|
ребро в |
||||
|
|
|
|
|
||||||||
|
( M = pN |
|
N −1 |
2 , пары вершин могут повторяться, |
||||||||
|
таком случае не удваивается, |
- округление вверх до целого |
|||
|
числа). |
|
|
|
|
|
|
||||
|
При появлении новой вершины, для нее генерируется M соседей. |
||||
|
Вероятность того, что появившаяся вершина станет соседом i-ой |
||||
|
вершины равна |
qi = (di +1), где |
di – степень i-ой вершины, |
||
17 |
коэффициент |
на каждом шаге выбирается так, что сумма всех |
|||
qi равна 1. После выбора очередной вершины-соседа, и qi |
|||||
|
|||||
|
пересчитываются, и следующий сосед выбирается из оставшихся |
||||
|
вершин ( M = p (N −1) 2 , - |
округление вверх до целого |
|||
|
|
|
|
|
|
|
числа). |
|
|
|
|
|
|
|
|
||
|
В квадратную область размером |
N на |
N помещается точка. |
||
|
Последующие точки ставятся в квадрате со стороной R с центром |
||||
|
в случайной уже существующей точке. Здесь точка соответствует |
||||
18вершине графа. Ребро ставится между парой вершин, если расстояние между соответствующими им точками не превышает
|
|
R0 (где R0 = pR, |
R = |
N 16, |
N 8, |
N |
4). |
|
||||
|
|
|
|
|
|
|||||||
|
Таблица 2 – Варианты заданий (свойства случайного графа) |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
№ |
|
|
|
Задание |
|
|
|
|
|
|
||
варианта |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|||||||||
|
|
Построить графики зависимости среднего диаметра (см. раздел |
|
|||||||||
|
|
|
|
|
|
|
||||||
1 – 6 |
|
2) графа от количества вершин при k =1, 4 |
(объем выборки для |
|
||||||||
|
усреднения выбрать самостоятельно, должно быть по одному |
|
||||||||||
|
|
|
||||||||||
|
|
графику для каждого значения k). |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|||||||
|
|
Построить график зависимости вероятности существования пути |
|
|||||||||
|
|
между первым и последним столбцами решетки от вероятности |
|
|||||||||
7 – 12 |
|
закрашивания |
клетки |
(объем |
выборки |
для вычисления |
|
|||||
|
вероятности существования пути выбрать самостоятельно, если |
|
||||||||||
|
|
|
||||||||||
|
|
задано несколько значений параметра М, должно быть по |
|
|||||||||
|
|
одному графику для каждого значения). |
|
|
|
|
||||||
|
|
|
|
|||||||||
|
|
Построить график зависимости среднего количества компонент |
|
|||||||||
|
|
связанности от параметра p (объем выборки для усреднения |
|
|||||||||
13 – 18 |
выбрать самостоятельно если |
задано |
|
несколько значений |
|
|||||||
|
|
параметра М или R, должно быть по одному графику для |
|
|||||||||
|
|
каждого значения). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Приложение 1
Встроенные функции для работы с графами на языке python.
#Встроенные функции из пакета igraph
# G - объект типа Graph
#Функция, вычисляющая диаметр графа
G.diameter(directed=True, unconn=True, weights=None)
#Функция, определяющая наличие связи между вершинами графа
G. vertex_connectivity(source=-1, target=-1, checks=True, neighbors="error")
#Функция, вычисляющая компоненты связности для графа
G. components(mode=STRONG)
#Встроенные функции из пакета networkx
#Подробное описание функций в документации к пакету: Algorithms — NetworkX 2.7.1 documentation
#Функция, вычисляющая диаметр графа diameter(G, e=None, usebounds=False)
#Функция, определяющая наличие связи между вершинами графа networkx.node_connectivity(G, s, t, flow_func=None)
#Функция, вычисляющая компоненты связности для графа networkx.connected_components(G)
Приложение 2
Встроенные функции MATLAB из библиотеки biograph для работы с
графами.
%G – список смежности
%Функция поиска кратчайшего пути в графе – можно использовать и для поиска диаметра и для поиска связи между вершинами
[dist, path, pred] = graphshortestpath(G, S, T)
%Функция поиска компонент связности графа
[S, C] = graphconncomp(G)