One family of optimal graphs with prescribed connectivities.pdf Введение Изучение графов с заданной вершинной или рёберной связностью представляет интерес как с теоретической, так и с прикладной точек зрения. В теоретическом плане эти исследования восходят к работам [1-3], в прикладном - к работе [4], в которой исследуется построение сетей минимальной стоимости с заданнной связностью. Большой интерес представляют графы Харари, которые имеют минимальное число рёбер при заданном значении вершинной связности [2, 5]. Рассмотрим простые неориентированные графы и их основные меры связности. Понятия из теории графов используются в соответствии с [6, 7]. Напомним, что связным называется граф, любая пара вершин которого соединена путём. В противном случае граф называется несвязным. Тривиальным называется одновершинный граф. Граф, любые две вершины которого смежны, называется полным. Определение 1. Вершинной связностью k графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Определение 2. Рёберная связность А нетривиального графа G определяется как наименьшее количество рёбер, удаление которых приводит к несвязному графу. Например, деревья имеют вершинную и рёберную связности 1. Полный п-вершин-ный граф имеет вершинную и рёберную связности п - 1. Далее будем рассматривать только связные графы. Обозначим минимальную степень вершины в графе через 5. Вершинная связность k, рёберная связность Л и минимальная степень вершины 5 произвольного графа связаны следующим неравенством: Теорема 1 [1]. Для любого графа G справедливо неравенство k С Л С 5. Доказано, что для любых подходящих значений k, Л и 5 существует соответствующий граф: Теорема 2 [3]. Для любых натуральных чисел a,b, с, таких, что 0 < а С b С с, существует граф G, у которого k = a, Л = b, c = 5. В работах [8, 9] рассматривается задача о поиске графов с минимальным числом вершин и рёбер для любых a, b, c из теоремы 2. В данной работе решается задача описания графов с заданным числом вершин п и с минимальным числом рёбер для пар возможных значений k и Л. Обозначим ,\\к,Л минимальное число вершин, которое может содержать граф с заданной вершинной связностью k и рёберной связностью Л. Теорема 3. 2(Л + 1) - k Л+1 при Л > k, при Л = k. Обозначим минимальное число рёбер, которое может содержать граф с заданной вершинной связностью k и рёберной связностью Л. Теорема 4. Г Л2 - k2 + k + Л + а Ek А - \\ при Л > k, при Л = k, к,х \\Л(Л +1)/2 где а = 0, если P(2k2 - - 2k)/2] С 0, P(2k2 - - 2k)/2] иначе. Очевидно, что построить граф, содержащий заданное число вершин п, с минимальным числом рёбер для заданных значений k и Л можно только при п Nk,\\. Если k = Л = 1, то N1,1 = 2. Легко видеть, что граф с минимальным числом рёбер для заданного числа вершин п с k = Л =1 - дерево с числом рёбер п - 1. Основной результат Определение 3. Диагональю порядка i назовём множество пар (k, Л), удовлетворяющих следующим условиям: 1) Л - k = i; 2) для заданных k и Л можно построить граф с вершинной связностью k и рёберной связностью Л; 3) граф из условия 2 является либо Л-регулярным, либо одна из его вершин имеет степень Л + 1, а остальные вершины имеют степени Л; 4) условие 3 должно выполняться для графов с любым числом вершин п Ж,д. Определение 4. Под парой значений (kmin(i), Лтт(^) будем понимать образующий элемент диагонали порядка i. Образующий элемент - это такая пара значений, которая удовлетворяет условиям из определения 3 и является наименьшим значением (k, X) для соответствующей диагонали. Если есть образующий элемент диагонали порядка i, то можно получить образующий элемент диагонали i + 1 следующим образом: kmin(i+1) = kmin(i) + 1, Xmin(i+1) = Xin(i) + 2. По аналогии для i - 1 диагонали: kmin(i-1) = kmin(i) - 1, Xmin (i-1) = Xmin( i ) 2. Определение 5. Пару (2, 2) назовём корневым образующим элементом и обозначим (kr , Xr ) . Корневой образующий элемент является образующим элементом диагонали порядка 0. Остальные образующие элементы диагоналей можно найти по следующей формуле: kmin(i) = kr + i, Xmin(i) = Xr + 2i. Обозначим множество диагоналей через D. Схематично множество D представлено на рис. 1. Рис. 1. Схема множества диагоналей D На рис. 1 точками помечены образующие элементы соответствующих диагоналей. Линиями выделены сами диагонали. Цифрами снизу обозначены порядки диагоналей. В таблице по вертикали идут значения вершинной связности, по горизонтали - рёберной связности. Графы Харари образуют диагональ порядка 0. Напомним, что графом Харари Ht,n называется n-вершинный граф с минимальным числом рёбер, у которого k = X = t [2]. Далее приводится основной результат работы, в котором описываются графы из множества D. Теорема 5. Пусть k X kmin(i), X X Xmin(i), X - k = i, i X 0. Тогда для любого n X Nk,x существует граф G с заданными k и X, содержащий n вершин, такой, что: - если X или n чётные, то G - X-регулярный граф; - если Л и n нечётные, то одна из вершин графа G имеет степень (Л + 1), остальные вершины имеют степени Л. При этом граф G является оптимальным по рёбрам, то есть состоит из наименьшего возможного числа рёбер, равного РЛп/2^.

Скачать электронную версию публикации