Cтраница 3
Утверждение 6.13.6. Блок Г ( Ь) не имеет разделяющих вершин, так как все его вершины циклически-реберно связаны. [31]
Обратно, разложение (5.4.2) может быть использовано для определения разделяющей вершины. Согласно этому определению вершина с петлей является разделяющей. [32]
Вершина v графа G называется точкой сочленения ( или разделяющей вершиной), если граф G v имеет больше связных компонент, чем G. Ребро графа G называется мостам, если его удаление увеличивает число связных компонент графа. [33]
Найти условия, при которых максимальные графы исключения не имеют разделяющих вершин. [34]
Разложимая сеть не распадается на два параллельных куска и не имеет разделяющей вершины в том и только в том случае, если она / / - разложима. [35]
Если выполнено 4, то граф G связен и не может иметь разделяющих вершин, так как иначе три вершины х, у, а, определенные как выше в (5.4.2), не могли бы располагаться на какой-то простой цепи Р ( х, у, а) в этом порядке. Наконец, из определений ясно, что 1 и 5 равносильны. [36]
Если выполнено 4, то граф G связен и не может иметь разделяющих вершин, так как иначе три вершины х, у, а, определенные, как выше в (5.4.2), не могли бы располагаться на какой-то простой цепи Р ( х, у, а) в этом порядке. Наконец, из определений ясно, что 1 и 5 равносильны. [37]
Вершина, общая двум или более блокам, называется точкой сочленения или разделяющей вершиной. Так как удаление точки сочленения нарушает связность графа, то наличие в графе та. В самом деле, замена каждого блока ребром с концами в разделяющих вершинах или просто висячим ребром, если соответствующий блок имеет только одну точку сочленения, превращает граф в дерево. Для описания такой деревообразной структуры используется понятие графа блоков F ( G) графа G: это граф, вершины которого со ответствуют блокам В и разделяющим вершинам z графа G ( рис. 1.5), причем вершины В и z соединены ребром при z e В, а вершины В между собой не смежны. Аналогом блока в ориентированных графах служит линейная компонента. [38]
Теорема 14.3.7. Если G - конечный связный граф с однократными ребрами, без разделяющих вершин и с локальными степенями р ( и) 3, то G имеет часть, гомоморфную полному 4-графу при связном гомоморфизме. [39]
Теорема 14.3.7. Если G - конечный связный граф с однократными ребрами, без разделяющих вершин и с локальными степенями p ( v) 3, то G имеет часть гомоморфную полному 4-графу при связном гомоморфизме. [40]
Если же граф G не 2-связен, то по лемме 1 он содержит такую разделяющую вершину 1 /, что G - 1 / имеет две компоненты связности, скажем GI и G2 ( с вершинами 1 / j e Ог, i 1, 2), поскольку граф G 2-связен. [41]
Ясно также, что два свойства: распадение сети на два параллельных куска и наличие разделяющей вершины - взаимоисключающи. Таким образом, разложимая двухполюсная сеть обладает в точности одним из следующих свойств: распадается на два параллельных куска, имеет разделяющую вершину, допускает / / - разложение. [42]
С другой стороны, если выполняется 3, то граф G связен и не может иметь разделяющих вершин, так как иначе отличные от а вершины уА, у si В в (5.4.2) не могли бы принадлежать одному простому циклу. [43]
Для того чтобы сеть S была s - сетъю, необходимо и достаточно, чтобы в S существовала разделяющая вершина. [44]
По предположению о связности граф Gb полученный из G после удаления ребер, отходящих от Ь, не может иметь разделяющих вершин. [45]