Iterative Equitable Partition of Graph As a Model of Constant Structure Discrete Time Closed Semantic System

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

Ключевые слова

замкнутая семантическая система; граф; изоморфизм.

Литература

1. Bloom, P. How Children Learn the Meanings of Words / P. Bloom. - Cambridge: MIT Press, 2002.
2. Papadimitriou, C.H. Computational Complexity / C.H. Papadimitriou. - London: Pearson, 1993.
3. Godsil, C.D. Algebraic Combinatorics / C.D. Godsil. - London: Chapman and Hall, 1993.
4. Unger, S.H. GIT - a Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism / S.H. Unger // Communications of the ACM. - 1964. - V. 7, № 1. - P. 26-34.
5. Вейсфейлер, Б.Ю. Сведение графа к канонической форме и алгебра, возникающая при этом сведении / Б.Ю. Вейсфейлер, А.А. Леман // Научно-техническая информация. - 1968. - Т. 2, № 9. - С. 12-16.
6. Арлазаров, В.Л. Алгоритм приведения конечных неориентированных графов к каноническому виду / В.Л. Арлазаров, И.И. Зуев, А.В. Усков, И.А. Фараджев // Журнал вычислительной математики и математической физики. - 1974. - Т. 14, № 3. - С. 195-201.
7. McKay, B.D. Practical Graph Isomorphism / B.D. McKay, A. Piperno // Journal of Symbolic Computation. - 2014. - № 60. - P. 94-112.
8. Syvanen, M. Horizontal Gene Transfer: Evidence and Possible Consequences / M. Syvanen // Annual Review of Genetics. - 1994. - V. 28, № 1. - P. 237-261.