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

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

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

Проблема систематизации графов в наиболее общем виде рассматривается в книге Ф. Харари [1], где приводится пример полного перечисления графов, генерированных в пределах числа вершин 1 < р < 6 и числа ребер 0 < q < 15 и сгруппированных по этим параметрам как по признакам сходства. Однако, при такой группировке не наблюдается какой-либо взаимосвязи между величинами указанных параметров и особенностями строения графов. Известна также работа [2], где представлен метод определения количественной меры сходства между отдельными сравниваемыми графами на основе структурных спектров. Но в этой работе не преследуется цель получения общей картины взаимосвязи между существующими разновидностями графов. Очевидно, что для систематизации графов в общем виде необходимы другие, более существенные признаки сходства, по которым известные структурные разновидности графов такие как связные, несвязные, деревья, псевдографы, полные графы и т. д., выступающие в настоящее время обособленно и существующие как бы сами по себе, были бы объединены в общую систему.

Целью данной работы является поиск внутренней взаимосвязи между традиционно выделенными разновидностями графов и установление между ними иерархии, что должно способствовать более полному раскрытию тех структурных свойств графов, которые столь необходимы для научного описания широкого круга явлений материального мира и мира идей. В данном случае рассматриваются конечные неориентированные связные и несвязные графы, в том числе графы с петлями и кратными ребрами, за исключением безреберных графов. Исследуемые графы получены методом полного их перечисления на основе полного перечисления разбиений. О соответствии между графами и разбиениями указывается в ряде работ [1]. Рассматривая разбиение как комбинаторный аналог графа, необходимо помнить, что в одном случае конкретному разбиению соответствует один конкретный граф, а в другом — вполне определенное количество изомерных графов. С учетом этого можно полагать, что полному перечислению разбиений, осуществленному в установленных пределах величины характеристики разбиения S, будет соответствовать полное перечисление графов. В таблице 1 приводится полное перечисление разбиений четных чисел для S = 2 ... 12, а в таблице 2 приведено полное перечисление соответствующих им графов. (Из-за большого объема таблицы 2 редакция сочла возможным привести здесь только ее фрагменты. Полностью эту таблицу можно получить у автора. ‑ прим. ред.). Одновременно эти графы разделены по типам на обыкновенные, псевдографы и несвязные графы.

Таблица 2 (фрагмент 1).

Таблица 2 (фрагмент 2).

Таблица 2 (фрагмент 3).

Таблица 2 (фрагмент 4).

Таблица 2 (фрагмент 5).

Таблица 2 (фрагмент 6).

Таблица 2 (фрагмент 7).

Таблица 2 (фрагмент 8).

Таблица 2 (фрагмент 9).

В таблице 1 перечисленные разбиения располагаются в колонках сверху вниз в порядке последовательного возрастания частей разбиения. Минимальному значению S = 2 соответствуют два исходных разбиения— 12 и 21, из которых у первого — часть разбиения минимальное нечетное число 1, а у второго — минимальное четное число 2. Этим разбиениям в таблице 2 соответствуют два исходных графа, являющихся началом перечисления несметного числа графов с бесконечным разнообразием их строения и бесконечным разнообразием их структурных свойств. Следующему значению S = 4 соответствуют пять разбиений — 14, 212, 22, 31, 4, из которых первое разбиение является сходным с предыдущим первым разбиением, а третье разбиение является сходным с предыдущим вторым разбиением. Сходство между этими разбиениями заключается в равенстве частей разбиений, а различие — в увеличении индексов. Остальные три разбиения имеют новое строение, но среди разбиений соответствующих следующему значению S = 6 у них также найдутся свои сходные разбиения. Так при всех последующих значениях S будут образовываться множества разбиений, в числе которых имеются подмножества разбиений сходных и новых по строению. Здесь проявилось фундаментальное свойство периодического повторения сходных разбиений, являющееся характерным признаком процесса полного перечисления разбиений. Как будет показано далее при периодическом повторении сходных разбиений у соответствующих им графов наблюдается периодическое повторение структурных свойств, а это, в свою очередь, соответствует наблюдаемым в природе процессам периодического прогрессивного развития структуры реальных объектов.

