Описание алгоритмов решения задачи

 

Решение задачи отыскания математического ожидания количества ребер, которые надо удалить (добавить) случайным образом до исчезновения (появления) пути, соединяющего левую и правую границы сети, проводится последовательным исполнением следующих алгоритмов.

Алгоритм генерации регулярных графов со степенью вершин 3,4,5,6,7,8 на прямоугольной сетке. В качестве будем рассматривать регулярные графы, изображенные на рисунках 2.11 и 2.12.

 

Рис. 2.11. Граф G _3,6,6 Рис. 2.12. Граф G _3,6,6

 

Забегая вперед, отметим, что результаты расчетов, выполненных для регулярных графов обоих типов, изображенных на рисунках 2.11 и 2.12, совпадают при достаточно больших размерах этих графов, то есть при достаточно больших .

Графы , , , , изображены на рисунках 2.13 –2.17 соответственно.

 

 

Рис. 2.13. Граф G _4,6,6 Рис. 2.14. Граф G _5,6,6

 

Рис. 2.15. Граф G _6,6,6 Рис. 2.16. Граф G _7,6,6

Рис. 2.17. Граф G _8,6,6

Моделирование случайного процесса удаления ребер. Моделирование случайного процесса удаления ребер на данных регулярных сетках проводим следующим образом:

– составим список всех ребер графа и последовательно занумеруем их, начиная с нуля;

– при помощи генератора случайных чисел получим случайное число от 0 до количества ребер;

– удалим ребро с соответствующим номером;

– вычеркнем удаленное ребро из списка ребер и уменьшим количество ребер, которые можно удалять.

Такая организация процесса удаления ребер не позволяет дважды удалить одно и то же ребро и обеспечивает равновероятный выбор очередного ребра для удаления.

В качестве генератора случайных чисел использовался генератор случайных чисел компании Microsoft из инструментария для разработки криптографических программ. (Microsoft Crypto API). Согласно обзорам компании Microsoft, указанный генератор производит случайные числа “лучшего качества”, чем генератор случайных чисел из стандартной библиотеки языка C++, используемого в настоящей работе для написания компьютерных программ, предназначенных для проведения численных экспериментов.

Процесс добавления ребер к пустому графу при решении двойственной задачи прочности сети будем проводить аналогично.

Нахождение пути между сторонами прямоугольной сетки. Всякий раз, после удаления (или добавления, в случае двойственной задачи) очередного ребра, следует проверять наличие пути, соединяющего левую и правую стороны сетки. Поиск пути на графе выполняется стандартным алгоритмом поиска в глубину – алгоритмом переборного характера, сильно замедляющим процесс вычислений. Для ускорения вычислений и избегания излишних повторений трудоёмкой процедуры поиска пути в глубину, будем использовать два дополнительных эвристических соображения:

– каждый раз будем запоминать найденный путь между границами сетки и, при удалении очередного ребра, сначала проверять, не принадлежит ли удаленное ребро найденному на предыдущем шаге пути. Очевидно, что если вновь удаленное ребро не принадлежит найденному ранее пути, то алгоритм поиска нового пути запускать не надо – путь между границами сетки и так есть;

– будем запоминать те вершины на левой стороне сетки, из которых не удалось проложить путь на правую сторону – эти вершины тупиковые. При дальнейшем удалении ребер из графа, эти вершины так и останутся тупиковыми, поскольку пути из них на правую сторону сетки образоваться уже не может и запускать из них процесс поиска пути бессмысленно;

– при поиске в глубину необходимо быстро просматривать список вершин, смежных с данной вершиной. Учитывая то, что рассматриваемые графы имеют фиксированную степень вершин, выберем, при организации вычислений, представление графа списком ребер.

Критерий остановки вычислений. Процесс вычисления математического ожидания организуем как последовательность испытаний, в ходе каждого из которых исходный граф будет подвергаться последовательному случайному добавлению ребер до появления пути между левой и правой границами сетки. Результатом испытания является количество добавленных ребер. Испытания должны проводиться многократно для возможно более точного вычисления среднего значения количества добавленных ребер (математического ожидания). Для остановки серии испытаний используем стандартный метод составления гистограммы результатов испытаний. В момент появления пути, соединяющего левую и правую стороны сетки, мы запоминаем количество добавленных ребер и модифицируем гистограмму (фактически – таблицу плотности распределения результатов испытаний), прибавляя в –й столбец гистограммы единицу. Остается выбрать критерий остановки, то есть определить момент, когда мы можем считать, что достаточно долго наблюдали случайный процесс, чтобы остановиться и посчитать математическое ожидание.

