Система графов

Системой графов является такая совокупность или множество графов, где между элементами зафиксировано соотношение. Графы систематизируются исходя из характеристик, чаще всего, таких как планарность, регулярность, транзитивность и т.д. Большая работа была проделана в области перечисления графов в соответствии с числом вершин и ребер ^[1]. Тем не менее, эти случаи не представляют собой системами, так как там не фиксировано соотношение между элементами (т. е. между графами). Эти соотношения были найдены в последующих исследованиях ^[2].

Атрибутика системы

Система графов с |V| вершинами раскладывается по числам ребер на m подсистем. Их количество m соответствует количеству рёбер полного графа плюс один, что означает наличие пустого графа (т. е. графа с 0 ребер).

Каждый граф $G$ имеет свои наибольшие подграфы $G^{sub}$, полученные удалением ребра $G^{sub} = G\setminus e_{i,j}$ и свои наименьшие надграфы $G^{sup} = G\cup e_{i,j}$, полученные добавлением ребра. Число наибольших подграфов равно числу ребер графа и число наименьших надграфов равно числу «не-ребер» графа. Полученные графы называется смежными графами $G^{adj}$. Так, в системе графов с |V| вершинами каждая подсистема связана со своей нижней и верхней смежной подсистемой.

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

Таким образом, каждой орбите пары вершин соответствует одна смежная структура. Эти соответствя представляют собой соотношения $F$ или морфизмы $F = G\rightarrow G^{adj}$ между структурами (т. е. между графами представляющих классы изоморфизма). Устанавливание морфизмов $F$ между структурами (графами) превращает совокупность графов в систему графов $\mathfrak {G} = (G, F)$ с |V| вершинами.

Общие свойства системы графов

Первая половина решетки системы графов с шестью вершин

• Система графов $\mathfrak {G}$ представима в виде обычного графа (точнее – решетки)
• Если число подсистем m чётное число (например, при |V| = 6 и |V| = 7), тогда решетка билатерально симметрична по отношении оси, которая делит систему пополам и разделяет графы $G$ от их дополнений $\overline G$.
• Если число подсистем m нечётное число (например, при |V|= 4, |V|= 5, |V|= 8, |V|= 9,), то в этом случае, разделяющей осью является подсистема, в которой находится графы $G$ и их дополнения $\overline G$, а также самодополняющиеся структуры.
• Морфизм $F$ является обратимым, каждая смежная структура $G^{adj}$ графа имеет «обратную орбиту», к которой приложенный «обратный морфизм» $F^{op}$ восстанавливает исходный граф $F^{op}= G^{adj}\rightarrow G$.
• Система $\mathfrak {G}$ непосредственно связана с проблемой восстановлений.

Пусть в каждой системе графов с |V| вершин число графов равно p, в том числе связных p*, число подсистем m, число морфизмов q и число орбит q*.

Системы графов по числам вершин |V|:

• 3-вершинные: p = 4, p* = 2, m = 4, q = 3, q* = 6.
• 4-вершинные: p = 11, p* = 6, m = 7, q = 14, q* = 28.
• 5-вершинные: p = 34, p* = 21, m = 11, q = 72, q* = 144.
• 6-вершинные: p = 156, p* = 112, m = 16, q = 572, q* = 1144.
• 7-вершинные: p = 1044, p* = 853, m = 22, q = ?

Число графов p, когда: |V| = 8 – 12344, когда |V| = 9 – 276668, когда |V| = 10 – 12005168, когда |V|=11 – 1018997864 и т. д. Последние не образуют системы, потому что соотношения ещё не найдено.

Вероятностные свойства

