Связный подграф

Cтраница 2

Легко видеть, что простое слабо соединенное множество порождает связный подграф. По предположению множество S является простым слабо соединенным, так что / 1 k и / 2 &2, откуда / 2 k, а это противоречит тому, что S - слабо соединенное множество. [16]

Для доказательства второго утверждения рассмотрим максимальный ( по включению) связный подграф Н ( а), содержащий холостое ребро а и состоящий только из холостых ребер. [17]

Минимальным остовным деревом ( МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент. [18]

Если мы ориентируем этот цикл в любом направлении, то получим сильно связный подграф, состоящий из п дуг и вершин. [19]

Остается показать, что каждый формальный цикл [ vh: vt ] есть сильно связный подграф. Как было отмечено ранее, процедура расстановки меток гарантирует существование внутри множества М И U vh Af-пути из любой вершины i e е М к начальной вершине vh вычищенного потенциального цикла. [20]

При перенесении такого подхода на разветвленные полимеры мы под выборочной последовательностью ( Uh), называемой fc - адой, будем понимать связный подграф молекулярного графа, состоящий из k узлов вместе со всеми выходящими из него ребрами. [21]

Имеются две возможности: либо в Сл ровно две компоненты и каждая из них содержит по одному концу ребра А, либо Сд - связный подграф. [22]

Граф, в котором каждая пара различных вершин соединяется, по крайней мере, одной цепью, называют связным, в противном случае - несвязным. Связный подграф, который не подлежит ни одному большему связному подграфу, называют компонентой связности графа. Очевидно, связный граф состоит из одной компоненты связности. Граф без циклов называют лесом. Связный граф без циклов - деревом. [23]

Подграф, являющийся полным ( пустым) графом, такой, что любой включающий его подграф исходного графа не является полным ( пустым), называется максимальным полным ( пустым) подграфом. Наибольший связный подграф несвязного графа называется компонентом связности. Подграф, являющийся деревом и включающий в себя все вершины исходного графа, называется остовом. Число ребер, не вошедших в остов, называется цикломатическим числом. Цикл в графе G ( X, U), длина которого равна Х, называется гамильто-новым циклом, а граф, в котором такой цикл существует, - гамильто-новым графом. [24]

Деревом называют систему ветвей, связывающих все узлы графа без образования контуров. Дерево представляет связный подграф, который содержит все узлы графа и получается путем удаления ветвей, образующих контуры. Между любой парой узлов дерева имеется единственный путь. Число возможных деревьев графа очень быстро растет с усложнением его структуры. [25]

Понятием расчетный газопровод определяется специальная функция системы управления расчетами, которая заключается в построении взаимосвязанных наборов данных для быстрого удовлетворения информационных запросов программ оптимизации режимов. Файлы расчетного газопровода определяют связный подграф, выделенный из графа ГТС с помощью специального алгоритма. [26]

Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [27]

Важнейшим понятием теории графов является дерево. Деревом связного графа называют связный подграф, содержащий все вершины этого графа, но не содержащий контуров. [28]

В полном графе с п вершинами все ребра покрашены в три цвета. Доказать, что найдется одноцветный связный подграф, содержащий не менее л / 2 вершин. [29]

Применим поиск в глубину для нахождения сильно связных компонент графа. Сначала покажем, что узлы каждой сильно связной компоненты образуют связный подграф в глубинном остовном лесу. Этот связный подграф представляет собой дерево, и его корень называется корнем сильно связной компоненты. Однако не каждое дерево в глубинном остовном лесу непременно представляет какую-то сильно связную компоненту. [30]

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