Обзор решения задач в выбранной области

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

Самые первые задачи теории графов восходят еще к Эйлеру (XVIII в.), хотя впервые термин «граф» появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г. [4]. С тех пор появилось множество новых задач, терминов, понятий, решений, связанных с этим разделом дискетной математики. Теория графов содержит довольно большое количество проблем, нерешённых и по сей день, и пока не доказанных гипотез.

В данной работе под вниманием оказывается одна из многих характеристик графа: связность. Связный граф — это граф, в котором между любой парой вершин существует как минимум один путь. Прямым применением теории графов и, в частности, такой его характеристики как связность выступает теория сетей. Рассмотрим один всем известный пример: Интернет. Все компьютеры и устройства, которые подключены во всемирную сеть, образуют по своей сути некий связный граф. Отдельно взятая пара компьютеров или любых других устройств может и не быть соединена между собой напрямую, однако от каждого из них можно передать информацию друг другу или же любому другому. Этот пример как раз наглядно иллюстрирует определение связности.

Существует множество способов проверки связности графов, в том числе основанных на алгоритмах поиска пути в графах [5]. Самый распространенный — алгоритм маркировки вершин. Эти алгоритмы просты в исполнении, и некоторым достаточно один раз посетить каждый узел. Однако в проблеме вычисления стохастической степени связности неориентированных графов не все так просто и эти алгоритмы будут недостаточно продуктивными.

Рассматриваемая задача по вычислению стохастической степени связности неориентированных графов содержит в себе набор подзадач, относящиеся не только к теории графов. Чтобы разобраться более детально, приведем следующий пример. Возьмем пример с железнодорожным сообщением в городах какого-либо региона (уже упомянутый пример из теории сетей тоже может быть наглядным). Если по каким-либо причинам (причина не существенна в данном изучении) были нарушены железнодорожные пути между городами A и B. При этом каждый из них связан с другими городами C, D, E и т. д. В данной ситуации есть вероятность, что город A или B (и возможно некоторые другие города, имевшие возможность попасть в дальний город только через один из этих двух) оказались изолированными от общей системы железнодорожной сети. Значит, связанность оказалась нарушенной. Так же и в компьютерных сетях при разрыве, например, кабеля один или несколько узлов могут оказаться изолированными. Однако в обоих случаях разрыв имел непредсказуемый характер. Невозможно было предугадать, какая связь будет выведена из строя. Это значит, что процесс имеет случайный характер. В данном ключе можно рассматривать граф, описывающий модель железнодорожного сообщения и компьютерной сети, как стохастическую систему. Ведь стохастическая система — это система, изменения в которой носят случайный характер. При случайных воздействиях, данных о состоянии системы недостаточно для предсказания событий в последующий момент времени. В данной работе граф рассматривается как стохастическая система со случайными воздействиями, приводящими к потере ребер и, в конечном счете, связности.

Вышеприведенные доводы приводят к необходимости совершенствования алгоритмов, проверяющих связность графов. Это открывает возможности для избегания алгоритмов обхода всех звеньев в графе, таких как поиски в глубину и в ширину.

Так как получаемые данные являются экспериментальными, то для их достоверности необходимо верно определить размер выборки. В теории вероятностей существую методы поиска объема выборки и доверительных интервалов для них.

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