О систематизации безреберных и объединенных графов на основе разбиений

О систематизации безреберных

и объединенных графов на основе разбиений

Аннотация: Кратко изложен способ составления периодической системы простых графов на основе сходства разбиений. В соответствии с этой методикой разработаны периодические системы безреберных и объединенных графов. Рассмотрена взаимосвязь периодических систем реберных, безреберных и объединенных графов между собой и с другими разновидностями графов. Осуществлено построение общей периодической системы графов. Показан эвристический потенциал предложенной систематизации.

1. Введение

В работе [1] приведена систематизация простых графов на основе разбиений числа. Однако в ней не изложена систематизация безреберных и объединенных графов. В данной статье завершается систематизация простых графов и рассматривается связь их с другими разновидностями графов.

Под безреберным графом здесь понимается такой несвязный граф, который состоит из компонентов в виде вершин, обладающих нулевой валентностью. Такие вершины еще называются пустыми, голыми, изолированными. Для графов, синтезированных только из вершин, обладающих валентностью отличной от нуля здесь вводится общее название – реберные. Существование безреберных и реберных графов предполагает возможность построения еще таких несвязных графов, составляющими которых являются как безреберные, так и реберные компоненты. Назовем такие графы объединенными.

Здесь графы рассматриваются с позиции практического применения их для построения структурных схем каких-то конкретных систем. Поэтому под простым графом понимается такая топологическая фигура, составляющими которой являются точки, или точки и соединяющие их линии. Точки называются вершинами графа и наделены общим свойством объектности, а линии называются ребрами графа и наделены общим свойством предикатности. Наличие этих свойств и отличает граф от топологической фигуры. С другой стороны, граф рассматривается как предельно абстрагированная структурная схема, составляющие которой еще не потеряли общих свойств объектности и предикатности. Эти свойства сохранены для того, чтобы при переходе от графа к структурной схеме исследуемой системы именно вершина графа, обозначенная точкой (окружностью, квадратом), получила название конкретного объекта, а ребро графа, обозначенное линией, – конкретного отношения между объектами.

2. Способ систематизации графов на основе разбиений

Систематизация графов осуществляется путем установления соответствия между разбиениями и графами и проведения систематизации разбиений, которая, в свою очередь, служит основой для систематизации графов.

Под разбиением понимается представление целого положительного числа S в виде суммы целых положительных чисел:

,

здесь S – характеристика разбиения; – часть разбиения.

Разбиение можно записать еще в краткой форме, т. е. без знаков сложения и без повторения одинаковых по величине частей разбиения. Их количество выражается числом, поставленным при соответствующей части разбиения вверху в виде индекса. Тогда все разбиения можно представить в виде общей формулы, состоящей из чисел натурального ряда, написанных в обратном порядке с соответствующими индексами.

,

здесь можно не писать части разбиения, имеющие нулевой индекс. Не обязательно писать и индекс равный единице.

О соответствии между разбиениями и графами говорится в работе [2], где приводится формула , в которой – число ребер графа; – степень i-й вершины графа. Здесь сумма степеней вершин графа представлена как разбиение числа, равного по величине 2q. Удвоенное число ребер равно числу половинок этих ребер. Если S – характеристика разбиения и , то . Так характеристике разбиения приводится в соответствие количество полуребер графа, а полуребро становится единицей количества его составных частей. Назовем эти части элементами графа и наделим понятие "элемент" свойствами, необходимыми для построения диаграммы графа. Под элементом здесь понимается отрезок линии, один конец которого обладает свойством валентности и способен соединиться с соответствующим концом второго элемента, образуя цельное ребро. Второй конец отрезка обладает свойством инцидентности к вершине графа. Этот конец отрезка обозначим на диаграмме жирной точкой. Если инцидентные концы нескольких элементов объединить в одно целое, то полученная фигура будет иметь вид точки, из которой пучком расходятся отрезки линий. Назовем эту фигуру звеном графа. Здесь инцидентные концы элементов образуют вершину графа. Само звено приводится в соответствие части разбиения, а число отрезков линий приводится в соответствие числу единиц у части разбиения. Число частей разбиения равно числу вершин графа, а сами части разбиения соответствуют комплекту звеньев. Разбиение становится математической моделью комплекта звеньев, из которого в одном случае синтезируется один граф, а в другом – несколько изомерных графов. Под изомерными графами понимаются такие различные по строению графы, которые синтезированы из одного и того же комплекта звеньев.

