Разметка - граф
Cтраница 1
Разметка графа приведена на основании того, что из состояния с меньшим номером в состояние с большим номером система переходит под воздействием входного потока с интенсивностью К. [1]
Разметка графа является стационарной, если свойства его дуг и вершин, определяемые, в частности, системой потоковых уравнений Ни, и 1, V (3.3) или (3.4), не изменяются никаким применением правил разметки. Правило определяет характер замены меток на отдельных этапах анализа. [2]
Простейшим примером применения разметки графов служат алгоритмы отыскания кратчайших путей в графе. [3]
X, то алгоритм функционирования сети на запросе х можно описать аналогично алгоритму разметки графа [51, 61]: считаем, что в начальный момент все вершины сети, кроме корня, неотмеченные, а некоторое упорядоченное множество вершин сети, которое назовем множеством активных вершин, содержит только корень сети. На каждом очередном шаге делаем следующее. Если множество активных вершин не пусто, то выбираем первую активную вершину и удаляем ее из множества активных вершин. Алгоритм завершает работу в тот момент, когда множество активных вершин окажется пустым. [4]
В свою очередь, древесная классификация позволяет выявить, исследовать и использовать ранее неизвестные свойства графов, зависящие и от топологии, и от разметки графа. [5]
 |
Информационный граф состояния системы массового обслуживания. [6] |
Такой граф называется размеченным графом состояний. Разметка графа учитывает переход системы из состояния с меньшими номерами в состояние с большими номерами под действием входного потока с интенсивностью Я. Рассмотрим переход из состояния с более высоким номером в состояние с меньшим номером. [7]
 |
Пример преобразования нечетной последовательности ветвей графа в четную. [8] |
При этом для любого узла графа автомата все входящие ветви должны быть отмечены одним из символов 77, Т2, а все выходящие ветви - другим. В свою очередь, такую разметку графа можно всегда выполнить, если только все замкнутые последовательности его ветвей содержат четное их число. [9]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продол жнется, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [10]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продолжается, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [11]
Теперь если взять произвольный запрос х Е X, то алгоритм функционирования сети на запросе х можно описать аналогично алгоритму разметки графа [51, 61]: считаем, что в начальный момент все вершины сети, кроме корня, неотмеченные, а некоторое упорядоченное множество вершин сети, которое назовем множеством активных вершин, содержит только корень сети. На каждом очередном шаге делаем следующее. Если множество активных вершин не пусто, то выбираем первую активную вершину и удаляем ее из множества активных вершин. Алгоритм завершает работу в тот момент, когда множество активных вершин окажется пустым. [12]
Цикл называется неприводимым, если его большой период - слово, которое по нему можно прочесть, - не циклично, т.е. не равно степени меньшего слова. Малым периодом цикла называется корень из его большого периода. Расположением слова в графе Г называется путь, по которому его можно прочитать. Если между графами Г; и Г можно установить соответствие, взаимно однозначное на стрелках и вершинах, при котором разным буквам разметки графа Г отвечают разные буквы разметки Г, то говорят, что граф Г; отличается от Г расклейкой букв. [13]
Страницы: 1