Решение. Для определения этих параметров изобразим граф и составим матрицу расстояний: (на пересечении столбца и строки (вершины графа) матрицы указывается расстояние

Для определения этих параметров изобразим граф и составим матрицу расстояний: (на пересечении столбца и строки (вершины графа) матрицы указывается расстояние между этими вершинами; такая матрица (выделена на рисунке) симметрична относительно главной диагонали).

В столбце с заголовком r( v_i ) укажем удаления от соответствующих вершин (максимальное значение расстояния каждой строки).

Вершины	a	b	c	d	e	f	r(v_i)	Центр
a								Нет
b								Нет
c								Да
d								Да
e								Да
f								Нет

Максимальное из удалений и будет диаметром графа (т.е. максимально возможным расстоянием между вершинами в исследуемом графе): D(G)= 3.

Вершины, для которых удаление r( v_i ) принимает минимальное значение (помечены в последнем столбце «Да»), являются центрами графа G, а значение удаления – радиусом графа:

r(G ) = 2.

Если ребра графа нагружены (каждому ребру поставлено в соответствие определенное числовое значение), то процедура исследования аналогична описанной выше, но при заполнении матрицы нужно определять расстояние между вершинами не по числу ребер, а по суммарной их длине.

3.6 Диаметр протяженности, радиус протяженности и центр протяженности графа

Рассмотрим единичный связный неориентированный граф G. Максимальная длина простой цепи с началом в v¢, и концом в v² называется протяженностью между этими вершинами (обозначается g(v¢,v²)).

Диаметр протяженности графа – максимальная из протяженностей между любыми парами вершин:

L(G) = max g(v¢,v²).

v',v" Î G

Для каждой вершины v_i существуют самые длинные простые цепи, связывающие ее с другими вершинами графа; их длина называется числом протяжённости для вершины v_i

l ( v_i ) = max g(v_j).

v_j Î G

Центр(центры) протяженности – вершина с минимальным числом протяженности. Самые длинные простые цепи с началом в центре протяженности называются радиальными, а их длина – радиусом протяжённости графа.

l(G) = min l(v_i).

v_i Î G

Параметры протяженности(центр, диаметр и радиус) при анализе графа на максимум определяются аналогично параметрам при анализе графа на минимум.

Пример. Для анализа на максимум используем граф G из предыдущего примера: V={a, b, c, d, e, f}; E={ab, ac, bc, cd, ce, de, ef}. Определить диаметр протяженности, центр(центры) протяженности и радиус протяженности этого графа.

Для определения этих параметров изобразим граф G и составим матрицу протяженностей: (на пересечении столбца и строки(вершины графа) матрицы указывается протяженность между этими вершинами; такая матрица(выделена на рисунке) симметрична относительно главной диагонали).

В столбце с заголовком l(v_i) приводятся числа протяженностей для вершин, указанных в начале каждой строки (максимальное из значений протяженностей каждой строки). Максимальное из чисел протяженностей и будет диаметром протяженности графа (т.е. максимально возможной протяженностью между вершинами в исследуемом графе): L(G) = 5.

Вершины	a	b	c	d	e	f	l(v_i)	Центр
a								Нет
b								Нет
c								Да
d								Нет
e								Нет
f								Нет

Вершина с, для которой число протяженности принимает минимальное значение, является центром протяженности графа G, а значение числа протяженности вершины с – радиусом протяженности графа: l(G) = 3.

Если ребра графа нагружены (каждому ребру поставлено в соответствие определенное числовое значение), то процедура исследования графа на максимум аналогична описанной выше, но при заполнении матрицы нужно определять протяженность между вершинами не по числу ребер, а по суммарной их длине.

3.7 Задачи к главе 3

1 Задан граф G: V ={A, B, C, D, E, F}; E ={AB, AD, BC, DЕ, CE, EF}.

Привести графическое изображение этого графа, привести примеры суграфа, покрывающего суграфа, подграфа G(U) для вершин U={C,D,E} (с пояснениями) и звездного графа для вершины D. Определить диаметр, центр и радиус графа G.

2 Задан граф G: V ={A, B, C, D, E, F}; E ={ AB, CB, BE, BD, EF, FD}.

Привести графическое изображение этого графа, привести примеры для него суграфа, покрывающего суграфа, подграфа G(U) для вершин U={А,D,E} (с пояснениями) и звездного графа для вершины В. Определить параметры протяженности (диаметр, центр и радиус) этого графа.

3 Задан граф G: V ={ A, B, C, D, E, F}; E ={ AB, CB, BE, BD, EF, DЕ}.

Привести графическое изображение этого графа, привести примеры для него суграфа, покрывающего суграфа, подграфа G(U) для вершин U={А,B,E} (с пояснениями) и звездного графа для вершины F. Определить параметры протяженности (диаметр, центр и радиус) этого графа.

4 Задан граф G: V ={A, B, C, D, E, F}; E ={AB, AF, BE, BD, BC, FC, EF}.

Привести графическое изображение этого графа, привести примеры суграфа, покрывающего суграфа, подграфа G(U) для вершин U={F,D,E} (с пояснениями) и звездного графа для вершины A. Определить диаметр, центр и радиус графа G.

4 Теория конечных автоматов

4.1 Конечные автоматы – распознаватели

Конечный автомат (в дальнейшем КА) – абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки (последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.

Принцип работы конечных автоматов различных уровней широко применяется в вычислительных устройствах как на аппаратном, так и на программном уровнях: это компиляторы, трансляторы программ, различные кодировщики, антивирусные программы и т.п. В принципе работу любой программы можно представить как работу цепочки конечных автоматов различной сложности. Рассмотрим построение простейших КА – распознавателей. В процессе построения такого конечного автомата должны быть определены следующие параметры:

а) входной алфавит V конечного автомата (конечное множество входных символов, которые будет распознавать КА);

б) конечное множество состояний S;