Теперь представим множество характеристик разбиения, как ряд четных чисел, например, и осуществим для этих характеристик полное перечисление разбиений, расположив разбиения каждой характеристики в своей строке в порядке последовательного возрастания их частей (см. табл. 1).

При сравнении разбиений разных характеристик обнаруживаются следующие закономерности:

1) Между отдельными разбиениями, находящимися в различных строках, наблюдается сходство их строения, заключающееся в совпадении величин частей разбиения и величин всех индексов, кроме индекса в одном случае при части разбиения 1, а в другом – при части разбиения 2. Далее будет показана роль этих частей разбиения в формировании периодической системы реберных графов. Примером сходных разбиений будут следующие множества, элементы которых взяты из каждой строки табл. 1: {12, 14, 16, 18, 110, 112}, {2012, 2112, 2212, 2312, 2412, 2512}, {21, 22, 23, 24, 25, 26} и т. д.

2) Во всех строках сходные разбиения располагаются одно за другим в одинаковой последовательности. Если, например, во второй строке существует такая последовательность: 14, 212, 22, то в третьей последовательность сходных разбиений сохраняется: 16, 2212, 23, в четвертой строке – тоже: 18, 2312, 24 и т. д.

3) Сходству строения разбиений соответствует сходство структуры графов, синтезированных на их основе. Например, сходным разбиениям 23, 24, 25 и т. д. соответствуют графы одноцикловой структуры с разным числом двухвалентных звеньев.

Эти закономерности послужили базой для создания периодической системы графов. Более подробно этот материал изложен в работе [1].

Под сходными разбиениями понимаются такие, которые получены путем последовательного добавления к исходному разбиению одних и тех же частей разбиения или(и) последовательного прибавления одних и тех же целых чисел к определенным частям разбиения.

При перечислении разбиений каждой характеристики в разных строках получается разное количество разбиений. Для того, что бы расположить сходные разбиения друг над другом в своих колонках, их необходимо сдвинуть вдоль строк вправо, обеспечивая совпадение вышестоящих сходных разбиений с разбиениями нижней строки. Получаем, таким образом, табл. 1, являющуюся периодической системой разбиений и, одновременно, периодической системой реберных графов. Здесь у сходных графов, расположенных в колонках, изменяется индекс при части разбиения 2. По этой причине в колонках расположились сходные графы из числа несвязных графов, обыкновенных графов и псевдографов. Если бы было принято за основу сходство по признаку изменения индекса при части разбиения 1, то в колонках расположились бы сходные несвязные графы, различающиеся только количеством компонент – 12.

3. Периодическая система реберных графов

Фрагмент периодической системы реберных графов приводится в табл. 1, которая укорочена справа так, что в нижней наиболее длинной строке указаны первые 18 разбиений из 77. Соответственно, сократилось число разбиений и в остальных строках, кроме первой. Утрачены разбиения, которым соответствуют, в основном, псевдографы. Это объясняется тем, что в каждой строке слева направо число вершин графов периодически убывает. Слева при том же числе ребер наблюдается наибольшее число вершин, что ведет к образованию только несвязных графов. Справа при том же числе ребер наблюдается наименьшее число вершин, что ведет к образованию только псевдографов. Левее середины строки в числе изомеров образуются также и обыкновенные графы.

Все колонки табл. 1 разделились в начале на группы, где номер группы N соответствует наибольшей части разбиения. Группы, в свою очередь, разделились на подгруппы так, что колонки каждой подгруппы содержат в себе разбиения с нарастающим количеством частей разбиения 3, т. е. 30, 31, 32, 33 и т. д. Ориентация на часть разбиения 3 объясняется тем, что увеличение числа частей разбиения 1 и 2 не оказывает существенного влияния на строение синтезируемых графов. В первом случае увеличивается число компонентов 12, а во втором – число двухэлементных звеньев в циклах. И только, начиная с части разбиения 3, увеличение числа частей разбиения вызывает четко различимое изменение структуры синтезируемых графов за счет увеличения числа циклов или(и) числа висячих вершин.

