Cтраница 4
Ориентированный или неориентированный граф без циклов ( в том числе без петель) называется ациклическим. Связный ациклический граф называется деревом; имеется любопытная теория деревьев. [46]
Ориентированный или неориентированный граф может быть однозначно представлен структурой смежности своих вершин. Списки Adj [ x ] составляются для каждой вершины графа. [47]
Рассмотрим теперь неориентированный граф 0 ( ь определяемый обобщенным циклом Gh. По теореме 4.4.2 Gi может иметь не более одного цикла. Предположим, что такой цикл С ( г существует. В каждой вершине о; цикла О 1 будет присоединяться конечное или бесконечное дерево с корнем ait связывающее вершину а - со всеми относящимися к ней вершинами. [48]
Теорема 8.1.6. Неориентированный граф G0 является графом Gu бисвязного ориентированного графа G тогда и только тогда, когда граф G0 связен и не имеет разделяющих ребер. [49]
Теорема 8.2.4. Неориентированный граф G0 является графом Gu для сильно ориентированно-циклически-ре-берно связного ориентированного графа G тогда и только тогда, когда G0 не имеет разделяющих вершин. [50]
Теорема 8.2.4. Неориентированный граф GQ является графом Gu для сильно ориеитированно-циклически-ре-берно связного ориентированного графа G тогда и только тогда, когда G0 не имеет разделяющих вершин. [51]
При описании неориентированных графов мы будем иметь дело с матрицами инциденций, элементами которых могут быть только нули и единицы. [52]
В случае неориентированного графа элементами векторного пространства при матричном представлении являются векторы, каждый из которых представляет подмножество ребер. Элементами этих векторов являются О или 1 в зависимости от того, принадлежит ли данное ребро рассматриваемому подмножеству или нет. В частности, каждый цикл и разрез имеют векторное представление. Сумма двух таких векторов также является вектором того же вида. [53]
В случае неориентированного графа две вершины называются соседями, если между ними есть ребро. [54]
Замечания относительно неориентированных графов. [55]
Матрица смежности неориентированного графа симметрична относительно главной диагонали, но для ориентированного графа ( см. несколько ниже) это утверждение не справедливо. [56]
На случай неориентированных графов переносятся почти все введенные выше понятия. Говоря о входе или выходе в неориентированном графе, будем иметь в виду некоторые выделенные вершины; например, откуда начинается и где заканчивается обход. [57]