Предисловие редактора перевода
Предисловие к русскому изданию
Предисловие
ТОПОЛОГИЯ КОНЕЧНОГО ТОЧЕЧНОГО МНОЖЕСТВА И МОЛЕКУЛЯРНАЯ СТРУКТУРА. Р. Меррифилд, 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. Выводы и перспективы
Литература
Предметный указатель

В - Р + Г = 1, (*)

где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).

Доказательство. Докажем, что равенство не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).

а) б)

Рис.2

Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем

В - (Р + 1) + (Г+1) = В – Р + Г.

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

Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:

для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;

для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.

В обоих случаях равенство не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:

(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.

Таким образом, удаление одного треугольника не меняет равенства.

Продолжая этот процесс удаления треугольников, в конце концов, мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно,

B - Р + Г= 1.

Значит, равенство имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение.

Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.

Приступим теперь к решению задачи о трех домиках и трех колодцах.

Решение . Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1.

Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9.

Следовательно, Г = 5. Каждая из пяти граней имеет, по крайней мере, четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5 4)/2 = 10, что противоречит условию, по которому их число равно 9.

Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому коло

Теория Графов в химии

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

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

В стереохимии орг. в-в наиболее часто используют молекулярные деревья - остовные деревья молекулярных графов, которые содержат только все вершины, соответствующие атомам Составление наборов молекулярных деревьев и установление их изоморфизма позволяют определять молекулярные структуры и находить полное число изомеров алканов, алкенов и алкинов. Молекулярные графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвленность, цикличность и т.п.) молекул различных соединений, к анализу и сопоставлению чисто математических признаков и свойств молекулярных графов и их деревьев, а также соответствующих им матриц. Для выявления количества корреляций между строением молекул и физико-химическими (в т.ч. фармакологическими) свойствами соединений разработано более 20 т. наз. Топологических индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), которые определяют с помощью матриц и числовых характеристик молекулярных деревьев. Напр., индекс Винера W = (m3 + m)/6, где т-число вершин, отвечающих атомам С, коррелирует с молекулярными объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографическими константами соединений, октановыми числами углеводородов и даже физиол. активностью лекарственных препаратов. Важными параметрами молекулярных графов, используемыми для определения таутомерных форм данного вещества и их реакционной способности, а также при классификации аминокислот, нуклеиновых кислот, углеводов и др. сложных природных соединений, являются средняя и полная (Н)информационная емкости. Анализ молекулярных графов полимеров, вершины которых отвечают мономерным звеньям, а ребра-химическими связям между ними, позволяет объяснить, например: эффекты исключенного объема, приводящие к качеств. изменениям прогнозируемых свойств полимеров. С применением Теории графов и принципов искусственного интеллекта разработано программное обеспечение информационно- поисковых систем в химии, а также автоматизированных систем идентификации молекулярных структур и рационального планирования органического синтеза. Для практической реализации на ЭВМ операций выбора рациональных путей хим. превращений на основе ретросинтетического и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины которых соответствуют молекулярным графам реагентов и продуктов, а дуги изображают превращения.

Для решения многомерных задач анализа и оптимизации химико-технологических систем (ХТС) используют следующие химико-технологические графы: потоковые, информационно-потоковые, сигнальные и графы надежности. Для изучения в хим. физике возмущений в системах, состоящих из большого числа частиц, используют т. наз. диаграммы Фейнмана-графы, вершины которых отвечают элементарным взаимодействиям физических частиц, ребра их путям после столкновений. В частности, эти графы позволяют исследовать механизмы колебательных реакций и определять устойчивость реакционных систем.Материальные потоковые графы отображают изменения расходов в-в в ХТС. Тепловые потоковые графы отображают балансы теплоты в ХТС; вершины графов соответствуют аппаратам, в которых изменяются расходы теплоты физических потоков, и, кроме того, источникам и стокам тепловой энергии системы; дуги отвечают физическим и фиктивным (физ.-хим. превращения энергии в аппаратах) тепловым потокам, а веса дуг равны энтальпиям потоков. Материальные и тепловые графы используют для составления программ автоматизированной разработки алгоритмов решения систем уравнений материальных и тепловых балансов сложных ХТС. Информационно-потоковые графы отображают логико-информационную структуру систем уравнений мат. моделей ХТС; применяются для составления оптимальных алгоритмов расчета этих систем. Двудольный информационный граф неориентированный или ориентированный граф, вершины которого отвечают соотв. уравнениям fl -f6 и переменным q1 – V, а ветви отображают их взаимосвязь. Информационный граф – орграф, изображающий порядок решения уравнений; вершины графа отвечают этим уравнениям, источникам и приемникам информации ХТС, а ветви-информац. переменным. Сигнальные графы соответствуют линейным системам уравнений математических моделей химико-технологических процессов и систем. Графы надежности применяют для расчета различных показателей надежности Х.