Переходя от разбиений к графам отметим, что при традиционном множественном подходе к генерированию графов их диаграммы строятся из точек и отрезков линий, что определяется соответствием их множеству элементов и подмножеству пар этих элементов. При представлении графа средствами комбинаторики части разбиения нельзя строго привести в соответствие понятиям «точка» и «отрезок линии». В разбиении нет чисел, соответствующих понятиям «вершина» и «ребро». Здесь оперируют выражением «удвоенное число ребер», т. е. частями ребер, полученными от разделения каждого ребра на две части. Поэтому мы вынуждены ввести понятие «часть ребра», делая этим заключительный шаг в дроблении графа на наименьшие составляющие. Если понятие «часть ребра» привести в соответствие комбинаторному понятию «единица в составе положительного целого числа», то оказывается, что оно играет в разбиении главенствующую роль. Это обязывает нас дать ему новое самостоятельное название — «элемент графа» или просто — «элемент». Один конец элемента должен обладать свойством инцидентности, т. е. иметь отношение к вершине графа. Обозначим его на схеме жирной точкой. А второй конец элемента должен обладать свойством валентности, т. е. способностью соединяться со вторым элементом, образуя ребро. Каждой части разбиения соответствует такое же число элементов, образующих структуру, которую мы назовем звеном. Схематически звено изображается пучком, составленным из элементов, инцидентные концы которых объединены в одной точке, образуя то, что соответствует понятию «вершина». А валентные концы элементов свободны и готовы к соединению с другими валентными концами и образованию ребер. Так часть разбиения приводится в соответствие звену, а индекс при части разбиения — числу звеньев одинаковой валентности и, как следствие, числу вершин одинаковой степени. В комбинаторном представлении графа исходными понятиями становятся понятия «элемент» и «звено», а понятия «вершина» и «ребро» становятся производными. В четвертой колонке таблицы 2 представлены схематические изображения комплектов звеньев, соответствующих указанным разбиениям. В пятой колонке приводится число изомерных обыкновенных графов - U, генерированных из данного комплекта звеньев. В шестой колонке указано число псевдографов — Р и в седьмой колонке — число несвязных графов — I. Сами графы размещены здесь же в строчку. Имеющая место у псевдографов кратность ребер и петель на диаграммах обозначена числами, стоящими, соответственно, возле ребра и петли. Под диаграммами графов расположены их порядковые номера. В таблице 2 каждому разбиению соответствует как минимум один граф. Если рассматривать строение псевдографов какого-то разбиения, не беря во внимание наличие петель и кратность ребер, то оказывается, что все такие структуры уже встречались ранее среди обыкновенных графов. И если рассматривать строение компонентов несвязных графов какого-то разбиения, то оказывается, что все такие структуры уже встречались ранее среди псевдографов и обыкновенных графов. Это определяет приоритетное положение обыкновенных графов над псевдографами и последних над несвязными графами.

