Произвольный граф

Cтраница 3

Если образовывать всевозможные порожденные подграфы произвольного графа Ге еФ ( л, р) исключением определенного числа вершин из какой-либо его комлоненты, то минимальное число ребер будет иметь подграф, образованный исключением вершин из компоненты с максимальным числом вершин. Причем это минимальное число ребер зависит только от числа исклю но, какие бы ребра графа Т чаемых вершин. [31]

Граф и ассоциированное с ним дерево цепей. [32]

Заметим, что дерево цепей произвольного графа всегда является деревом, и если граф G - дерево, то его дерево цепей совпадает с ним самим. [33]

В общем случае обозначим через G произвольный граф с п вершинами, т ребрами и k компонентами. Применяя описанную выше процедуру к каждой компоненте G, получим в результате граф, называемый остовным лесом. Таким образом, циклический ранг дает меру связности графа ( смысл этого понятия будет уточнен в упр. [34]

В случае, когда G - произвольный граф и М - 2, доказательство проводится аналогичным образом. [35]

Теорема 6.4.1. Пусть G - - произвольный граф и (6.4.1) - семейство его конечных частей. [36]

Задача выявления циклов отрицательного веса в произвольном графе важна как сама по себе, так и в качестве основного шага в более сложных алгоритмах ( см. разд. В настоящем разделе эта задача обсуждается несколько более подробно, чем в предыдущем. [37]

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

Сетевая модель означает представление данных в виде произвольного графа. Достоинством сетевой и иерархической моделей данных является возможность их эффективной реализации по показателям затрат памяти и оперативности. Недостатком сетевой модели данных является высокая сложность и жесткость схемы БД, построенной на ее основе. [39]

Во-вторых, деревья могут использоваться для представления произвольных графов с конечным числом вершин. Это очевидно, поскольку произвольный граф - кодируется матрицей смежности или инциденций, а каждая из них - представима деревом. Так что все действия с конечными графами сводимы к операциям над деревьями. Поэтому можно говорить, что деревья, как средство представления и работы с произвольными структурами, универсальны. [40]

Определим понятия включения и изоморфного вложения для произвольных графов. Для этого предварительно дадим определение сужению и продолжению отображений. [41]

Пусть дано равенство К - N двух произвольных графов Бержа. [42]

Так, в [76] ограничивается граф ВС - произвольный граф алгоритма отображается на линейный граф. В [77, 78] уже на произвольный граф ВС отображаются деревья и так называемые последовательно-параллельные графы. И, наконец, в [77, 79] ограничения касаются обоих графов - линейный граф алгоритма отображается на линейный граф ВС. [43]

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

Задачу об отыскании fe - оптимальных путей в произвольном графе во многих случаях можно свести к аналогичной задаче для последовательного графа, хотя это сведение не всегда легко осуществить. [45]

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