Cтраница 1
Элементарный двудольный граф является минимальным тогда и только тогда, когда он не содержит эластичных циклов, имеющих хорды. [1]
Всякий минимальный элементарный двудольный граф G разделяется своими 2-ребрами. [2]
Если G - элементарный двудольный граф, отличный от KI, то он 2-связен. [3]
Пусть G - минимальный элементарный двудольный граф, являющийся наименьшим по числу вершин графом, содержащим граф GQ. Из теоремы 4.2.1 вытекает, что G является к тому же минимальным элементарным графом. [4]
Если G - минимальный элементарный двудольный граф, то рассмотрим его произвольную колосковую декомпозицию, начинающуюся с какого-либо эластичного цикла. Всякая хорда в этом цикле была бы остью, что, как мы видели, невозможно. [5]
Всякий эластичный элементарный подграф минимального элементарного двудольного графа является минимальным элементарным графом. [6]
Предположим, что G - элементарный двудольный граф. [7]
Если G - отличный от 4-цикла минимальный элементарный двудольный граф, то 4-цикла в нем нет. [8]
В теореме 4.2.2 было показано, что в минимальном элементарном двудольном графе 4-цикла быть не должно. Полный список таких исключительных подграфов не известен. [9]
Известно еще несколько интересных утверждений, связанных с колосковой структурой элементарных двудольных графов, но их удобнее излагать после обсуждения свойств минимальных элементарных двудольных графов, которые будут рассмотрены в следующем разделе. [10]
Нижеследующая лемма не только предоставляет возможность получить еще одну характеризацию минимальных элементарных двудольных графов в терминах циклов и хорд. Она имеет также ряд весьма интересных следствий. [11]
Эта теорема описывает способ разложения графа G на меньшие элементарные графы Н и элементарный двудольный граф G s, который служит каркасом при новой сборке графов Н, обеспечивающей восстановление графа G. Если какой-либо из элементарных графов Н не является бикритическим, то мы выберем некий класс разбиения Р ( Н), имеющий более одной вершины, и повторим декомпозицию. Будем продолжать эту процедуру до тех пор, пока не получим перечень би-критических графов. [12]
Граф G будет регуляризуемым тогда и только тогда, когда каждая компонента графа G является либо элементарным двудольным графом, либо 2-бикритическим графом. [13]
Мы уже видели, что для факторно-критических графов существует теория колосковой декомпозиции, абсолютно аналогичная соответствующей теории для элементарных двудольных графов. Эту технику можно весьма успешно применить для изучения минимальных факторно-критических графов, и полученные результаты совершенно аналогичны результатам, относящимся к минимальным элементарным двудольным графам. [14]
Известно еще несколько интересных утверждений, связанных с колосковой структурой элементарных двудольных графов, но их удобнее излагать после обсуждения свойств минимальных элементарных двудольных графов, которые будут рассмотрены в следующем разделе. [15]