Вершина - орграф
Cтраница 3
 |
Система ПЕРТ. приорететная структура курсов. [31] |
Система ПЕРТ ( см. рис. 8.2) - это просто орграф, представляющий данную приоритетную структуру. Вершины орграфа в данном случае - восемь курсов. Дуги орграфа отражают представленные в таблице требования, необходимые для усвоения данного курса. [32]
Рассмотрим теперь задачу о нахождении связки путей из х в у, имеющей максимально возможную мощность. На множестве вершин орграфа Г зададим функцию /, которая каждой вершине V сопоставляет неотрицательное целое число / ( У), называемое ее пропускной способностью. [33]
Степень входа вершины v равна нулю. Степени входа вершин орграфа G, отличных от v, полож: ительны. [34]
Пусть Г - орграф и г - какая-то его вершина. Если для каждой вершины орграфа Г, отличной от г, в нем существует путь, идущий из г в эту вершину, то орграф Г имеет растущее из г остовное дерево. [35]
Обобщенный и ненаправленный мультигра-фы, отображающие такую схему, приведены на рис. 1 - 25, а. Отсутствие путей между вершинами несвязного орграфа свидетельствует об отсутствии пути для тока между узлами соответствующей схемы. [36]
В нем присутствует контур abode а, проходящий через все вершины. Поэтому для любой пары вершин орграфа найдется путь, ведущий от первой ко второй. [37]
ЕЕ U, если понятие, соответствующее вершине Xj ЕЕ X, следует из понятия, соответствующего вершине х, ЕЕ X. Легко убедиться, что база вершин полученного орграфа G ( X, U) соответствует системе базовых понятий. [38]
Рассмотрим задачу отыскания такого минимального по числу путей покрытия, а именно подмножества множества всех s - f - путей, что каждая вершина орграфа принадлежит хотя бы одному такому пути. [39]
На главной диагонали A ( G) должны стоять нули. Матрица A ( G) в противоположность матрице смежности обычного графа не обязана быть симметрической: она обладает этим свойством тогда и только тогда, когда любые две разные вершины орграфа либо не смежны, либо соединены двумя противоположно направленными дугами. [40]
Пусть фиксирована нумерация вершин орграфа. Дуга называется обратной при этой нумерации, если она ведет от вершины с большим номером к вершине с меньшим номером. Построить такую нумерацию вершин заданного орграфа, при которой число обратных дуг минимально. [41]
Например, вершины орграфа на рис. 8.6 ( а) топологически отсортированы, а на рис. 8.6 ( Ь) нет. Топологическая сортировка может рассматриваться как процесс отыскания линейного порядка, в который может быть вложен данный частичный порядок. Нетрудно показать, что топологическая сортировка вершин орграфа возможна тогда и только тогда, когда он является ациклическим ( упр. Топологическая сортировка полезна при анализе схем действия, где большой и сложный план представляется как орграф, вершины которого соответствуют целям плана, а ребра - действиям. Топологическая сортировка дает порядок, в котором могут быть достигнуты цели. [42]
B an в зависимости от шага алгоритма d хранятся степени массива а. Последней степенью массива а является ( п - 1) - я, т.к. максимально возможный минимальный путь в орграфе равен ( п - 1), в этом случае он включает в себя все вершины орграфа. [43]
Страницы: 1 2 3