Практическое применение теории графов. Теория Графов в химии и нерешённые задачи Графы и химия

1 За последние десятилетия в теоретиче-ской химии широкое распространение получи-ли представления топологии и теории графов. Они полезны при поиске количественных соот-ношений «структура - свойство» и «структура-активность», а также в решении теоретико-графовых и комбинаторно-алгебраических за-дач, возникающих в ходе сбора, хранения и об-работки информации по структуре и свойствам веществ.

Графы служат, прежде всего, средством изображения молекул. При топологическом описании молекулы её изображают в виде мо-лекулярного графа (МГ), где вершины соответ-ствуют атомам, а рёбра - химическим связям (теоретико-графовая модель молекулы). Обыч-но в таком представлении рассматривают толь-ко скелетные атомы, например, углеводороды со «стёртыми» атомами водорода.

Валентность химических элементов на-кладывает на степени вершин определённые ограничения. У деревьев-алканов (связных гра-фов, не имеющих циклов) степени вершин (г) не могут превышать четырёх (г = 1, 2, 3, 4).

Графы можно задавать в матричном виде, что удобно при работе с ними на ЭВМ.

Матрица смежности вершин простого графа - это квадратная матрица А = [аσχ] с эле-ментами аσχ = 1, если вершины σ и χ соедине-ны ребром, аσχ = 0 - в противном случае. Ма-трица расстояний - это квадратная матрица D = с элементами dσχ, определяемыми как минимальное число рёбер (наикратчайшее рас-стояние) между вершинами σ и χ. Иногда при-меняются также матрицы смежности и расстоя-ний по рёбрам (А е и D e).

Вид матриц А и D (А е и D e) зависит от спо-соба нумерации вершин (или рёбер), что вызы-вает неудобство при обращении с ними. Для характеризации графа применяются инварианты графа - топологические индексы (ТИ).

Число путей длины один

pi = хсс 0 = m = n-1

Число путей длины два

Число троек смежных ребер (с общей вершиной)

Число Винера (W), определяемое как по-лусумма элементов матрицы расстояний рассма-триваемого графа:

и т.д.

Методология изучения связи «структура-свойство» через топологические индексы в теоретико-графовом подходе включает в себя следующие этапы .

Выбор объектов исследования (обучаю-щая выборка) и анализ состояния численных данных по свойству Р для данного круга соеди-нений.

Отбор ТИ с учетом их дискриминирую-щей способности, корреляционной способности со свойствами и т.д.

Изучение графических зависимостей «Свойство Р - ТИ графа молекулы», например, Р от n - числа скелетных атомов, Р от W - чис-ла Винера и т.п.

Установление функциональной (аналити-ческой) зависимости Р = _ДТИ), например,

Р = а(ТИ) + b ,

Р = аln(ТИ) + b ,

Р = а(ТИ) 1 +b(ТИ) 2 +...+n(ТИ) n +с

и т.п. Здесь а, b, с - некоторые параме-тры (не следует путать их с параметрами адди-тивных схем.), подлежащих определению.

Численные расчеты Р, сопоставление рас-считанных значений с экспериментальными.

Предсказание свойств еще не изученных и даже не полученных соединений (вне данной выборки).

Топологические индексы также исполь-зуются в построении аддитивных схем расчёта и прогнозирования. Они могут применяться при разработке новых лекарственных средств, при оценке канцерогенной активности некоторых химических веществ, для предсказания относи-тельной устойчивости новых (ещё не синтези-рованных) соединений и т.д.

Следует однако помнить, что выбор ТИ нередко носит случайный характер; они могут не отражать важные структурные особенности молекул или дублировать информацию (получа-емую с помощью других индексов), а расчетные схемы не иметь прочного теоретического фунда-мента и плохо поддаваться физико-химической интерпретации.

Коллектив кафедры физической химии ТвГУ уже в течение многих лет ведет расчетно-теоретическое исследование по проблеме «Связь свойств веществ со строением молекул: математическое (компьютерное) моделирование». В центре внимания целенаправленный по-иск новых структур, алгоритмы решения ряда теоретико-графовых и комбинаторных задач, возникающих в ходе сбора и обработки инфор-мации о структуре и свойствах веществ, созда-ние экспертных информационно-поисковых си-стем и баз данных, разработка количественных методов расчета и прогнозирования.

Нами были построены аддитивные схе-мы и найдены аналитические зависимости вида Р = У(ТИ) для ряда органических и других мо-лекул. По полученным формулам выполнены численные расчеты физико-химических свойств рассматриваемых соединений, с .

Список литературы

1. Виноградова М.Г., Папулов Ю.Г., Смо-ляков В.М. Количественные корреляции «струк-тура свойство « алканов. Аддитивные схемы расчета. Тверь, 1999. 96 с.
2. Химические приложения топологии и теории графов / Под ред. Р. Кинга. М.: Мир, 1987. 560 с.
3. Применение теории графов в химии / Под ред. Н.С. Зефирова и С.И. Кучанова. Ново-сибирск: Наука, 1988. 306 с.
4. Станкевич М.И., Станкевич И.В., Зе-фиров Н.С. Топологические индексы в органи-ческой химии // Успехи химии. 1988. Т.57, №3,С.337-366.
5. Виноградова М.Г., Салтыкова М.Н. Теоретико-графовый подход в изучении взаимосвязи между строением и свойствами алкилсиланов.// Фундаментальные исследования, 2009. №1. С. 17-19.
6. Виноградова М.Г., Салтыкова М.Н., Ефремова А.О., Мальчевская О.А. Взаимосвязь между строением и свойствами алкилсиланов //Успехи современного естествознания, №1, 2010. С.136-137.
7. Виноградова М.Г., Салтыкова М.Н.,Ефремова А.О. Корреляции «Структура - свойство» алкилсиланов: теоретико-графовый подход // Успехи современного естествознания, №3, 2010. С.141-142.

Библиографическая ссылка

Виноградова М.Г. ТЕОРИЯ ГРАФОВ В ХИМИИ // Международный журнал прикладных и фундаментальных исследований. – 2010. – № 12. – С. 140-142;
URL: http://dev.applied-research.ru/ru/article/view?id=1031 (дата обращения: 17.12.2019). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»