Использованная литература :

1.Берж К., Т. г. и ее применение, перевод с французского, М., 1962;

2.Кемени Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1963;

3.Ope О., Графы и их применение, пер. с англ., М., 1965;

4. Белых О. В., Беляев Э. В., Возможности применения Т. г. в социологии, в сб.: Человек и общество, вып. 1, [Л.], 1966;

5. Количественные методы в социологических исследованиях, М., 1966; Беляев Э. В., Проблемы социологических измерения, "ВФ", 1967, No 7; Bavelas. Communication patterns in task oriented groups, в кн. Lerner D., Lass well H., Policy sciences, Stanford, 1951;

Реферат по предмету высшая математика на тему:

Применение в химии теории графов

Выполнил студент группы НХ-202

Москва 2011
Графами называется область конечной математики, изучающая дискретные структуры; применяется для решения различных теоретических и прикладных задач.
Некоторые основные понятия. Граф - совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,а). Если на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называются дугами, или ветвями; если неориентированы, - ребрами. Соответственно, граф, содержащий только дуги, называется ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра - смешанным. Граф, имеющий кратные ребра, называется мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям), - двудольным; дуги (ребра) и (или) вершины, которым отвечают определенные веса или числовые значения каких-либо параметров, - взвешенным. Путь в графе - чередующаяся последовательность вершин и дуг, в которой ни одна из вершин не повторяется (напр., a, b на рис. 1,a); контур-замкнутый путь, в котором первая и последняя вершины совпадают (напр.,f, h); петля - дуга (ребро), которая начинается и кончается в одной и той же вершине. Цепь графа - последовательность ребер, в которой ни одна из вершин не повторяется (например, с, d, e); цикл - замкнутая цепь, в которой ее начальная и конечная вершины совпадают. Граф называется связным, если любая пара его вершин соединена цепью или путем; в противоположном случае граф называется несвязным.
Дерево - связный неориентированный граф, не содержащий циклов или контуров (рис. 1,б). Остовный подграф некоторого графа - его подмножество, содержащее все вершины и лишь определенные ребра. Остовное дерево некоторого графа - его остовный подграф, представляющий собой дерево. Графы называются изоморфными, если существует взаимно однозначное соответствие между совокупностями их вершин и ребер (дуг).
Для решения задач графов теории и ее приложений графы представляют с помощью матриц (смежности, инцидентности, двустрочных и др.), а также спец. числовых характеристик. Например, в матрице смежности (рис. 1,в) строки и столбцы отвечают номерам вершин графа, а ее элементы принимают значения 0 и 1 (соответственно, отсутствие и наличие дуги между данной парой вершин); в матрице инцидентности (рис. 1,г) строки отвечают номерам вершин, столбцы - номерам дуг, а элементы принимают значения 0, + 1 и - 1 (соответственно, отсутствие, наличие дуги, входящей в вершину и выходящей из нее). Наиболее употребительные числовые характеристики: число вершин (т), число дуг или ребер (n), цикломатическое число, или ранг графа (п - т + k, где k-число связных подграфов в несвязном графе; например, для графа на рис. 1,б ранг будет: 10-6+ 1 =5).
Применение теории графов базируется на построении и анализе различных классов химических и химико-технологических графов, которые называются также топологияческими моделями, т.е. моделями, учитывающими только характер связи вершин. Дуги (ребра) и вершины этих графов отображают химические и химико-технологические понятия, явления, процессы или объекты и соответственно качественные и количественные взаимосвязи либо определенные отношения между ними.

