Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
к. Известен ряд ^-реберных "стягиваемых" подграфов графа G; это число
способов выбора К ребер из множества ребер графа G. И число несвязных
подграфов оказывается реконструируемым с помощью расширенной нами леммы
Кэли.
Существует аналогичная теория, рассматривающая вместо несвязных
сепарабельные (но связные) графы. Мы нашли возможность реконструкции
числа стягиваемых сепарабельных связных подграфов графа G с данным
множеством блоков. Обнаружив это, мы сообщаем В, что он может определить
число стягиваемых несепарабельных подграфов графа G с данным числом
ребер.
308
У. Татт
В частности, мы можем реконструировать число стягиваемых деревьев и число
гамильтоновых циклов в графе G. Первое является числом стягиваемых
связных подграфов с п - 1 вершинами, второе - числом стягиваемых
несепарабельных подграфов с п ребрами.
Все это представляется увлекательным для человека, впервые знакомящегося
с теорией реконструкции. Но когда он приобретет опыт, будет отрицательно
к этому относиться, говоря, что это лишь набор упражнений по применению
леммы Кэли.
Имеются особые классы графов, принадлежность к которым может быть
установлена и члены которых реконструируемы. Рассмотрим, например, к-
валентные регулярные графы, в которых каждая вершина имеет валентность к.
Мы можем сказать, что граф G относится к этому виду, если установим, что
каждый подграф Gj имеет как раз на к меньше ребер, чем граф G. Если это
так, то проблема реконструкции графа из любого подграфа Gy тривиальна.
Другой такой особый класс образуют деревья. Связный граф G будет деревом,
если каждый подграф Gy - лес и хоть какой-то подграф Gj не является
цепью. Таким образом, деревья распознаваемы, и Кэли доказал, что они
реконструируемы. Это доказательство нетривиально. Отметим, однако, что,
помимо некоторых тривиальных случаев, наибольшие цепи, имеющиеся среди
Gy, являются цепями наибольшей длины в графе G. Но любые две цепи
наибольшей длины в G имеют одно и то же среднее ребро или вершину. Итак,
можно предположить, что среднее ребро или вершина графа G оказываются в
более чем одном подграфе Gy. Это служит первой путеводной нитью к
определению того, что подграфы Gy перекрываются в графе G.
Оставляя эти особые случаи в стороне, я думаю, что будет справедливо
сказать о том, что современная общая теория реконструкции остановилась на
лемме Кэли. Многое можно извлечь из того факта, что некоторые полиномы,
.соответствующие графу G, реконструируемы. Но эти полиномы могут быть
выражены с помощью соответствующих подграфов графа G, которые могут быть
адекватно перечислены с использованием леммы Кэли и наших расширенных
вариантов ее.
ИСПОЛЬЗОВАНИЕ РИМАНОВЫХ ПОВЕРХНОСТЕЙ В ТЕОРЕТИКО-ГРАФОВОМ ПРЕДСТАВЛЕНИИ
МЁБИУСОВСКИХ СИСТЕМ
А. Дей (А.С. Day) \ Р. Маллион (R.B. Mallion)2,
М. Ригби (M.J. Rigby) 3
1 The Dyson Perrins Laboratory, University of Oxford, United Kingdom 2
The King's School, Canterbury, United Kingdom 3 1, Church House, Orts
Road, Reading, United Kingdom
Изучены мёбиусовские системы с использованием нового теоретикографового
метода, включающего рассмотрение непланарных графов, которые могут быть
уложены без пересечений на двулистной римановой поверхности. В рамках
такого формализма появление отрицательных элементов в полученных матрицах
смежности связано совершенно естественным образом с математическим
аппаратом римановых поверхностей, при этом отпадает необходимость
прибегать к довольно интуитивным физическим соображениям. Кроме того,
подчеркивается, что условия теоремы Перрона-Фро-бениуса для
неотрицательных матриц неприменимы к матрицам смежности мёбиусовских
графов, и обсуждается важность этого обстоятельства для собственных
значений и собственных векторов таких графов.
1. ВВЕДЕНИЕ
В настоящее время в теоретической органической химии достаточно хорошо
разработаны теоретико-графовые формулировки простой теории молекулярных
орбиталей для сопряженных систем (например, [1-4]). Такое рассмотрение
почти всегда основывается на молекулярных графах, которые могут быть
уложены (т. е. "изображены") без пересечений на плоскости. Несколько лет
назад Граовач и Тринайстич распространили эти идеи, относящиеся к
планарным графам, на мёбиусо .ские системы (циклические системы 2/7..-
орбиталей с нечетным числом инверсий знака, возникающих в результате
отрицательных перекрываний между соседними орбиталями базисного набора с
противоположным знаком в областях перекрывания [5-13]*). Их подход
включал совершенно правильный, но до некоторой степени произвольный
способ задания "обрамляющих"
* См. также [22*]. - Прим. перев:
310
А Дей, Р Маллион, М. Ригби
весовых коэффициентов ребер* [14] при +1, если 2р,-орбитали атомов
углерода / и j имеют ориентацию "положительная - положительная", и при -
1, если эти орбитали имеют ориентацию "положительная - отрицательная".
В этой статье нами вводится новая теоретико-графовая трактовка
мебиусовских систем [15], основанная на рассмотрении непланарных графов,
