Эйлеров цикл в однородных семантических сетях.

Перейдем к задаче на нахождение эйлерова цикла в заданном фрагменте сети.

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом [16].

Теорема: Конечный граф G является эйлеровым графом тогда и только тогда, когда

4. G связен.

5. Все его локальные степени четны [16].

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

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

 

 

 

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

 

 

 

Предлагаем следующий способ: искусственно вводится дополнительный вес Q для каждого ребра - это номер дороги. Далее заменяем каждое ребро на две дуги, каждой из которых присваиваем вес исходного ребра, т.е. его номер.

Вместо отношения достижимости (транзитивное замыкание) возьмем на взвешенном графе G(V,E) рефлексивно транзитивное замыкание E1 на V бинарного отношения E.

 

 

Т.о. получаем, что наш новый граф может содержать петли, т.е. является псевдографом:

 

 

Для каждой вершины графа G1(V,E1) задаем множество, состоящее из множеств дуг с различными номерами, пройденных по пути в исходной сети от одной смежной ребру вершины до другой. DÌE1´2E - отношение множества дуг полученного графа во множество множеств дуг с различными номерами, пройденных по пути от одной вершины к другой. Таким образом, D определяет подмножество цепей, по которым можно пройти от одной вершины к другой. Определим отношение CÌE1´2Q, которое для каждого дуги e из E1 ставит в соответствие номера дуг для D(e). Для множества C каждой цепи ставится в соответствие количество номеров дуг в данной цепи . Для каждого ребра приписываем новый вес MÌE´N - максимум мощностей множества номеров различных ребер, пройденных по пути в исходной сети - максимум длин соответствующих цепей. Этот максимум не превосходит половины мощности множества дуг исходной сети (мощности ребер |E|), а если совпадает с ним, то существует цепь, включающая дуги со всеми возможными номерами.

Построим сеть, где дуга eÎE2 тогда и только тогда, когда eÎE1 и в имеющейся сети вес этой дуги равен M(e)=|E|.

 

Заметим, что существование для вершины петли означает также существование цикла, включающего дуги со всеми различными номерами. Определим для вершин свойство  существования такого цикла из данной вершины. Заметим, что в исходном, неориентированном графе построенному таким образом циклу соответствует эйлеров цикл.

Математическое соотношение будет выглядеть следующим образом:

 

Или, применяя формулу,

.

 

Таким образом, мы получили набор математических высказываний, необходимых для описания преобразования сетевых моделей в ходе решения поставленных задач.