Вершина - орграф
Cтраница 1
Вершина орграфа называется источником, если все другие вершины орграфа достижимы из нее. Двойственным образом определяется сток. Существует, естественно, одинаковое число орграфов с источником и орграфов со стоком; эти совокупности взаимно обратны. [1]
Вершину орграфа, в которую не входит ни одна дуга, назовем начальной или входом, вершину, из которой ни одна дуга не выходит, - конечной или выходом, а остальные вершины - внутренними. [2]
Всякая вершина орграфа с одним входом М - достижима из него. [3]
Для вершин орграфа существуют параметры, называемые полустепенью исхода, полу-степенью захода и степенью вершины. Полустепеныо исхода р вершины х называется число исходящих из нее ребер. Полустепеныо захода q вершины х называется число входящих в нее ребер. [4]
Например, вершины орграфа на рис. 8.6 ( а) топологически отсортированы, а на рис. 8.6 ( Ь) нет. Топологическая сортировка может рассматриваться как процесс отыскания линейного порядка, в который может быть вложен данный частичный порядок. Нетрудно показать, что топологическая сортировка вершин орграфа возможна тогда и только тогда, когда он является ациклическим ( упр. Топологическая сортировка полезна при анализе схем действия, где большой и сложный план представляется как орграф, вершины которого соответствуют целям плана, а ребра - действиям. Топологическая сортировка дает порядок, в котором могут быть достигнуты цели. [5]
Найти все вершину орграфа, от которых существует путь заданной длины к выделенной вершине. [6]
Найти такую нумерацию вершин орграфа, при которой всякая дуга ведет от вершины с меньшим номером к вершине с большим номером. [7]
Пусть фиксирована нумерация вершин орграфа. Дуга называется обратной при этой нумерации, если она ведет от вершины с большим номером к вершине с меньшим номером. Построить такую нумерацию вершин заданного орграфа, при которой число обратных дуг минимально. [8]
Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины. [9]
Пусть х и у - различные вершины орграфа Т и в Т не существует дуги, идущей из х в у. Тогда наибольшее число попарно внутренне непересекающихся линейных путей в орграфе Г, идущих из х в у, равно наименьшему целому числу &, такому, что для некоторого разреза ( Их, Иу) между вершинами х и у в орграфе Г число стоков подмножества Их равно Ъ, и вершина х стоком для их не является. [10]
Подмножество Ха С X называется базой вершин орграфа L ( X, U, И. [11]
Тогда, очевидно, 2 содержит все вершины орграфа Г, обладающие свойством Р ( см. доказательство теоремы VI. Значит, как и в упомянутом доказательстве, дуги Ох определяют нужное нам дерево. [12]
Введенные в § 1 различные типы нумерации вершин орграфа, в частности Л - ну. [13]
Метод Демукрона основан на использовании матрицы смежности вершин орграфа. Пусть орграф представлен матрицей смежности АПУ. [14]
 |
Пример орграфа. [15] |
Страницы: 1 2 3