Рис. 1. Иллюстрация некоторых основных понятий: а-смешанный граф; б-остовное дерево (сплошные дуги a, h, d, f, h) и нек-рый подграф (пунктирные дуги с, e, g, k, l) орграфа; в, г-матрицы соотв. смежности и инцидентности орграфа.
Теоретические задачи. Химические графы дают возможность прогнозировать химические превращения, пояснять сущность и систематизировать некоторые основные понятия химии: структуру, конфигурацию, конформации, квантовомеханические и статистико-механические взаимодействия молекул, изомерию и др. К химическим графам относятся молекулярные, двудольные и сигнальные графы кинетических уравнений реакций.
Молекулярные графы, применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул (рис. 2). Вершины и ребра этих графов отвечают, соответственно, атомам и химическим связям между ними.

Рис. 2. Молекулярные графы и деревья: а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).
В стереохимии органических веществ наиболее часто используют молекулярные деревья -остовные деревья молекулярных графов, которые содержат только все вершины, соответствующие атомам С (рис. 2, а и б). Составление наборов молекулярных деревьев и установление их изоморфизма позволяют определять молекулярные структуры и находить полное число изомеров алканов, алкенов и алкинов (рис. 2, в).
Молекулярные графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвлепность, цикличность и т.п.) молекул различных соединений, к анализу и сопоставлению чисто математических признаков и свойств молекулярных графов и их деревьев, а также соответствующих им матриц. Для выявления количественных корреляций между строением молекул и физико-химическими (в т.ч. фармакологическими) свойствами соединений разработано более 20 тысяч названий топологических индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), которые определяют с помощью матриц и числовых характеристик молекулярных деревьев. Например, индекс Винера W = (m 3 + m)/6, где m-число вершин, отвечающих атомам С, коррелирует с молекулярными объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографическими константами соединений, октановыми числами углеводородов и даже физиологической активностью лекарственных препаратов.
Важными параметрами молекулярных графов, используемыми для определения таутомерных форм данного вещества и их реакционной способности, а также при классификации аминокислот, нуклеиновых кислот, углеводов и других сложных природных соединений, являются средняя и полная (Н) информационные емкости. Параметр вычисляется по формуле энтропии информации Шеннона: , где p t -вероятность принадлежности вершин m графа i-тому виду, или классу эквивалентности, k; i = , Параметр. Изучение молекулярных структур типа неорганических кластеров или лент Мёбиуса сводится к установлению изоморфизма соответствующих молекулярных графов путем их укладки (вложения) в сложные многогранники (например, полиэдры в случае кластеров) или спец. многомерные поверхности (например, римановые). Анализ молекулярных графов полимеров, вершины которых отвечают мономерным звеньям, а ребра - химическим связям между ними, позволяет объяснить, например, эффекты исключенного объема, приводящие к качественным изменениям прогнозируемых свойств полимеров.

Рис. 3. Графы реакций: а-двудольный; б-сигнальный ур-ний кинетики; r 1 , г 2 -р-ции; а 1 -а 6 -реагенты; k-константы скорости р-цнй; s-комплексная переменная преобразования Лапласа.
С применением графов теории и принципов искусственного интеллекта разработано программное обеспечение информационно-поисковых систем в химии, а также автоматизированных систем идентификации молекулярных структур и рационального планирования органического синтеза. Для практической реализации на ЭВМ операций выбора рациональных путей химических превращений на основе ретросинтетического и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины которых соответствуют молекулярным графам реагентов и продуктов, а дуги изображают превращения веществ.

