Cтраница 1
Существенные ребра должны принадлежать каждому порождающему графу. [1]
Если А - существенное ребро графа О, то оно принадлежит либо некоторому его треугольнику, либо некоторой его триаде. [2]
Пусть А - существенное ребро графа О и Ь - трехвалентная вершина в С, инцидентная в графе С А ребрам X и У. Тогда либо А принадлежит некоторому треугольнику графа С, либо граф 0 к трехсвязен. [3]
Согласно предыдущему единственный базисный граф существует тогда и только тогда, когда существенные ребра образуют базисный граф, а это имеет место, только если выполняется условие теоремы. Теорема 8.4.6 применима, в частности, к конечным графам. [4]
Теорема 9.1.1. Ациклический граф G имеет не более одного базисного графа В, и если такой граф В существует, то он состоит из существенных ребер. [5]
Очевидно, это равносильно тому, что Е не является излишним в G. Таким образом, существенные ребра принадлежат каждому базисному графу, если таковые существуют. [6]
Если базисный граф существует, то условие выполняется. С другой стороны, если оно выполняется, то все существенные ребра определяют базис. [7]
Частичное упорядочение является транзитивным замыканием любого своего порождающего графа. Как в теореме 9.1.1, мы получаем, что частичное упорядочение имеет не более одного базисного графа В, и если такой граф В существует, то он состоит из существенных ребер. Следует отметить, что, когда частичное упорядочение представляют в виде графа, обычно изображают не сам граф частичного упорядочения, а его базисный граф В. В частности, это имеет место, когда цепи между а и b конечны. [8]
Теорема 8.4.7. Пусть G - такой граф, что кажгЧш его порождающий граф содержит базисный граф для О. Для того чтобы G имел единственный базисный граф, необходимо и достаточно, чтобы для каждого ребра Е ( а, Ь) существовала цепь Р ( а, Ь), состоящая из существенных ребер. [9]
В заключение сделаем несколько замечаний о том случае, когда базисный граф единственный. Ребро Е графа G назовем существенным, если оно принадлежит каждому порождающему графу для G. Очевидно, это равносильно тому, что Е не является излишним в G. Таким образом, существенные ребра принадлежат каждому базисному графу, если таковые существуют. [10]