На рисунках 2.18 и 2.19 изображены графики плотностей распределения (гистограммы) результатов испытаний графа G _4,20,20 (7350 и 37530 испытаний соответственно).

Рис. 2.18. Плотность распределения результатов 7350 испытаний

графа G_4,20,20

 

Рис. 2.19. Плотность распределения результатов 37530 испытаний

графа G_4,20,20.

Мы видим, что в обоих случаях плотности распределений имеют ярко выраженную область сгущения. Математические ожидания, посчитанные по соответствующим гистограммам, различаются менее чем на 0,5.

Представленные графики плотности распределения “очень похожи” на графики плотности нормального распределения. На рисунках 2.20 и 2.21 на графики плотности распределений, полученные в процессе наших испытаний, наложены графики плотности нормального распределения со средним значением и среднеквадратичным отклонением .

 

Рис. 2.20. Рис. 2.21.

Исходя из вышеизложенного, с практически приемлемой точностью вычислений, можно принять следующий критерий остановки серии испытаний для вычисления математического ожидания. Будем останавливать испытания тогда, когда в какой-то точке гистограммы накопится 500 значений. Эксперименты показали, что при таком критерии остановки имеем гарантированную точность 0,1 для расчета математического ожидания и 0,001 для значения отношения математического ожидания к количеству вершин или ребер рассматриваемых нами графов.

Краткое описание программ. Для решения поставленной задачи был разработан класс CRectGraph, позволяющий обрабатывать графы произвольного размера со степенями вершин до 256 на прямоугольной сетке. Для реализации вычислительного эксперимента написана программа RectGraphCalc.exe, осуществляющая расчет математического ожидания количества ребер графа , которое следует случайным образом добавить к графу , чтобы в графе появился путь, соединяющий левую и правую сторону сетки.

Для тестирования и отладки класса CRectGraph разработана программа GraphView.exe, позволяющая пошагово следить за процессом удаления (добавления) ребер и поиском пути в графе. Виды экранов программы приведены на следующих рисунках.

На рисунке 2.22 изображена прямоугольная сетка , к которой случайным образом добавляются ребра графа _. Добавленные ребра отображены черным цветом. Отсутствующие – белым. В момент добавления ребра № 34 из 72 возможных ребер, образовался путь, закрашенный на рисунке 2.22 красным цветом. Последнее добавленное ребро, приведшее к образованию пути, закрашено зеленым.

Рис. 2.22. Добавление ребер к .

 

На рисунке 2.23 изображена прямоугольная сетка , из которой случайным образом удаляются ребра _. Удаленные ребра отображены белым цветом, оставшиеся ребра – черным. В момент удаления ребра № 112 из 144 возможных ребер, разорвался последний путь, закрашенный на рисунке красным цветом. Последнее удаленное ребро, приведшее к уничтожению пути, закрашено зеленым.

Рис. 2.23. Удаление ребер

 

На рисунке 2.24 приведено окно настроек программы. Пользователь может задать ширину и высоту сетки, степень вершин, выбрать режим работы (удаление или добавление ребер).

В программе предусмотрена дополнительная возможность – устранение искажений результатов вычислений, возникающих за счет «краевого эффекта». Краевой эффект на регулярных прямоугольных сетках проявляется в том, что вершины графа, расположенные на верхнем и нижнем крае сетки меньшие имеют степени вершин, нежели внутренние вершины сетки, что нарушает регулярность графа на краях сетки. Для минимизации искажений результатов вычислений, вызванных краевым эффектом, в написанной программе имеется возможность “свернуть сетку в цилиндр”. Для этого склеиваются между собой соответствующие свободные ребра с верхней и с нижней сторон сети, после чего рассматриваемый граф оказывается расположенным на цилиндре и становится полностью регулярным.

Рис. 2.24. Окно настроек программы