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

Cтраница 1

Разделяющие ребра соответствуют в нашей интерпретации единственным мостам через реку или тупикам. Поэтому предположим, что в связном графе G0 нет разделяющих ребер. Можно построить бисвязные ориентированные части графа, вводя подходящие направления; например, из простого цикла возникают два таких графа. Эти ориентированные части графа образуют частично упорядоченное множество, если считать Н Н2, когда ребра Н2 принадлежат HI и имеют те же направления. [1]

Разделяющие ребра соответствуют в пашей интерпретации единственным мостам через реку или тупикам. Поэтому предположим, что в связном графе GO пет разделяющих ребер. Можно построить опсвязные ориентированные части графа, вводя подходящие направления; например, пз простого цикла возникают два таких графа. Эти ориентированные части графа образуют частично упорядоченное множество, если считать / / 1 э / / 2, когда ребра / / 2 принадлежат / / [ п имеют те же направления. Рассмотрим упорядоченное по включению семейство / / бисвя. [2]

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

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

Если F - разделяющее ребро гиперграфа Н, а & и & - ассоциированные с ним множества ребер, то гиперграфы, определенные множествами ребер U F и & г ( J F, замкнуты относительно Я. [5]

Будем также считать Е разделяющим ребром, если оно является концевым; в этом случае один из графов 77, или 77 2 в (5.2.1) сведется к одной вершине. [6]

Будем также считать Е разделяющим ребром, если оно является концевым; в этом случае один из графов Н или Ну. [7]

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

Поэтому каждое соединяющее ребро для L должно быть разделяющим ребром. Заметим также, что не может быть более одного такого ребра, связывающего два листовых множества Ь и Z / г, так как иначе эти ребра оказались бы циклическими. Эти рассуждения приводят к теореме. [9]

Ребро Е ( а, Ь) называется разделяющим ребром ( или мостом, или разрезающим ребром) в G, если в графе GI, получающемся после удаления Е, вершины а и и не связаны. [10]

Поэтому каждое соединяющее ребро для L должно быть разделяющим ребром. Заметим также, что не может быть более одного такого ребра, связывающего два листовых множества L. Эти рассуждения приводят к теореме. [11]

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

Ребро Е - ( а, Ь) называется разделяющим ребром ( пли мостом, или разрезающим ребром) в G, если в графе GI, получающемся после удаления Е, вершины а н Ь не связаны. [13]

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

Ребро и ( х, у) е U называется разделяющим ребром ( или мостом, или разрезающим ребром) в Г, если в графе Г, получающемся после удаления ребра и, вершины х и у не связаны. [15]

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