Ребро - дерево
Cтраница 2
Описанный в данном разделе алгоритм вычисляет пропускные способности ребер дерева Т аа га - 1 этапов. Каждый этап состоит в вычислении потока в графе, получаемом последовательно из ранее построенного графа с помощью конденсации, как об этом говорилось выше в разд. [16]
Этот разряд принимает одно значение, если указатель является ребром дерева, и другое, если указатель - нить. [17]
C, либо ( b) подграф, состоящий из ребра дерева ( у, w), vt С, w ( C, и ориентире ванного поддерева, имеющего корнем w, вместе со всеми обратными ребрами из этого поддерева. Вершина vt в С, из которой начинается сегмент, называется базовой вершиной сегмента. [18]
 |
Граф технологических цепей размерных связей процесса механической обработки заготовки ступенчатого валика. [19] |
Любой замкнутый контур совмещенного графа образует размерную цепь, у которой ребро исходного дерева является замыкающим звеном, а ребра производного дерева - составляющими звеньями. [20]
Когда во время порождения ( и размещения), сегментов мы возвращаемся вниз по ребру дерева ( Wj-i, vt), то знаем, что все сегменты, начинающиеся в вершине vt ( или выше), порождены и успешно размещены. Поскольку сегменты порождаются, в порядке убывания их базовых вершин ( в С), ни один из еще непорожденных сегментов не может начинаться в вершине, большей vt - поэтому по теореме 8.4 ни одно обратное ребро, входящее в вершину vt - T или выше, не может мешать размещению следующего сегмента. [21]
Определить вероятность того, что получится ориентированное дерево с корнем в некоторой вершине, если ребра дерева, содержащего п ребер, ориентируются случайным образом. Ответ зависит от п, а не от структуры дерева. [22]
Пук - величина / - го дерева графа; ун - код k - то ребра дерева; г - число деревьев графа. [23]
Добавление любого ребра ( х х) из О, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из x в х, и только что добавленного ребра. Так как в графе О имеется т ребер, п - 1 из которых лежат в Т, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа С. [24]
Добавление любого ребра ( xi: xs) из G, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из X ] в Х, и только что добавленного ребра. Так как в графе G имеется т ребер, п - 1 из которых лежат в Г, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа G. [25]
Следует заметить, что предложение 2.2.17 показывает независимость описания фундаментальной группы, данного в терминах образующих, соответствующих ребрам максимального дерева, от выбора этого дерева, а кроме того то, что n ( Q /, X, v) не зависит с точностью до изоморфизма от выбора вершины и. [26]
Любой замкнутый контур совмещенного графа образует размерную цепь, у которой ребро исходного дерева является замыкающим звеном, а ребра производного дерева - составляющими звеньями. [27]
Последовательный декодер является декодером, предназначенным для кодов с древовидной структурой, который декодирует их путем принятия пробных гипотез относительно последовательных ребер дерева и изменяет эти гипотезы, если последующий выбор указывает на неправильность ранее принятых гипотез. К сожалению, чрезвычайная простота этой концепции исчезнет при четкой формулировке правила о том, должен ли декодер продолжать принимать новые гипотезы, или он должен вернуться для изменения старой гипотезы. Нашим целям отвечают три требования к стратегии поиска при последовательном декодировании. Во-первых, стратегия должна в конце концов с высокой вероятностью привести к правильному декодированию последовательности источника. Во-вторых, количество вычислений, требуемых декодером, не должно быть чрезмерным. Наконец ( это требование не возникает для действующих систем), стратегия должна допускать математическое исследование. Первая такая стратегия ( или алгоритм) была предложена Возенкрафтом ( 1957), который к тому же явился автором идеи последовательного декодирования. [28]
Выходим теперь из z и начинаем путь по следующему ребру, исходящему из г. Каждый раз, когда мы проходим ребро дерева, мы продолжаем построение пути; когда мы проходим обратное ребро, оно становится последним ребром текущего пути. Таким образом, каждый путь состоит из последовательности ребер дерева ( их число 0), за которыми следует одно обратное ребро. Новый путь начинается из начальной вершины последнего обратного ребра; если в этой вершине неисследованных ребер больше нет, возвращаемся к предыдущей вершине на последнем пути. Процесс продолжается до тех пор, пока в графе G не исчерпаются непройденные ребра. Алгоритм 8.14 осуществляет это разложение орграфа на пути и цикл. [29]
Процесс переноса в динамике показан в табл. 3.1. Очевидно, после п - 1 шага в запись будут перенесены все ребра дерева, причем запись будет для каждого дерева единстве иной. [30]
Страницы: 1 2 3 4 5