Из анализа строения графов таблицы 2 следует, что периодически повторяющимся сходным разбиениям соответствуют графы с периодически повторяющимся сходным строением. Так при сходных разбиениях 2012, 2112, 2212, 2312 среди обыкновенных графов повторяются графы класса «цепь», при сходных разбиениях 12= 1111, 2112, 3113, 4114 среди обыкновенных графов повторяются графы класса «веер», а при сходных разбиениях 23, 24, 25, 26 среди обыкновенных графов повторяются графы класса «кольцо». Также периодично повторяется строение и остальных графов типа «обыкновенные». Этой закономерности следуют и все представители изомерных графов, относящихся к сходным разбиениям. Например, при разбиениях 3231 и 3241 обыкновенный граф № 1 первого разбиения сходен с обыкновенным графом № 2 второго разбиения. Соответственно изомерный граф № 2 сходен с изомерным графом № 3. Тоже у псевдографов № 1 первого разбиения и № 1 второго. Такое же сходство наблюдается и между представителями изомерных несвязных графов. В таблице 1 в каждом множестве разбиений, соответствующем определенному значению S, имеется подмножество разбиений, у которых изменяющийся индекс принадлежит минимальной нечетной части разбиения — 1 и подмножество разбиений, у которого изменяющийся индекс принадлежит минимальной четной части разбиения — 2. При каждом новом значении S такие разбиения располагаются сверху вниз в одинаковой последовательности, хотя между ними и появляются новые разбиения. Например, существующая при S = 2 последовательность разбиений 12 и 21 при S = 4 повторяется как 14 и 22 при S = 6 как 16 и 23 и т. д. И это сохранение последовательности наблюдается у всех сходных разбиений.

На основе выявленного сохранения последовательности построена периодическая система графов, представленная в таблице 3.

Здесь в первой колонке откладываются значения характеристики разбиения S, а в строках вписываются все разбиения каждого значения характеристики S в той последовательности, в которой они расположены в таблице 1. Вначале заполняется нижняя строка для S = 12, так как этой характеристике соответствует у нас наибольшее число разбиений. Затем заполняется следующая верхняя строка для 5 = 10. При этом сходные разбиения, отличающиеся только величиной индекса при четной части разбиения 2, записываются в свои колонки. Так наращивается таблица до S = 2. Здесь все колонки разделены на группы, где номер группы соответствует наибольшей части разбиения. Группы, в свою очередь, разделены на подгруппы так, что колонки каждой подгруппы содержат в себе разбиения с нарастающей последовательностью количества частей разбиения 3, т. е. 30, 31, 32, 33 и т. д. В каждой из заполненных клеток таблицы в верхней ее части расположено разбиение, в середине — диаграмма графа, а в нижней части, через точки, слева — количество обыкновенных графов-изомеров, посередине — количество псевдографов-изомеров и справа — количество несвязных графов-изомеров. Из таблицы 2 следует, что одному конкретному разбиению может соответствовать или один, или два, или три типа графов. Поэтому мы вынуждены клетки таблицы 3 считать трехслойными, как это показано на рис. 1, в котором нижний слой, наиболее обширный и сплошной, содержит в себе несвязные графы. Средний слой имеет форму отдельных островов и содержит в себе псевдографы, и верхний слой имеет форму островов, укороченных спереди и содержит в себе обыкновенные графы, разделенные с помощью колонок на следующие три класса: деревьев — Т, комбинированных — С и контурных — О. В результате клетки, расположенные в центральной части таблицы 3, представляют графы типа «обыкновенные», слева и в промежутках между островами обыкновенных графов открыты клетки с несвязными графами, а вверху и справа преобладают псевдографы. На рис. 1 параметр m — толщина слоя, которая определяет количество изомерных графов данного типа у данного разбиения R0.

Рисунок 1.

Если рассматривать таблицу 3 в горизонтальном направлении по строкам, то с каждым шагом вправо наблюдается рост величины частей разбиения от единицы и до двенадцати. При этом у обыкновенных графов во всех полных подгруппах обнаруживается повторяемость классов графов в такой последовательности: деревья, комбинированные и контурные. В подгруппах, расположенных правее, недостающие типы и классы графов находятся ниже и будут появляться при S > 12. По краям каждой строки расположены примитивные графы — антиподы. Слева — несвязные графы, генерированные из максимального числа звеньев минимальной валентности, а справа расположен связный граф, состоящий из одного звена наивысшей валентности. При рассмотрении строки от краев к середине наблюдается рост плотности графов и в некоторых строках обнаруживаются графы максимальной плотности — полные графы. Например, у разбиений 23 и 34.

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