Для создания комплексов программ автоматизир. синтеза оптим. высоконадежных произ-в (в т. ч. ресурсосберегающих) наряду с принципами искусств. интеллекта применяют ориентированные семантические, или смысловые, графы вариантов решений ХТС. Эти графы, к-рые в частном случае являются деревьями, изображают процедуры генерации множества рациональных альтернативных схем ХТС (напр., 14 возможных при разделении ректификацией пятиком"понентной смеси целевых продуктов) и процедуры упорядоченного выбора среди них схемы, оптимальной по нек-рому критерию эффективности системы (см. Оптимизация).

Графов теорию используют также для разработки алгоритмов оптимизации временных графиков функционирования оборудования многоассортиментных гибких произ-в, алгоритмов оптим. размещения аппаратуры и трассировки трубопроводных систем, алгоритмов оптим. управления химико-технол. процессами и произ-вами, при сетевом планировании их работы и т.д.

Лит.. Зыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; Яцимирский К. Б., Применение теории графов в химии , Киев, 1973; Кафаров В. В., Перов В. Л., Мешалкин В. П., Принципы математического моделирования химико-технологических систем, М., 1974; Кристофидес Н., Теория графов. Алгоритмический подход, пер. с англ., М., 1978; Кафаров В. В., Перов В. Л., Мешал кин В. П., Математические основы автоматизированного проектирования химических производств , М., 1979; Химические приложения топологии и теории графов, под ред. Р. Кинга, пер. с англ., М., 1987; Chemical Applications of Graph Theory, Balaban A.T. (Ed.), N.Y.-L., 1976. В. В. Кафаров, В. П. Мешалкин.
===
Исп. литература для статьи «ГРАФОВ ТЕОРИЯ» : нет данных

Страница «ГРАФОВ ТЕОРИЯ» подготовлена по материалам

Предисловие редактора перевода
Предисловие к русскому изданию
Предисловие
ТОПОЛОГИЯ КОНЕЧНОГО ТОЧЕЧНОГО МНОЖЕСТВА И МОЛЕКУЛЯРНАЯ СТРУКТУРА. Р. Меррифилд, X. Симмонс
1. Введение
2. Конечная топология
2.1. Граф топологии
2.2. Качественные характеристики графовой топологии
2.3. Количественные характеристики графовой топологии: комбинаторика
3. Топология альтернантных молекул
3.1. Сложность структуры
3.2. Связность и делокализация
4. Топология неальтернантных молекул
4.1. Дуплекс графа
4.2. Топология дуплекса
Литература
СТЕРЕОХИМИЧЕСКАЯ ТОПОЛОГИЯ. Д. Волба
1. Введение
2. Подход к синтезу топологических стереоизомеров, основанный на лентах Мебиуса
2.1. Полный синтез первой молекулярной ленты Мебиуса
3. Критерии топологической стереоизомерии
3.1. Топологическая хиральность
3.2. Топологическая диастереоизомерия
4. «Клиппинг»-реакция (clipping reaction) и подходы к синтезу молекулярного трилистного узла
4.1. Разрыв ступеней мебиусовой лестницы
4.2. Молекулярный трилистный узел
Литература
КАЧЕСТВЕННАЯ СТЕРЕОХИМИЯ Дж. Дугунджи
1. Введение
2. Пермутационные изомеры
3. Группа химической идентичности
Литература
ТЕОРИЯ МОЛЕКУЛЯРНОЙ СТРУКТУРЫ. Р. Бейдер
1. Обзор теории
2. Некоторые приложения
Литература
АЛГЕБРАИЧЕСКАЯ И ТОПОЛОГИЧЕСКАЯ СТРУКТУРА КВАНТОВОЙ ХИМИИ, ХИМИЧЕСКОЙ КИНЕТИКИ И НАГЛЯДНЫЕ ПРАВИЛА, ПОЗВОЛЯЮЩИЕ СДЕЛАТЬ КАЧЕСТВЕННЫЕ ПРОГНОЗЫ ДЛЯ ХИМИЧЕСКОЙ ПРАКТИКИ. О. Синаноглу
1. Введение
2. Микрохимия или качественные квантовохимические правила, полученные непосредственно из структурных формул или диаграмм ORTEP
2.1. Поле векторного пространства валентностей Vn(R), существующее в евклидовом трехмерном пространстве (?)
2.2. Принцип линейной ковариантности в квантовой химии
2.3. Неунитарная классификация молекул
2.4. От структурных формул молекул к более детальным структурно-электронным формулам (и к графам)
2.5. «Структурная и деформационная ковариантность» молекул и графические правила для получения качественных квантовохими-ческих результатов
3. Морфология реакционных механизмов, путей синтеза и топологические «правила стадия/соединение»
4. Особенности получения квантовых качественных характеристик каждой реакционной стадии механизма или пути реакции
Литература
РЕАКЦИОННАЯ ТОПОЛОГИЯ: ТЕОРИЯ МНОГООБРАЗИЙ ПОТЕНЦИАЛЬНЫХ ПОВЕРХНОСТЕЙ И КВАНТОВОХИМИЧЕСКИЙ ДИЗАЙН СИНТЕЗА. П. Межей
1. Введение
2. Топологические многообразия, дифференцируемые многообразия и реакционная топология
3. Соотношения критических точек; графы пересечения в топологическом пространстве (М, Тс) и квантовохимические схемы реакций
4. Вычислительные аспекты
5. Вырожденные критические точки и химические структуры, не отвечающие истинным минимумам ППЭ
6. Выводы
Литература
ТОПОЛОГИЯ СВЯЗЫВАНИЯ В ПОЛИЭДРИЧЕСКИХ МОЛЕКУЛАХ. Р. Кинг
1. Введение
2. Основа концепции
3. Атомы вершин
4. Полиэдрические системы с локализованным связыванием
5. Системы с полностью делокализованным связыванием
6. Электронно-избыточные полиэдрические системы
7. Электронно-дефицитные полиэдрические системы
8. Аномальные вершины
9. Полиэдраны
10. Выводы
Литература
ФОРМЫ КЛАСТЕРОВ ЭЛЕМЕНТОВ ГЛАВНЫХ ПОДГРУПП: ТОПОЛОГИЧЕСКИЙ ПОДХОД К СЧЕТУ СКЕЛЕТНЫХ ЭЛЕКТРОНОВ. М. Мак-Глинчи, Й. Таль
1. Введение
2. Кластеры с полностью делокализованным связыванием
3. Кластеры с локализацией связывания на ребрах
3.1. Шестиатомные кластеры
3.2. Семиатомные кластеры
3.3. Восьмиатомные кластеры
4. Квантово-топологическое обоснование полиэдрической модели
5. Выводы
Литература
ТОПОЛОГИЧЕСКИЕ СВОЙСТВА БИНАРНЫХ СОЕДИНЕНИЙ СЕРЫ С АЗОТОМ. А. Тернер
1. Введение
2. Прототипная молекула - тетранитрид тетрасеры
3. Плоские циклические молекулы и ионы SnNm
4. Неплоские системы - эквивалентность центров зарядового распределения
5. Применение теории функционала электронной плотности
Литература
СЛЕДУЕТ ЛИ ЗАНИМАТЬСЯ РАЗРАБОТКОЙ ТОПОЛОГИЧЕСКИХ ИНДЕКСОВ? Д. Руврэ
1. Введение
2. Индекс Винера
3. Конструирование индексов
4. Индексы матрицы расстояний
5. Индексы матрицы смежности
6. Центрические топологические индексы
7. Теоретико-информационные индексы
8. Составные топологические индексы
9. Некоторые математические соотношения
10. Форма и размер молекул
11. Основные применения индексов
12. Библиографическая классификация соединений
13. Определение физико-химических параметров
14. Разработка фармацевтических лекарственных препаратов
15. Выводы
Литература
ТОПОЛОГИЧЕСКИЕ ИНДЕКСЫ, ОСНОВАННЫЕ НА СИММЕТРИИ ОКРЕСТНОСТЕЙ: ХИМИЧЕСКИЕ И БИОХИМИЧЕСКИЕ ПРИМЕНЕНИЯ. В. Магнусон, Д. Харрис, С. Бейсак
1. Введение
2. Информационное содержание графа
2.1. Определения
2.2. Основные положения
2.3. Соотношение эквивалентности
2.4. Расчет других топологических индексов
3. Расчет индексов
4. Применения при исследованиях количественных корреляций структура-активность (ККСА)
4.1. Растворимость спиртов
4.2. Ингибирование микросомального пapa-гидроксилирования анилина спиртами
4.3. Токсичность (LD50) барбитуратов
Литература
УПОРЯДОЧИВАНИЕ ГРАФОВ КАК ПОДХОД К ИССЛЕДОВАНИЯМ КОРРЕЛЯЦИЙ СТРУКТУРА-АКТИВНОСТЬ. М. Рандич, Дж. Краус, Б. Дзонова-Джерман-Блазич
1. Введение
2. Основные принципы метода
3. Применение к веществам, обладающим антималярийным действием
3.1. Построение последовательности цепей
3.2. Сравнение молекул А-М
4. Обсуждение
Литература
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МОЛЕКУЛЯРНОЙ СЛОЖНОСТИ. С. Бертц
1. Ваедение
2. Разработка модели
2.1. Теория графов и молекулярная топология
2.2. Теория информации и молекулярная симметрия
3. Проверка модели
3.1. Ограничения модели
4. Надежность модели
5. Выводы
Литература
МАТРИЦА РАССТОЯНИЙ ДЛЯ МОЛЕКУЛ, СОДЕРЖАЩИХ ГЕТЕРО-АТОМЫ. М. Бариш, Дж. Яшари, Р. Лалл, В. Шривастава, И. Тринайстич
1. Введение
2. Взаимосвязь между матрицей смежности и матрицей расстояний
3. Матрица расстояний для гетеросистем
Литература
КАНОНИЧЕСКАЯ НУМЕРАЦИЯ И СИСТЕМА ЛИНЕЙНЫХ ОБОЗНАЧЕНИЙ ХИМИЧЕСКИХ ГРАФОВ. У. Херндон
1. Введение
2. Каноническая нумерация
3. Однозначные линейные обозначения
4. Каноническая нумерация регулярных графов
5. Выводы
Литература
СИММЕТРИЯ И СПЕКТРЫ ГРАФОВ. ИХ ПРИМЕНЕНИЯ В ХИМИИ. К. Баласубраманиан
1. Введение
2. Обрезка деревьев
3. Обрезка деревьев и группы симметрии деревьев
4. Спектральные полиномы деревьев, получаемые с помощью процесса обрезки
5. Применения в химии
Литература
ГРУППЫ АВТОМОРФИЗМОВ НЕКОТОРЫХ ХИМИЧЕСКИХ ГРАФОВ. Г. Джонс, Э. Ллойд
1. Введение
2. Некоторые графы и их группы
3. Реакционные графы
3.1. Пример 1: механизм Берри
3.2. Пример 2: 1,2-сдвиги в карбониевых ионах
3.3. Пример 3: 1,2-сдвиги в гомотетраэдранильных катионах
3.4. Пример 4: дигональные твисты в октаэдрических комплексах
3.5. Пример 5: 1,3-сдвиги в гомотетраэдранильных катионах
4. Суборбитальные графы
5. Выводы
Литература
ПРОБЛЕМА РЕКОНСТРУКЦИИ. У. Татт
ИСПОЛЬЗОВАНИЕ РИМАНОВЫХ ПОВЕРХНОСТЕЙ В ТЕОРЕТИКО-ГРАФОВОМ ПРЕДСТАВЛЕНИИ МЁБИУСОВСКИХ СИСТЕМ. А. Дей, Р. Маллион, М. Ригби
1. Введение
2. Формализм метода
3. Применение
4. Выводы
Литература
ГЛОБАЛЬНАЯ ДИНАМИКА НЕКОТОРЫХ КЛАССОВ РЕАКЦИОННЫХ СИСТЕМ. X. Отмер
1. Введение
2. Теоретико-графовая формулировка
2.1. Структура управляющих уравнений
2.2. Некоторые понятия теории графов
2.3. Инварианты реакции
2.4. Существование стационарных состояний
3. Вершинно-управляемые сети
3.1. Постоянные входные потоки
3.2. Периодические входные потоки
4. Выводы
Литература
«ЛОГИЧЕСКОЕ ОПИСАНИЕ» В СРАВНЕНИИ С «НЕПРЕРЫВНЫМ ОПИСАНИЕМ» СИСТЕМ, СОДЕРЖАЩИХ ПЕТЛИ ОБРАТНОЙ СВЯЗИ: СООТНОШЕНИЕ МЕЖДУ ЗАПАЗДЫВАНИЯМИ ПО ВРЕМЕНИ И ПАРАМЕТРАМИ. Р. Томас
1. Введение
2. Логическое описание систем, содержащих петли обратной связи
2.1. Запаздывания «включения» и «выключения»
2.2. Логические уравнения
2.3. Таблицы состояний
2.4. Цепи (последовательности состояний)
2.5. Анализ устойчивости
3. Непрерывное описание
3.1. Логические запаздывания по времени и непрерывные параметры
Литература
КАЧЕСТВЕННАЯ ДИНАМИКА И УСТОЙЧИВОСТЬ ХИМИЧЕСКИХ РЕАКЦИОННЫХ СИСТЕМ. Б. Кларк
1. Введение
2. Задание химической системы
3. Масштабы времени - удаление веществ, реагирующих слишком быстро и слишком медленно
4. Теория химических сетей
5. Динамика системы
6. Многообразие стационарных состояний
7. Простые теоремы для анализа сетей
8. Более глубокое обсуждение стационарных состояний и их существования
9. Правильность
10. Однозначность
11. Глобальное притяжение
12. Сети, в которых многообразием не является правильным, однозначным и глобально притягивающим
13. Топология сети и устойчивость
14. Заключительные замечания
15. Приложение
15.1. Универсальные функции
15.2. Функции для символьной обработки и расчета матрицы токов
15.3. Функции, проверяющие выполнение теорем, и родственные функции
15.4. Отдельные функции
Литература
ВЫСШИЙ ХАОС В ПРОСТЫХ РЕАКЦИОННЫХ СИСТЕМАХ. О. Ресслер, Дж. Хадсон
1. Введение
2. Метод порождения обыкновенного хаоса
3. Метод порождения высшего хаоса
4. Обсуждение
Литература
СТРАННЫЕ АТТРАКТОРЫ В ЛИНЕЙНЫХ ПЕРИОДИЧЕСКИХ ПЕРЕДАТОЧНЫХ ФУНКЦИЯХ С ПЕРИОДИЧЕСКИМИ ВОЗМУЩЕНИЯМИ. X. Дегн
1. Введение
2. Результаты
Литература
ИСПОЛЬЗОВАНИЕ АНАЛИЗА ЧУВСТВИТЕЛЬНОСТИ ПРИ ОПРЕДЕЛЕНИИ СТРУКТУРНОЙ УСТОЙЧИВОСТИ МНОГОПАРАМЕТРИЧЕСКИХ ОСЦИЛЛЯТОРОВ. Р. Лартер
1. Введение
2. Метод
2.1. Стандартная теория
2.2. Модифицированная теория
3. Результаты
3.1. Начальные условия
3.2. Константы скорости
3.3. Более сложные ситуации
Литература
ПРЕДСТАВЛЕНИЕ n-МЕРНЫХ ХИМИЧЕСКИХ МНОГООБРАЗИЙ С ПОМОЩЬЮ ЭЛЕКТРИЧЕСКИХ СЕТЕЙ. Л. Пьюзнер
1. Введение: топологический и геометрический анализ химических процессов
2. Основные геометрические свойства n-мерных метрических многообразий
3. Представление в виде сети
4. Пример для двумерной системы
5. Оптимальные пути
6. Пример использования химической сети для линейных переходов между множественными состояниями
7. Вариационные сети
Приложение: анализ сетей
Литература
ЛОГИКА ХИМИЧЕСКИХ ИДЕИ. П. Плят, Е. Хасс
1. Введение
2. Топология перициклических реакций
3. Решетки перициклических реакций
4. Ортомодулярные и булевы реакционные четырехмерные решетки
5. Выводы
Литература
МНОГОМЕРНАЯ Х-МОДЕЛЬ. ТЕОРЕТИКО-ГРАФОВЫЙ И АЛГЕБРАИЧЕСКИЙ ПОДХОД К ОПИСАНИЮ МЕХАНИЗМОВ СЛОЖНЫХ ХИМИЧЕСКИХ РЕАКЦИЙ. Е. Хасс, П. Плят
1. Введение
2. Однопараметрическая Х-модель
3. Многомерная Х-модель
3.1. Реакционные пути для -циклоприсоединений
4. Выводы
Литература
КЛАССИФИКАЦИЯ МЕХАНИЗМОВ ХИМИЧЕСКИХ РЕАКЦИЙ С ГЕОМЕТРИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ. П. Селлерс
1. Введение
2. Пример Мильнера
3. Механизмы без циклов
4. Другие механизмы
5. Множественные суммарные реакции
6. Выводы
Литература
ГРАФЫ, МОДЕЛИ ПОЛИМЕРОВ, ИСКЛЮЧЕННЫЙ ОБЪЕМ И ХИМИЧЕСКАЯ РЕАЛЬНОСТЬ. Д. Клейн, В. Зайтц
1. Введение
2. Изолированные линейные цепи
3. Подсчет изомеров
4. Конформации разветвленных полимеров
5. Теория скейлинга
6. Матрицы переноса
7. Самоподобие и перенормировка
8. Обсуждение
Литература
ФУНКЦИЯ ОБЪЕМА ДЛЯ ВОДЫ, ОСНОВАННАЯ НА МОДЕЛИ СЛУЧАЙНОГО ПОДГРАФА РЕШЕТКИ. Л. Квинтас
1. Введение и предварительные математические замечания
2. Модель случайных графов для воды
3. Функция объема для воды
4. Соответствие V(p) численным данным
5. Заключительные замечания
Литература
ТОПОЛОГИЧЕСКИЕ АСПЕКТЫ ФЕРМЕНТ-СУБСТРАТНОГО РАСПОЗНАВАНИЯ. С. Сваминатан
1. Проблема фермент-субстратного распознавания
2. Модель Эдельштейн-Розена
3. Метод феноменологического исчисления
4. Гильбертово пространство описания
5. Постулаты для динамики сложных систем
6. Модель фермент-субстратного распознавания
7. Заключительные замечания
Литература
ДИНАМИКА ОБРАЗОВАНИЯ ВТОРИЧНОЙ СТРУКТУРЫ РНК. X. Мартинец
1. Введение
2. Методы минимизации энергии
3. Метод моделирования
4. Выводы
Литература
ПРОГРАММА НА ЯЗЫКЕ ЛИСП ДЛЯ ФУНКЦИОНАЛЬНО-ФРАГМЕНТНОГО ПРЕДСТАВЛЕНИЯ МОЛЕКУЛ И ИХ ГЕОМЕТРИИ. К. Триндл, Р. Гиван
1. Введение
2. Лисп - язык нечисленного программирования
3. Представление молекул с помощью языка лисп
4. Неформальный алгоритм распознавания фрагментов
5. Некоторые специальные проблемы
6. Построение матрицы расстояний с помощью банка данных о фрагментах
7. Факторный анализ и алгоритм Криппена определения геометрии через расстояния
8. Выводы и перспективы
Литература
Предметный указатель

УДК 547.12:541.14(083.73)

ХИМИКУ - О ТЕОРИИ ГРАФОВ: ГРАФЫ В ХИМИЧЕСКОЙ НОМЕНКЛАТУРЕ

Bryuskc Y.E. To the chemist about graph theory: Graphs in the chemical nomenclature. The author addresses this article on different issues of graph theory and the role of graphs in the chemical nomenclature to chemists.

Монография специально посвящена применению графов в химии. Из трех ее разделов наибольший интерес для изучаемой темы представляет раздел «Графы в структурной химии» . А химику, не знающему ничего о графах, достаточно эффективную помощь может оказать приложение [ 1 г]. Наверно, для химиков подойдут еще монографии . А для ознакомления с современным состоянием теории графов подойдет трудная, по-видимому, для нематематика, как и некоторые другие книги по теории графов, книга .

При просмотре доступной информации по применению теории графов в химии (по 2002 г., включая интернет) сложилось впечатление, что обойдены стороной возможность и необходимость применения этой теории в химической номенклатуре. Наряду с общими «химическими» сведениями о теории графов, здесь предпринята попытка немного уменьшить этот недостаток.

1. МОЛЕКУЛЯРНЫЕ ГРАФЫ

Так что такое граф? Это множество точек (непустое и, обычно, конечное) с соединяющими некоторые из них (иногда ни одной, а иногда - все) линиями (здесь и далее необходимые определения и термины выделены полужирным курсивом). Посмотрев на рис. 1, химик скажет, что это - углеродные скелеты этана, бутана, изобутана и циклобутана. А то, что они нарисованы по-разному, не имеет здесь значения. А у циклобутана точки можно и не ставить, как делают это химики, рисуя, например, молекулы циклогексана, бензола и его аналогов (см., напр., рис. 2г и ). Так, вот, подобным графам-скелетам дали название молекулярных графов (МГ). . Еще осталось добавить, что в теории графов точки наиболее часто называют вершинами, а соединяющие их линии - ребрами. Какие еще особенности графов и, соответственно, МГ необходимо отметить. Для графа «безразлично», как пара его вершин соединена ребром, важно только знать, есть оно или нет. Поэтому графы с кратными ребрами называют мулыниграфами. И, таким образом, мультиграфы представляют здесь МГ с двойными или (и) тройными связями (рис. 2). Но не будем добавлять к ним термина «мультиграфы»; так в последнее время поступают и в самой теории графов (см. ).

Таким образом, приведенные здесь МГ отличаются от графа только тем, что их вершины отображают ато-

мы углеродных скелетов, т. е. без атомов водорода, т. к. их добавление весьма значительно усложняет МГ (см. ). Это давно уже поняли химики-органики, не знающие (конечно же, не все) графов, но широко применяющие МГ. Ребра же символизируют связи между некоторыми из атомов углерода.

Рис. 1. МГ этапа (а), бутана (б, в), изобутана (г, д) и циклобутана (е, ж)

Рис. 2. МГ с кратными связями (ребрами): бутена-1 (а), бутена-2 (б), метилпропена (в) и циклогексена (г)

Дадим теперь более общее определение графа, несколько измененное по сравнению с .

Графом называется множество объектов (цельных и безразлично каких - см. определение выше) и заданное множество бинарных (парных) отношений между этими объектами.

Такое определение (конечно, в более строгой математической форме) имеется, очевидно, во всех книгах по теории графов. Оно показывает, что в графе обычно отвлекаются от качественного различия между вершинами и ребрами. Для конкретного графа важно только, есть ли в нем эта вершина-объект (углеродный атом), а также есть ли ребро-отношение (связь) или нет его между этой парой вершин (атомов). Однако это далеко не всегда так! И когда это не так, то появляются мультиграфы (см. выше) и их усложнение псевдографы (в них ребро соединено с одной и той же вершиной в виде петли), помеченные (пронумерованные) графы, раскрашенные, ориентированные (орграфы), взвешенные графы и другие. Определение таких графов почти всегда включает слова: «Граф, который... (у которого...)». Эти же слова можно было бы поставить и перед определением МГ (см. выше).

1.1. СТРУКТУРА ГРАФА

Что еще нужно знать химику о графах (МГ)?

Вершины графа, соединенные ребром, называются смежными, соединенные вершина и ребро называются инцидентными. Число инцидентных одной и той же вершине ребер называется ее степенью или валентностью. Оба варианта почти равноправны в самой теории графов , а «один из основателей современной теории графов» У. Татт в своей книге применяет только термин «валентность» и пишет что «Термин “валентность” навеян химическими аналогиями». Поэтому здесь применение этого термина тем более оправдано. Вершины, не имеющие ребер (например, МГ метана), называются изолированными, валентности 1 - висячими, валентности 2 -двухвалентными (обычно в МГ таких вершин большинство), валентности 3 и 4 - узловыми. А в МГ их соответственно стоит называть первичными, вторичными (неузловые), третичными и четвертичными вершинами или же углеродными атомами, как называют их химики.

Иногда в процессе изучения удаляют из графа некоторые ребра (связи) или вершины. Последние обязательно удаляются со всеми их связями, что приводит к соответствующему уменьшению валентности каждой из смежных с ней вершин, остающихся в графе. Оставшуюся часть называют подграфом исходного графа.

Следуя этому подходу, удалим среднюю связь из МГ бутана (рис. 16). Оставшееся - подграф. Но «добраться» от одного конца этого графа до другого по связям невозможно, хотя «в память» об МГ бутана этот подграф - один граф. В теории графов такие графы называются несвязными, а его связные части - компонентами. Если «присмотреться» с химической точки зрения, то полученный так подграф МГ бутана состоит из двух МГ этана (см. рис. 1а). А связный граф, таким образом, состоит из одной компоненты. Граф, состоящий из одних изолированных вершин (см. выше), на-

зывается вполне несвязным, а противоположный ему граф, у которого каждая вершина соединена ребрами со всеми остальными, называется полным. Вполне понятно, что все МГ обычных органических молекул являются связными графами, даже МГ метана, состоящий из одной изолированной вершины.

1.2. ЦЕПИ И ЦИКЛЫ

На рис. 1 и 2 видно, что в графе (МГ) почти всегда имеется последовательность чередующихся атомов и связей. Такая последовательность в графе называется цепью. Но число ее «звеньев» в МГ будем считать не по числу ребер-связей, как принято в теории графов, , а по числу вершин-атомов. В теории графов у графа этана, рис. 1а одно звено; у МГ того же этана будем считать два звена, а одно - в МГ метана. В теории графов у графа-точки метана нет звеньев. А в химии важнее знать число атомов в цепи по сравнению с числом связей между ними. Рассматривая так МГ изобутана (рис. 1г), следует считать его состоящим из двух цепей. Более длинная цепь состоит из трех вершин-атомов, более короткая - из одной.

В химии, в особенности в органической номенклатуре, для изобутана и более сложных подобных структур (например, рис. За) применяют термин «разветвленная цепь», как будто бы это одна цепь с какими-то «ветвями». Изучение применения этого определения показало, что оно вносило и вносит весьма существенную путаницу в номенклатуру органических соединений, и от него следует решительно отказаться. Термин «разветвление» можно оставить, только лишь рассматривая переход от одной цепи к другой, но не рассматривая структуру, как одну цепь.

Цепь превращается в цикл, если соединить ее начало и конец новой связью.

На рис. 3 показан ациклический МГ (а) с двумя цепями: 1-5 и 6, 7. На этом же рисунке показано, что МГ нафталина (б) и спироундекана (в) содержат по два простых конденсированных цикла, имеющих общие атомы. У МГ нафталина таких атомов два: 5 и 10, а у МГ спироундекана - один, 6. У дифенила циклы разобщены: связь 7, 6 не входит ни в один из них.

10______И 1________________?

Рис. 3. Нумерованные МГ: 3-этилпентана (а), нафталина (б), спироундекана (в) и дифенила (г). В МГ‘ б и г ароматичность циклов не обозначена

1.2.1. БЛОКИ, ТОЧКИ СОЧЛЕНЕНИЯ, МОСТЫ

В теории графов выделяют такие графы, которые становятся несвязными только после удаления более чем одной вершины. Такой граф имеет название блок. МГ циклогексена, рис. 2г, и нафталина, рис. 3 - блоки, а МГ спироундекана не является блоком, так как для того, чтобы сделать его несвязным, достаточно удалить одну вершину 6. Она называется точкой сочленения. В МГ дифенила две точки сочленения - 6 и 7. А удаление ребра, соединяющего эти точки, также приводит к несвязному графу. Такое ребро имеет название мост или перешеек, в структуру циклов эти ребра не входят. Рассматривать ациклический граф в этом аспекте нет смысла, так как в нем все ребра являются мостами, а все вершины, кроме висячих - точками сочленения. Конденсированные циклы, даже имеющие точку сочленения, в органической химии относят к цельной циклической системе, а циклы, разделенные хотя бы одним мостом, являются отдельными системами (в номенклатуре - ансамбли циклов).

1.2.2. ГАМИЛЬТОНОВ ЦИКЛ

В МГ простых циклов имеется замкнутая цепь, содержащая все атомы цикла. Название такого цикла -гамильтонов цикл (не «гамильтоновый»). Кроме простых гамильтонов цикл имеется во многих конденсированных циклах, например, в МГ нафталина, рис. 36. В МГ рис. Зв и Зг цепи содержат все атомы МГ, но не замкнуты в циклы. Такая цепь называется гамильтоновой цепью. Гамильтонова цепь имеется в МГ нормального углеводорода, например, бутана (рис 16, в).

1.2.3. ДЕРЕВЬЯ. ЦИКЛИЧЕСКИЙ РАНГ

Таким образом, в теории графов представлены две фундаментальные формы графов: деревья и циклы (простые и конденсированные), которым в химии однозначно соответствуют два класса МГ: нециклических (ациклических) и циклических углеводородов (рис. 3). Деревом называют только связный ациклический граф, соответствующий несвязный - это лес.

Не зная теории графов, химики оперируют с одним из фундаментальных ее понятий - цикломатическим числом (циклическим рангом) графа, определяя число циклов в скелете (МГ) углеводорода как число связей, которые надо разорвать, чтобы из циклического получить нециклический МГ. В теории графов дерево, полученное таким образом из циклического МГ, называется остовом, а любая связь, образующая в нем цикл при обратной процедуре, называется хордой. Циклический ранг графа и, соответственно, число циклов (с) в МГ углеводорода определяется как число таких хорд по формуле (1):

с =

где - число связей, р - число вершин-атомов в МГ. В любом ациклическом МГ число циклов, конечно, равно нулю и из (1) следует, что число атомов в нем на 1 больше числа связей, что известно не только спе-

циалисту по теории графов, но и химику. Химическим аналогом этой формулы является формула (2)

с= 1/2р3+/?4+ 1, (2)

где Рз - число третичных, а р4 - число четвертичных углеродных атомов.

1.3. ИЗОМОРФИЗМ И ИЗОМЕРИЯ

Весьма важный аспект изоморфизма, общий для теории графов и органической номенклатуры, в теории графов обычно рассматривают вначале. «Невольно» он и отражен здесь в первом же рисунке. На вопрос, идентичны ли пары МГ бутана (16, в), изобутана (1 г, д) и циклобутана (1е, ж), химик ответит «да», а в теории графов ответят «нет». Ответ будет: они изоморфны. Изоморфизм - это отношение эквивалентности на графах , , одним из вариантов которого может быть их идентичность (равносильность), если их можно совместить, не изменяя одного из рисунков. Автор книги по основам современной номенклатуры органических соединений показывает , что можно преобразовывать для совмещения различные формы одной и той же молекулярной структуры (углеродного скелета), а также и то, как можно попыткой подобного совмещения убедиться в том, что сравниваемые структуры не совмещаются и представляют изомерные молекулы, отличающиеся различным порядком связей (структурная изомерия) и не являющиеся, конечно, изоморфными [Там же, с. 43, 44]. Таким образом, изомерные графы так же как и изомерные МГ, описывающие изомерные молекулы, являются неизоморфными графами, имеющими вершины с одним и тем же заданным распределением валентностей. Такие графы и именно в качестве изомерных МГ начали изучать еще в конце XIX века , однако химический термин «изомерные» они получили в теории графов, по-видимому, только в самое последнее время , . Изомерия графов (МГ) соответствует только структурной изомерии молекул и не включает оптическую, конформационную и другие химические виды изомерии, хотя, аналогично перспективным МГ (см. ниже п. 2.2.), образованы еще специальные виды МГ, отражающие эти и другие аспекты структурной химии .

1.3.1. ПРОБЛЕМА ИЗОМОРФИЗМА

Простейшая, на первый взгляд, проблема определения принадлежности различных изоморфных МГ одной и той же молекуле становится весьма сложной и острой при переходе к циклическим МГ. Авторы уникальной монографии по номенклатуре органических соединений довольно подробно анализируют то, как можно нарисовать много различных изображений углеродных скелетов одной и той же сложной циклической молекулы, да так, что часто становится непонятным, какие же из этих рисунков изображают одну и ту же структуру. Они же показали, как много путаницы и противоречий возникало (и имеется до сих пор) в этом отношении на протяжении всей

Рис. 4. Изоморфные МГ углеводорода СцНм

истории развития номенклатуры органических соединений. Например, с первого взгляда совсем неясно, что все пять МГ, изображенных на рис. 4, изоморфные и соответствуют одному и тому же (гипотетическому) углеводороду. А если некоторые из них нарисованы неплоскими, с пересечениями связей вне атомов, как на рис. 4д (см. § 2), распознать их еще труднее. А рис. 4д показывает, что этот МГ имеет гамильтонов цикл.

2. ПЛАНАРНОСТЬ 2.1. УКЛАДКИ

Возвратимся к изображениям МГ на плоскости, как исходной основе теории графов (см. первое определение графа). Если граф (МГ) можно нарисовать на листе бумаги без пересечения связей вне атомов, то считают, что такой МГ укладывается на плоскости. Если МГ можно так уложить на плоскости, даже если он нарисован с пересечениями, его называют планарным, а если он уже уложен (т.е. без таких пересечений), то плоским. А есть ли непланарные графы, которые нельзя уложить на плоскости? Теория графов установила не только их существование, но и то, как это можно определить. Однако при рассмотрении громадного числа циклических МГ в течение многих лет не удалось найти ни одного, который был бы непланарен, хотя большинство из них химики рисуют неплоскими: часто так их нарисовать легче. Поэтому будем считать все МГ обычных органических молекул планарными до тех пор, пока это не будет опровергнуто дополнительными поиском или синтезом.

2.2. НЕПЛАНАРНОСТЬ И ДВУДОЛЬНЫЕ ГРАФЫ

Все же два критерия свидетельствуют о том, что непланарные молекулярные структуры могут быть. Первый - «диагональная», еще не синтезированная форма бензола. На рис. 5а ее МГ показан в той форме, в которой его изображают в книгах по химии (в центре шестиугольника атома нет), а на рис. 56 показан другой МГ той же диагональной формы, который показывает, что от «лишнего» пересечения двух связей на плоскости избавиться невозможно.

Любой, даже поверхностно знающий теорию графов, сразу определит, что рис. 56 представляет одну из

Рис. 5. Полный двудольный граф Кз,з, соответствующий МГ диагонального изомера бензола

двух форм наименьшего непланарного графа, так называемый полный двудольный граф А"з-3. Это такой граф, в котором каждая вершина из одной группы (группа (1, рис. 56) соединена со всеми вершинами другой группы (/, рис. 56) и наоборот. Если связи есть не со всеми вершинами другой группы, граф будет просто двудольным, но основной его признак - отсутствие связей внутри группы - не должен нарушаться.

Вторая форма наименьшего непланарного графа -полный граф (см. п. 1.1.), представляющий собой пятиугольник со всеми диагоналями. Ясно, что этот граф не может быть МГ, потому что все валентности его углеродных атомов в нем заняты и для водорода их не остается.

2.3. ТОПОЛОГИЧЕСКАЯ СВЯЗНОСТЬ

И все же существуют молекулы, МГ которых нельзя нарисовать на плоскости без пересечения связей. Это - катенаны, которые представляют собой циклические молекулы, два (и больше) кольца которых синтетически «продеты» одно в другое . Химической связи между ее частями-кольцами нет, поэтому МГ этой молекулы следовало бы считать несвязным. Но разъединить эти кольца без разрыва химической связи нельзя, не удается также нарисовать его на плоскости без пересечения колец. Такую связь между кольцами назвали механической или топологической . МГ катенана по этой причине целесообразно считать связным, а вопрос, является ли он непланарным, оставить без ответа.

2.4. ВНЕШНИЙ ЦИКЛ

Есть еще один вопрос, ответ на который химики обходят молчанием. Только для трех из пяти правильных выпуклых многогранников можно в принципе синтезировать химические аналоги: тетраэдран (С4Н4), кубан (С8Н8) и додекаэдран (С|2Н12). Почему единственный, по-видимому, синтезированный из них углеводород кубан, имеющий, конечно, шесть граней-циклов, в современной органической номенклатуре называется пентациклооктан , . Частично ответ на это дан выше (циклома-тическое число МГ). Но полный ответ, существенный для органической химии и для органической номенклатуры как ее важной части, дает знаменитая теорема Эйлера, которую знает, пожалуй, любой математик. Она формулируется так : для любого полиэдра, расположенного на сфере и имеющего V точек

Рис. 6. Перспективное изображение (перспективный МГ) кубана (а) и его МГ (уложенный на плоскости - б)

(вершин), Е линий (ребер) и ^ граней (грань ограничена циклом),

У - Е + Е = 2.

Куб здесь не уложен на поверхность сферы, на ней находятся только его вершины-точки. Если оставить такой куб без сферы, то получится рис. 6а; если уложить его на сфере, то его грани (внутренние области простых циклов) займут ее всю, а если же уложить его на плоскости, то получится рис. 66. Посчитаем в нем число циклов (простых). Получим пять (пента). А куда делся цикл 1238? В него теперь вложены остальные пять циклов, он перестал быть простым, и ни в теории графов, ни в органической номенклатуре теперь как бы не считается, что и отражает формула 1. Почему «как бы»? По аналогии со сферой, в теории графов считается, что циклу 1238 «принадлежит» вся бесконечная «часть» плоскости, которой при укладке МГ рис. 6 на сфере соответствует конечная часть ее внутренней поверхности. Поэтому у уложенного на плоскости не только многогранника, но и любого плоского МГ цикл, внутри которого находятся все остальные циклы, назван внешним циклом, а соответствующая ему бесконечная «часть» плоскости - внешней гранью. А формула (3), отличающаяся от формулы (1) «только» единицей, и отражает «добавление» внешнего цикла в любой планарный МГ. И, таким образом, шестигранный кубан правильно назван в номенклатуре пентацикл ооктаном.

Поскольку все известные до сих пор МГ обычных органических молекул являются планарными, все их можно сделать плоскими, уложенными во внешний цикл. Доказано, что плоский граф можно «переуло-жить» так, чтобы сделать внешним любой внутренний цикл. Поэтому для МГ целесообразно сделать внешним наибольший (наиболее длинный) из его циклов. Таким образом, наибольший внешний цикл плоского МГ можно считать своеобразным «габаритом» не только для него, но и для самой органической молекулы, которую он представляет. Одна из процедур получения МГ с наибольшим внешним циклом описана ниже, п. 5.2.

2.5. ПЕРСПЕКТИВНЫЕ МГ

Химики изображают весьма значительную часть углеродных скелетов так, как видел бы их глаз в наиболее устойчивой конфигурации и (или) конформации, т. е. перспективно нарисованными на плоскости, но не уложенными на нее. В теории графов не отражается

Рис. 7. Структурная формула (а), МГ (б) и перспективный МГ (в) бициклического углеводорода

пространственное расположение системы вершин и соединяющих их ребер, но здесь целесообразно поступить, как в , где приведены перспективные МГ (ПМГ). Если необходимо будет отличать их от «настоящих» планарных МГ, можно называть, как указано выше. В отмеченной выше большой монографии по насыщенным (ациклическим и циклическим) углеводородам приведены 253 рисунка циклических углеродных скелетов. Из них 136 являются планарными (почти все плоские) МГ, а остальные 117 представляют собой упомянутые выше перспективные МГ. На рис. 7 показано, как они же демонстрируют «превращение» структурной формулы в плоский МГ, а его - в МГ перспективный . Довольно много подобных перспективных МГ приводится в упомянутом выше учебнике органической химии .

Интересно немного «пристальнее» рассмотреть МГ рис. 7в. Так же, как и у перспективного изображения кубана (рис. 6а), у него перспективное изображение освобождает внешний семичленный цикл от вложения в него других циклов и придает ему равные «права» с другими циклами. Однако это далеко не всегда так. Если циклы сконденсированы по одному (рис. Зв) или по двум атомам (рис. 36), то перспективное изображение не приведет к освобождению внешнего цикла, хотя любой из шестичленных циклов в каждом из этих МГ можно сделать внешним, вложив в него другой. А у моноциклического МГ цикл «сам себе» внешний и второй цикл в перспективном изображении у него, конечно, не появится.

3. СИММЕТРИЯ

Отвлекаясь от различия в свойствах объектов-вершин графа, невольно впадают в другую крайность, молчаливо считая их одинаковыми. Различия обусловлены только различием в валентности вершин. Для МГ углеводородов эта одинаковость имеет реальную основу в виде одинаковости атомов углеродного скелета. Химикам известно, что все нормальные алканы имеют симметричные атомные группы, находящиеся на одинаковых расстояниях от середины цепи, поэтому их МГ - соответствующие симметричные вершины. Для симметрии необходима не только одинаковость ато-

мов, но и одинаковость (эквивалентность) положения, одна и та же для любого вида изоморфных МГ. Все МГ с небольшим числом атомов обладают симметрией; наименьший ациклический МГ, не имеющий ни одной пары эквивалентных атомов, имеет их семь (3-метил гексан).

Если удалить у каждого из двух изоморфных равносильных МГ по одной вершине, которые занимают различные положения при их совмещении, то изо-морфность полученных при этом подграфов означает, что эти вершины-атомы симметричны. Такой внутренний изоморфизм графа называется автоморфизм, а симметричные вершины называют подобными. Общие абстрактные аспекты симметрии изучает математическая теория групп. Разнообразие симметричных пар при всех таких удалениях имеет определенное число и называется группой автоморфизмов. Симметрия атомов имеет большое значение при их нумерации (§ 4).

Для органической номенклатуры и химии симметрия атомов и их групп в молекулах также имеет большое значение, так как производные углеводородов, полученные путем одинакового замещения водорода у любого из симметричных атомов, не различаются по строению, а следовательно, и по свойствам.

4. НУМЕРАЦИЯ

Упомянутая выше (§ 3) одинаковость атомов углерода в МГ уменьшает информативность о структуре молекулы, вследствие уменьшения разнообразия составляющих ее частей. Давно известным и применяющимся во всех вариантах органической номенклатуры способом увеличения информативности является нумерация атомов молекулы (и ее МГ). В теории графов такие графы называются помеченными («метить» можно не только числами). Нумерация атомов позволяет получить необходимую информацию о порядке связей в молекуле и в МГ, для чего достаточно, например, указать номера непосредственно связанных атомов. Выше (рис. 3 и 6) были приведены нумерованные МГ. Уже там эта нумерация увеличила информативность о них и облегчила пояснения, приведенные в тексте. А на рис. 7а показана нумерация углеродных атомов структурной формулы конденсированного углеводорода, которая применяется в современной органической номенклатуре.

Нумерация вершин позволяет представить граф, не рисуя его на бумаге. Наиболее распространенным способом такого представления является матрица смежностей, которая с различной степенью подробности описана почти во всех книгах по теории графов (см., например, , ). Более простым является список ребер (связей), в котором записывают номера всех пар смежных вершин. Эти номера разделяют пробелом, пары записывают одну под другой , . Обычно (не всегда) первым в паре пишут меньший номер. Удобнее записывать пары в одной строке, номера в паре разделять запятой, а сами пары отделять друг от друга тире или дефисом.

Однако хорошо известная химикам неоднозначность выбора порядка самой нумерации атомов в одном и том же МГ приводит к чрезмерному увеличению разнообразия и, вместо увеличения, приводит к уменьшению информативности о молекуле и ее МГ.

Поэтому здесь нужны критерии, устраняющие такое разнообразие нумерации и обеспечивающие ее однозначность. Для графов предложено несколько вариантов однозначной нумерации вершин, в которых цель достигается путем применения определенной системы правил. А поскольку в разных вариантах эти правила различные, здесь также имеет место некоторое разнообразие. По-видимому, наибольшее распространение получил матричный способ однозначной нумерации при помощи упомянутой выше матрицы смежностей, названный каноническим .

4.1. ИЗОМОРФИЗМ НУМЕРОВАННЫХ МГ

Для того чтобы нумерованные графы (МГ) считались изоморфными, необходимо, чтобы при совмещении равносильных (см. п. 1.3) МГ совпали не только атомы (вершины) и связи, но и номера. На рис. 8 приведены знакомые нам (рис. 1) МГ бутана и изобутана. Видно, что все они пронумерованы по-разному. Но МГ 8а и 86 можно совместить вместе со всеми номерами, повернув один из них на 180°, но ни один из этих двух никаким перемещением не удастся совместить с МГ рис. 8в. Таким образом, нумерованные МГ 8а, 86 изоморфны, а МГ 8в не изоморфен ни одному из них, хотя при отсутствии нумерации изоморфными были бы все три. Произошло это потому, что у МГ 8а и 86 одинаковыми номерами помечены симметричные атомы, а у МГ 8в - нет. У нумерованных МГ изобутана с совпадением всех номеров можно совместить любую пару из тройки рис 8г, 8д и 8е, так как все три первичных атома симметричны, а единственный несимметричный третичный атом помечен одним и тем же номером. А в МГ 8ж несимметричный атом помечен другим номером, и этот МГ не удастся совместить ни с одним из МГ тройки 8г, 8д, 8е.

Рис. 8. Различные нумерации МГ бутана (а - в) и изобутана (г-ж)

Сопоставим списки связей для этих МГ. Пара МГ 8а, 86 имеет одинаковые списки: 1,2 - 2,3 - 3,4, а у МГ 8в список другой: 1,2 - 2,4 - 3,4. Также у тройки МГ 8г, 8д, 8е идентичные списки связей: 1,2 - 2,3 - 2,4, а список у МГ 8ж также другой: 1,2 - 1,3 - 1,4.

Изложенное выше приводит к трем основным следствиям.

Первое. Однозначно пронумерованные изоморфные графы (МГ) остаются изоморфными и в результате такой нумерации. Конечно, для этого нужно применить одну и ту же систему правил однозначной нумерации.

Второе. Любой способ однозначной нумерации осуществляется с точностью до симметрии вершин. Это значит, что перестановка номеров между подобными вершинами не приводит к нарушению однозначности нумерации.

Третье. Оно естественно следует из первого: ни для какой пары неизоморфных непомеченных графов нельзя, после их однозначной нумерации, получить совпадающие списки связей или совпадающие канонические матрицы смежностей. Это и позволяет решить проблему изоморфизма (пп. 1.3.1.) путем приведения нумерации сравниваемых графов (МГ) к канонической .

Химики знают что, например, одну и ту же нумерацию атомов бензольного кольца можно получить, начиная ее от любого из атомов цикла и продолжая последовательно по нему в любую сторону. Так же можно получить одну и ту же нумерацию атомов нафталинового цикла, если начинать ее от любого из четырех вторичных атомов, смежного с третичным атомом и продолжая ее по цепи в сторону, противоположную от него (см. рис. 36).

4.2. ЦЕПНАЯ НУМЕРАЦИЯ

Цепная структура (см. п. 1.2.) и структура циклическая как производная цепной являются неотъемлемым и естественным свойством любого графа и, соответственно, МГ. Поэтому последовательная нумерация вершин и ребер графа, состоящего из одной цепи или из одного цикла, была так и названа: естественной . Если считать звеном цепи в МГ вершину (атом, см. п. 1.2.), то цепи или (и) циклы существуют в любом МГ. Такая нумерация атомов МГ и получила соответствующее название цепной. Связи между атомами с последовательными номерами названы цепными, а с непоследовательными - неценными . И неудивительно, что эта последовательная, цепная, нумерация атомов углерода молекулы и ее МГ применяется в органической химии почти с самого начала ее существования . Однако затем авторы различных систем нумерации углеродных атомов конденсированных циклических молекул, словно сговорившись, вводили правила, которые нарушают естественный цепной характер этой нумерации . А, ведь, в циклической структуре цепей почти всегда меньше, и они длиннее, чем в ациклической.

Таким образом, цепных связей в нумерованном МГ больше, чем нецепных (см. рис. 3, 6, 7 и 8), и объем числового представления МГ можно значительно уменьшить, если считать все цепные связи заведомо существующими. Кроме того, наличие в записи наибольшего номера атома (последний номер) однозначно

информирует о том, что все атомы с меньшими номерами в МГ существуют и прямой (явной) информации о них можно также не давать. Эта не записываемая часть информации является косвенной или неявной. Сокращенная цифровая информация применяется в современной органической номенклатуре в виде кода (шифр ) в составе названия соединения.

При применении такого сокращения к списку связей с записью в одной строке (см. п. 4.1) получают линейно-цепной код. В нем цепные связи не обозначают, а в обозначении нецепной связи больший номер пишут первым. Линейно-цепные коды МГ, помеченных выше, показывают, что можно значительно сократить цифровое представление МГ по сравнению со списком связей:

рис. За: 06,3-7; 36: 10,1 - 10,5;

Зв: 6,1 - 11,6; Зг: 6,1 - 12,7; рис. 6а и 66: 5,2 - 6,1 - 7,4 - 8,1 - 8,3; рис. 8а и 86: 4; 8г, 8д и 8е: 04,2.

Таким образом, линейно-цепной код МГ состоит из сообщений с разделительными знаками , содержащих информацию о нецепных связях, разделительным знаком является дефис (тире) с пробелами. Сообщение о последнем атоме дают тогда, когда его номер не находится в нецепной связи (коды рис. За и 8а, 86). Поскольку все цепные связи в коде считаются существующими, прямую информацию об отсутствии некоторых из них дают «незначащим» нулем непосредственно перед номером, с которого начинается новая цепь (начальный номер: коды рис. За и 4г, 4д, 4е). Сообщения, в которых нецепные связи образованы одним и тем же большим или меньшим (но не большим и меньшим) номером, объединяют в одно. В объединенном сообщении больший общий номер помещают на первое место, располагая другие номера после него в возрастающем порядке: рис. 36: 10,1,5;

рис. 6а и 66: 5,2 - 6,1 - 7,4 - 8,1,3.

Если общим номером является меньший, его располагают в сообщении на последнем месте, помещая другие номера перед ним также в возрастающем порядке. В объединенном сообщении связь между нумерованными атомами считается существующей тогда, когда больший номер расположен впереди (левее) меньшего, а связь между атомами с расположенным впереди меньшим номером отсутствует. В этом выявляется смысл помещения большего номера впереди меньшего при наличии связи между атомами с этими номерами.

Для обеспечения ввода информации об органической молекуле в ЭВМ были разработаны другие самостоятельные системы кодирования структурных формул , . Линейная запись цепного кода МГ также вполне пригодна для непосредственного ввода в ЭВМ.

К упомянутому выше разнообразию способов однозначной нумерации атомов МГ добавлена однозначная цепная нумерация. По аналогии с канонической нумерацией по матрице смежностей (см. выше § 4) она названа цепной канонической нумерацией . В ней нумерацию начинают с атомов более длинных цепей; и выбирают такой ее порядок, при котором связи с непоследовательными номерами своих атомов получают максимально возможные такие номера. В качестве

Рис. 9. Перепроектирование МГ (а) в МГ с большим внешним циклом (б или в) при помощи канонической цепной нумерации

цепной она является подходящей для нумерации атомов МГ и может быть применена в органической номенклатуре для однозначной нумерации атомов структуры. Более подробное описание см. .

Теперь появилась возможность описать получение укладки МГ с наибольшим внешним циклом из МГ рис. 4а. Здесь видно, что внутренний шестичленный цикл больше внешнего пятичленного. Нарисовав шестичленный цикл 3, 4, 5, 6, 7, 8 внешним, помечаем его этими же номерами (рис. 96). Затем присоединяем к нему внутренние атомы, соблюдая тот же порядок номеров связей. Внутри пятичленного цикла рис. 9а есть еще один шестичленный цикл 1, 2, 3, 4, 5, 11. Нарисовав его внешним и присоединив к нему внутренние атомы, получим МГ рис. 9в. Цепная каноническая нумерация всех циклов рис. 9 дает один и тот же код: 8,3 - 9,2 - 10,7 - 11,1,5, что и доказывает изоморфность всех этих МГ.

ЛИТЕРАТУРА

1. Применение теории графов в химии / Под ред. чл.-кор. АН СССР Н.С. Зефирова и канд. хим. наук С.И. Кучанова. Новосибирск: Наука, 1988. 306 с.

а: Станкевич И.В. Графы в структурной химии. С. 7-69. б: Яблонский Г.С.. Евстигнеев В.А., Быков В.И. Графы в химической кинетике. С. 70-143.

в: Кучанов С.И.. Королев С.В.. Потоков С.В. Графы в химической физике полимеров. С. 144-299.

г: Королев С.В., Кучанов С.И. Приложение. Понятия теории графов. С. 300-305.

2. Харари Ф. Теория графов. М.: Мир, 1973. 302 с.

3. Уичсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

4. Оре О. Графы и их применение. М.: Мир, 1965. 176 с.

5. Березина Л.Ю. Графы и их применение: Пособие для учителей. М.: Просвещение, 1979. 144 с.

6. Дистель Р. Теория графов: Пер. с англ. О.В. Бородина. Новосибирск: Изд-во Ин-та математики, 2002. 336 с.

7. Татт У. Теория графов: Пер с англ. Г.П. Гаврилова. М.: Мир, 1988. 424 с.

8. Бенкс Дж. Названия органических соединений. М.: Химия, 1980. 304 с.

9. Шилов A.A. О систематизации графов на основе разбиений // Методы и средства работы с документами: Сб. тр. Ин-та системного анализа РАН. М.: Эдиториал УРСС, 2000. 376 с.

10. Шилов A.A. О систематизации безреберных и объединенных графов на основе разбиений // Управление информационными потоками: Сб. тр. Ин-та системного анализа РАН. М.: Едиториал УРСС, 2002. 368 с.

11. Терентьев А.П., Кост A.H.. Цукерман A.M.. Потапов В.М. Номенклатура органических соединений. Обзор, критика, предложения. М.: Изд-во АН СССР, 1955. 304 с.

12. Шилл Г. Катенаны, ротаксаны и узлы. М.: Мир, 1973. 212 с.

13. Кларк Т.. Мак Керви М.А. Насыщенные углеводороды II Общая органическая химия."Г. I. М.: Химия, 1981. С. 56-168.

14. Нейпанд О.Я. Органическая химия. М.: Высш. шк., 1990. 752 с.

15. Гудман С., Хидетниеми С. Введение в анализ и разработку алгоритмов. М.: Мир, 1981. 368 с.

16. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 216с.

17. Брюске Я.Э. Цепная нумерация и кодирование циклических углеводородов // Ж. структурной химии. Т. 36. № 4. С. 729-734.

18. Математический энциклопедический словарь. М.: Совет, энциклопедия, 1988. 848 с.

19. Брюске Я.Э. Линейно-цепное кодирование и названия ациклических углеводородов // Вестн. Тамбов, ун-та. Сер. Естеств. и техн. науки. Тамбов, 1996. Т. 1. Вып. 1. С. 34-38.

20. Брюске Я.Э. Линейно-цепное кодирование формул органических соединений. VIII. Увеличение явной информативности о структуре в кодах углеводородов // Вестн. Тамбов, ун-та. Сер. Естеств. и техн. науки. Тамбов, 2000. Т. 5. Вып. I. С. 38-43.

1 За последние десятилетия в теоретиче-ской химии широкое распространение получи-ли представления топологии и теории графов. Они полезны при поиске количественных соот-ношений «структура - свойство» и «структура-активность», а также в решении теоретико-графовых и комбинаторно-алгебраических за-дач, возникающих в ходе сбора, хранения и об-работки информации по структуре и свойствам веществ.

Графы служат, прежде всего, средством изображения молекул. При топологическом описании молекулы её изображают в виде мо-лекулярного графа (МГ), где вершины соответ-ствуют атомам, а рёбра - химическим связям (теоретико-графовая модель молекулы). Обыч-но в таком представлении рассматривают толь-ко скелетные атомы, например, углеводороды со «стёртыми» атомами водорода.

Валентность химических элементов на-кладывает на степени вершин определённые ограничения. У деревьев-алканов (связных гра-фов, не имеющих циклов) степени вершин (г) не могут превышать четырёх (г = 1, 2, 3, 4).

Графы можно задавать в матричном виде, что удобно при работе с ними на ЭВМ.

Матрица смежности вершин простого графа - это квадратная матрица А = [аσχ] с эле-ментами аσχ = 1, если вершины σ и χ соедине-ны ребром, аσχ = 0 - в противном случае. Ма-трица расстояний - это квадратная матрица D = с элементами dσχ, определяемыми как минимальное число рёбер (наикратчайшее рас-стояние) между вершинами σ и χ. Иногда при-меняются также матрицы смежности и расстоя-ний по рёбрам (А е и D e).

Вид матриц А и D (А е и D e) зависит от спо-соба нумерации вершин (или рёбер), что вызы-вает неудобство при обращении с ними. Для характеризации графа применяются инварианты графа - топологические индексы (ТИ).

Число путей длины один

pi = хсс 0 = m = n-1

Число путей длины два

Число троек смежных ребер (с общей вершиной)

Число Винера (W), определяемое как по-лусумма элементов матрицы расстояний рассма-триваемого графа:

и т.д.

Методология изучения связи «структура-свойство» через топологические индексы в теоретико-графовом подходе включает в себя следующие этапы .

Выбор объектов исследования (обучаю-щая выборка) и анализ состояния численных данных по свойству Р для данного круга соеди-нений.

Отбор ТИ с учетом их дискриминирую-щей способности, корреляционной способности со свойствами и т.д.

Изучение графических зависимостей «Свойство Р - ТИ графа молекулы», например, Р от n - числа скелетных атомов, Р от W - чис-ла Винера и т.п.

Установление функциональной (аналити-ческой) зависимости Р = _ДТИ), например,

