Разделяющее ребро

Cтраница 3

Так как никакой из исключенных графов (6.4.1) не имеет разделяющих ребер, из теоремы 6.4.3 следует, что максимальный граф исключения Я должен покрывать вершины G. Я и при этом не получилось бы запрещенных частей (6.4.1), так как они не имеют разделяющих ребер. [31]

Компоненты Г ( Ц циклически-реберной связности графа. Компоненты Г ( Ц связности графа. Компоненты Г ( Ц с Г ( Ц связаны мостами. [32]

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

Вершины циклически-реберно связаны. [34]

Допустим, что разделяющее ребро и является циклическим. Тогда после его удаления вершины х и у останутся связанными, а значит, разложение (6.13.1) невозможно, что противоречит условию: и - разделяющее ребро. Теперь и ( х, у) - не циклическое ребро, т.е. не существует цепей, соединяющих х и у и не содержащих и. [35]

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

Циклически-реберная связность определяет отношение эквивалентности па множесть-е вершин V графа G. Листовое множество может состоять только из вершины а0; тогда листовое множество Оо называется особым. Это может случиться только тогда, когда все ребра в а0 являются петлями или разделяющими ребрами. [37]

Циклически-реберная связность определяет отношение эквивалентности на множестве вершин V графа G. Множество всех вершин, циклически-реберно связанных с данной вершиной а0, назовем листовым множеством L ( UO)), которому принадлежит Со. Листовое множество может состоять только из вершины UQ; тогда листовое множество а0 называется особым. Это может случиться только тогда, когда все ребра в а0 являются петлями или разделяющими ребрами. [38]

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