3.6.3.Синтез графов.

на основе вышеизложенного задача генерации графов сводится к составлению разбиений согласно (3.33) и смежностно-степенных таблиц в соответствии с (3.36) – (3.39).

По своей сущности задача синтеза графов состоит в выборе на множестве вершин V из их декартового произведения V´V (т.е. из полного графа, в котором каждая вершина соединена со всеми остальными вершинами) множества рёбер Â [q пар (v_i,v_j)]. Осуществляют этот выбор в последовательности, не допускающей пропуска синтеза какого-нибудь графа и синтеза изоморфных графов.

Построение графа по разбиению Q осуществляют в таком порядке. Нумеруют вершины в соответствии с неравенствами (3.33). Потом соединяют i–ю вершину, имеющую степень и т.д. Так как ранее vi была соединена i-1 рёбрами с предшествующими, то она оставшимися рёбрами соединяется с вершинами, имеющими номера от Начинают синтезировать граф с i=1, причём для всех i > 1 следят за тем, чтобы текущие степени degvi не превысили заданных разбиением, а кроме того, отбрасываются варианты генерации несвязных и разделимых графов (т.е. содержащих точки сочленения и мосты). Эти условия иногда приводят к нарушению последовательности соединяемых вершин и к изменению выражений, определяющих их номера.

Пример 4. Построим графы по разбиению Q3=(4, 3, 3, 2, 2, 2) из примера 1. нанесём и пронумеруем шесть вершин. соединим вершину v1, имеющей , ребрами с вершинами, у которых номера изменяются от . В результате образуется подграф, изображённый на рис. 3.6. Далее вершина v2 соединяется p2– 1= 2 рёбрами с вершинами 3 и 4 (рис. 3.6, б). У вершины v3 осталось только одно ребро, которое следует соединить с вершиной v6 (рис. 3.6, в), так как вершина v4 уже имеет степень 2, заданную разбиением. присоединение ребра к вершине 5 приведёт к несвязному графу, ибо степени вершин с i £ 5 уже будут соответствовать заданному разбиению, а вершину 6 не подсоединить к этой части графа, не нарушив разбиение. С помощью последнего ребра, соединив вершины v5 и v6 , образуем окончательный граф (рис. 3.6, г). Подчеркнём, одному разбиению могут соответствовать несколько неизоморфных графов.

3.6.3. Методика синтеза графа по смежностно-степенным таблицам .

1. представим CCТ в виде 2q мерного вектора и для сравнения двух синтезированных таблиц одинакового размера

и введём отношение линейного порядка

, (3.43)

которое понимается лексикографически.

Для таблиц T_а - T_м (3.40) первые четыре элемента векторов идентичны, но уже следующие 6 элементов (4,3,2,4,3,2) идентичны только у таблиц T_а – T_г, наконец, так как выделенные значками элементы соответствующих векторов (3,3,2,2,4,3,2,4,3,2,4,4,2,3,2,2,2)>(3,3,2,2,4,3,2,4,3,2,4,4,2,3,,2,2)>(3,3,2,2,4,3,2,4,3 ,2,4,2,4,2,3,3,2) определяют нумерацию графов и таблиц согласно с лексикографическим отношением . Именно так все графы рис.3.5 и их таблицы (3.40) лексикографически упорядочены.

2. Пересоединением вершин графа в рамках заданного разбиения строят CCТ с максимальным вектором (t_ij) . Присваивают ей номер один и называют канонической для данного разбиения. Методика построения этой таблицы аналогична вышеизложенному алгоритму генерации графа по разбиению.

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

заметим, что при проведении такой операции всегда происходит изменение t_ij как минимум в четырёх строках (вершинах) i при заданном числе рёбер. во-первых, в двух строках соединяемых ребром. во-вторых, чтобы сохранить разбиение Q, удалённое ребро должно быть также подсоединено к двум вершинам, а именно к тем, у которых степени p_i были изменены.

4.При изменении элементов ССТ надо учитывать, что строки с одинаковыми элементами неразличимы, что нельзя нарушать неравенство и что сумма квадратов элементов CCТ постоянна и равна

(3.44)

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

Пример 5. Построим все CCТ для разбиения Q_i=(3,3,3,3,2,2) из примера 1 множества графов Г(6,8). Построение CCТ T₁ начнём с соединения вершины v₁ c вершинами v₂-v₄. Поэтому на первом шаге образуется первая строка, содержащая степени вершин v₂-v₄ и столбец, указывающий, что v₂ - v₄ соединены с вершиной, степень которой равна p₁=3. Покажем все шаги построения Т₁ (верхние индексы в скобках указывают номер шага):

