Альтернирующее дерево
Cтраница 1
Альтернирующее дерево Т с корнем в экспонированной вершине хг показано сплошными линиями, а все другие ребра графа, не входящие в дерево Г - пунктиром. Так как между двумя внешними вершинами х12 и х13 существует ребро, то добавление к дереву вышеупомянутого последнего ребра дает цветок. [1]
Альтернирующее дерево Т с корнем в экспонированной вершине х1 показано сплошными линиями, а все другие ребра графа, не входящие в дерево Т - пунктиром. Так как между двумя внешними вершинами х12 и х13 существует ребро, то добавление к дереву вышеупомянутого последнего ребра дает цветок. [2]
Новое альтернирующее дерево можно затем расширять до тех пор, пока опять не возникнут приведенные выше случаи А, Б или В. [3]
Если альтернирующее дерево уже существует, то продолжать выращивать его. [4]
Ребра в альтернирующем дереве, входящие в паросочетание. [5]
 |
Альтернирующее дерево. / - внутренние вершины, Ф - внешние вершины. [6] |
На рис. 12.6 изображено альтернирующее дерево. [7]
Аугменталъное дерево - это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева х0, до некоторой экспонированной вершины хе, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины х0 и далее - по ребру ( х0, ее), будет тогда аугментальной цепью. [8]
 |
Альтернирующее дерево. / - внутренние вершины, Ф - внешние вершины. [9] |
Аугменталъное дерево - это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева х0, до некоторой экспонированной вершины хе, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины х0 и далее - по ребру ( х0, ее), будет тогда аугментальной цепью. [10]
 |
Альтернирующее дерево. / - внутренние вершины, Ф - внешние вершины. [11] |
Степень любой внутренней вершины альтернирующего дерева равна 2, в то время как степень внешней вершины может быть любым целым положительным числом. [12]
Если в С уже существует альтернирующее дерево, то продолжать его построение. [13]
 |
Венгерское дерево. [14] |
Венгерское дерево - это такое альтернирующее дерево в графе, что каждое ребро графа, имеющее внешнюю вершину дерева в качестве концевой, имеет другой концевой вершиной внутреннюю вершину этого дерева. [15]
Страницы: 1 2 3