Рис. 4. Одноконтурная химико-технологическая система и соответствующие графы: а-структурная схема; б, в-материальные потоковые графы соотв. по общим массовым расходам и расходу компонента А; г- тепловой потоковый граф; д-фрагмент системы ур-ний (f 1 - f 6) материального баланса, полученной из анализа графов на рис. 4, б и в; е-двудольный информационный орграф; ж-информационный граф, I-смеситель; II-реактор; III-ректификационная колонна; IV-холодильник; I 1 -I 8 -технол. потоки; q-массовый расход; H-энтальпия потока; i. s и i*, s*- соотв. реальные и фиктивные источники и стоки материальных и тепловых потоков; с-концентрация реагента; V-объем реактора.
Матричные представления молекулярных графов различных соединений эквивалентны (после преобразования соответствующих элементов матриц) матричным методам квантовой химии. Поэтому теорию графов применяют при выполнении сложных квантово-химических расчетов: для определения числа, свойств и энергий молекулярных орбиталей, прогнозирования реакционной способности сопряженных альтернантных и неальтернантных полиенов, выявления ароматических и антиароматических свойств веществ и др.
Для изучения в химической физике возмущений в системах, состоящих из большого числа частиц, используют так называемые диаграммы Фейнмана - графы, вершины которых отвечают элементарным взаимодействиям физических частиц, ребра - их путям после столкновений. В частности, эти графы позволяют исследовать механизмы колебательных реакций и определять устойчивость реакционных систем.
Для выбора рациональных путей превращения молекул реагентов при заданном множестве известных взаимодействий используют двудольные графы реакций (вершины соответствуют молекулам и этим реакциям, дуги - взаимодействиям молекул в реакции; рис. 3,a). Такие графы позволяют разрабатывать диалоговые алгоритмы выбора оптимальных путей химических превращений, для которых требуется наименьшее число промежуточных реакций, минимальное число реагентов из перечня допустимых или достигается наибольший выход продуктов.
Сигнальные графы уравнений кинетики реакций отображают системы кинетических уравнений, представленных в алгебраическо-операторной форме (рис. 3,б). Вершины графов отвечают так называемым информационным переменным, или сигналам, в виде концентраций реагентов, дуги - взаимосвязям сигналов, причем веса дуг определяются кинетическими константами. Такие графы применяют при изучении механизмов и кинетики сложных каталитических реакций, сложных фазовых равновесий при образовании комплексных соединений, а также для расчета параметров аддитивных свойств растворов.
Прикладные задачи. Для решения многомерных задач анализа и оптимизации химико-технологических систем (ХТС) используют следующие химико-технологические графы (рис. 4): потоковые, информационно-потоковые, сигнальные и графы надежности. К потоковым графам, представляющим собой взвешенные орграфы, относятся параметрические, материальные по общим массовым расходам физических потоков и массовым расходам некоторых химических компонентов либо элементов, а также тепловые графы. Перечисленные графы соответствуют физико-химическим превращениям веществ и энергии в данной ХТС.
Параметрические потоковые графы отображают преобразование параметров (массовых расходов и др.) физических потоков элементами ХТС; вершины графов отвечают математическим моделям аппаратов, а также источникам и стокам указанных потоков, а дуги - самим потокам, причем веса дуг равны числу параметров соответствующего потока. Параметрические графы служат для разработки алгоритмов анализа технологических режимов многоконтурных ХТС. Такие алгоритмы устанавливают последовательность расчета систем уравнений математических моделей отдельных аппаратов какой-либо системы для определения параметров ее выходных потоков при известных значениях переменных входных потоков.
Материальные потоковые графы отображают изменения расходов веществ в ХТС. Вершины графов отвечают аппаратам, в которых трансформируются общие массовые расходы физических потоков и массовые расходы некоторых химических компонентов или элементов, а также источникам и стокам веществ потоков либо данных компонентов; соответственно, дуги графов отвечают физическим потокам или физическим и фиктивным (химические превращения веществ в аппаратах) источникам и стокам каких-либо компонентов, а веса дуг равны массовым расходам обоих типов. Тепловые потоковые графы отображают балансы теплоты в ХТС; вершины графов соответствуют аппаратам, в которых изменяются расходы теплоты физических потоков, и, кроме того, источникам и стокам тепловой энергии системы; дуги отвечают физическим и фиктивным (физ.-хим. превращения энергии в аппаратах) тепловым потокам, а веса дуг равны энтальпиям потоков. Материальные и тепловые графы используют для составления программ автоматизированной разработки алгоритмов решения систем уравнений материальных и тепловых балансов сложных ХТС.
Информационно-пстоковые графы отображают логико-информационную структуру систем уравнений математических моделей ХТС; применяются для составления оптимальных алгоритмов расчета этих систем. Двудольный информационный граф (рис. 4, е) неориентированный или ориентированный граф, вершины которого отвечают, соответственно, уравнениям f l -f 6 и переменным q 1 - V, а ветви отображают их взаимосвязь. Информационный граф (рис. 4, ж) - орграф, изображающий порядок решения уравнений; вершины графа отвечают этим уравнениям, источникам и приемникам информации ХТС, а ветви - информационным переменным.
Сигнальные графы соответствуют линейным системам уравнений математических моделей химико- технологических процессов и систем. Вершины графов отвечают сигналам (например, температуре), ветви - связям между ними. Такие графы используют для анализа статических и динамических режимов многопараметрических процессов и ХТС, а также показателей ряда их важнейших свойств (устойчивости, чувствительности, управляемости).
Графы надежности применяют для расчета различных показателей надежности ХТС. Среди многочисленных групп этих графов (например, параметрических, логико-функциональных) особенно важны так называемые деревья отказов. Каждое такое дерево - взвешенный орграф, отображающий взаимосвязь множества простых отказов отдельных процессов и аппаратов ХТС, которые приводят к множеству вторичных отказов и результирующему отказу системы в целом.
Для создания комплексов программ автоматизированного синтеза оптимальных высоконадежных производств (в том числе ресурсосберегающих) наряду с принципами искусственного интеллекта применяют ориентированные семантические, или смысловые, графы вариантов решений ХТС. Эти графы, которые в частном случае являются деревьями, изображают процедуры генерации множества рациональных альтернативных схем ХТС (например, 14 возможных при разделении ректификацией пятикомпонентной смеси целевых продуктов) и процедуры упорядоченного выбора среди них схемы, оптимальной по некоторому критерию эффективности системы.
и т.д.................

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 2

