Cтраница 4
Такое распределение авторы, следуя Вейлю, называют равномерным: если все точки отрезка [ - 1, 1] рассматривать как проекции точек полуокружности ж2 г / 2 1 У 0, тона ней будем иметь равномерное распределение, при котором число точек на любой дуге пропорционально ее длине. [46]
Ниже мы покажем, что это параметрическое выражение для длины дуги имеет над предыдущей формулой то существенное преимущество, что его применение не ограничивается однозначными ветвями кривых, представленными уравнениями вида y f ( x); это выражение сохраняет силу для любой дуги кривой и даже для замкнутой кривой, если только производные x ( t) и у ( t) непрерывны вдоль рассматриваемой дуги. [47]
Для данной сети N ( D, ф) определим поток через N как функцию ф, сопоставляющую каждой дуге а из D неотрицательное действительное число ф ( а) ( называемое потоком через а) таким образом, что ( i) ф ( д): ф ( а) для любой дуги а; ( и) по отношению к сети ( D, ф) полустепень исхода и полустепень захода любой вершины ( отличной от у и да) равны между собой. Говоря неформально, это означает, что поток через любую дугу не превосходит ее пропускной способн эс-ти и что полный поток, входящий в любую вершину ( отличную от v и w), равен полному потоку, выходящему из нее. Для удобства назовем дугу а, для которой ф ( а) ф ( а), насыщенной ( на рис. 29.2 насыщенными являются дуги ( v, z), ( х, z), ( у, z), ( х, w) и ( z, w)); остальные дуги называются ненасыщенными. [48]
Ориентированный граф G F, [ / должен обладать следующими свойствами: существует единственная вершина графа v е V, из которой дуги только выходят; существует единственная вершина графа vNeV, в которую дуги только входят; в графе отсутствуют циклы ( ациклический граф); для любой вершины vt существует путь из v в VN, проходящий через эту вершину; для любой дуги ( ul5 Vj) существует путь из v в VN, содержащий эту дугу. [49]
Удалим из G2 любую дугу, вес которой не меньше с2, и так будем продолжать до тех пор, пока не получим орграф Gm 1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фт в Gm ( с весом ст) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm 1 следует, что в G. Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе G может быть найден с помощью построения полного орграфа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам - бесконечные веса. Если решение минимаксной задачи коммивояжера для Ог имеет конечный вес ( на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот. [50]
На окружности радиуса 1 с центром в начале координат берется какая-либо точка. Вероятность взять точку на любой дуге окружности зависит только от величины этой дуги и пропорциональна ей. [51]
Связная часть сети, содержащая все узлы и только N - 1 дуг, называется деревом. Дерево но содержит контуров и удаление любой дуги дерева приводит к потере связности. [52]
Сильной компонентой орграфа называется максимальный сильны л подграф, односторонней компонентой - максимальный односторонний подграф и слабой компонентой - максимальный слабый подграф. Легко проверить, что любая вершина и любая дуга орграфа D принадлежат точно одной слабой компоненте и по крайней мере одной односторонней компоненте. Более того, каждая вершина находится точно в одной сильной компоненте, а дуга либо лежит в одной сильной компоненте, либо не лежит ни в одной, в зависимости от того, принадлежит эта дуга или нет некоторому контуру. [53]
Например, заданы стандартное окружение для анализа G ( V, A), ( L, Л), F, 2V х 2А - F и некоторая начальная разметка графа G. Требуется найти стационарную разметку, при которой свойство любой дуги является наибольшей нижней гранью множества допустимых в соответствии с правилами разметки свойств. Задача анализа называется прямой, когда свойства любой вершины определяются свойствами ее предшественников. Если же свойства вершины зависят только от свойств ее преемников, то имеет место обратная задача анализа. [54]
Спаривание имеется не у каждого орграфа. Концами произвольного ребра графа О являются начало и конец любой дуги из соответствующей этому ребру пары. [55]