Термин - теория - граф
Cтраница 2
Метод пуговиц и нитей легко интерпретировать в терминах теории графов. [16]
Постановку задачи коммивояжера используют часто и в терминах теории графов. В простейшем случае отображение Г - направлен-ный отрезок, соединяющий две произвольные точки множества X. Элементы х е X называются вершинами графа, а направленный отрезок, соединяющий точки хеХ и у е Гх е X, - дугой графа. [17]
Кларка, сформулировала достаточно общие условия единственности стационарных состояний в терминах теории графов. [18]
ЦИКЛ [ closed circuit ( of a graph) ] - термин теории графов: замкнутая цепь, т.е. такая цепь, которая, начавшись в некоторой вершине, завершается в ней же. [19]
В химической физике полимеров решение многих задач значительно упрощается, если их удается сформулировать в терминах теории графов. Такой подход особенно эффективен при описании разветвленных и сетчатых полимеров, которые представляют собой наборы макромолекул с различным числом структурных единиц ( звеньев), соединенных между собой всевозможными способами. Для того чтобы учесть возникающую в таких системах структурную изомерию макромолекул, каждой из них удобно поставить в соответствие молекулярный граф, аналогичный структурной формуле в классической органической химии. Однако синтетические полимеры являются наборами практически бесконечного числа индивидуальных химических соединений, а поэтому отвечающие им статистические ансамбли молекулярных графов содержат такое же число различных представителей. Их распределение в полимерном образце является случайным и определяется условиями его синтеза. Следовательно, в теории полимеров приходится иметь дело с ансамблями случайных графов, для нахождения вероятностной меры которых нужно рассматривать процесс получения полимерного образца, когда происходит формирование соответствующего этому образцу набора макромолекул. Такая необходимость совместного физического и химического рассмотрения полимерных систем, как будет видно из дальнейшего, является одной из основных особенностей их теоретического описания. [20]
 |
Цепная коробка передач. [21] |
Вначале анализируют матрицу [ Ас I, в результате чего выделяют каждую из составляющих г передач, что в терминах теории графов соответствует выделению из данного графа всех элементарных путей от начальной вершины графа до конечной. По этим матрицам и вектору ц определяется матрица [ Н ] КПД, элемент которой r mk представляет собой КПД от ведущего вала до вала т на & - й передаче. [22]
В рассматривавшихся нами задачах всюду Р 1 и траектории конечны. Условие конечности траекторий процесса может быть легко интерпретировано в терминах теории графов. Траектории процесса, очевидно, сопоставляется путь в этом графе. Таким образом, в случае конечного графа для того чтобы процесс динамического программирования не имел бесконечных траекторий, необходимо и достаточно, чтобы соответствующий ему граф не имел контуров. [23]
 |
Ориентированный граф [ IMAGE ] Взвешенный граф. [24] |
Теорию графов часто называют языком дискретной математики. И действительно, чрезвычайная емкость этого языка позволяет сформулировать в терминах теории графов большое число задач дискретной математики. Поэтому те усилия, которые, возможно, потребуются для преодоления несколько скучной последовательности определений, полностью окупятся при чтении дальнейшего материала. Все вводимые понятия теорий графов условно разобьем на четыре группы. [25]
Если порядок в этих поддеревьях существен, дерево называется упорядоченным деревом, в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как граф ( G. Таким образом в терминах теории графов можно дать другое определение ( ориентированного) дерева: дерево - это ориентированный ациклический ( А. [26]
Заметим, что полный граф Gn содержит как эйлеровы, так и гамильтоновы циклы. Задачи выделения эйлеровых и гамильтоновых циклов тесно связаны с так называемыми задачами о лабиринте и о коммивояжере. Задача о лабиринте в терминах теории графов формулируется как задача определения в связном графе G ( X, U) такого маршрута S, который начинается в заданной вершине Xi и приводит в другую искомую вершину Xj, причем маршрут S должен содержать кратчайшее число ребер. Известные методы Тэрри, Трюмо, Люка и Кенига, описанные в работе О. Оре [115], позволяют находить такой маршрут. [27]
Задача генерации всех возможных сценариев может быть решена различными методами. Все они, так или иначе, сводятся к перебору дуг графа, описывающего создавшуюся проблему. Поэтому решение задачи могло бы быть дано и в терминах теории графов. Однако с точки зрения перспектив решения подобных задач для графов со значительно более сложной структурой ( например, когда на элементы графа накладываются различные условия) более перспективным может оказаться использование аппарата формальных грамматик. [28]
Таким образом, методы теории графов находят применение и для анализа кинетических моделей нелинейных химических реакций. Более того, в последнее время А. Н. Ивановой [73] развиты методы анализа ряда критических явлений и для распределенных систем типа реакция диффузия. Условия возникновения в таких системах диссипативных структур удается также сформулировать в терминах теории графов, естественным образом учитывающих особенности структуры механизма сложной химической реакции. [29]
Исключение объема можно объяснить с помощью простых модификаций моделей полимеров, хотя полученные модели трудно интерпретировать математически. Одна из таких модификаций состоит в том, что графы полимеров должны быть уложены без самопересечений на регулярном графе решетки в евклидовом пространстве. Например, в случае единственной / V-мономерной линейной цепи модель без исключения объема представляет полимер с помощью Л - шагового случайного блуждания ( при допущении повторных заходов в центр решетки), тогда как соответствующая модель с исключением объема представляет полимер с помощью Л - шагового блуждания без самопересечений. Оба типа моделей формулируются исключительно в терминах теории графов. О математических трудностях, возникающих в упомянутой выше модели с исключением объема, свидетельствует отсутствие полностью строгих математических доказательств даже в случае очевидно справедливых предположений [3], таких, как: среднее расстояние между концами ( R-N / V-шаговых блужданий без самопересечений на регулярной решетке увеличивается с ростом N, или эта величина ( RyN больше по сравнению с соответствующей средней величиной для Лг-шаговых случайных блужданий без самопересечений. [30]
Страницы: 1 2