в) начальное состояние КА – s ₀ (состояние, с которого начинает работу КА при обработке новой цепочки);

г) множество допускающих состояний – S _доп (подмножество состояний, с элементами которого сравнивается достигнутое КА состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре "текущее состояние – входной символ" ставит в соответствие новое состояние КА из множества состояний S).

Примечания:

1 В множество входных символов обязательно включают особый символ "конец цепочки", который сообщает КА о том, что достигнутое состояние s_i нужно сравнить с элементами множества S _доп и, если s_i Î S _доп, пропустить цепочку; в противном случае цепочка отвергается. В тексте этот символ будет иметь вид –|.

2 Часто при распознании цепочек возникает ситуация, когда невозможно текущей паре "состояние – входной символ" поставить в соответствие новое состояние. По сути это означает, что цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом " Е " ("error"); попав в такое состояние, КА отвергает проверяемую цепочку и переходит в начальное состояние. В конкретных программных реализациях может вызываться обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.

КА всегда начинает работу из начального состояния s ₀. Символы распознаваемой цепочки поступают посимвольно, начиная с первого, и изменяют состояния КА в соответствии с таблицей переходов. После поступления символа "конец цепочки" достигнутое автоматом состояние фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается. По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА – компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке программирования).

Построение КА для распознания заданного множества цепочек – процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству. Он эффективен в следующих случаях:

– распознаваемые цепочки содержат определенные сочетания символов в начале, конце или (и) середине цепочки;

– распознаваемые цепочки содержат ограниченное число повторений определенных символов или их сочетаний (не больше n; точно n; не меньше n, причем n = 1,2,3);

– распознаваемые цепочки содержат запрет на определенные сочетания символов в начале, конце или (и) во всей цепочке;

– распознаваемые цепочки содержат комбинации названных выше ограничений.

4.2 Эквивалентные состояния КА

Состояния s и t двух различных конечных автоматов эквивалентны тогда и только тогда, когда первый КА, начав работу из состояния s, будет допускать те же цепочки, что и второй КА, начав работу из состояния t. Если эти состояния начальные, то эти автоматы эквивалентны (т.е. будут распознавать одни и те же множества).

Два состояния конечного автомата эквивалентны тогда и только тогда, когда, начав работу из этих состояний, конечный автомат будет допускать одни и те же цепочки.

Другими словами, если для двух состояний КА нет различающей цепочки, то такие состояния эквивалентны (различающая – такая цепочка символов, которая приводит КА из сравниваемых состояний к различным конечным результатам).

Эквивалентные состояния, принадлежащие одному КА, не нарушая эквивалентности, можно заменить одним (в таблице переходов оставить одну из строк эквивалентных состояний, удалив остальные, при этом заменить имена удаленных состояний на оставленное).

Приведенное выше определение эквивалентных состояний не дает эффективного алгоритма поиска таких состояний.

Поиск эквивалентных состояний производится в процессе многократного разбиения множества состояний КА в зависимости от характера воздействия входных символов. Эта операция производится пошагово.

