Пленарный граф

Cтраница 2

Уитни также доказал, что каждый максимальный пленарный граф является блоком. [16]

Поскольку двойственные графы определены только для пленарных графов, то очевидно, что граф является пленарным тогда и только тогда, когда он имеет двойственный. С другой стороны, если дан произвольный граф, то приведенные выше рассмотрения не позволяют определить, пленарный он или нет. Поэтому желательно найти такое определение двойственности, которое обобщало бы геометрическую двойственность и одновременно позволяло бы ( по крайней мере в принципе) узнать, пла-нарен данный граф или нет. [17]

Легко видеть, что каждый подграф пленарного графа планарен и что любой граф, содержащий в качестве подграфа непланарный граф, сам не может быть пленарным. Отсюда сразу вытекает, что любой граф, содержащий / Cs или / С3 з в качестве подграфа, не планарен. [18]

Пусть ( G, р) - взвешенный пленарный граф и пусть т обозначает максимальный размер такой 1 ( р - упаковки циклов в G, что каждый из циклов содержит нечетное число отрицательных ребер. [19]

Докажите, что число топологически различных укладок пленарного графа на плоскости конечно. [20]

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

Тутт [65, 66] весьма энергично взялся за задачу перечисления пленарных графов. Триангуляция сферы называется простой, если каждый треугольник есть грань. Тутт отделяя внешний треугольник от других граней, подсчитал простые триангуляции сферы, в которых он является корневым. [22]

ЗЗстест нн являемся стремление ваделить в классе всех трехсЕЯзных пленарных графов базисы относительно тех % т иных операций таг. [23]

Внешнепланарный граф и две его внешнеплоские укладки.| Три максимальных внешнеплоских графа. [24]

В этом разделе приводятся результаты для внешнепланарных графов, аналогичные результатам для пленарных графов. [25]

Свойство двусвязности, или неразделимости, представляет особый интерес в связи с исследованием пленарных графов. Если связный граф изображен на двумерной сфере, то точки сферы, не принадлежащие нарисованному графу, распадаются на конечное число топологических дисков. В случае когда граф двусвязен, каждый из этих дисков ограничен некоторым циклом графа. Это предложение является топологической теоремой, а соответствующий ему комбинаторный результат приведен в гл. [26]

Значение теоремы Штейница заключается в том, что она позволяет изучение 3-многогранников заменять исследованием трех-связных пленарных графов. [27]

Например, мы увидим, что довольно искусственные определения абстрактной двойственности и двойственности по Уитни для пленарных графов ( см. § 15, 16) являются прямыми следствиями соответствующего определения двойственности для матроидов. Мысль, которую мы хотим здесь провести, заключается в том, что различные понятия теории матроидов не только обобщают свои аналоги из теории графов, но часто и упрощают их. [28]

Предлагаемый метод принадлежит классу методов, основанных на заметании плоскости, и, по существу, совпадает с процедурой регуляризации пленарного графа, описанной в разд. Действительно, множества 5 и Е определяют пла-нарный граф, уложенный на плоскости. [29]

Пусть каждый конечный подграф счетного графа G fe-pac - крашиваем; докажите, что Отожей-раскрашиваем, и выведите отсюда, что каждый счетный пленарный граф 5-раскрашиваем. [30]

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