Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
которые, хотя и непредставимы адекватно на плоскости (поскольку могут
иметь место пересечения), могут быть уложены на римановой поверхности.
Будет видно, что при таком формализме отрицательные элементы полученных
матриц смежности обусловлены совершенно естественным образом топологией
римано-вых поверхностей, а не вводятся искусственно, как это было в
прежнем подходе [5], в результате более случайных и более интуитивных
физических соображений. Подчеркнем также, что условия теоремы Перрона-
Фробениуса [16] для неотрицательных матриц неприменимы к матрицам
смежности мебиусовских графов; нами обсуждается важность этого
обстоятельства для собственных значений и собственных векторов таких
графов.
2. ФОРМАЛИЗМ МЕТОДА
Предположим существование графов, которые не могут быть уложены без
пересечений на плоскости, но могут быть уложены на данной римановой
поверхности. Пусть вершины графа G представляют переменные и, v, х, у,
... и т. д., а ребра графа G - некоторую функцию / двух переменных,
которых данное ребро соединяет, как, например, показано на рис. 1. В этом
случае граф G - графическое представление множества функций двух
переменных между определенными парами переменных. Такое представление
будет полностью удовлетворительным, если может быть гарантировано,
что/(х, .у) для некоторых х,у е V графа G = [ V; Е\ (где V - множество
вершин и Е - множество ребер графа G) будет однозначной функцией. Однако
часто оказывается, что функция/неоднозначна. В таком случае в обычной
практике вне области теории графов (см., например, [17]) функцию/
представляют на римановой поверхности,
РИС 1 Представление функции/(л:, у) с помощью графа.
* То есть недиагональных элементов а матрицы смежности, которая
соответствует планарному графу, представляющему связность углеродных
атомов в рассматриваемой мебиусовской системе.
Использование римановых поверхностей
311
имеющей столько листов, сколько необходимо для того, чтобы каждое
значение функции * могло быть представлено на отдельном листе. Тогда на
каждом листе функция / будет однозначной. Например, если z = х + iy и
f(x,y) = /(г), то функция комплексного переменногоf(z) = ZW2 является
двузначной, т. е. для каждого значения z имеются два значения /(г), и
функция может быть полностью представлена на двулистной римановой
поверхности ^2. Поверхность можно представить [17], если рассматривать
г-плоскость, показанную на рис. 2, как включающую два наложенных друг на
друга листа. Оба листа теперь разрезаются по линии ОА, и разрезанное
ребро верхнего листа, как раз ниже ОА на рис. 2, соединяется с
разрезанным ребром нижнего листа, как раз выше ОА, и наоборот. Тогда,
если мы начинаем с точки Р на нижнем листе, где г = г0 = г ехр (г'0) и /
= /0 = г1/2 ехр (гв/2), и осуществляем полный поворот против часовой
стрелки вокруг исходной точки 0, мы возвращаемся к точке P(z0), но на
верхнем листе, где / = _ri/2 ехр (/0/2) = -/0. Для того чтобы вернуться
к/ = /0, необходим второй полный поворот. Таким образом достигается
двойное покрытие комплексной плоскости г. Каждый лист ^2 соответствует
одной ветви функции, и на таком листе функция г1/2 однозначна. Мы
обозначим линию ОА и аналогичную линию в (т > 2) как линию разветвления
римановой поверхности. Распространение на случаи более высокого порядка
осуществляется непосредственно: например, /(г) = г1/3 полностью
представляется на трилистной римановой поверхности и / (г) = loge г - на
поверхности имеющей бесконечно много листов.
Эти соображения позволяют предположить, каким образом может быть
разработан теоретико-графовый метод представления графов многозначных
бинарных отношений - а именно путем
РИС 2 Представление многозначной функции f(z) в ПЛОСКОСТИ Z.
ОА - линия разветвления, вдоль которой разрезаются наложенные одна на
другую z плоскости для того, чтобы образовать ^ или
S (т > 2) т v '
'(ЛЬ ж
* При данном значении переменной. - Прим. перев.
312
А. Дей, Р. Маллион, М. Ригби
О
О
ДисшТ Лист П
a(Sf} = +1
p(S,h + \
Sz
a(Sj--1 p(Sz) = - 1
A
1
2
A
РИС. 3 Типичный граф (!) на римановой поверхности Если бы vRv имело лишь
единственное значение, то этот граф мог бы быть представлен адекватно в
плоскости, как в случае 2
РИС 4 Граф на римановой поверхности с^2, матрица смежности которого пред
ставлена уравнением (1).
укладки графа, представляющего /я-злачное бинарное отношение на римановой
поверхности Зёт. Для простоты ограничимся случаем двузначного бинарного
отношения R. Граф { V; R} легко может быть изображен на поверхности
следующим образом:
1. Изображаем линию, которая будет представлять собой линию разветвления
(ОА на рис. 2) поверхности аЛ2-
2. На этой линии изображаем все вершины графа G (е V).
3. R может принимать любое из двух значений I и II, и, если vtRVj
принимает значение I, изображаем ребро (г,, Vj) на листе I поверхности
&2' если vfivj принимает значение II, изображаем это ребро на листе II.
Типичный граф, полученный таким путем, может выглядеть, как показано на
