Остовное дерево
Cтраница 4
 |
Восстановление графа из Ж3 5. [46] |
Рассмотрим в R любую связную компоненту С и выделим в ней произвольным образом остовное дерево D. [47]
Следовательно, из v2 в УЗ идет путь из ребер, уже вошедших в остовное дерево, и потому ( v2, vs) не добавляется. [48]
 |
Граф, его остовное дерево и фундаментальное множество. [49] |
При порождении фундаментального множества циклов удобно использовать метод поиска в глубину; он строит остовное дерево и каждое обратное ребро порождает цикл относительно этого дерева. Для того чтобы следить за ребрами дерева, используется поиск в глубину со стеком, в котором хранятся все текущие вершины пройденного пути в данный момент. Когда попадаем на обратное ребро, обнаруженный цикл будет состоять из этого ребра и ребер, соединяющих вершины из верха стека. [50]
В сформулированном выше условии единственности решения системы (11.1.5) - (11.1.9), опирающемся на понятие остовного дерева, мы молчаливо подразумевали, что сопротивления Re положительные. Однако это слишком сильное ограничение, так как при моделировании некоторых более развитых электронных устройств мы должны пользоваться отрицательными сопротивлениями. Если допускаются отрицательные значения Re, то сформулированное выше условие существования единственного решения системы уравнений (11.1.5) - (11.1.9) перестает быть достаточным. [51]
 |
Два различных минимальных остовных деревадпя одной сети. [52] |
Возможно, список возможных связей опустеет прежде, чем все узлы будут добавлены к остовному дереву. В этом случае сеть признается несвязанной, и пути от корневого узла ко всем остальным узлам сети не существует. [53]
Одна из них состоит из сына s узла а и всех его потомков в глубинном остовном дереве. Следовательно, в этом остовном дереве узел а должен иметь сына s, потомки которого не соединены обратными ребрами с подлинными предками узла а. Обратно, из-за отсутствия поперечных ребер узел а, отличный от корня, является точкой сочленения, если никакой потомок некоторого его сына не соединен обратным ребром ни с каким подлинным предком узла а. Корень глубинного остовного дерева является точкой сочленения тогда и только тогда, когда он имеет не менее двух сыновей. [54]
Докажите, что мосты G ( V, Е) должны быть в каждом остовном дереве графа G. [55]
Страницы: 1 2 3 4