Графы-изомеры, соответствующие каждому разбиению, разделяются на классы несвязных графов, псевдографов и обыкновенных графов. Последние, в свою очередь, разделяются по колонкам на когорты деревьев, комбинированных и циклических графов.

В каждой из заполненных клеток табл. 1 в верхней ее части расположено разбиение, в середине – диаграмма одного из наиболее плотных графов-изомеров, а в нижней части, через точки, слева – количество обыкновенных графов-изомеров, посередине – количество псевдографов-изомеров и справа – количество несвязных графов-изомеров.

Под обыкновенным графом здесь понимается такой связный граф, у которого нет кратных ребер, т. е. связь между двумя вершинами может осуществляться только одним ребром, и у которого нет петель.

Под псевдографом здесь понимается такой связный граф, у которого имеются или кратные ребра, или петли, или то и другое вместе.

Под комбинированным графом здесь понимается такой обыкновенный граф, в структуре которого одновременно наблюдаются признаки и циклического графа, и графа-дерева, т. е. имеются и циклы, и висячие вершины.

4. Система безреберных графов

При рассмотрении безреберных графов возникает необходимость несколько расширить привычное представление о разбиении числа. Поскольку валентность вершины безреберного графа равна нулю, то соответствующая ей часть разбиения будет также выражена нулем. Поэтому в общую формулу разбиения водится новая часть разбиения – ноль, и эта формула принимает следующий вид:

,

где – число частей разбиения, соответствующих безреберным компонентам.

Однокомпонентный безреберный граф состоит из одной пустой вершины, обозначаемой на диаграмме точкой, а в разбиении – нулем с индексом . Для безреберных графов формула разбиений будет выглядеть

.

Изображение звена однокомпонентного безреберного графа совпадает с изображением самогó однокомпонентного безреберного графа. Многокомпонентные безреберные графы изображаются на диаграмме в виде соответствующего числа точек. Система безреберных графов, построенная на основе разбиений, представляет собой простое их перечисление и приводится в табл. 2.

Далее будет показано, что при установлении связи между системой безреберных графов и системой реберных графов, построенной в координатах S, N, система безреберных графов займет по отношению к этим координатам положение третьей координаты – аппликаты F0.

На практике структурные схемы, содержащие только безреберные графы, выражают состав таких объектов, взаимодействие которых в данном случае не рассматривается. Это, например, размещение звезд на карте неба, размещение строений на плане населенного пункта и т. п.

5. Периодическая система объединенных графов

Под объединенными графами здесь понимаются такие несвязные графы, которые содержат в себе как безреберные, так и реберные компоненты. В табл. 3 приводится периодическая система объединенных графов, полученная путем добавления к реберным графам табл. 1 одного безреберного компонента. Если добавлять к реберным графам по очереди различное число безреберных компонентов, то будут получаться таблицы объединенных графов со всеми вариантами безреберных компонентов и осуществляться таким образом полное перечисление объединенных графов. В табл. 3 клетка с исходным безреберным графом расположена в верхней строке, соответствующей характеристике разбиения , и в левой колонке, соответствующей группе разбиений . Вниз и вправо от этой клетки располагается бесконечное число объединенных графов с одним безреберным компонентом. Следующая периодическая система объединенных графов будет с двумя безреберными компонентами. Затем с тремя, четырьмя и т. д.

На практике объединенные графы могут служить основой для построения таких структурных схем, у которых существует взаимодействие между одними объектами и отсутствует между другими. Например, в атомной физике, если в структурной схеме электронного строения атома гелия, состоящего из двухвалентного ядра и двух электронов, учесть еще наличие двух нейтронов, то соответствующее ей разбиение будет иметь вид:

,

а соответствующая ей диаграмма объединенного графа будет выглядеть как показано на рис. 1, где реберный компонент граф-дерево объединен с двумя безреберными компонентами.

6. Общая периодическая система графов

