Задание на лабораторную работу N1

Задан случайный граф , где X={ x_i } – множество вершин, Y ={(x_i,x_j)} – множество ребер, P ={ p_i } – множество вероятностей существования ребер. Вероятности существования ребер равны между собой и равны p.

В ходе выполнения лабораторной работы необходимо выполнить следующие действия.

1. Вычислить вероятность существования пути между заданной парой вершин x_i, x_j в графе .

2. Построить зависимость вероятности существования пути в случайном графе от вероятности существования ребра.

Лабораторная работа состоит из двух этапов.

Этап 1. Вывод формулы вероятности существования пути в случайном графе, как функции от p (по аналогии с третьим путем решения задачи 1).

Этап 2. Разработка программы вычисления вероятности существования пути в случайном графе (по аналогии со вторым путем решения задачи 1).

Критерием правильности выполнения ЛР является совпадение результатов первого и второго этапов. Совпадение должно подтверждаться графиком , где p изменяется в интервале от 0 до 1 с шагом 0.1.