Подготовил

Легкоконец Владислав, ученик 10А класса

Практическое применение Теории Графов

Руководитель

Л.И. Носкова, учитель математики

ст.Брюховецкая

2011 г.

1.Введение………………………………………………………………………….………….3

2.История возникновения теории графов………………………………………….………..4

3.Основные определения и теоремы теории графов……………………………….………6

4.Задачи,решаемые при помощи графов……………………………..……………………..8

4.1 Знаменитые задачи………………………………….………………………...8

4.2 Несколько интересных задач………………………………….……………..9

5.Применение графов в различных областях жизни людей……………………………...11

6.Решение задач……………………………………………………………………………...12

7. Заключение………………….…………………………………………………………….13

8. Список литературы………….……………………………………………………………14

9.Приложение…………………………………………………………………….…………15

Введение

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

Решение многих жизненных задач требует длинных вычислений, а иногда и эти вычисления не приносят успеха. В этом и состоит проблема исследования . Возникает вопрос: нельзя ли для их решения найти простое, рациональное, короткое и изящное решение. Упрощается ли решение задач, если использовать графы? Это определило тему моего исследования : «Практическое применение теории графов»

Целью исследования было с помощью графов научиться быстро решать практические задачи.

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

Задачи исследования:

1.Изучить литературу и ресурсы сети Интернет по данной проблеме.

2.Проверить эффективность метода графов при решении практических задач.

3. Сделать вывод.

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

В работе используются следующие методы: наблюдение, поиск, отбор, анализ.

История возникновения теории графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов.

[Приложение рис.1] Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [Приложение рис.2] , на котором A обозначает остров, а B ,C иD – части континента, отделенные друг от друга рукавами реки

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Основные определения и теоремы теории графов

Теория графов – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.

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

Это определение можно сформулировать иначе: графомназывается непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B , C , D . Иногда граф в целом будем обозначать одной заглавной буквой.

Определение 2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.

Определение 3. Граф, состоящий только из изолированных вершин, называется нуль- графом.

Обозначение: O "– граф с вершинами, не имеющий ребер

Определение 4. Граф, в котором каждая пара вершин соединена ребром, называется полным.

Обозначение: U " – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n –угольник, в котором проведены все диагонали

Определение 5. Степеньювершиныназывается число ребер, которым принадлежит вершина.

Определение 6. Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепениk .

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

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

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

Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт.

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

Определение 11. Цикломназывается путь, в котором совпадают начальная и конечная точка.

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

Определение 13. Длиной пути, проложенного на цикле, называется число ребер этого пути.

Определение 14. Две вершины A и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из A в B .

Определение 15. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

Определение 16. Деревомназывается связный граф, не содержащий циклов.

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

Определение 17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Определение 18. Дерево, все n вершин которого имеют номера от 1 до n , называют деревом с перенумерованными вершинами.

Итак, мы рассмотрели основные определения теории графов, без которых было бы невозможно доказательство теорем, а, следовательно и решение задач.

Задачи решаемые при помощи графов

Знаменитые задачи

