Гамильтонов граф

Важность матриц смежности графов в теории Хюккеля хорошо известна [12—30] . Несмотря на то что всегда можно получить собственные значения хюккелевского гамильтониана для химической системы с помощью современных ЭВМ, теория графов играет важную роль, особенно если интерес представляет аналитическое поведение спектров собственных значений для химических систем как функции некоторых переменных. По этой причине изучение спектров графов оказывается полезным, несмотря на доступность современных ЭВМ. Например, Кинг [31] показал, что аналитическое поведение динамики колебательных химических реакций может быть прогнозировано в результате исследования вида спектров соответствующих диаграмм, известных как диаграммы влияния. [c.279]

Класс NP определён только для предикатов. Говорят, например, что свойство графа иметь гамильтонов цикл принадлежит NP . [c.29]

Гамильтонов граф — это граф, который содержит цикл, проходящий через все вершипы точно по одному разу. Смысл гамильтонова графа применительно к механизму сложной реакции следующий существует единый цикл превращений (стадий), объединяющий все интермедиаты. Гамильтонов граф — это и одномаршрутный (см. рнс. 1.1), и некоторые двухмаршрутпые механизмы (см. рпс. II.1, O II.2). Гамильтоновым является граф, представленный на рпс. III.1, а, а также граф достаточно сложной фермепта- [c.116]

В свою очередь каждый из изомеров II, III и IV порождает два новых и т. д. Весь этот процесс можно изобразить в виде графа. Для этого поставим в соответствие каждому изомеру точку на плоскости. Наличие 1,2-перегруппировки, переводящей один изомер в другой, позволяет считать эти точки смежными и поэтому две такие точки соединяются ребром (рис. 1.13). Граф, изображенный на этом рисунке, называют тонологическим представлением описанной выше перегруппировки. По-видимому, работа [48] была одной из первых, в которой подробно проанализирована структура графов, возникающих при описании внутримолекулярных перегруппировок. В последующих работах, например [49], графы исиользовалпсь для описания перегруппировок в различных системах с высокой симметрией молекулярного скелета в октаэдрических, тетраэдрических и др. В работе [49] использовались группы перестановок, содержащие большое число элементов. Рассматривались графы достаточно сложной структуры. При этом решались проблемы, связанные с неоднозначностью реализацией этих графов на плоскости. Было предложено, в частности, располагать вершины графов в вершинах правильных и-угольников, где п равно числу изомеров. Графы строятся таким образом, чтобы они имели максимальное число элементов симметрии. Граф (рис. 1.14) построеи для описания перегруппировок в октаэдрическом комплексе со всеми различными лигандами, нри которых сохраняются положения четырех из лигандов. В такого типа графах имеется гамильтонов цикл, т. е. замкнутый маршрут, проходящий через все вершины графа в точности один раз [49]. [c.27]

Рассмотрим теперь внутренние орбитали. Предположим, что эти орбитали полностью эквивалентны, взаимодействуют попарно друг с другом, причем эти взаимодействия характеризуются одним и тем же значением резонансного интеграла . Такой системе орбиталей можно поставить в соответствие полный граф и гамильтониан Н, определенный на этом графе Я = а 2 Рц Ь Р 2 Спектр этого гамильтониана состоит из двух чисел а — р и а + + (и—1)Р, причем кратность несвязывающего уровня энергии а — [c.35]

Гамильтоноб цикл — замкнутый путь в графе, проходящий через все вершины графа ровно по одному разу. Граф, в котором есть хотя бы один гамильтонов цикл, называется гамилътоноьъш. [c.29]

Пример 2.1. Пусть R x, у) = г/ есть гамильтонов цикл в графе ж . Более точно нужно сказать так ж есть двоичный код некоторого графа, SL у — код гамильтонова цикла в этом графе (используем такое коднрованне, при котором код цикла ие длиннее кода графа), такие что.. . . Возьмём q n) — п. Тогда Ь х) будет в точности означать, что в графе найдётся гамильтонов цикл. [c.31]

Определение 2.3. Имеются два персонажа король Arthur (Артур), умственные способности которого полиномиально ограничены, н волшебник Merlin (Мерлин), который интеллектуально всемогущ н знает правильные ответы иа все вопросы. Король А интересуется некоторым свойством L(x) (наиример, есть ли у графа гамильтонов цикл ), а волшебник М хочет, чтобы король признал наличие этого свойства (ну, скажем, граф стремится к званию гамильтонова и дал М взятку). А не доверяет своему волшебнику, зиая его корыстолюбие, и хочет иметь возможность самостоятельно проверить предложенный М ответ. [c.32]

Работу производили на хроматографе ЛХМ-7А с детектором теплопроводности, реконструированным по схеме, показанной иа рис. 4.12. Вводили 2 мкл смеси (по делениям микрошприца типа Гамильтон). Работы выполнял лаборант, который еще недостаточно отработал приемы воспроизводимого ввода пробы. Результаты измерений и вычислений представлены ниже в таблице, В правую половину таблицы занесены параметры пика, соответствующего общему количеству введенной пробы. Ширину этого пика на половине высоты измеряли по секундомеру и поэтому соответствующее значение площади выражали в см-с. Эти единицы можно перевести в см , поскольку известна скорость движения диаграммы, однако необходи.мости в этом пет. В последнюю графу таблицы внесены значения площади пика, приведенные к единице параметра общего пика. [c.145]

Справочник химика 21

Химия и химическая технология