Cтраница 4
Для каждой вершины хг из О, являющейся внутренней вершиной дерева Т или содержащейся в псевдовершине из Т, помеченной как внутренняя, увеличиваем яг до я, А. [46]
Элементарной граф-схемой называется граф-схема без контуров, каждая внутренняя вершина которой является логической. [47]
Наконец, если каждая внешняя вершина имеет соседями только внутренние вершины, то мы можем утверждать, что паросочетание М уже само является наибольшим. Чтобы убедиться в этом, предположим, что лес F содержит m внутренних и п внешних вершин. Далее, если мы удалим все внутренние вершины леса F из графа G, то получившийся граф будет содержать все внешние вершины леса F как изолированные вершины. Но паросочетание М пропускает в точности 5 вершин, и поэтому оно должно быть наибольшим паросочетанием. [48]