Ориентированный маршрут

Cтраница 1

Ориентированный маршрут называется путем, а ориентированный простой цикл - контуром. [1]

ВХС существует ориентированный маршрут в г-е водохранилище, а также само г-е водохранилище. [2]

Путем ( или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. [3]

Выберем замкнутую последовательность дуг ( ориентированный маршрут) Р такую, что Р проходит через все вершины D. Начальная и конечная вершины не обязательно должны фиксироваться. [4]

В последнем случае говорят, что ориентированный маршрут соединяет UQ и vn или, точнее, что он идет из иа в ип. [5]

Эйлеров орграф. [6]

Орграф называется эйлеровым, если существует замкнутый остовный ориентированный маршрут, проходящий через каждую дугу точно один раз. Такой маршрут называется эйлеровым контуром. Один критерий эйлеровости орграфа состоит в следующем ( см. Харари [1], стр. Например, орграф, показанный на рис. 1.8.1, не является эйлеровым, а орграф D, изображенный на рис. 1.8.2, эйлеров. [7]

Теорема 5.5. Матрица V дает число ориентированных маршрутов длины п между любыми двумя вершинами ориентированного графа. [8]

В настоящее время широко используется аэромагнитная съемка, выполняемая по строго ориентированным маршрутам полета самолета. [9]

В этом случае каждая вершина достижима из любой другой вершины ориентированным маршрутом, состоящим из m дуг, и граф, соответствующий Vm, является полным ( действительно, он имеет дугу, направленную от любой другой) и имеет петли у каждой вершины. [10]

Докажите, что ( i, /) - й элемент из Ak равен числу ориентированных маршрутов длины fe из vt в Vj. [11]

Доказать, что конечный ориентированный граф сильно связен, тогда и только тогда, когда существует замкнутый ориентированный маршрут, в который каждая дуга входит, по крайней мере, один раз. [12]

Ориентированный граф такой, что для некоторого целого числа k каждая пара разных вершин может быть соединена ориентированным маршрутом, состоящим точно из k элементов. [13]

Если граф G ациклический, то добавление ребер Е - ( а, Ь), аЬ, не может дать ориентированного цикла в G (, так как он соответствовал бы некоторому циклическому ориентированному маршруту в G. Gt является графом частичного упорядочения, при условии, что он не имеет кратных ребер. [14]

Если граф G ациклический, то добавление ребер Е - ( и, 6), а Ь, не может дать ориентированного цикла в G, так как он соответствовал бы некоторому циклическому ориентированному маршруту в G. Gt является графом частичного упорядочения, при условии, что он не имеет кратных ребер. [15]

Страницы: 1 2