Индексы структурной сложности орграфов в базисах ориентированных цепных фрагментов
ОЦФ — связный орграф, состоящей либо из одной вершины (ОЦФ длины 0, наименьший элемент базиса), либо из большего числа вершин, причем две из них имеют степень 1, а остальные — 2 (длина ОЦФ равна числу дуг в нём). Отметим, что полустепени исхода и захода могут быть любыми. Использования ОЦФ в качестве элементов базиса позволяет увеличить дискриминирующую способность индексов СС при сохранении… Читать ещё >
Индексы структурной сложности орграфов в базисах ориентированных цепных фрагментов (реферат, курсовая, диплом, контрольная)
Рассмотрим задачу нахождения индекса, вектор-индекса СС и полного структурного спектра (ПСС) орграфа G в базисе произвольных фрагментов. Вектор-индекс, индекс структурной сложности и ПСС орграфа G в базисе произвольных фрагментов [Кохов, 2002]:
.
.
.
где G — орграф, — элементы базиса, wi — количество канонических изоморфных вложений фрагментов в орграф G, относительно которого характеризуется сложность графа. В качестве параметров построения индексов, вектор-индексов, ПСС необходимо задать сложность хотя бы некоторых базовых фрагментов минимального размера, сложность фрагментов большей длины может вычисляться рекурсивно.
Для разработки алгоритмов и дальнейших исследований в качестве мер сложности выбраны вектор-индексы, индексы СС и ПСС в базисе простых путей (ISSC (G/P)), полупутей (ISSC (G/PP)), контуров (ISSC (G/C)), полуконтуров (ISSC (G/CC)) и ориентированных цепных фрагментов (ОЦФ) (ISSC (G1/OCF)).
ОЦФ — связный орграф, состоящей либо из одной вершины (ОЦФ длины 0, наименьший элемент базиса), либо из большего числа вершин, причем две из них имеют степень 1, а остальные — 2 (длина ОЦФ равна числу дуг в нём). Отметим, что полустепени исхода и захода могут быть любыми. Использования ОЦФ в качестве элементов базиса позволяет увеличить дискриминирующую способность индексов СС при сохранении вычислительной сложности алгоритмов построения индексов.
В таблице 1 приведен пример базовых ОЦФ и их значений сложности.
Табл. 1.
Диаграммы минимальных ОЦФ. | Стандартные значения сложности ОЦФ. | |
ISSC (F0/OCF) = 1. | ||
ISSC (F1/OCF) = 3. | ||
ISSC (F2/OCF) = 9. | ||
ISSC (F3/OCF) = 10. | ||
ISSC (F4/OCF) = 11. | ||
Таблица 2 содержит пример вычисления значений индексов СС в базисах путей, полупутей, контуров, полуконтуров и ОЦФ для орграфов G1 и G2.
Табл. 2.
Орграф G1 | Орграф G2 | Значения индексов. | |
  ISSC (G1/P) = 86, ISSC (G2/P) = 86. | |||
ISSC (G1/PP) = 242, ISSC (G2/PP) = 242. | |||
ISSC (G1/C) = 133, ISSC (G2/C) = 16. | |||
ISSC (G1/CC) = 234, ISSC (G2/CC) = 234. | |||
ISSC (G1/OCF) = 129, ISSC (G2/OCF) = 128. | |||
Отметим, что хотя путь являются ОЦФ, его отдельное рассмотрение полезно как для сравнительного анализа, так и для выделения самого простого алгоритма построения индекса СС.
Корректность работы алгоритмов подтверждена результатами вычислительных экспериментов на различных семействах ориентированных орграфов.
Были исследованы все орграфы до 6 вершин включительно (1 540 421), и несколько более узких классов (например, 20 278 544 бесконтурных и 4 664 216 планарных бесконтурных орграфов до 8 вершин) и несколько представительных семейств с числом вершин до 1000 (более 10 000 орграфов). В качестве базисов для исследования были выбраны базисы связанных путей, полупутей, контуров, полуконтуров и ОЦФ всех длин.
Проведена классификация исследованных классов и семейств орграфов с целью разбиения множеств орграфов с одинаковым числом вершин на классы эквивалентности, на основе значения индексов СС в различных базисах. На Рис. 1. и Рис. 2. приведены примеры графиков чувствительности (отношения числа классов к числу орграфов) для индексов СС орграфов и планарных орграфов в базисах путей, полупутей, контуров, полуконтуров, ОЦФ. Наиболее точную классификацию удалось получить, используя значение индексов СС в базисе ОЦФ, при длине элементов базиса равной числу вершин в орграфе.
Рис. 2 График чувствительности различения индексов сложности для планарных орграфов на 7 вершинах