14-06-2023
Системой графов является такая совокупность или множество графов, где между элементами зафиксировано соотношение. Графы систематизируются исходя из характеристик, чаще всего, таких как планарность, регулярность, транзитивность и т.д. Большая работа была проделана в области перечисления графов в соответствии с числом вершин и ребер [1]. Тем не менее, эти случаи не представляют собой системами, так как там не фиксировано соотношение между элементами (т. е. между графами). Эти соотношения были найдены в последующих исследованиях [2].
Содержание |
Система графов с |V| вершинами раскладывается по числам ребер на m подсистем. Их количество m соответствует количеству рёбер полного графа плюс один, что означает наличие пустого графа (т. е. графа с 0 ребер).
Каждый граф имеет свои наибольшие подграфы , полученные удалением ребра и свои наименьшие надграфы , полученные добавлением ребра. Число наибольших подграфов равно числу ребер графа и число наименьших надграфов равно числу «не-ребер» графа. Полученные графы называется смежными графами . Так, в системе графов с |V| вершинами каждая подсистема связана со своей нижней и верхней смежной подсистемой.
Множество вершин графа распределяется на орбиты (т. е. на определенные классы эквивалентности или транзитивности) и, в их рамках, в свою очередь пары вершин разбиваются на свои орбиты [3]. В рамках каждой орбиты пары вершин, полученные смежные графы являются изоморфными и образовывает класс изоморфизма. Однако, каждая подсистема системы графов состоит из неизоморфных графов, т. е. из графов которые представляют разные классы изоморфизма, другими словами, из структур.
Таким образом, каждой орбите пары вершин соответствует одна смежная структура. Эти соответствя представляют собой соотношения или морфизмы между структурами (т. е. между графами представляющих классы изоморфизма). Устанавливание морфизмов между структурами (графами) превращает совокупность графов в систему графов с |V| вершинами.
Пусть в каждой системе графов с |V| вершин число графов равно p, в том числе связных p*, число подсистем m, число морфизмов q и число орбит q*.
Системы графов по числам вершин |V|:
Число графов p, когда: |V| = 8 – 12344, когда |V| = 9 – 276668, когда |V| = 10 – 12005168, когда |V|=11 – 1018997864 и т. д. Последние не образуют системы, потому что соотношения ещё не найдено.
Морфизмы в системе играют значительную роль. Так, некоторые фрагменты или аспекты системы могут быть характеризованы определенными алгебраическими структурами. Легко доказуемым являются следующие утверждение:
Существуют реальные системы, чью функционирование возможным представить в виде последовательного изменения её структуры во времени. Если структуры системы рассматривать как состояния реальной системы в момент времени , то сукцессия представляет собой динамическое или эволюционное явление, порожденное морфизмами , как результат внутреннего влиания. Таким способом построена одна элегантная, но абстрактная модель онтогенеза.
Такой подход использован при исследовании ценогенеза, эволюции природных сообществ, где состояния исследуемого процесса было представлено в виде графов [4].
Официально признанными являются лишь совокупности |V|-вершинных графов, а не системы. Первая совокупность диаграмм графов до шести вершин была представлена в 1969 году известным математиком Фрэнком Харари. В 2004 году был издан объемный «Атлас графов», который содержит диаграммы и параметры уже до семи вершинных графов [5]. Тем не менее, эта книга отличается по своим масштабам (более 10000 графов), а также по классификации и параметрам графов. Такие системы графов можно формировать только алгоритмическим путем, точнее, путём семиотического моделирования. Мало вероятно, что кто-то пытался выполнить эту работу на основе комбинаторики или алгебры, так как там отсутствуют атрибуты установления морфизмов .
Система графов.