Cтраница 2
Так как G - ациклический граф, то каждая его компонента является деревом. В нашем случае должно быть kl, так что G - связный граф. Таким образом, G - дерево и любые две его вершины соединяет единственная простая цепь. Если к дереву G добавить ребро uv, то ребро вместе с единственной простой цепью, соединяющей вершины и и v, образует простой цикл, который также единствен в силу единственности простой цепи. [16]
Граф без циклов называется ациклическим графом. [17]
Теорема 9.2.1. Пусть в ациклическом графе G цепи между вершинами а b конечны. Тогда любая пара максимальных цепей (9.2.1), связывающих эти вершины, деформационно эквивалентна. [18]
Теорема 9.2.1. Пусть в ациклическом графе G цепи между вершинами аЬ конечны. Тогда любая пара максимальных цепей (9.2.1), связывающих эти вершины, деформационно эквивалентна. [19]
Теорема 9.1.2. Для того чтобы ациклический граф имел базис, необходимо и достаточно, чтобы концы любого ребра Ео ( ао, aj) были связаны максимальной цепью. [20]
Предположим теперь, что G есть ациклический граф. Поэтому любому иаросочетаипю М n G ( F, V) соответствует разложение (10.2.1) множества У, в котором каждое G ( Vi) является квазиупорядочением со счетным числом вершин. Если G есть частичное упорядочение, то множества Vi оказываются упорядоченными. [21]
Предположим теперь, что G есть ациклический граф. [22]
Пусть (2.1) есть система уравнений на ациклическом графе. [23]
Ациклический граф называют лесом, а если ациклический граф к тому же связный, его называют деревом. [24]
Рассмотрим схему химических реакций, которой соответствует ациклический граф. [25]
Покажите, что время вычисления транзитивной редукции ациклического графа имеет тот же порядок, что и время вычисления транзитивной редукции произвольного графа, если принять те же допущения, что и в упр. [26]
Рассмотрим теперь произвольную схему реакций, которой соответствует ациклический граф, и для которой выполняются условия I - 2, Выделим из всей системы линейно независимые реакции, причем так, чтобы каждое нулевое вещество вступало в реакцию. [27]
Теорема 8.4.6 сводит проблему существования базисного графа к случаю ациклических графов и бисвязных графов. [28]
Теорема 8.4.6 сводит проблему существования базисного графа к случаю ациклических графов и бисвязыых графов. [29]
Матрицы S, D, В для моделей с ациклическим графом являются существенно разреженными, а структура их определяется структурой 0-узлового графа, под которым понимается подграф рассматриваемой модели, образованный безынерционными узлами и связывающими их соединениями. [30]