Об операции вершинной подстановки и точных расширениях графов

ОБ ОПЕРАЦИИ ВЕРШИННОЙ ПОДСТАНОВКИ И ТОЧНЫХ РАСШИРЕНИЯХ ГРАФОВ

Саратовский государственный университет имени , Саратов, Россия

Ориентированным графом называется пара G = (V, a), где V – конечное непустое множество, называемое множеством вершин, а a – отношение на множестве вершин V, называемое отношением смежности.

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

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

Рассмотрим два семейства точных расширений графов: семейство транзитивных турниров и семейство циклически симметричных графов.

Транзитивный турнир – это турнир, у которого из существования дуг (u, v) и (v, w) вытекает существование дуги (u, w). В работе [1] показано, что точным k расширением турнира Tn при n > 2 является транзитивный турнир Tn+k.

Рассмотрим схему построения семейства вершинно-симметрических графов с циклической симметрией предложенную в работе [2]. Если G – некоторый n-вершинный циклически симметричный граф, то его можно изобразить так, что при повороте полученной картинки на 360/n градусов в любую сторону и сколько угодно раз, мы будем все время наблюдать один и тот же граф. Матрица смежности циклически симметричного графа, изображенного таким образом, обладает интересным свойством. Каждая строка матрицы кроме первой получается из предыдущей строки циклическим сдвигом на одну позицию вправо. Таким образом, чтобы перебрать все вершинно-симметрические графы с циклической симметрией необходимо перебрать все возможные первые строки матрицы смежности и достроить последующие указанным способом.

В приведенной ниже таблице можно проследить количество транзитивных турниров (семейство T) и количество циклически симметричных турниров (семейство S) до 12 вершин.

Таблица

Точные расширения турниров до 12 вершин

N	Максимальный минорный код турнира	N	Семейство	Максимальный минорный код точного расширения
2	1	3	S	5
2	1	3	T	7
3	7	4	T	63
4	59	5	S	947
4	63	5	T	1023
5	982	6		31435
5	1011	6	T2 ^ S3	32359
5	1023	6	T	32767
6	31435	7	S	2011853
6	32487	7	S	2079175
6	32767	7	T	2097151
7	2097151	8	T
8		9	S
8		9	S
8		9	S
8		9	T3 ^ S3
8		9	T
9		10
9		10	T2 ^ S5
9		10	T
10		11	S
10		11	S
10		11	S
10		11	S
10		11	T
11		12	T4 ^ S3	3
11		12	T	3

Рассмотрим операцию над парой графов G1 и G2, которую назовем операцией вершинной подстановки графа G1 в граф G2.

Результатом вершинной подстановки графа G1= (V1, a1) в G2= (V2, a2), |V1| = n1, |V2| = n2, будет граф G=(V, a), такой что:

1)  V = {Vi, j | i=1..n1, j=1..n2}, |V| = n1*n2

2)  (Vi, k, Vj, t) Î a, если k = t и (Vi, Vj) Î a1 или если k ¹ t и (Vk, Vt) Î a2

Рассмотрим граф T ^ S, получающийся в результате вершинной подстановки транзитивного турнира T с n1 вершинами в циклически симметричный граф S с числом вершин n2. В полученном графе вместо каждой вершины графа S будет располагаться n1 вершин соответствующего турнира T. Выберем любую составную вершину нового графа – один из подставленных турниров, например первый T1. Заметим, что по схеме вершинной подстановки, множество вершин графа T ^ S не из T1, с которыми будут связаны вершины турнира T1, совпадают. Удаляя любую из вершин T1, мы будем получать один и тот же транзитивный турнир с числом вершин n1 – 1, связанный всегда с одними и теми же вершинами T ^ S. То есть мы получим n1 изоморфный граф.

Далее если воспользоваться свойством циклической симметрии исходного графа S и повернуть его по часовой стрелке на 360/n2, то можно провести аналогичные рассуждения для подставленного турнира T2 и т. д. То есть полученный граф T ^ S будет точным расширением.

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

В таблице, графы получающиеся подстановкой T турнира c n2 вершинами в S турнир с n1 вершиной обозначены Sn1 ^ Tn2.

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

1.  Минимальные расширения транзитивных турниров // Вестник ТГУ. Приложение. 2006. № 17. С. 187 – 190.

2.  , Точные расширения некоторых турниров // Вестник ТГУ. Приложение. 2007. № 23. С. 211 – 216.