Рост числа элементов у графов предела не имеет, поэтому таблица 3 может бесконечно развиваться вниз и вправо. При этом будет идти процесс приращения новых групп и подгрупп и образования в средней части таблицы графов более сложного строения. Так, для любого мыслимого графа в таблице 3 существует своя клетка, которую можно легко найти с помощью разбиения этого графа. В связи с тем, что таблица 3 слишком громоздка, мы делим ее на несколько более компактных таблиц. Для этого колонки с однотипными графами выносим в отдельные таблицы, сохраняя при этом тот порядок их расположения, который имеется в таблице 3. Так графы типа «обыкновенные» представлены тремя таблицами — в таблице 4 размещены графы-деревья, в таблице 5 — комбинированные графы, а в таблице 6 — контурные графы. Псевдографы размещены в таблице 7, а несвязные графы — в таблице 8.

В таблицах 3...8 наблюдается ранее отмеченное сходство разбиений, расположенных в колонках. Первым признаком сходства разбиений является равенство величин частей разбиений и их индексов, кроме индекса при части разбиения 2. Вторым признаком сходства разбиений, является постоянство величины прироста индекса при части разбиений 2, наблюдаемое у разбиений, расположенных на строку ниже. Однако установить сходство разбиений возможно и по другим признакам, например, по постоянству прироста величин индексов при остальных частях разбиения и по постоянству прироста величин самих частей разбиения. В этом случае сходные разбиения располагаются не в колонках, а на нисходящих диагоналях, начинающихся из левого верхнего угла таблиц и расходящихся веером вправо вниз. Так осуществляется обобщение всех разбиений и объединение их, вместе с соответствующими им графами, в самостоятельные классы. Ранее, при рассмотрении таблицы 2, были выделены периодически повторяющиеся сходные по структуре графы классов «цепь», «веер» и «кольцо». Рассмотрим подробнее свойства этих и других классов графов.

Графы класса «цепь» относятся к графам-деревьям и расположены в колонке 6 таблицы 4, где длина цепи растет с каждым шагом вниз за счет прибавления по одному двухвалентному звену. Этим графам соответствуют разбиения: 2012, 2112, 2212, 2312 и т. д. Указанные разбиения и сходные с ними по этому признаку последующие разбиения выражаются формулой перечисления разбиений

где S — число элементов графа и характеристика разбиения.

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

Графы класса «веер» также относятся к графам-деревьям и расположены на нисходящей диагонали, идущей по верхним клеткам колонок № 1, 6, 11, 22, 36, 48, относящихся, соответственно, к группам № 1, 2, 3, 4, 5, 6. Здесь при переходе от группы к группе на диаграммах графов увеличивается количество пластин «веера» на единицу за счет роста на единицу первой части разбиения и индекса при второй части. Указанным графам соответствуют разбиения 12 = 1111, 2112, 3113, 4114, 5115, 6116 .Эти разбиения и сходные с ними разбиения последующих номеров групп представлены формулой перечисления разбиений

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

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

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

который будет расположен в таблице на диагонали, параллельной диагонали с графами класса R2.

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

Графы класса «кольцо» относятся к контурным графам и представлены в колонке 7 таблицы 6. С каждым шагом вниз растет размер кольца за счет прибавления к графу по одному двухвалентному звену. Указанным графам соответствуют разбиения 23, 24, 25, 26 и т. д. Эти разбиения и сходные с ними разбиения последующих характеристик выразятся формулой перечисления разбиений

Соответственно во всех остальных колонках таблицы 6 наблюдаются сходные графы, которые относятся к определенным классам и описываются своими формулами перечисления разбиений. Как и в таблице 4 здесь также образуются классы сходных графов, которые располагаются на диагоналях таблицы и на параллельных линиях. Например, графы класса «полные» представлены в колонках 7 и 19 разбиениями 23 и 34. Указанные и сходные с ними разбиения последующих номеров групп выразятся формулой перечисления разбиений

