Cтраница 4
По предположению о связности граф GI, полученный из G после удаления ребер, отходящих от 6, не может иметь разделяющих вершин. [46]
Теорема 8.2.4. Неориентированный граф G0 является графом Gu для сильно ориентированно-циклически-ре-берно связного ориентированного графа G тогда и только тогда, когда G0 не имеет разделяющих вершин. [47]
Теорема 8.2.4. Неориентированный граф GQ является графом Gu для сильно ориеитированно-циклически-ре-берно связного ориентированного графа G тогда и только тогда, когда G0 не имеет разделяющих вершин. [48]
Sn является разделяющей вершиной сети S. Любая другая разделяющая вершина сети S лежит внутри некоторой подсети Sf и является для S; разделяющей. Действительно, всякая цепь подсети S является подцепью некоторой цепи сети S ( см. ( 2), стр. [49]
Вершина z называется разделяющей вершины р и у ( ( З а, ут а) в графе G. S и у принадлежат одной компоненте связности и всякая цепь [ 3, у ] содержит а. [50]
Предположим, что G не имеет разделяющих вершин. Так как G не имеет разделяющих вершин, H - G. Тогда граф G сильно циклически связен, и по теореме 5.4.1 любая пара его ребер содержится в простом цикле. [51]
Теорема применима также к ориентированным графам. Если а - минимальное число разделяющих вершин для ориентированных цепей от Л к В, то существует о непересекающихся ориентированных цепей между этими множествами. [52]