Разделяющая вершина

Cтраница 2

Таким образом, множество всех разделяющих вершин s - cemu единственным образом определяет ее каноническое разложение. [16]

Ветвью блоков, висящей на разделяющей вершине z, называется подграф G У U z), V z, та - кой, что вершины из V. V ( V U z) и подграф У связен. [17]

Предположим, что G не имеет разделяющих вершин. Так как G не имеет разделяющих вершин, H - G. Тогда граф G сильно циклически связен, и по теореме 5.4.1 любая пара его ребер содержится в простом цикле. [18]

Граф G связен и не имеет разделяющих вершин. [19]

Предположим, что G пе имеет разделяющих вершин. Если Н не совпадает с целым графом, то он имеет некоторую соединяющую вершину а, в которой есть реб - pji дополнительного графа Я. [20]

Граф G связен и не имеет разделяющих вершин. [21]

В графе G вершину а назовем разделяющей вершиной ( разрезающей вершиной), если существует собственная непустая часть / /, имеющая а своей единственной соединяющей вершиной. И все ребра должны идти к вершинам из II, H G ( A) является подграфом. [22]

Разделимый граф ( а и его двусвязные компоненты ( Ь. Точки сочлене ния. b, f и i. [23]

Такая вершина называется точкой сочленения или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Например, вершины Ь, / и i на рис. 8.7 ( а) являются точками сочленения, при этом других точек сочленения нет. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком. Отыскание точек сочленения и двусвяз-ных компонент данного графа важно при изучении надежности коммуникационных и транспортных сетей. Это важно также и при определении других свойств графа G, таких, например, как пла-нарность, так как часто полезно разложить G на его двусвязные компоненты и изучать каждую из них в отдельности ( разд. Это соображение позволяет нам использовать поиск в глубину для нахождения точек сочленения и двусвязных компонент графа за операций. [24]

В графе G вершину а назовем разделяющей вершиной ( разрезающей вершиной), если существует собственная непустая часть Н, имеющая а своей единственной соединяющей вершиной. Так как в любой вершине Ьфа из Н все ребра должны идти к вершинам из Н, H G ( A) является подграфом. [25]

Дираку: если G - граф без разделяющих вершин, то либо длина максимальных простых циклов удовлетворяет неравенству k 2ро, либо граф имеет гамнльтонов цикл. Другое доказательство теоремы Дирака дали Эрдеш и Галлаи; наша аргументация является небольшим усовершенствованием их метода. [26]

Теорема 15.4.4. Пусть граф G связный и без разделяющих вершин. Для того чтобы все циклические изоморфизмы G индуцировались изоморфизмами, необходимо и достаточно, чтобы граф G был 3-вершинно связным. [27]

Теорема 15.4.4. Пусть граф G связный и без разделяющих вершин. [28]

Затем снова путем проверки всех возможных разрезов, разделяющих вершины на группы, определяются пропускные способности оставшихся ребер. [29]

Обратно, разложение (5.4.2) может быть использовано для определения разделяющей вершины. Согласно этому определению вершина с петлей является разделяющей. [30]

Страницы: 1 2 3 4