Р = а(ТИ) + b ,

Р = аln(ТИ) + b ,

Р = а(ТИ) 1 +b(ТИ) 2 +...+n(ТИ) n +с

и т.п. Здесь а, b, с - некоторые параме-тры (не следует путать их с параметрами адди-тивных схем.), подлежащих определению.

Численные расчеты Р, сопоставление рас-считанных значений с экспериментальными.

Предсказание свойств еще не изученных и даже не полученных соединений (вне данной выборки).

Топологические индексы также исполь-зуются в построении аддитивных схем расчёта и прогнозирования. Они могут применяться при разработке новых лекарственных средств, при оценке канцерогенной активности некоторых химических веществ, для предсказания относи-тельной устойчивости новых (ещё не синтези-рованных) соединений и т.д.

Следует однако помнить, что выбор ТИ нередко носит случайный характер; они могут не отражать важные структурные особенности молекул или дублировать информацию (получа-емую с помощью других индексов), а расчетные схемы не иметь прочного теоретического фунда-мента и плохо поддаваться физико-химической интерпретации.

Коллектив кафедры физической химии ТвГУ уже в течение многих лет ведет расчетно-теоретическое исследование по проблеме «Связь свойств веществ со строением молекул: математическое (компьютерное) моделирование». В центре внимания целенаправленный по-иск новых структур, алгоритмы решения ряда теоретико-графовых и комбинаторных задач, возникающих в ходе сбора и обработки инфор-мации о структуре и свойствах веществ, созда-ние экспертных информационно-поисковых си-стем и баз данных, разработка количественных методов расчета и прогнозирования.

