Cтраница 3
Вершины va и Vk будем называть соответственно началом и концом пути, а число k - длиной пути. Vk различны, то будем говорить об элементарном пути. Множество А вместе с ребрами графа G, инцидентными вершинам из А, определяет некоторый подграф, называемый компонентой связности графа G. Очевидно, что множества вершин компонент связности произвольного графа попарно не пересекаются. [31]
Все элементарные пути графа на рис. 206 приведены на стр. Так как в графе с шестью вершинами не существует элементарного пути длины больше 5, то матрица ] М 6) пуста. [32]
Структурный анализ при решении перечисленных или иных крупных специфических задач может приобретать особый смысл, однако, можно выделить ряд традиционных частных задач СА, характерных для многих приложений. К ним, в частности, относятся задачи нахождения всех элементарных контуров в ориентированных графах и нахождение всех элементарных путей из одного узла ориентированного графа в другой. Если результат решения первой задачи - полный описок всех элементарных контуров в заданном графе - есть его абсолютная характеристика, не зависящая от выбранной точки зрения на граф, то результат решения второй задачи - список всех элементарных путей - является характеристикой относительной, так как содержание этого списка зависит от того, какие два узла приняты за начальный и конечный. [33]
Граф G называется конечным, если конечны множества X и U. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Элементарный путь, проходящий через все вершины графа, называется гамильтоновым. Цикл ( контур), проходящий через все вершины графа, называется гамильтоновым. [34]
Структурный анализ при решении перечисленных или иных крупных специфических задач может приобретать особый смысл, однако, можно выделить ряд традиционных частных задач СА, характерных для многих приложений. К ним, в частности, относятся задачи нахождения всех элементарных контуров в ориентированных графах и нахождение всех элементарных путей из одного узла ориентированного графа в другой. Если результат решения первой задачи - полный описок всех элементарных контуров в заданном графе - есть его абсолютная характеристика, не зависящая от выбранной точки зрения на граф, то результат решения второй задачи - список всех элементарных путей - является характеристикой относительной, так как содержание этого списка зависит от того, какие два узла приняты за начальный и конечный. [35]
Пусть Н - множество вершин а, для которых существует путь [ as, а ], не содержащий ребер из W. Для каждого ребра из W существует путь из as в ps, содержащий это ребро и не содержащий других ребер из W. Понятно, что существует и элементарный путь с теми же свойствами. [36]