Систематизацию и полное перечисление всех реберных, безреберных и объединенных графов можно представить как последовательное расположение таблиц, в которых периодическая система реберных графов (см. табл. 1) будет стоять первой и считаться таблицей с числом безреберных компонентов равных нулю – . За ней следуют таблицы объединенных графов с одним (см. табл. 3) безреберным компонентом – , с двумя компонентами – , с тремя – и так до бесконечности. Образовалась периодическая система простых графов. В полученной системе клетки, расположенные в верхнем левом углу каждой таблицы, содержат безреберные графы, образующие между собой последовательность, аналогичную той, которая представлена в системе безреберных графов (см. табл. 2). Если в общей периодической системе по оси абсцисс отложены номера групп N, а по оси ординат – величины характеристики разбиения S, то по оси аппликат откладывается число безреберных компонентов – (см. рис. 2).

В отличие от простых графов известны еще графы, составные части которых наделены дополнительными неструктурными свойствами, например, ориентированности, раскрашенности, взвешенности, помеченности и т. п. Примем для таких графов общее название – нагруженные. На рис. 2 они располагаются по очереди справа от периодической системы простых графов. Кроме перечисленных наименований нагруженных графов могут создаваться и другие нагруженные графы, системы которых на рис. 2 будут пристраиваться далее с правой стороны. Рассматриваемые совместно простые и нагруженные графы образуют общую периодическую систему графов с полным их перечислением.

Что касается разделения графов на конечные и бесконечные, то в периодической системе графов имеется возможность увеличения характеристики разбиения до бесконечности. Следовательно все эти графы находятся в составе этой системы.

Присваиваемые графам дополнительные понятия, такие как двудольный, хордальный, полный, регулярный и т. п., отражают структурные особенности простых графов и, поэтому, все названные и все подобные им разновидности графов входят в состав периодической системы простых графов.

7. Заключение

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

Из настоящей работы следует, что разбиения числа являются весьма продуктивной математической моделью, позволяющей по их строению определять наиболее общие свойства соответствующих им графов. Наличие или отсутствие в составе разбиения трех крайних справа частей разбиения совместно с наличием или отсутствием остальных частей разбиения однозначно фиксирует конкретные свойства графов. Это видно из следующих примеров.

*  Если имеются только части разбиения ноль, т. е. , то таким разбиениям соответствует только безреберные графы.

*  если имеются нули и другие части разбиения, т. е. , то этим разбиениям соответствуют только объединенные графы.

*  Если имеются только единицы, т. е. , то этим разбиениям соответствуют только несвязные графы, состоящие из компонент .

*  Если отсутствуют нули, но имеются единицы и остальные части разбиения, т. е. , то таким разбиениям соответствуют только реберные графы с висячими вершинами.

*  Если отсутствуют нули и единицы, т. е. , то этим разбиениям соответствуют только реберные циклические графы.

*  Если имеются только двойки, т. е. , то таким разбиениям соответствуют только одноцикловые графы и т. д.

Разбиения, содержащие часть разбиения ноль, обладают максимальной общностью, охватывая наибольшее число графов. По мере исключения части разбиения ноль, а затем и части разбиения один общность разбиений последовательно уменьшается.

Все эти и другие закономерности, выявленные в процессе систематизации графов, создают условия для проведения классификации графов и, как следствие, для некоторого упорядочения их терминологии.

Предложенный метод систематизации графов позволяет осуществлять упорядочение структурных схем объектов природы и познания, что способствует дальнейшему развитию общей теории систем.

Список литературы

1. О систематизации графов на основе разбиений // Методы и средства работы с документами: Сборник трудов ИСА РАН / Под ред. , . М.: Эдиториал УРСС, 2000. С. 340-372.

2. Теория графов. М.: Мир, 19с.

Таблица 2

Система безреберных графов

Рис. 1

Простые графы

Нагруженные ориентированные графы

Нагруженные раскрашенные графы

Нагруженные взвешенные графы

Рис. 2

Таблица 1

Периодическая система реберных графов (фрагмент)

Таблица 3

Периодическая система безреберных и объединенных графов (фрагмент)