Пленарная графа

Cтраница 1

Пленарные графы с р41 вершинами 4-раскрашиваемы. [1]

Заметим, что двойственные пленарные графы имеют одинаковые древесные сложности. [2]

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

Доказано даже, что пленарные графы на изоморфизм можно проверить за 0 ( У) операций. [4]

Допустим, что все пленарные графы с р вершинами ( р 5) 5-раскрашиваемы. Пусть G - плоский графе р 1 вершинами. В силу следствия 11.1 ( д) в графе G найдется вершина v степени 5 или менее. По предположению индукции плоский граф G - v 5-раскра-шиваем. [5]

Связь между планарными матроидами и пленарными графами будет выявлена в следующем параграфе. [6]

Хотя не известно, все ли пленарные графы 4-раскрашиваемы, все они, несомненно, 5-раскрашиваемы. [7]

Запрещенные графы для внешней планарности. [8]

Баттлу, Харари и Кодаме [1] принадлежит следующая ниже теорема о пленарных графах, дающая достаточное условие того, что дополнение планарного графа планарно. [9]

Понятво что зйачввие & & л достигается на графах, расклеиваемых ва треховязные пленарные графы о 5 гранями. [10]

В этой монографии освещается много центральных тем, которые можно рассчитывать найти в книге по теории графов - например, теорема Менгера и потоки в сетях, проблема восстановления, матричная теорема о деревьях, теория факторов ( или паросочетаний) для графов ( созданная в значительной степени самим профессором Таттом), хроматические многочлены, теорема Брукса, теорема Гринберга, пленарные графы, теорема Куратовского. Но это ни в коем случае не еще одна книга по теории графов, ибо излагаемый материал связывается в единое целое глубоко индивидуальным подходом профессора Татта. Кроме того, самые обычные темы преподносятся с некоторыми приятными сюрпризами, такими, как принадлежащая автору изящная теория разложения графов на трехсвязные 3-блоки ( кроме монографии [5], ее ни в какой книге не найдешь), интересный, замечательный подход к электрическим цепям и - быть может, самое примечательное - классификационная теорема для замкнутых поверхностей. Обычно эту теорему относят к топологии, но проф. Татт демонстрирует нам, что она отлично подходит для работы по теории графов - комбинаторная по своей сущности природа рассуждений здесь, действительно, на месте. [11]

Граф, который можно так изобразить на плоскости, что никакие два его ребра не пересекаются между собой), называется планар-ным. Пленарные графы важны как с теоретической, так и с практической точек зрения и обладают рядом таких свойств, связанных с раскраской, о которых следует упомянуть. [12]

Граф, который можно так изобразить на плоскости, что никакие два его ребра не пересекаются между собой 1), называется планар-ным. Пленарные графы важны как с теоретической, так и с практической точек зрения и обладают рядом таких свойств, связанных с раскраской, о которых следует упомянуть. [13]

В этой главе приведены все известные критерии планарности. В их число входят теоремы Понтрягина - Куратовского и Вагнера, в которых пленарные графы характеризуются в терминах запрещенных подграфов; результат Уитни о связи планарности графа с существованием комбинаторно двойственного графа; данное Мак-Лейном описание планарности, в котором используется циклическая структура графа. [14]

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

Страницы: 1