Последовательность - ребро
Cтраница 3
Кроме того, Эйлеру удалось доказать и противоположное утверждение, так что граф, в котором любая пара вершин связана некоторой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. [31]
Принимая во внимание диафаммы, соответствующие рис. 5.33 ( слева) и 5.34 ( справа), покажите, как происходит посещение узлов в графе, построенном для последовательности ребер 0 - 2, 1 - 4, 2 - 5, 3 - 6, 0 - 4, 6 - 0 и 1 - 3 ( см. упражнение 3.70), при рекурсивном поиске в глубину. [32]
Граф G ( X, А) называют полным, если для любой пары вершин имеется по крайней мере одно ребро. Последовательность ребер, в которой любые два соседних ребра смежные, называют маршрутом графа. [33]
 |
Варианты задания расположения ВЧ в ХС. [34] |
Введем еще несколько определений, которые нам понадобятся при последующем рассмотрении. Последовательность ребер 1ц, в которой у каждого ребра одна вершина является граничной с последующим ребром, а другая с предыдущим, называется цепью, и о графе, в котором любые две вершины можно соединить цепью, будем говорить, что граф связен. [35]
Последовательность ребер, в которой исходная и конечная вершины совпадают, называется циклом. Если последовательность ребер включает циклы, она не может быть элементарной. [36]
Структурное дерево - это помеченный граф ( помеченные ребра и узлы), где узлам соответствуют грамматические типы или синтаксические единицы, а ребра различаются своим порядковым номером. Цепь дерева - последовательность ребер, каждое из которых связано с предшествующим. В лингвистике слова или последовательности, которые функционируют в качестве элементов другой конструкции, называются составляющими. [37]
 |
Задача о коне Аттилы. [38] |
Задачи такого типа решаются в теории графов, неоднократно упоминаемой в нашей книге. Путем в графе называется такая последовательность ребер, в которой каждые два соседних ребра имеют общую вершину. [39]
Предположим, что вершины х и у соединимы R Lxy системой из k l простых цепей, попарно не имеющих других общих вершин. Каждой такой цепи отвечает в L последовательность различных ребер, у которой соседние ребра смежны ( имеют общую инцидентную вершину), причем все k последовательностей попарно не имеют общих ребер. [40]
Выходим теперь из z и начинаем путь по следующему ребру, исходящему из г. Каждый раз, когда мы проходим ребро дерева, мы продолжаем построение пути; когда мы проходим обратное ребро, оно становится последним ребром текущего пути. Таким образом, каждый путь состоит из последовательности ребер дерева ( их число 0), за которыми следует одно обратное ребро. Новый путь начинается из начальной вершины последнего обратного ребра; если в этой вершине неисследованных ребер больше нет, возвращаемся к предыдущей вершине на последнем пути. Процесс продолжается до тех пор, пока в графе G не исчерпаются непройденные ребра. Алгоритм 8.14 осуществляет это разложение орграфа на пути и цикл. [41]
На рис. 2.4.2 a, b, e, g - висячие вершины, с, d и f - узлы. Очевидно, их можно рассматривать как часть последовательности ребер, соединяющих другие вершины. [42]
Пусть граф Г не имеет дважды циклических вершин. Назовем цепью подграф графа Г, состоящий из последовательности ребер, в которой конец предыдущего ребра является началом следующего, и никакая вершина не встречается дважды. [43]
Очевидно, что время работы процедуры VERTEX ( /) пропорционально числу ребер, инцидентных Vj. Аналогично можно построить процедуру FACE ( /), вырабатывающую последовательность ребер, окружающих грань / /; для этого в описанной выше процедуре VERTEX ( /) массивы HV и 1 / 1 нужно заменить соответственно массивами HF и FI. Отметим, что процедура VERTEX отыскивает ребра, двигаясь вокруг вершины против часовой стрелки, в то время как процедура FACE отыскивает ребра, двигаясь вокруг грани по часовой стрелке. [44]
Иногда важно различать разные способы упорядочения ребер при образовании цепей или циклов, в других случаях упорядочение не существует. Обе ситуации встречаются достаточно часто, поэтому введение различных терминов для упорядоченных и неупорядоченных последовательностей ребер вполне оправдано. [45]
Страницы: 1 2 3 4