Нами были построены аддитивные схе-мы и найдены аналитические зависимости вида Р = У(ТИ) для ряда органических и других мо-лекул. По полученным формулам выполнены численные расчеты физико-химических свойств рассматриваемых соединений, с .

Список литературы

1. Виноградова М.Г., Папулов Ю.Г., Смо-ляков В.М. Количественные корреляции «струк-тура свойство « алканов. Аддитивные схемы расчета. Тверь, 1999. 96 с.
2. Химические приложения топологии и теории графов / Под ред. Р. Кинга. М.: Мир, 1987. 560 с.
3. Применение теории графов в химии / Под ред. Н.С. Зефирова и С.И. Кучанова. Ново-сибирск: Наука, 1988. 306 с.
4. Станкевич М.И., Станкевич И.В., Зе-фиров Н.С. Топологические индексы в органи-ческой химии // Успехи химии. 1988. Т.57, №3,С.337-366.
5. Виноградова М.Г., Салтыкова М.Н. Теоретико-графовый подход в изучении взаимосвязи между строением и свойствами алкилсиланов.// Фундаментальные исследования, 2009. №1. С. 17-19.
6. Виноградова М.Г., Салтыкова М.Н., Ефремова А.О., Мальчевская О.А. Взаимосвязь между строением и свойствами алкилсиланов //Успехи современного естествознания, №1, 2010. С.136-137.
7. Виноградова М.Г., Салтыкова М.Н.,Ефремова А.О. Корреляции «Структура - свойство» алкилсиланов: теоретико-графовый подход // Успехи современного естествознания, №3, 2010. С.141-142.

Библиографическая ссылка

Виноградова М.Г. ТЕОРИЯ ГРАФОВ В ХИМИИ // Международный журнал прикладных и фундаментальных исследований. – 2010. – № 12. – С. 140-142;
URL: https://applied-research.ru/ru/article/view?id=1031 (дата обращения: 17.12.2019). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»