• Случайность в системе $\mathfrak {G}$ проявляется в виде выбора смежных структур. Вероятность связана с внутренней системной разнообразностью структуры, т. е. с орбитами.
• Отношение $PF_{n}=\left(\frac {m_{n}} {card}\right)$, где n индекс бинарной орбиты, $m_{n}$ её мощность и card число соответственных пар вершин структуры, определяет вероятность морфизма от структуры $G$ к смежной структуры $F_{n}=G\rightarrow G_{n}^{adj}$.
• Наряду с вероятности морфизма, в системе определяется и вероятность перехода $P_{i,j}$ от исходной структуры $G_{i}$ к не-смежной структуры $G_{j}$.
• Вероятности переходов $P_{i,j}$ в системе образуют стационарную цепь Маркова.
• Вероятность существования структуры $PS$ в системе $\mathfrak {G}$ характеризует её наличие среди других структур подсистемы. Эта выражается формулой: $PS=\sum_{n=1}^N PS_{n}^{sup}\times PF_{n}^{sub}$, где n индекс бинарной орбиты данной структуры (графа), $PS_{n}^{sup}$ вероятность существования смежной надструктуры, и $PF_{n}^{sub}$ вероятность её морфизма.
• Сумма вероятностей существовании структур подсистемы равно единице, $PS_{m}=\sum PS_{i}=1$.
• Вероятности существовании структуры и её дополнений равны, $PS(G)= PS(\overline G)$.
• Вероятности существования $PS$ являются рациональными числами, где их наименьшие общие кратные непосредственно связано со степениью |V| системы.
• Распределение $PS$ в подсистеме обладает правосторонней симметрией и приближается к логарифмическому нормальному распределению

Об алгебраических свойствах

Морфизмы в системе $\mathfrak {G}$ играют значительную роль. Так, некоторые фрагменты или аспекты системы могут быть характеризованы определенными алгебраическими структурами. Легко доказуемым являются следующие утверждение:

• Класса морфизмов F образует в смысле композиции F&F аддитивную группу $A$.
• Класса структур GS системы совместно с классом морфизмов F образует категорию $C$.

О возможном использовании

Существуют реальные системы, чью функционирование возможным представить в виде последовательного изменения её структуры во времени. Если структуры системы $\mathfrak {G}$ рассматривать как состояния $S_{t}$ реальной системы в момент времени $t$, то сукцессия $SF = S_{t=1}\rightarrow S_{t=2}\rightarrow S_{t=3}\rightarrow$ представляет собой динамическое или эволюционное явление, порожденное морфизмами $F$, как результат внутреннего влиания. Таким способом построена одна элегантная, но абстрактная модель онтогенеза.

Такой подход использован при исследовании ценогенеза, эволюции природных сообществ, где состояния исследуемого процесса было представлено в виде графов ^[4].

Резюме

Официально признанными являются лишь совокупности |V|-вершинных графов, а не системы. Первая совокупность диаграмм графов до шести вершин была представлена в 1969 году известным математиком Фрэнком Харари. В 2004 году был издан объемный «Атлас графов», который содержит диаграммы и параметры уже до семи вершинных графов ^[5]. Тем не менее, эта книга отличается по своим масштабам (более 10000 графов), а также по классификации и параметрам графов. Такие системы графов можно формировать только алгоритмическим путем, точнее, путём семиотического моделирования. Мало вероятно, что кто-то пытался выполнить эту работу на основе комбинаторики или алгебры, так как там отсутствуют атрибуты установления морфизмов $F = G\rightarrow G^{adj}$.

Ссылки

1. ↑ Harary, F., Palmer, E. M., 1973. Graph Enumeration. Academic Press.
2. ↑ Tevet, J. T., 1990. Interpretation on some Graph Theoretical Problems. Estonian Academy of Sciences.
3. ↑ Harary, F., 1972. Graph Theory. Addison-Wesley, N.Y.
4. ↑ Martin, J., Tevet, J. T. 1988. On the interrelations between structure, dynamics and evolution of ephilitic lichen synusiae. – Proc. Estonian Acad. Sci., 37 (1988) N 1, 56-66
5. ↑ Read, R. C., Wilson, R. J. 2004. An Atlas of Graphs. Clarendon Press, Oxford.