Cтраница 1
Неориентированные графы с абсолютно унимодулярными матрицами инциденций играют заметную роль в различных приложениях теории графов. [1]
Рассмотрим неориентированные графы G без петель и кратных ребер. [2]
Будем рассматривать неориентированные графы без петель и кратных ребер, построенные на множестве Vn из п 2 нумерованных вершин. [3]
Очевидно, что неориентированные графы, сопоставленные Г и рд Г, совпадают. Преобразование Г - рд Г можно применить несколько раз, используя различные вершины. Получающиеся таким образом колчаны имеют тот же неориентированный граф, что и Г, но различные ориентации. Основной результат этого параграфа состоит в том, что на этом пути можно получить все возможные ориентации. [4]
Это понятие относится к неориентированным графам. [5]
Как ориентированные, так и неориентированные графы будут нами изучаться существенно глубже, однако, соответствующие определения нам будет лучше давать уже по ходу дела, сопровождая их поясняющими примерами. [6]
В этой статье рассматриваются конечные неориентированные графы без кратных ребер и петель. Через E ( G) обозначено множество Вершин графа G, через K ( G) - множество его ребер. [7]
Мы будем рассматривать как ориентированные, так и неориентированные графы. Граф мы будем всегда обозначать GV, Еу, где V обозначает множество вершин, а Е - множество ребер), причем Е V X V для ориентированного графа и Е х, у: х, г / е V / х у для неориентированного графа. [8]
Говорят, что два ориентированных графа изоморфны, если их соответствующие неориентированные графы изоморфны в обычном смысле и, кроме того, граничные точки каждой пары соответствующих дуг упорядочены одинаковым образом. [9]
В главе 5 вводится ряд матриц, с помощью которых можно описывать, используя алгебраический аппарат, ориентированные и неориентированные графы. Эти матрицы задают отношения инциденций между вершинами и ребрами и. Они являются удобной формой представления структурных свойств графа. [10]
Если G - неориентированный граф, то ребра ( a, ft) и ( ft, а) существуют одновременно, таким образом, неориентированным графам соответствуют симметрические матрицы смежности. [11]
Если G - неориентированный граф, то ребра ( а, Ь) и ( Ь, а) существуют одновременно, таким образом, неориентированным графам соответствуют симметрические матрицы смежности. [12]
Эта сложность возникает потому, что ребра в орграфе уже ориентированы, и мы не можем свободно проходить их в выбранном нами направлении, как мы делали при поиске в глубину на неориентированных графах. [13]
Каждой вершине соответствует связный список с узлами для всех вершин, связанных с данной. В неориентированных графах, если существует узел для вершины j в i-том списке, то должен существовать узел для вершины i в j - том списке. На рис. 3.15 показан пример представления неориентированного графа с помощью списков смежности. Программа 3.19 демонстрирует метод создания такого представления для вводимой последовательности ребер. [14]
В этом случае вершины а и b должны быть соединены ориентированным ребром в каждом направлении, но проще заменить их одним неориептирошш-ным ребром. Таким образом, неориентированные графы отвечают симметрическим отношениям. [15]