Практикум по дисциплине «Дискретная математика»
жүктеу/скачать 0,98 Mb.
|
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
|
Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем  . Присваиваем k:=k+1 и переходим к 2).
Замечания Множество  называется фронтом волны kго уровня.
Вершины  могут быть выделены неоднозначно, что соответствует случаю, если  несколько минимальных путей из  в  .
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу расстояний R(D) между его вершинами. Это квадратная матрица размерности  , элементы главной диагонали которой равны нулю ( , i=1,..,n).
Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (  , если  ). Далее построчно заполняем матрицу следующим образом.
Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i-тая и на пересечении с j-тым столбцом стоит единица (то есть  ). Это значит, что из вершины  можно попасть в вершину  за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент  . Тогда из вершины в вершину  можно попасть за два шага. Таким образом, можно записать  . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
жүктеу/скачать 0,98 Mb. Достарыңызбен бөлісу:
|