Некоторые понятия теории графов

НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ [c.327]

Разработана математическая модель молекулярной сложности, основанная на понятиях теории графов и теории информации. Проведено сравнение с другими индексами и показано применение этой модели к некоторым проблемам синтеза. Внесена ясность в соотношение молекулярной сложности и сложности синтеза. [c.236]

Часто применяют алгоритмы, которые используют методы и понятия теории графов. В этом случае матрицу близостей рассматривают в виде графа с п вершинами, которые соединены между собой п — 1 ребрами. Весом данного ребра является расстояние между вершинами [13]. Это — начальный граф далее, задавая некоторое пороговое расстояние и считая, что две точки находятся в той же группе, если расстояние между ними меньше заданного, получается разделение на группы (алгоритм единственной связи). Другим рассматриваемым приемом является нахождение минимального незамкнутого пути, который проходит через все вершины. Группировку получают по правилу ближайшего соседа. Удаление самого длинного ребра в пути вызывает разделение на две группы, удаление следующего по длине ребра — разделение на три группы и т. д. [c.117]

Изложим некоторые элементарные понятия теории графов (51 применительно к описанию конфигураций макромолекул. Как уже отмечалось, каждую молекулу полимера можно схематически изобразить в виде некоторого молекулярного графа, т. е. набором вершин, соединенных ребрами. Различают вершины, из которых выходит только одно ребро и все остальные. Первые называются висячими вершинами, а вторые — узлами. Ребро, выходящее из висячей вершины, назовем боковым, в отличие от внутреннего ребра, соединяющего два узла. Вершины различных типов на. графах раскрашиваются в разные цвета, как на рис. 2.1. При изображении конкретной молекулы в виде графа некоторым фрагментом молекулы ставятся в соответствие вершины, а некоторым — ребра. Выбор закона соответствия неоднозначен и зависит как от типа процесса получения разветвленного полимера, так и от того, какие его характеристики требуется рассчитать. [c.52]

Для формулировки основных положений построения кинетических моделей реакций с применением теории графов сначала приведем ее некоторые определения и понятия, заимствованные из литературы [12, 65, 66, 87]. [c.97]

Для дальнейшего изложения нам удобно использовать некоторые понятия из теории графов Иллюстрировать эти определения мы будем на примере графа, представленного на рис. 23. [c.95]

Понятие об индексе связности заимствовано из теории графов. Структурная формула соединения в том виде, как мы ее записываем, представляет собой связный граф в котором атомы углерода и гетероатомы являются вершинами (атомы водорода при этом опускаются), а простые и.кратные связи - соответственно одинарными или кратными ребрами. Величина индекс связности графа 4 , характеризует его разветвленность и определяется числом способов, которыми цепочка из трех атомов может быть "прейдена" внутри молекулы. Подсчет числа т удобно производить с помощью другого, так называемого реберного графа от графа /И, вершины которого соответствуют ребрам в графе 4 , а ребра связывают те и только те вершины, которые отечают смежным ребрам графа М. Число ребер в графе В М) равно индексу связности т. В табл.20 приведены структурные формулы некоторых углеводородов, реберные графы и величины т. [c.182]

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

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