Cтраница 2
Теперь наших знаний вполне достаточно, чтобы разработать процедуру построения элементарных графов, используя два семейства основных строительных блоков, а именно, семейство элементарных двудольных графов и семейство бикритических графов. [16]
Если при некотором k 3 граф G является fc - регулярным, циклически ( k 1) - реберносвязным и име т четное число вершин, то он является либо бикритическим графом, либо элементарным двудольным графом. [17]
Пусть G есть 2-расширяемый граф с р 6 вершинами. Тогда G является либо бикритическим графом, либо элементарным двудольным графом. [18]
Интересно взглянуть на лемму 4.2.9 с иной точки зрения. Пусть GO - произвольный двудольный граф, и рассмотрим совокупность всех элементарных двудольных графов, содержащих GQ в качестве подграфа. [19]
Двудольную колосковую декомпозицию иногда удобно описывать с помощью набора подграфов ( G0 Gi... G), где GO х и G, х PI Pi при 1 г г. В силу теоремы 4.1.6 каждый граф G является элементарным двудольным графом. [20]
Если мы хотим доказать, что некий двудольный граф является элементарным, то, очевидно, это достаточно установить для его остов-ного минимального элементарного подграфа. Приводимые ниже результаты показывают, что минимальный элементарный двудольный граф должен быть малым в разных смыслах графом. Одна из мер малости отражает тот факт, что минимальный граф не может содержать подграфы определенного вида. Мы представим один такой результат. [21]
Известно, что при проектировании не всегда существует взаимопонимание между постановщиками задач и программистами, которое является следствием недостаточного уровня формализованное расчета показателей в постановках задач. Этим объясняется актуальность задачи формализации расчета показателей. Одним из наиболее перспективных направлений создания формализованных методик является метод использования элементарных двудольных графов для каждого рассчитываемого показателя с заданием всех операций, необходимых для его получения. [22]
Теперь обратим свое внимание на такие факторно-критические и бикритические графы, которые являются минимальными относительно удаления ребер. Из теоремы 4.2.11 вытекает алгоритмическая разрешимость проблемы о том, является ли данный граф подграфом минимального элементарного двудольного графа. Хотя для минимальных бикритиче-ских графов аналогичных результатов не получено, для них известны несколько исключительных подграфов. Здесь мы подробно рассмотрим только один такой класс, чтобы проиллюстрировать возможности нашей техники. [23]
Введем новый вид декомпозиции, которая называется колосковой декомпозицией. Так, с помощью этой декомпозиции нам удастся доказать, что во всяком элементарном двудольном графе содержится остовный элементарный подграф, имеющий не более 3 ( р - 6) / 2 ребер. Кроме того, мы покажем, как двудольный граф общего вида, обладающий совершенным паросочетанием, собирается из элементарных двудольных графов. Эти результаты явятся также некоей мотивацией нашего подхода к изучению элементарных графов и декомпозиционной техники в целом. [24]
Введем новый вид декомпозиции, которая называется колосковой декомпозицией. Так, с помощью этой декомпозиции нам удастся доказать, что во всяком элементарном двудольном графе содержится остовный элементарный подграф, имеющий не более 3 ( р - 6) / 2 ребер. Кроме того, мы покажем, как двудольный граф общего вида, обладающий совершенным паросочетанием, собирается из элементарных двудольных графов. Эти результаты явятся также некоей мотивацией нашего подхода к изучению элементарных графов и декомпозиционной техники в целом. [25]