Взвешенный граф

Cтраница 3

Существует много модификаций описанных методов. Одним из них является построение взвешенного графа схемы. Для этого подсчитывают для каждой пары элементов число соединяющих их цепей. [31]

А, Пп, Е, Е -, Гя, обозначения к-рых переносятся п н особенности. С, точностью до изоморфизма такая особенность определяется споим взвешенным графом Г ( [ 3, 11), см. таблицу, кол. [32]

Рассмотрим характеризационную задачу преобразования модели, задающей выходные функции автомата, в модель, определяющую его функции возбуждения. Соответствующую выходной функции fj автомата модель / Л представим взвешенным графом Gfj, множество вершин и дуг которого взаимно однозначно соответствует вершинам и дугам графа переходов автомата Gn, причем дуги графа Gfj взвешены переменной, принимающей значения у - й выходной функции на соответствующих переходах автомата из одного состояния в другое. Дуги графа Gfj ориентированы. Если структура запрещенных фигур не зависит от ориентации дуг, будем рассматривать соответствующий неориентированный граф, обозначая его Gfj. [33]

Пусть J - произвольное Т - соединение в графе G и взвешенный граф ( G, wj) такой, как определено выше. Тогда J является наименьшим Т - соединением в том и только том случае, когда взвешенный граф ( G, wj) является консервативным. [34]

Однако взвешивание графа А 4, показанное на рис. 6.6.1, дает один из соответствующих контрпримеров: этот взвешенный граф консервативный, но двух ре-берно непересекающихся разрезов не содержит, а одного разреза для доказательства его консервативности не достаточно. [35]

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

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

Представление с помощью списка дуг применяется в тех случаях, когда необходимо иметь отдельную, независимую нумерациюv дуг. При этом способе каждой дуге сопоставляется троша и -, х, уУ, где и - дуга, х - ее начало, у - ее конец. Этот способ представления легко обобщается - на случай взвешенных графов. Более того, он наиболее приспособлен для хранения различной информации о дугах. [38]

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

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

Дискретная физическая система. [41]

Естественной моделью НТС на концептуальном уровне является сеть, вершины графа которой представляют аппараты, а дуги - потоки. С каждой дугой и вершиной связаны некоторые веса в виде числовых значений. Одни из них константы, такие, как диаметр аппарата или активность катализатора, другие - переменные, представляющие свойства потоков. Таким образом, сеть есть взвешенный граф, который представляет как структурные, так и переменные свойства НТС. [42]

Граф Кокстера определяет лишь углы между парами корней базиса; по нему не восстанавливается матрица Картана ( но восстанавливается группа Вейля): существуют дуальные неизоморфные К. Однако матрица Картана ( а с ней и К. Ориентация вводится по правилу: если простые корни а - и а - не ортогональны п имеют разную длину, то на двух или трех ребрах, соединяющих i - ю и / - ю вершины, ставится знак неравенства, ориентированный в сторону вершины, отвечающей корню меньшей длины. В нек-рых случаях над каждой вершиной графа Кокстера надписывают число, пропорциональное квадрату длины соответствующего корня ( с общим для всех корней коэффициентом пропорциональности); по такому взвешенному графу также однозначно восстанавливается К. [43]

Производящая функция, рассматриваемая как цельный объект, может обладать такими свойствами, которые трудно и противоестественно записать в терминах отдельных коэффициентов ряда и которые даже совсем не имеют места для отдельно взятого коэффициента. Этим объясняется кажущийся парадокс: ряд задач на подсчет удается решить только после вышеупомянутого усложнения их постановки. Общий подход к нахождению считающих рядов и их производящих функций был впервые предложен Пойя [180]; сам автор применил свою основную теорему для подсчета количества неизоморфных деревьев с заданным числом вершин и выделенной вершиной ( корнем), а также для определения количества изомеров у некоторых химических соединений. Подробное изложение теоремы Пойя и разнообразных ее применений имеется в книге Риордана [52], однако для первого ознакомления мы рекомендуем статью Харари [133], в которой без введения большого числа понятий даются формулировка этой теоремы и ее непосредственные приложения, такие как подсчет графов и диграфов ( направленных графов) с заданными количествами вершин и ребер, подсчет связных графов и некоторых взвешенных графов. Из работ этого направления, появившихся в период между выходом оригинала книги Риордана ( 1958 г.) и 1962 годом, отметим работу Рида [185, 186]; доказанная им теорема суперпозиции позволяет значительно расширить сферу применимости теоремы Пойя, например, дает возможность подсчитывать количество неизоморфных графов с заданными степенями вершин. [44]

Страницы: 1 2 3