Аналогично образуется вторая строка и вторые элементы в строках 3 и 4 таблицы после соединения ребрами вершины v₂ с v₃ и v₄. Так как степень p₃=3, а текущее значение p₃=2, то необходимо добавить ещё одно ребро, соединяющее v₃ и v_i, тем самым, закончив формирование . Его нельзя включить между v₃ и v₄, так как тогда образуется несвязный граф (между подграфами с degv_i =3 и degv_i=2 нет связей). к тому же вершины v₅ и v₆ пришлось бы соединить двумя параллельными рёбрами. Поэтому, соединив v₃ с v₅, дополняем строку v₃ степенью пятой вершины p₅=2, а строку v5 — степенью p₃=3, заканчиваем формирование .

Подобным же образом формируют строки 4 и 6 (). На этом шаге нельзя было соединять вершины v₅ и v₆ , так как тогда вершина v₆

осталась бы изолированной. Последним ребром графа соединяют вершины v₅ и v₆­­ (), заканчивая построение T₁.

Переходим к синтезу CCТ T₂, начиная с вершин с большими номерами. Пятая и шестая строки канонической T₁ неразличимы, поскольку они принадлежат одной орбите. Сделать одну из вершин j в лексикографическом смысле меньше другой можно, если соединить её с вершиной, имеющей p_i= p_j-1. В T₁ вершины v₅ и v₆­ одним ребром уже были соединены, а второе ребро, соединяющее их, превратит граф в несвязный мультиграф. Поэтому переходят к следующей строке с меньшим номером – четвёртой. В ней второй элемент t₄₂=3 уменьшают на единицу: и соединяют v₄ ребром с v₅ и образуют , поскольку учитывают предысторию построения , согласно которой v₄ была соединена с v₆. изменение в канонической CCТ на вызывает также изменение подсоединения одного ребра, инцидентного вершине p₂=3, и другого ребра, инцидентного вершине p₆=2. Соединение этих вершин приводит к окончательному виду CCТ T₂.

Составим теперь CCТ T₃. Лексикографическое уменьшение таблицы T₂ начинаем с попытки уменьшить в третьей строке элемент t₃₂=3 на единицу: , но тогда два ребра, инцидентные вершине v₂, нельзя будет соединить с другими вершинами (элементы t₂₂ и t₂₃­ для выполнения равенства (3.41) надо положить равными p₂=3 (см. ) , т.е. образовать две петли). Поэтому переходят к изменению первой строки T₂ , сделав в ней t₁₃=degv₆₍₅₎=2. Это вызывает согласно (3.41) необходимость увеличить одну из нижележащих строк. Увеличение второй или третьей строки сделает её одинаковой с первой строкой T₂. Тогда, изменив элемент t₄₂ четвёртой строки, образуем окончательную CCТ .

Дальнейшее лексикографическое уменьшение CCТ невозможно, и, значит все CCТ построены. На рис. 3.7,а,б изображены графы, имеющие CCТ T₁ и T₂ , а на рис.3.7,в,г – графы, у которых одна и та же CCТ T₃ . Их различие состоит в том, что вершины v₅ и v₆ смежны соответственно с парами вершин v₁, v₄ и вершинами v₂ , v₃ . Причём вершины в этих парах смежны на рис.3.7,в и несмежны на рис.3.7,г.

Применительно к ЭВМ алгоритм синтеза различных ССТ является процедурой, на каждом шаге которой заполняется одна строка таблицы T .

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

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

уменьшению. При заполнении строк необходимо выполнять (3.30), (3.40) и (3.41). Если хотя бы одно из этих условий не выполнимо, то рассматривается следующий вариант перестановок t_ij i-ой строки.

3. Если все варианты перестановок для i-ой строки исчерпаны, то переходят к (i-1)-ой строке и рассматриваются другие перестановки .

4. После заполнения всех строк проверяется соотношение (3.41).

5. Работа алгоритма закончена, когда исчерпаны всевозможные перестановки в первой строке.

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

Таким образом, применение разбиений и смежностно-степенных таблиц позволяет синтезировать достаточно большое число неизоморфных графов. Для отдельных устройств с небольшим числом узлов строятся практически все различные структуры. Так синтез на ЭВМ всех неизоморфных графов с числом v=7 и q=8...13 показал, что из них 85% имеют разные ССТ.

Числа t_ij таблицы T и матрицы Д_Q и Д_k могут отражать, как уже отмечалось, не только степени вершин графа и факт соединения вершины i и j ребром (дугой), но и такие их характеристики, как цвет ребра, его направление, наличие параллельных ребер и т.д. Для кодирования подобной информации можно использовать полиадическую позиционную систему счисления, в которой с каждым i-м разрядом связан свой интервал изменения цифр 0, 1, …, L_i - 1 , а вес E k-ого разряда равен произведению длин интервалов всех предшествующих ему разрядов: E_k = L₁L₂…L_k-2L_k-1; E₀ = 1. Число по значениям цифр , в разрядах определяют из формулы

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