Исходная вершина

Cтраница 4

Задачу построения эйлерова цикла ( если он существует) можно решить, например, с помощью алгоритма, основанного на следующем правиле. Начнем маршрут Р в произвольной вершине а графа G и будем продолжать его, насколько возможно, все время через новые ребра. Так как к каждой вершине подходит четное число ребер, этот процесс может закончиться только в исходной вершине а. При этом получится замкнутый маршрут, проходящий через каждое свое ребро по одному разу, т.е. цикл Р a ai a. [46]

В соответствии с частью ( а) упражнения 4.5 каждая из этих двух вершин смежна с 2 ( п - 2) вершинами. В соответствии с частью ( Ь) в обоих множествах 2 ( п - 2) вершин появляются четыре интересующие нас вершины. Таким образом, существует 4 ( п - 2) - 4 различных вершин, смежных одной или обеим исходным вершинам. [47]

Пересечение нескольких циклов, лежащих в одной плоскости. [48]

Поскольку циклы / С, L и М заданы номерами своих вершин в порядке их обхода ( направление обхода некритично), последовательно проверяем вершины цикла М на принадлежность области цикла К - Предположим, что вершина тр лежит вне цикла / С, а следующая за ней вершина тр 1 - внутри цикла / С. Находим координаты точки Тя пересечения ребра m mr 1 и ребра цикла L. Аналогично поступаем при определении точки Г4 пересечения ребра m ml 1 с циклом К - Процесс продолжается до тех пор, пока не вернемся в исходную вершину тр. [49]

Транспонированная матрица является результатом зеркального отображения ранее полученной матрицы смежности относительно главной диагонали. Поэтому она - матрица смежности того графа, который получается из исходного при перемене ориентации всех его дуг. Исходные вершины Xi графа при этом превращаются для всех дуг в выходные Xj и наоборот. [50]

Одним из известных параллельно-последовательных методов компоновки является метод оптимального ( параллельного) свертывания схемы. В этом случае для осуществления компоновки образуется специальное прадерево свертки, которое строится следующим образом. Исходные вершины графа схемы считаются принадлежащими первому уровню прадерева свертки Рсг. На первом этапе из множества исходных вершин выбираются равноценные группы вершин для заданного критерия оптимизации, которые принимаются в качестве центров дальнейшего наращивания подграфов Gt. Каждую такую группу могут составлять две и более вершин исходного графа схемы. Образованные группы вершин считаются принадлежащими множеству Р второго уровня прадерева свертки. [51]

Поочередно меняя каждую внебазисную переменную, найдем все Л - М ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах L, и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине L0, то переместимся в наинизшую из новых вершин и повторим процесс. Если же minL; L0, то минимум уже достигнут в исходной вершине. [52]

Пример графа. [53]

Рассмотрим граф с рис. 6.4. Начав обход в глубину в вершине 1, мы затем посетим последовательно вершины 2, 3, 4, 7, 5 и 6 и упремся в тупик. Затем нам придется вернуться в вершину 7 и обнаружить, что вершина 8 осталась непосещенной. Вернувшись в вершину 4, мы обнаруживаем, что непосещенной осталась вершина 9; ее посещение вновь заводит нас в тупик. Мы снова возвращаемся назад в исходную вершину, и поскольку все соседние с ней вершины оказались посещенными, обход закончен. [54]

Используя эту формулировку для каждой вершины vit мы можем определить числа Sj следующим образом. Полагаем SjS [ - К, где К есть алгебраическая сумма напряжений по любой цепи, направленной от v к Vj. Полагая, например, Si - 3 в предыдущем примере, мы получим значения S, показанные на рис. 6.37. Напряжения определяют значения Sj с точностью до аддитивной константы. В электротехнике величины Sj могут рассматриваться как потенциалы относительно выбранного потенциала исходной вершины. Очевидно, величины напряжений будут соответствовать разностям потенциалов. [55]

Задача раскрашивания областей произвольной карты может быть сведена к задаче раскрашивания областей трехвалентной карты. Это достигается путем замены какой-то вершины степени, отличной от трех, на замкнутую многоугольную область с числом вершин, равным числу ребер, инцидентных с исходной вершиной. Каждая из новых вершин имеет степень 3, и к ней инцидентно одно из этих ребер. Раскраска исходной карты получается из раскраски трехвалентной карты путем стягивания каждой из новых областей снова в исходную вершину. Таким образом, если четырех цветов достаточно для раскрашивания трехвалентной карты, то их достаточно и для раскрашивания исходной карты. [56]

Страницы: 1 2 3 4