for t :

                               flow = find_flow(s, t)

                               ans = min(ans, flow)

3.3. Алгоритм вычисления вершинной связности графа

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

Вершинной связностью графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Вершинная связность несвязного графа равна 0, а связность связного графа равна 1 [3].

Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную 1. Для этого воспользуемся следующим приёмом.

Разобьем каждую вершину v графа на две вершины v1 и v2. Все ребра, которые входили в вершину v, будут входить в v1. Все ребра, которые выходили из вершины v, будут выходить из v2. Так же добавим ребро (v1, v2) с пропускной способностью 1. Пример подобного преобразования показан на рисунке 5.

Рисунок 5 – Преобразование вершин графа

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

НЕ нашли? Не то? Что вы ищете?

4. СТРАТЕГИИ ИЗМЕНЕНИЯ ГРАФА

Целью данной работы является исследование процессов изменения характеристик графа G с течением времени. Для проведения необходимых расчётов рассматриваются три основные стратегии изменения графа G.

Стратегия 1. Вершина, достигающая при движении границы круга, в котором генерировался граф, отражается от неё по принципу «угол отражения равен углу падения», после чего продолжает движение с новым вектором скорости, до следующего достижения границы области.

Стратегия 2. Вершина, достигающая при движении границы круга, исключается из графа.

Стратегия 3. Круг радиуса R используется только в момент формирования начального графа. В дальнейшем на процесс движения вершин графа отсутствуют какие-либо ограничения.

В результате, начиная с момента времени t = 0, значения связности 1 или 0, а также вершинной и рёберной связностей представляют собой случайные процессы, характеристики которых необходимо оценить.

Для каждой из стратегий необходимо вычислить зависимость вероятности связности графа от времени P(t), Mл(t) – среднее значение рёберной связности. Mk(t) – среднее значение вершинной связности. Mq(t) – среднее количество рёбер.

Для стратегии 2 представляет интерес процесс изменения количества вершин в графе с течением времени. Поэтому в этом случае необходимо вычислить среднее количество вершин в графе – Mn(t).

Получение этих оценок осуществляется следующим образом. Тело основного цикла программы состоит из этапа генерации случайного графа. Затем для сгенерированного графа осуществляется движение его вершин с помощью вызова процедуры move(g, dt, n), параметрами которой являются: g – указатель на графовую структуру данных, dt – единица изменения времени, n – номер стратегии движения вершин 1, 2 или 3.

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

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

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

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

vector <float> coherence_probability(0) – Вектор вероятностей связности графа.

vector <float> number_of_ribs(0) – Количество рёбер в графе.

vector <float> rib_coherence(0) – Изменение рёберной связности графа.

vector <float> node_coherence(0) – Изменение вершинной связности графа.

vector <float> number_of_nodes(0) – Изменение количества вершин в графе

5. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ

5.1. Исследование 1

Исследование 1 представляет собой анализ изменения графовых характеристик связности для случайных графов, состоящих из 10, 15, 25 вершин для первой стратегии изменения графа.

Радиус генерации графа – R = 1,5. Длина вектора скорости каждой вершины равна 1. Движение вершин графа осуществляется, начиная с нулевого значения системного времени и заканчивая моментом 2,5. Шаг изменения переменной системного времени
dt = 0,1.

В результате вычислений были сформированы 4 вектора размерностью 25. Вектор значений вероятностей связности случайного графа. Вектор значений среднего количества рёбер случайного графа. А также вектор значений вершинной и рёберной связностей случайного графа.

В каждой позиции этих векторов хранится значение графовых характеристик связности, соответствующее моментам времени t от 0 до 25.

Графики, построенные с помощью данных, полученных благодаря проведённым расчётам, представлены на рисунках 6 – 17.

Рисунок 6 – График зависимости вероятности связности графа из 10 вершин от времени

Рисунок 7 – График зависимости вероятности связности графа из 15 вершин от времени

Рисунок 8 – График зависимости вероятности связности графа из 25 вершин от времени

Проанализировав графики зависимости вероятности связности графа от времени, можно заметить на нём некоторую периодичность.

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

Можно сделать вывод, что при увеличении концентрации вершин в круге генерации вероятность связности графа значительно возрастает.

Рисунок 9 – График изменения среднего числа рёбер графа из 10 вершин

Рисунок 10 – График изменения среднего числа рёбер графа из 15 вершин

Рисунок 11 – График изменения среднего числа рёбер графа из 25 вершин

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

Рисунок 12 – График изменения среднего значения вершинной связности графа из 10 вершин

Рисунок 13 – График изменения среднего значения вершинной связности графа из 15 вершин

Рисунок 14 – График изменения среднего значения вершинной связности графа из 25 вершин

Рисунок 15 – График изменения среднего значения рёберной связности графа из 10 вершин

Рисунок 16 – График изменения среднего значения рёберной связности графа из 15 вершин

Рисунок 17 – График изменения среднего значения вершинной связности графа из 25 вершин

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

5.2. Исследование 2

Исследование 2 представляет собой анализ изменения графовых характеристик связности для случайных графов, состоящих из 15, 20, 30 вершин для второй стратегии изменения графа.

Радиус генерации графа – R = 1,5 для первых двух графов и R = 2 для третьего графа. Длина вектора скорости каждой вершины равна 1. Движение вершин графа осуществляется, начиная с нулевого значения системного времени и заканчивая моментом 2,0 для первых двух графов и моментом 2,5 для третьего графа. Шаг изменения переменной системного времени dt = 0,1.

Графики, построенные с помощью данных, полученных благодаря проведённым расчётам, представлены на рисунках 18 – 32.

Рисунок 18 – График зависимости вероятности связности графа из 15 вершин от времени

Рисунок 19 – График изменения среднего числа вершин графа из 15 вершин

Рисунок 20 – График изменения среднего числа рёбер графа из 15 вершин

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9