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

Cтраница 2

Подразбиение вершины на инцидентную и слабо инцидентную. [16]

Гиперсети S ( X, V, R) сопоставим смешанный граф G - ( X U У, Е), полученный из данной гиперсети по следующему правилу. Легко показать, что любому квазимаршруту в гиперсети S ( X, V, R) взаимно однозначно соответствует ориентированный маршрут в смешанном графе G ( X U У, Е) между вершинами из множества X. Но в смешанном графе задача поиска - независимых по ребрам и дугам маршрутов между парами вершин полиномиально вычислима. [17]

Однако, обратное, вообще говоря, неверно. Например, на рис. 2.2 последовательность аь а2, а6 определяет незамкнутый маршрут, соединяющий вершины v2 и v4, но из-за различной ориентации дут не образует ориентированный маршрут. [18]

Магнитные аномалии на поверхности Земли могут отражать существование в ее недрах складчатых структур или массивов плотных кристаллических пород. Напряженность магнитного поля измеряется с помощью специального прибора - магнитометра. Замеры производят непрерывно по строго ориентированным маршрутам полета самолетов. [19]

Непрерывная последовательность ребер ( ориентированных и неориентированных), в которой любые два соседних ребра имеют общую концевую точку, называется маршрутом графа. Одно и то же ребро может встречаться в маршруте несколько раз. Если граф является ориентированным, то для него можно рассматривать как ориентированные маршруты, в которых все ребра проходят в направлении их ориентации, так и неориентированные маршруты, не принимая во внимание ориентацию ребер. [20]

Пусть D-ориентированпый граф, имеющий вершину V, которая соединена с каждой из оставшихся вершин D дугой в каждом направлении. Допустим, что существует, по крайней мере, одна дуга, которая не инцидентна и. Доказать, что для любого нелого k 4 и для любых двух ( не обязательно различных) вершин v и w существует ориентированный маршрут из v к w, содержащий точно k дуг. [21]

X, R таким образом, что вершины и ребра чередуются, а всякие два соседних элемента инцидентны. Квазимаршрут в гиперсети S ( X, V, R) - это конечная последовательность д, в которой пара соседних элементов х, г; инцидентна, а Г, xi i слабо инцидентна. Если в определении маршрута заменить инцидентность на слабую инцидентность, то получим определение слабого маршрута. Ориентированные маршруты определяются аналогично, с учетом ориентации ребер. [22]

Маршрутом называют путь по графу, последовательно соединяющий смежные вершины. Если все ребра Xi маршрута различны, то он называется цепью, а если различны к тому же и все вершины г -, то простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь - простым циклом. Для орграфов определено также понятие ориентированных маршрутов ( следовательно, цепей и циклов), когда переходы между вершинами возможны только от начальной вершины ребра к конечной, но не наоборот. Простая ориентированная цепь носит название контура. [23]

Страницы: 1 2