Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
точки в различных компонентах пространства (X, ¦/). Таким образом, G {./)
имеет по крайней мере столько же различных графовых компонент, сколько
пространство (X, .У) - топологических.
G(S)
Топология конечного точечного множества
15
Предположим, наоборот, что G(X) состоит из нескольких компонент G = U,G,.
Тогда множествах = U В" являются несвяз-
peTj и
ными открытыми множествами, объединением которых является X, и,
следовательно, (X , у) имеет по меньшей мере столько же компонент,
сколько и G(X).
Объединяя эти два результата, приходим к выводу, что конец* ное
топологическое пространство и его граф имеют одно и то же число
компонент. В частности, связный граф соответствует связному пространству.
Аксиомы разделения. Пространство не является пространством типа Т0, если
оно содержит по крайней мере одну пару точек, которые либо обе
присутствуют, либо обе отсутствуют в каждом открытом множестве, т.е. они
топологически неразличимы. Если р и q являются такой парой, то р е Bq и q
е Вр, так что для диграфа
не-Г0-пространства характерно наличие подграфа . Этот
подграф не может быть результатом ориентации двудольного графа, поэтому
пространства графовой топологии являются Г0-про-странствами.
С другой стороны, конечное Г,-пространство, в котором каждая из
произвольной пары точек принадлежит к открытому множеству, не содержащему
другую пару точек, имеет диграф D(.X), в котором множество ребер является
пустым (т. е. конечное Ггпростран-ство имеет дискретную топологию),
поскольку для каждой p,q р & Bq и q & Вр. Таким образом, пространства
графовой топологии не являются Г,-пространствами.
Действительно, эти пространства образуют подмножество класса всех ^-
пространств, поскольку последнее включает такие пространства, как г
, которые не могут возникнуть из
двудольного графа. Основным свойством, характеризующим эти пространства,
является то, что для каждой вершины (X) их диграфа одно из множеств -
захода в вершину (U?), исхода из вершины (Ux ) - пустое. Это означает,
что каждая точка пространства является либо открытым (Ux - 0), либо
замкнутым ({/л+ = 0) множеством.
Гомеоморфизм. Поскольку граф топологии единственный, следовательно,
никакие два различных графа не приводят к одному и тому же
топологическому пространству. С химической точки зрения это означает, что
только гомеоморфные молекулы являются стереоизомерами.
16
Р. Меррифилд, X. Симмонс
2.3. КОЛИЧЕСТВЕННЫЕ ХАРАКТЕРИСТИКИ
ГРАФОВОЙ ТОПОЛОГИИ: КОМБИНАТОРИКА
Комбинаторные аспекты, которые возникают естественным образом при
рассмотрении структуры конечного топологического пространства, не имеют
аналогий в континуальной топологии, где постановка таких вопросов лишена
смысла. Первый вопрос комбинаторики, относящийся к конечному
пространству, - это вопрос о числе открытых множеств, т. е. \./1.
Открытые множества образуются как объединения базисных элементов Вр.
Однако не все такие объединения различны. Для произвольного объединения
базисных множеств
V = Вх U В2 U ...,
если, скажем, В{ с В2, тогда В{ может быть исключено из объединения без
влияния на результат. Таким образом, различные открытые множества будут
получаться, только если никакие два базисных множества, входящие в
объединение, не являются сравнимыми (по вложению). Однако сравнимыми
базисными множествами считаются множества, соответствующие смежным
вершинам G(У), так что каждое множество взаимно несмежных вершин графа G
{¦/) приводит к иному открытому множеству. Другими словами, мощность
конечной топологии \-/\ равна числу независимых множеств вершин ее графа.
Следующий шаг состоит в перечислении независимых множеств вершин графа,
число которых будет обозначаться как a(G). Удобнее всего это сделать
рекуррентно. Рассмотрим соотношение между независимыми множествами графа
G и такими множествами графов G, в которых вершина р удалена. Каждое
независимое множество G-р также независимо в G. Другие независимые
множества графа G являются объединениями р с теми независимыми
множествами G-р, которые не содержат вершин, смежных с р. Число таких
множеств равно ct(G - р - Ар), где Ар - множество вершин графа G, смежных
с р. Таким образом, основное рекуррентное соотношение для a(G)
записывается в виде
a(G) = a(G -р) + a(G - р - Ар). (1)
Предположим, что G - двухкомпонентный граф G, U G2. Тогда независимые
множества G являются результатом объединений любого независимого
множества G, с любым множеством G2. Вторая основная формула получается с
помощью индукции:
ff(U,G() = П,.а(С,).
(2)
Топология, конечного точечного множества
17
Этот один из конечных результатов завершает схему расчета ct(G) для
любого графа. Рассмотрим путь Рп и влияние добавления точки к одному
концу с образованием Р"+1. Согласно рекуррентному соотношению (1),
<т(Ря+1) = а(Р") + а(Р"_,), (3)
что идентично рекуррентному соотношению Фибоначчи:
+ i i> = = О-
Поскольку P0 имеет одно независимое множество (0), а Р, - два (0, {1\),
