On degree structure of graphs.pdf В [1] введено мультимножество, называемое степенной структурой графа. Укажем определяющие свойства степенной структуры графов. 1. Ориентированные графы Для n-вершинного орграфа Г обозначим nr,s число вершин с полустепенью захода r и полустепенью исхода s, где 0 ^ r, s,nr,s ^ n. Целое неотрицательное число nr,s называется кратностью пары (r, s) полустепеней вершин в орграфе Г. Мультимножество всех пар (r, s) полустепеней вершин в орграфе Г называется степенной структурой орграфа Г, обозначается D(r). Таким образом, D(r) = {(r, s)""r's}, где, как правило, пары с нулевой кратностью не записаны в мультимножестве Д(Г). Например, степенная структура контура K длины n имеет вид D(K) = {(1,1)n}, степенная структура полного n-вершинного орграфа Г имеет вид Д(Г) = {(n,n)n}. Для степенной структуры n-вершинного орграфа Г, заданной мультимножеством Д(Г) = {(r, s)""r's}, выполнен ряд свойств. 1) Для орграфа Г с числом вершин n > 1 и с числом дуг m £ nr,s = n; (1) (r,s) £ (r + s)nr,s = 2m. (2) (r,s) Равенство (2) есть запись одной из первых теорем теории графов, доказанных Эйлером, в терминах степенной структуры орграфа. 2) Если орграфы Г и Г' изоморфны, то Д(Г) = Д(Г'). 3) В орграфе Г: - no,o есть число изолированных вершин; - £ n0,s есть число вершин с полустепенью захода 0; s - £ nr,0 есть число вершин с полустепенью исхода 0; r - если орграф Г сильносвязный, то n0,s = nr,0 = 0 при любых s и r; - число ациклических неизолированных вершин не меньше У] n0,s + £ nr,0; s>0 r>0 - число циклических вершин не превышает n - £ n0,s - £ nr,0. sr 4) Пусть X есть n-множество, Г(д) -граф преобразования g множества X, тогда - nr,s = 0 при любом s = 1, r любое; - равенства (1) и (2) имеют вид no,i + ni,i + ... + nn,i = n; (3) n E(r + 1)nr,i = 2n; (4) r=0 - n0,i есть число элементов X, не имеющих прообразов относительно g; - число ациклических вершин не меньше n0,i; - число циклических вершин не превышает n - n0,i. 2. Неориентированные графы Для n-вершинного графа Г обозначим q(r) число вершин степени r, 0 ^ r, q(r) ^ n (кратность степени r). Мультимножество допустимых натуральных чисел r назовём степенной структурой графа Г (обозначим её Д(Г)); таким образом, Д(Г) = {r[q(r)]}, при q(r) = 0 элемент r опускается. Например, степенная структура цикла C длины n имеет вид Д(С) = {2[n]}, степенная структура полного n-вершинного графа Г имеет вид Д(Г) = {n[n]}. Для степенной структуры n-вершинного графа Г, заданной мультимножеством Д(Г) = {r[q(r)]}, выполнен ряд свойств. 1) Для графа Г с числом вершин n > 1 и с числом рёбер m q(0) + q(1) + ... + q(n) = n; (5) E rqr = 2m. (6) r 2) Если графы Г и Г' изоморфны, то Д(Г) = Д(Г'). 3) q(0) есть число изолированных вершин. 3. Описание степенной структуры минимальных примитивных орграфов Примитивный орграф называется минимальным, если любая его n-вершинная часть не является примитивным графом. Обозначим Г^щ^т) множество всех минимальных примитивных n-вершинных орграфов c числом дуг m > n. Теорема 1 [1]. При n ^ 3 орграф Г е Г^ш^п + 1), если и только если Г есть объединение двух простых контуров взаимно простых длин l и Л, общая часть которых есть путь длины q, где 0 ^ q ^ n - 2, 1>Л, l + Л - q = n +1; при q = 0 общая часть контуров есть вершина. Следствие 1. Для Г е Г^п(п, n+1), где n ^ 3, или £(Г) = {(1,1)n-2, (1, 2), (2,1)}, или ДГ) = {(1,1)n-^ (2, 2)}. Теорема 2 [1]. Если Г е О, n + 2), то ^(Г) принадлежит следующим 9 классам при указанных n: № n ^ ... D(r) № n ^ ... D(r) 1 5 (1,1)n-1, (3, 3)1 6 6 (1,1)n-3, (2,1)2, (1, 3)1 2 5 (1,1)n-2, (2,1)1, (2, 3)1 7 6 (1,1)n-3, (1, 2)2, (3,1)1 3 5 (1,1)n-2, (1, 2)1, (3, 2)1 8 6 (1,1)n-3, (1, 2)1, (2,1)1, (2, 2)1 4 5 (1,1)n-2, (2, 2)2 9 6 (1,1)n-4, (1, 2)2, (2,1)2 5 4 (1,1)n-2, (1, 3)1, (3,1)1 Лемма 1. Пусть a,b - взаимно простые натуральные числа, тогда любое натуральное n > ab представимо линейной комбинацией n = la + ЛЬ, где l, Л > 0. Теорема 3. Для любого n ^ 5 и k = 2,..., n - 3 имеется орграф Г е Г^^п, n + k) со степенной структурой Д(Г) = {(1,1)n-1, (k + 1, k + 1)1}. В силу леммы любое число, не меньшее 7, представимо линейной комбинацией 2/ + ЗА, где /, А > 0. Значит, при n ^ 5 и k = 2,...,n - 3 множество дуг орграфа (порядка n + k) можно разделить на / контуров длины 2 и А контуров длины 3 с единственной общей вершиной, что обеспечивает примитивность и минимальность орграфа. Для данного орграфа n + k = 2/ + ЗА, n = / + 2А +1, отсюда k = / + А - 1. Значит, степенная структура имеет требуемый вид.

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