Неориентированный граф
Cтраница 3
 |
Последовательность преобразований для различных трудных задач. [31] |
Построим неориентированный граф G ( V, E), узлами которого служат пары целых чисел [ i, j ] для lIt 7 и l / s &i - Первая компонента такой пары представляет сомножитель, а вторая - литерал, входящий в него. Таким образом, каждый узел графа естественным образом соответствует конкретному вхождению в конкретный сомножитель. [32]
Для неориентированного графа доказать, что в нем число вершин е нечетной степенью четно. [33]
Для неориентированного графа, изображенного на рис. 9.15, найти цикломатическое и коцикломатическое числа, а также фундаментальные циклы относительно некоторого остовного дерева. [34]
Для неориентированного графа доказать, что в нем число вершин с нечетной степенью четно. [35]
Для неориентированного графа, изображенного на рис. 9.15, найти цикломатическое и коцикломатическое числа, а также фундаментальные циклы относительно некоторого остовного дерева. [36]
Для неориентированных графов, к которым принадлежит рассматриваемый, при наличии записи в строке i и столбце j обязательно существует запись в строке j и столбце i. На рис. 3.14 показан пример матрицы смежности для неориентированного графа. Программа 3.18 демонстрирует создание матрицы смежности для вводимой последовательности ребер. [37]
 |
Примеры деревьев. [38] |
Для неориентированного графа понятия дуга, путь и контур заменяются понятиями ребро, цепь, цикл. Ребро - это отрезок, соединяющий две вершины. Граф на рис. 2 - 1 имеет восемь дуг, но семь ребер. Цепью - называется последовательность ребер. Циклом называется конечная цепь, у которой начальная и конечная вершины совпадают. [39]
На неориентированном графе Г ( X, Uf Ф) поиск в глубину осуществляется следующим образом. [40]
В неориентированном графе маршрут, в котором все вершины различны, называется простой цепью. [41]
В неориентированном графе последовательность ребер, в которой у каждого ребра одна из граничных вершин является также граничной вершиной предыдущего ребра, а другая - граничной вершиной последующего ребра, называется цепью. [42]
 |
Поиск в глубину на графе. [43] |
На неориентированном графе G - ( V, Е) поиск в глубину осуществляется следующим образом. Если вершина w уже пройдена ( посещалась ранее), мы возвращаемся в v и выбираем другое ребро. [44]
Ориентированный или неориентированный граф ( G. G, в котором для каждых трех вершин и, v и хез, не совпадающих друг с другом, имеете путь от и к w, не содержащий и. В случае неориентированного графа это соответствует графу, не имеющему точек сочленения ( С. Говорят, что между двумя ребрами неориентированного графа существует зависимость, если они тождественны или если имеется цикл ( С. [45]
Страницы: 1 2 3 4