Задача коммивояжера

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё обламывали зубы лучшие математики.

Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Метод решения задачи коммивояжера

Жадный алгоритм “иди в ближайший (в который еще не входил) город”.
“Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Рассмотрим для примера сеть на рисунке [приложение рис.3] , представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Задача о Кенигсбергских мостах.

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

Рассмотрим граф, соответствующий схеме мостов [приложение рис.2].

Чтобы ответить на вопрос задачи, достаточно выяснить, является ли граф эйлеровым. (Хотя бы из одной вершины должно выходить четное число мостов). Нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно.

Несколько интересных задач

1. "Маршруты".

Задача 1

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза [приложение рис.4].

Решение :

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF ; перечеркнем FO ; отметим жирной линией FH , НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D - Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву [приложение рис.5] .

Задача 2

На рисунке изображена схема местности [приложение рис.6].

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой - самый длинный.

Решение :

Последовательно "расслаиваем" схему в дерево, начиная с вершины 1[приложение рис.7] . Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

2 "Группы, знакомства"

Задача 1

Участники музыкального фестиваля, познакомившись, обменялись конвертами с адресами. Докажите, что:

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Решение: Пусть участники фестиваля А 1 , А 2 , А 3 . . . , А n – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами [Приложение рис.8]

Решение:

а) степень каждой вершины А i показывает число конвертов, которое передал участник А i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n , N =2p , где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.

Задача 2

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д. Это первые буквы имён. Соединим те точки, которые соответствуют именам созвонившихся ребят.

[ приложение рис.9]

Из рисунка видно, что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Применение графов в различных областях жизни людей

Кроме приведенных примеров, графы широко используются в строительстве, электротехнике, менеджменте, логистике, географии, машиностроении, социологии, программировании, автоматизации технологических процессов и производств, психологии, рекламе. Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного исследования.

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

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

Молекулярные графы и деревья: [приложение рис.10] а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

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

Белковые сети

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

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

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

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

Пример генеалогического дерева моей семьи [приложение рис.12].

Еще один пример. На рисунке показано библейское генеалогическое дерево [приложение рис.13].

Решение задач

1.Транспортная задача . Пусть в городе Краснодаре находится база с сырьём, которое нужно развести по городам Крымск, Темрюк, Славянск-на-Кубани и Тимашевск одним заездом, затратив при этом как можно меньше времени и топлива и вернувшись обратно в Краснодар.

Решение:

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

Для удобства решения обозначаем города цифрами: Краснодар – 1, Крымск – 2, Темрюк – 3, Славянск – 4, Тимашевск – 5.

В результате вышло 24 решения, но нам нужны только кратчайшие пути. Из всех решений удовлетворяют только два, это 350 км.

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

Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами [приложение рис.16].

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Заключение

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

Решая практические задачи с помощью теории графов стало ясно видно, что в каждом шаге, в каждом этапе их решения необходимо применить творчество.

С самого начала, на первом этапе, оно заключается в том, что нужно суметь проанализировать и закодировать условие задачи. Второй этап – схематическая запись, которая состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.

Решая транспортную задачу или задачу на составление генеалогического дерева я сделал вывод, что безусловно метод графов интересен, красив и нагляден.

Я убедился, что графы достаточно широко применяются в экономике, управлении, технике. Также теория графов применяется в программировании.Об этом в данной работе не шла речь, но думаю, что это только вопрос времени.

В настоящей научной работе рассмотрены математические графы, области их применения, решено несколько задач с помощью графов. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты). Кроме того, работая над научной работой, я освоил работу на компьютере в текстовом редакторе WORD . Таким образом, задачи научной работы выполнены.

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

Литература

Берж К. Теория графов и ее применения. -M.: ИИЛ, 1962.

Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. -M.: ИИЛ, 1963.

Оре О. Графы и их применение. -M.: Мир, 1965.

Харари Ф. Теория графов. -M.: Мир, 1973.

Зыков А.А. Теория конечных графов. -Новосибирск: Наука, 1969.

Березина Л.Ю. Графы и их применение. -M.: Просвещение, 1979. -144 c.

"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

Приложение

Приложение

П

Рис. 6

Рис. 7

Рис. 8

риложение

Приложение

Приложение

Приложение

П

Рис. 14

риложение

Приложение

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). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»