Плоская графа

Cтраница 1

Иллюстрации к теореме Поша.| Граф Татта. [1]

Плоские графы рассматриваются в гл. [2]

Дуальные графы.| Ориентированный граф. [3]

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

Дуализации могут подвергаться также сжатые плоские графы. При этом происходит взаимное преобразование узлов и контуров дуальных графов. [5]

Некоторые органические молекулы могут быть представлены как плоские графы. При этом атомы соответствуют вершинам, а связи между атомами - ребрам. [6]

Второй том будет посвящен более частным вопросам: плоским графам, гипотезе четырех красок, теории потоков, играм, электрическим сетям, а также приложениям к ряду других областей, в которых теория графов является основным инструментом. [7]

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

Примеры графов. [9]

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

Цикл работ Татта [207-211] ( последняя из них вышла в начале 1963 г.) посвящен плоским графам и картам. [11]

Используемые методы по существу те же, что и в [2], но здесь они детально переработаны так, чтобы их можно было применять ко всем плоским графам. В обобщенной теореме ( теорема 1, см. ниже) утверждается, что любой плоский граф, имеющий цикл, обладает циклом, удовлетворяющим некоторым особым условиям. Для важного класса плоских графов, включающего и графы, которые изучались Хасслером Уитни, в этих условиях требуется, чтобы цикл был гамильтоновым. [12]

Первый фундаментальный результат, именно чисто комбинаторный критерий того, что данный граф является плоским, принадлежит Л. С. Понтрягину и Куратовско-му ( см., например, [4], гл. Ряд результатов о плоских графах был получен Уитни в 1931 - 33 годах, одна из его работ этого периода [218] заново напечатана в 1962 г. Бэтл, Харари и Юкихиро [78] дают простое доказательство ( не основанное на полном переборе всех случаев) того факта, что каждый плоский граф с 9 вершинами обладает неплоским дополнением. Упомянем еще раз и о работах Уэйсмана [215, 216] ( § 2), где фигурирует задача разложения данного графа на минимальное число плоских частичных графов. [13]

Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из теоремы Эйлера о плоских графах следует, что S - содержит FI 2N треугольников. [14]

Используя тот факт, что дерево является двудольным графом, и рассматривая его хорды, можно показать, что граф является двудольным тогда и только тогда, когда каждый цикл содержит четное число ребер. В свою очередь в плоских графах каждый цикл будет содержать четное число ребер тогда и только тогда, когда каждый цикл, ограничивающий некоторую грань, обладает этим свойством. Читателю рекомендуется провести детальное доказательство этого шага. Но это эквивалентно утверждению, что каждая вершина исходного графа имеет четную степень. [15]

Страницы: 1 2