Порядок выполнения ЛР

Этап 1.

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

2. Студент должен подробно изложить ход рассуждений при выводе формулы, сопроводив эти рассуждения изображениями исходного графа и «дерева» его упрощений, которые возникают в процессе вывода формулы.

3. Результирующая формула должна быть представлена в виде многочлена .

Этап 2.

1. Способ задания топологии графа в программе студент выбирает самостоятельно (например, ввод с клавиатуры, в виде матрицы смежности, загружаемой из файла, или в виде списка ребер).

2. Для разрабатываемой программы необходимо обеспечить возможность изменения топологии случайного графа (только для множеств Y и P).

3. Алгоритм нахождения пути в графе студент выбирает самостоятельно (например, на основе упрощенного алгоритма Дейкстры для нахождения кратчайших путей в графе).

4. Вероятность существования пути в графе может быть получена путем полного перебора всех возможных вариантов случайного графа с учетом вероятности их появления.

5. В программе также должно быть представлено вычисление вероятности существования пути в графе по формуле, полученной на этапе 1.

Вопросы для самостоятельной подготовки

1. Определить максимальное число ребер в обыкновенном неориентированном графе с n вершинами.

2. Определить минимально возможное число ребер в обыкновенном неориентированном связном графе с n вершинами.

3. Для второго пути решения задачи 1 вывести общую формулу для расчета значений K и N.