Шаг 1: множество состояний КА разбить на две подгруппы по воздействию символа "конец цепочки" (допускающие и отвергающие) и записать их в виде двух подмножеств; в каждом из полученных подмножеств все состояния по воздействию символа "конец цепочки" эквивалентны.

Шаг 2: повторить запись подмножеств, полученных на момент выполнения этого шага, в виде новой строки и стрелками показать переходы для каждого состояния из предыдущей в новую строку по воздействию другого входного символа.

Шаг 3: выполнить разбиение подмножеств состояний на новые эквивалентные по входному символу подмножества, руководствуясь правилом – "оснований для разбиения подмножества нет, если все его элементы (состояния) переходят в одно подмножество".

Шаг 4: если в образованных подмножествах больше одного состояния, повторять шаг 2 до полного перебора всех входных символов; после завершения процесса два и больше состояния, входящие в полученные в конце подмножества эквивалентны между собой.

4.3 Недостижимые состояния КА

Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов.

Не нарушая эквивалентности, такие состояния можно исключить из таблицы переходов КА. Процедура поиска недостижимых состояний следующая:

Шаг 1: записать одноэлементное множество, в которое входит начальное состояние.

Шаг 2: дополнить это множество состояниями, в которые переходит КА из состояний, уже присутствующих в множестве при воздействии любых входных символов.

Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен исчерпывающий список достижимых состояний; остальные состояния КА недостижимы

Конечный автомат, в котором исключены недостижимые и эквивалентные состояния называется минимальным КА.

Для каждого КА существует бесконечное множество других эквивалентных ему КА (распознают то же множество цепочек), однако минимальный КА – единственный (автомат с минимальным числом состояний).

4.4 Недетерминированный конечный автомат

Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре "входной символ – состояние" ставится в соответствие множество состояний (а не единственное, как в КА) и начальных состояний может быть несколько. Такой автомат может получиться при решении конкретной задачи – построении распознавателя для регулярного множества. Единственный недостаток такого НКА, по сравнению с КА, невозможность простой программной реализации.

В процессе построения такого недетерминированного конечного автомата должны быть определены следующие параметры:

а) входной алфавит V (конечное множество входных символов и символ "конец цепочки");

б) конечное множество состояний S;

в) множество начальных состояний S _нач (подмножество состояний, с которых может начинать работу НКА при обработке новой цепочки);

г) множество допускающих состояний S _доп (подмножество множества состояний S, с которым сравнивается достигнутое НКА состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре "текущее состояние – входной символ" ставит в соответствие несколько новых состояний; если паре "текущее состояние – входной символ" нельзя поставить в соответствие ни одно состояние из множества S, то клетку таблицы переходов оставляют пустой.

Работу НКА можно интерпретировать двумя способами:

1 На некоторых шагах при распознании цепочки с помощью НКА есть множество выборов. Если имеется хотя бы одна последовательность состояний, при которой НКА заканчивает работу в допускающем состоянии, то такая цепочка будет допущена этим НКА.

2 При возникновении альтернативы во время работы НКА (в выборе начального состояния или перехода) автомат распадается на конечные автоматы по количеству альтернатив, которые работают параллельно. Если при поступлении символа "конец цепочки" хотя бы один из параллельно работающих КА находится в допускающем состоянии, то такая цепочка будет допущена этим НКА.

Существует процедура эквивалентного преобразования НКА в КА по следующему алгоритму (преобразуется таблица переходов НКА):

1 Для будущей управляющей таблицы эквивалентного КА изобразить столбцы по количеству входных символов и обозначить их входными символами.

2 В первую клетку первой строки занести как множество все начальные состояния НКА.

3 Заполнить остальные клетки этой строки (кроме последней): по таблице переходов НКА выписать в виде множеств все состояния, в которые переходят состояния, записанные в первой клетке через соответствующие входные символы.

4 В первой клетке очередной строки записать одно из новых множеств состояний, которые получены в п.3 при заполнении клеток таблицы переходов, и выполнить п.3.

5 Закончить процесс построения таблицы переходов после того, как будут исчерпаны все варианты множеств, которые появились в таблице.

6 При заполнении столбца с символом "конец цепочки" ставить "допустить", если в множество состояний первой клетки строки входит хотя бы одно допускающее состояние НКА, и "отвергнуть" – в противном случае.

7. Переобозначить множества состояний как новые состояния и заново заполнить таблицу переходов (получена таблица переходов эквивалентного КА).

8. Определить остальные параметры КА по полученной таблице переходов.

Описанную выше процедуру проиллюстрируем на конкретном примере.

Пример. НКА задан таблицей переходов: