Тестирование софта - статьи


         

Примеры графов де Бройна изображены


При этом ребро x1x2…xk-1xk начинается в вершине x1x2…xk-1 и заканчивается в вершине x2…xk-1xk. Примеры графов де Бройна изображены на рис. 1. Достаточно легко убедиться в выполнении следующего утверждения. Утверждение 1. 1) Граф B(m, 1) имеет ровно одну вершину — пустое слово — и m ребер-петель. 2) Граф B(m, 2) изоморфен полному ориентированному графу с петлями на m вершинах. 3) Количества входящих и выходящих ребер для любой вершины B(m, k) равны m. "v Î V(m, k) in-deg(v) = out-deg(v) = m

Рисунок  1. Графы B(3, 1), B(3, 2), B(2, 3), B(2, 4). Последний пункт непосредственно влечет следующее. Утверждение 2. 1) Для всех m, k ? 1 граф B(m, k) эйлеров, т.е. в нем существует цикл, включающий все ребра 2) Любой эйлеров путь в B(m, k) однозначно соответствует слову де Бройна, а значит такие слова существуют для всех m, k ? 1.
Для построения слова, соответствующего пути в B(m, k), выпишем слово, соответствующее первому ребру пути, затем для каждого следующего ребра пути будем приписывать в конец полученного слова последний символ этого ребра. Определим для ориентированного графа G дуальный граф L(G) как граф, имеющий в качестве вершин множество ребер G, а в качестве ребер — множество пар смежных ребер G, т.е. таких, что конец первой является началом второй. При этом ребро L(G) начинается в вершине, соответствующей первому элементу пары, а кончается в вершине, соответствующей второму. Утверждение 3. 1) Для всех m, k ? 1 дуальный граф к B(m, k) изоморфен B(m, k+1).
Это легко проверить, заметив, что паре смежных ребер B(m, k) соответсвует слово длины (k+1), построенное по правилу из второго пункта предыдущего замечания.
Кроме того, все m-слова длины (k+1) могут быть получены таким способом. 2) Эйлеров путь или цикл на графе G соответствует гамильтонову (проходящему через каждую вершину ровно один раз) пути или циклу на графе L(G) 3) Для всех m, k ? 1 граф B(m, k) имеет гамильтонов цикл Сделанные замечания позволяют определить достаточно эффективный алгоритм построения слов де Бройна — для этого достаточно построить граф B(m, k), что требует объема памяти и времени O(mk), и найти в нем эйлеров цикл, что можно сделать за время, пропорциональное количеству ребер графа, т.е.

Содержание  Назад  Вперед