Мои программы
Zurück
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
[color=purple][size=30]Программа
«Построение случайного графа»[/size]
[/color]
[size=20][color=maroon]1.Общее[/color][/size]
Теория графов:это набор алгоритмов для вычисления разных характеристик графов.
Чтобы оценить алгоритмы, надо провести проверочные расчёты.
Для получения полезной информации расчёты следует проводить над однотипными графами.
Таким объектом могут быть случайные графы.
То есть графы параметры, которых имеют вероятностный вид.
Конкретно.
Есть граф G с n вершинами.
Случайным образом вводятся ребра (дуги).
Принято, что ребро соответствует двум противоположно направленным дугам.
По определенному порядку вводятся дуги.
Важнейшей характеристикой графа являютсястепени вершин.
Степень вершины это число ребёр, инцидентных вершине или число дуг исходящих (входящих) дуг.
Распределение степеней вершин зависит от алгоритма построения случайного графа.
Граф G – связный.
То есть между каждыми двумя вершинами есть путь из рёбер или однонаправленных дуг.
[size=20][color=maroon]2.Алгоритм – основной цикл[/color][/size]
Алгоритм построения случайного графа сходен с алгоритмом случайного дерева.
Исходное состояние: nподграфов.
По одной вершине в подграфе.
Далее случайным образом выбираются подграфыbи d.
К подграфуb присоединяются вершины подграфа d.
Между вершинами подграфов случайным образом вводятся по паре противоположно направленных дуг.
Обязательно между вершиной подграфаb и вершиной подграфаd не входившей в подграф b.
Так заполняется матрица смежности.
Между каждой парой вершин только одна пара противоположно направленных дуг.
Расчёты заканчиваются, если в подграфе n вершин.
[size=20][color=maroon]3.Алгоритм – суперцикл[/color][/size]
Для получения усредненных величин введен суперцикл.
На каждой итерации основного цикла выполняется основной цикл.
[size=20][color=maroon]4.Исходные[/color][/size]
n- число вершин графа
tt- допустимое число итераций основного цикла
x – число итераций суперцикла
CC -
[size=20][color=maroon]5.Вывод[/color][/size]
K – счетчик основного цикла
u:array [1..n, 1 ..n] - подграфы
p : array [1..n,1..n]- матрица смежности
uu :array [1..5*n] – величина k при формировании подграфа[color=green][/color]
r :array [1..n]- - суммарные степени вершин
s1:array [1..100, 1..2]- последовательность пар подграфов b и d
hh :array [1..x]- матрица вспомогательная
r1 : array [1..n]- усредненные степени вершин
ff: array [1..n]- матрица вспомогательная
r2 : array [1..n]- матрица вспомогательная
r3 : array [1..n] -матрица вспомогательная
Вспомогательные матрицы намечено использовать для изучения распределения степеней вершин
[size=20][color=maroon]6.Программа A Graf[/color][/size]
Программа на Дельфи 7
[size=20]Скачать[/size]