Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Сильно связанные компоненты орграфа, их частичное упорядочение и преобразование орграфа в сеть". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу: там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же выполнение ИДЗ проводится по следующему алгоритму.
- Строим матрицу смежности вершин орграфа.
- Умножаем эту матрицу саму на себя (как булевскую) до тех пор, пока она не перестанет изменяться.
- Путём перестановки строк и столбцов приводим её к блочно-верхне-треугольному виду.
- Блоки на главной диагонали дают сильно связанные компоненты, а блоки выше главной диагонали − частичное упорядочение.
- Заменяем каждую компоненту сильной связности одной вершиной. Дуги внутри компоненты (они образуют орцикл) удаляем.
- Если после такой замены образуются кратные дуги, заменем их одной. Веса дуг складываем.
- Если из первой вершины недостижима какая-либо другая, добавляем фиктивную стартовую вершину. Проводим из неё дуги в первую вершину и в те, которые недостижимы из первой. Веса этих дуг берём нулевыми (в некоторых задачах нужно будет заменить их бесконечными).
- Если последняя вершина недостижима из какой-либо другой, добавляем фиктивную конечную вершину. Проводим дуги в неё из последней вершины и из тех, из которых последняя вершина недостижима. Веса этих дуг берём нулевыми (в некоторых задачах нужно будет заменить их бесконечными).
Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.
Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести
координаты вершин для рисования орграфа. Они задаются
в виде матрицы
В следующей области ввода левая часть − обязательная для заполнения. В ней определяется структура орграфа.
Каждая дуга в орграфе соединяет две вершины. Номера этих вершин задаются в виде матрицы
x (пробел) y |
v1 (пробел) v2 | Вес |