а следующий параллельный класс —

Наконец, графы класса «комбинированные», приведенные в таблице 5, обладают теми же свойствами сходства, что и контурные графы. Каждый граф является сходным по отношению к графам своей колонки и к графам одной из диагоналей, т. е. принадлежит, как минимум, к двум классам. Так, за счет пересечения ряда колонок рядом диагоналей устанавливается генетическое родство между всеми графами одного типа. Изложенные закономерности сходства распространяются и на все изомерные графы. У каждого изомера имеются свои сходные графы. Те же закономерности сходства наблюдаются и у псевдографов, представленных в таблице 7.

Периодическая система несвязных графов представлена в таблице 8. Существование только несвязных графов при разбиениях группы 1 объясняется невозможностью объединить все звенья комплекта в связный граф по причине избытка примитивных звеньев валентности 1, которые могут соединяться между собой только попарно, образуя компоненты 12. Если таблицы связных графов строились по принципу объединения в одну колонку разбиений с изменяемым индексом при части разбиения 2, то таблица несвязных графов строится по принципу объединения в одну колонку разбиений с изменяемым индексом при части разбиения 1. Для этого все строчки таблицы 3 сдвигаем влево до упора и полученные таким образом колонки переносим в таблицу 8. Если рассматривать таблицу 8 в горизонтальном направлении по строчкам слева направо, то у графов наблюдается периодическое сокращение числа звеньев от максимальной величины до двух и периодическое увеличение валентности звеньев от единицы до максимальной величины. Если же рассматривать графы в вертикальном направлении в колонках, то при движении по колонке вверх со строки на строку в графах с каждым шагом убывает по два элемента, что соответствует убыванию одной простейшей компоненты 12. В связи с этим некоторые колонки в верхней части логически заканчиваются связным графом. Наличие такого графа в табл. 8 можно объяснить предельным состоянием несвязных графов, когда процесс убывания количества компонент останавливается на единице. Таким образом проявляется генетическая связь между связными и несвязными графами. В отличие от таблицы 3, исходные наипростейшие графы, соответствующие разбиениям 12 и 21, заняли, наконец-то, свое «законное» место в верхнем левом углу, тогда как в таблице 3 они находятся, соответственно, в шестой и седьмой колонках. В таблице 8 классы несвязных сходных графов образуются и в колонках, и на нисходящих диагоналях. Так, графы, расположенные в колонке 1, определятся формулой перечисления разбиений

в колонке 2

в колонке 3

и т. д.

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

на ниже лежащей параллельной диагонали —

еще ниже

и т. д.

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

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

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

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

где А — атомный номер химического элемента.

В данном случае разбиение 1111 представляет собой электронную структуру атома водорода, 2112 — гелия, 3113 — лития и т. д.

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

• В химии общеизвестный процесс развития гомологического ряда насыщенных углеводородов описывается классом графов

где n — порядковый номер вещества в гомологическом ряду.

Здесь разбиение 4114 представляет собой структуру молекулы метана, 4216 — этана, 4318 — пропана и т. д.

• В механике процесс развития структуры механизма для многоступенчатого преобразования скорости вращательного движения представлен классом графов

где Т — число ступеней преобразования движения. Разбиение 213022 представляет собой структуру одноступенчатого редуктора, 313122 — двухступенчатого, 413222 — трехступенчатого и т. д.

• В ботанике процесс развития строения кроны дерева, например, при дихотодиальном ветвлении имеет класс графов

где g — возраст дерева в годах. Разбиение 3012 определяет структуру дерева в первый год его существования, 3113 — во второй год, 3214 — в третий год и т. д.

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

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

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

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

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

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

1. Теория графов. — М.: Мир, 1973. — 250 с.

2. Кохов количественного определения сходства графов на основе структурных спектров // Вычислительные системы. Приложения теории графов в химии. Выпуск 149, 1993. — С. 51-83.