О паросочетаниях в числовых графах

О паросочетаниях в числовых графах

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2015
Автори: Шулинок, И.Э., Шулинок, Г.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Назва видання:Теорія оптимальних рішень
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/112393
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:О паросочетаниях в числовых графах / И.Э. Шулинок, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 29-34. — Бібліогр.: 2 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-112393
record_format dspace
spelling irk-123456789-1123932017-01-21T03:03:16Z О паросочетаниях в числовых графах Шулинок, И.Э. Шулинок, Г.А. Рассматриваются натуральные арифметические и натуральные модульные графы. Доказываются свойства графов, содержащих паросочетания всех вершин. Предлагаются методы, позволяющие для произвольного натурального арифметического и натурального модульного графа определить наличие совершенного паросочетания. Розглядаються натуральні арифметичні й натуральні модульні графи. Доводяться властивості графів, що містять узгодження всіх вершин. Пропонуються методи, які дозволяють для довільного натурального арифметичного і натурального модульного графа визначити наявність досконалого узгодження вершин. Natural arithmetic and natural modular graphs are considered. The graphs qualities for perfect matching are solved. The methods to allow determine a perfect matching for any natural arithmetic and natural modular graph are proposed. 2015 Article О паросочетаниях в числовых графах / И.Э. Шулинок, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 29-34. — Бібліогр.: 2 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/112393 519.1 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматриваются натуральные арифметические и натуральные модульные графы. Доказываются свойства графов, содержащих паросочетания всех вершин. Предлагаются методы, позволяющие для произвольного натурального арифметического и натурального модульного графа определить наличие совершенного паросочетания.
format Article
author Шулинок, И.Э.
Шулинок, Г.А.
spellingShingle Шулинок, И.Э.
Шулинок, Г.А.
О паросочетаниях в числовых графах
Теорія оптимальних рішень
author_facet Шулинок, И.Э.
Шулинок, Г.А.
author_sort Шулинок, И.Э.
title О паросочетаниях в числовых графах
title_short О паросочетаниях в числовых графах
title_full О паросочетаниях в числовых графах
title_fullStr О паросочетаниях в числовых графах
title_full_unstemmed О паросочетаниях в числовых графах
title_sort о паросочетаниях в числовых графах
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2015
url http://dspace.nbuv.gov.ua/handle/123456789/112393
citation_txt О паросочетаниях в числовых графах / И.Э. Шулинок, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 29-34. — Бібліогр.: 2 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT šulinokié oparosočetaniâhvčislovyhgrafah
AT šulinokga oparosočetaniâhvčislovyhgrafah
first_indexed 2025-07-08T03:50:57Z
last_indexed 2025-07-08T03:50:57Z
_version_ 1837049218677604352
fulltext Теорія оптимальних рішень. 2015 29 ТЕОРIЯ ОПТИМАЛЬНИХ РIШЕНЬ Рассматриваются натуральные арифметические и натуральные модульные графы. Доказываются свойства графов, содержащих па- росочетания всех вершин. Предла- гаются методы, позволяющие для произвольного натурального ариф- метического и натурального мо- дульного графа определить нали- чие совершенного паросочетания. _____________________________  И.Э. Шулинок, Г.А. Шулинок, 2015 УДК 519.1 И.Э. ШУЛИНОК, Г.А. ШУЛИНОК О ПАРОСОЧЕТАНИЯХ В ЧИСЛОВЫХ ГРАФАХ Введение. Известно [1], что числовые графы обладают рядом полезных свойств, в том числе и алгоритмической эффективностью. Уже найдены эффективные алгоритмы проверки изоморфизма и нахождения хроматического числа, а также алгоритмы поиска в глубину и ширину на числовых графах. Цель данного ис- следования найти способ поиска паросочета- ний, охватывающих наибольшее число вершин числового графа. Определение 1. Числовым графом G(X, U, F, g) называется такой граф, в кото- ром вершины содержатся в множестве X, и пары вершин ,x y X соединены дугами тогда и только тогда, когда F(x, y) .U Множество X называется множеством вер- шин, множество U множеством образующих, функция F: X × X→ – порождающей функ- цией. Множество X = n. Функция g: X→{0,1} называется функцией исключений. В зависимости от вида порождающей функции и функции исключений, различают натуральные числовые графы (g(x) = 1, ),x X  а также арифметические (F(x,y) = = x + y, А-графы) и модульные (F(x, y) = =|x – y|, М-графы) графы. Назовем такие натуральные графы соответственно НА-гра- фами и НМ-графами. Определение 2. Паросочетание ребер числового графа G – это набор ребер вида (xi, xj), xi, xj ,X в котором вершины при- сутствуют лишь однажды, и F(xi, xj) ,U т. е. соединяются ребром. Рассмотрим случай с НА-графами, по- скольку эти графы исследуются уже доста- точно давно, и за это время их структура до- статочно изучена. И.Э. ШУЛИНОК, Г.А. ШУЛИНОК 30 Теорія оптимальних рішень. 2015 Пусть NAn (u) – натуральный арифметический граф с n вершинами и одной образующей u. Исходя из свойств НА-графов вытекает, что образующая u = n + 1 сообщает графу       2 n ребер вида (k, 1 + n – k), k = 1, 2, ...,       2 n . Очевид- но, эти ребра несвязны, т. е. являются паросочетанием. При четном числе вершин весь граф представляет собой совершенное паросочетание (рис. 1). При нечетном n такая образующая будет давать максимальное паросочетание. Сформулируем этот результат в виде леммы. РИС. 1. Паросочетание графа 8(9)NA Лемма 1. НА-граф с одной образующей u = n + 1 – это максимальное паро- сочетание для заданного числа вершин n. Несложно заметить, что произвольный НА-граф, содержащий образующую u = n + 1 и имеющий четное число вершин будет содержать совершенное паро- сочетание. Для натуральных модульных графов с одной образующей существу- ет более одного варианта образующих, которые сообщают максимальное паро- сочетание. Вариант образующей u = 1 показан на рис. 2. Как известно [1], эта образующая сообщает графу гамильтонову цепь. Выбрав чередующиеся ребра цепи можно получить максимальное паросочетание для заданного n. Лемма 2. В НМ-графе с образующей u = 1 максимальное паросочетание имеет вид: (1, 2) (3, 4), ..., (2k – 1, 2k), где        2 n k . Известно [1], что НМ-граф с одной образующей представляет собой набор цепей (u > 1). Особый интерес для нас представляет случай, когда u | n и n ≡ 0(mod 2u). В этом случае количество цепей соответствует u, но каждая из цепей состоит из       u n вершин. Цепь нечетной длины (содержащая четное коли- чество вершин) будет содержать полное паросочетание. Условие n ≡ 0(mod 2u) или       u n ≡ 0(mod 2) обеспечивает это. Тем самым лемма доказана. 1 1 6 8 2 1 7 3 6 4 5 О ПАРОСОЧЕТАНИЯХ В ЧИСЛОВЫХ ГРАФАХ Теорія оптимальних рішень. 2015 31 Лемма 3. НМ-граф NMn(u) такой, что u | n и n ≡ 0(mod 2u) содержит совер- шенное паросочетание. 1 84 73 62 5 (1, 2) (3, 4) (5, 6) (7, 8) NM 8 (1) РИС. 2. Паросочетание полученное из гамильтоновой цепи на примере NM8(1) Очевидно, что граф, содержащий образующие, соответствующие условиям лемм 2 и 3 будет вмещать в себе совершенное паросочетание при четном числе вершин. Вычислить это паросочетание достаточно просто: каждая цепь начина- ется с вершины x = 1,2,…, u, а дальше берется ребро за ребром (рис. 3). РИС. 3. Граф NM16 (2) и паросочетание в составляющих цепях Также среди НМ-графов с одной образующей можно найти граф, изоморф- ный NAn (n + 1). Лемма 4. НМ-граф 2 n n NM          изоморфен графу NAn(n + 1). Доказательство. Сопоставим вершинам графа NAn(n + 1) вершины графа 2 n n NM          следующим образом: вершина       2 n ↔       2 n + 1, k↔k, k = 1,2, ...,       2 n , 1 14 7 5 4 3 2 6 13 10 11 12 8 9 10 16 15 И.Э. ШУЛИНОК, Г.А. ШУЛИНОК 32 Теорія оптимальних рішень. 2015 n – k + 1↔k +       2 n . Охвачены все вершины. Сопоставление взаимно однознач- ное. Связность сохраняется. Графы изоморфны. Лемма доказана. Следствие. НМ-граф 2 n n NM          дает максимальное паросочетание для заданного n. Для начала рассмотрим натуральные арифметические графы с двумя обра- зующими. Выберем граф NAn(u1, u2) такой, чтобы 3 ≤ u1 ≤ u2 и u2 = n + u1. При этом образующая u1 ≡ 1(mod 2). В этом графе образующая u1 сообщает графу ребра (1, u1 – 1), (2, u1 – 2), …, 1 1 1, . 2 2 u u u                Образующая u2 при условии чет- ности числа вершин тоже нечетна, а следовательно сообщает графу ребра (u1, n), (u1 + 1, n – 1), …, (              2 ,1 2 1 1 1 1 u u u u ). При четном n таких ребер будет 2 n , т. е. это будет совершенным паросочетанием. Тем самым лемма доказана. Лемма 5. Граф NAn(u1, u2), такой, что 3 ≤ u1 ≤ u2 и u2 = n + u1 и образующая u1 ≡ 1(mod 2) будет изоморфна графу NAn(n + 1). Среди натуральных модульных графов с двумя образующими легко обна- ружить графы, изоморфные гамильтоновой цепи или графу NMn(1). В таких графах пара образующих будет иметь вид u1 ≤ u2, u1, u2  U, u1 + u2 = n + 1. Пример такого графа показано на рис. 4. РИС. 4. Граф NM14(2,13) с двумя образующими, изоморфный гамильтоновой цепи NM14(1) Как видно, этот граф изоморфен NM14(1), а по лемме 2 получается, что в нем есть паросочетание из 7 ребер: (1, 14), (2, 4), (3, 5), (6, 8), (7, 9), (10,12) и (11, 13), которые представляют собой ребра цепи взятые от начала и до конца (рис. 3, б). Общий результат можно задать формально. 1 6 5 3 4 11 2 12 9 8 7 10 14 13 1 6 5 3 4 11 2 12 9 8 7 10 14 13 а б О ПАРОСОЧЕТАНИЯХ В ЧИСЛОВЫХ ГРАФАХ Теорія оптимальних рішень. 2015 33 Лемма 6. Граф NMn(u1, u2) с образующими вида u1 + u2 = n+1, n ≡ 0 (mod 2), НОД(u1,u2 ) = 1, содержит совершенное паросочетание из 2 n ребер. Интерес для нас представляют НМ-графы с нечетными образующими. В работе [1] показано, что такие графы будут двудольными. НМ-граф с един- ственной нечетной образующей будет несвязным (при u > 1), однако можно ска- зать о существовании совершенного паросочетания при условии, что u | n и u n ≡ 0(mod 2), т. е. при выполнении условия леммы 3. В случае, когда образу- ющих больше одной, получается связный (если образующие взаимно простые) двудольный граф или же граф распадается на связные компоненты (если у обра- зующих есть НОД). Пусть NMn(u1, u2), u1 ≡ 1(mod 2), u2 ≡ 1(mod 2). Этот граф будет двудольным, каждая из долей будет содержать четные и нечетные вершины соответственно. Пусть n ≡ 0(mod 2). В этом случае обе доли будут иметь одинаковый размер. По теореме Холла о паросочетаниях [2] такой граф будет содержать совершен- ное паросочетание, если вершины с кодами от 2 до u1 – 1, а также вершины с кодами от n – u1, n – u1 + 2,…, n должны быть связаны по крайней мере с u1 не- четными вершинами. Рассмотрим двудольный НМ-граф с нечетными образующими. В терминах теоремы Холла, пусть A = {1, 3, …, u1, n – u1 + 2, n – u1 + 4, …, n – 1}. Тогда NA = {1 + u1,1 + u2, …, 1 + um, …, um + n – 1}. По теореме Холла граф NMn(1 < u1, u2, …, um ≤ n – 1), ui ≡ 1(mod 2), i = 1, 2, …, m, n = 2k, будет содер- жать совершенное паросочетание тогда и только тогда, когда произвольное подмножество нечетных вершин будет связано с подмножеством четных вер- шин той же или большей мощности. Однако в случае НМ-графа можно сокра- тить количество подмножеств для анализа. Легко показать, что в случае, когда вершины в подмножестве A соответствуют свойству mkAaauaa jikji ,,2,1,,,2  , (1) подмножество связных четных вершин будет иметь меньшую мощность. Также, интерес представляют другие нечетные вершины, которые соответству- ют свойству (1). Этот результат формально можно изложить в виде теоремы Холла для нату- ральных модульных графов. Теорема 1. Числовой граф NMn(1 < u1, u2, …, um ≤ n – 1), ui ≡ 1(mod 2), i = 1,2, …, m, n = 2k будет иметь совершенное паросочетание, если подмноже- ство связных вершин для подмножества нечетных вершин A = {1,3,…, u1, n–u1, n – u1 + 2, n – u1 + 4,…, n – 1} будет иметь мощность не меньшую |A|. В случае натуральных арифметических графов прослеживается другое свойство. Рассмотрим полный двудольный НА-граф c четным числом вершин И.Э. ШУЛИНОК, Г.А. ШУЛИНОК 34 Теорія оптимальних рішень. 2015 NAn(3, 5, 7,…, n – 1 , n + 1,…, 2n – 1), n ≡ 0(mod 2). Очевидно, что граф будет двудольным. Одна из долей будет состоять только из четных вершин, а другая – из нечетных. По теореме Холла, чтобы в таком графе существовало совершен- ное паросочетание, необходимо и достаточно, чтобы любое подмножество не- четных вершин было бы связано с не меньшим подмножеством четных. Исходя из лемм 1 и 5, полный двудольный граф распадается на набор из 2 n паросочета- ний. Кроме паросочетания, получаемого по лемме 1, будут паросочетания, полученные с помощью пар образующих (u, n + u). При этом, используя допол- нительные образующие, можно получить более общий результат. Таким обра- зом, можно сформулировать теорему Холла для НА-графов. Теорема 2. Двудольный граф NAn (u1, u2,…,um) содержит совершенное паросочетание тогда и только тогда, когда цепи, содержащие вершину 1 и вер- шину n содержат совершенное паросочетание. Следствие. НА-граф NAn(u1, u2) с двумя нечетными образующими содержит совершенное паросочетание тогда и только тогда, когда n|(u2 – u1), u1 < u2. Заключение. Данная работа положила начало исследованию паросочетаний на числовых графах. Определено, что в условиях, применимых к теореме Холла (двудольные графы) для НМ-графов и НА-графов можно получить исчерпы- вающий ответ для графов с нечетными образующими. І.Е. Шулінок, Г.О. Шулінок ПРО ПАРОУЗГОДЖЕННЯ ЧИСЛОВИХ ГРАФІВ Розглядаються натуральні арифметичні й натуральні модульні графи. Доводяться властивості графів, що містять узгодження всіх вершин. Пропонуються методи, які дозволяють для довільного натурального арифметичного і натурального модульного графа визначити наяв- ність досконалого узгодження вершин. I.E. Shulinok, G.A. Shulinok ABOUT NUMERIC GRAPHS NODES MATCHING Natural arithmetic and natural modular graphs are considered. The graphs qualities for perfect matching are solved. The methods to allow determine a perfect matching for any natural arithmetic and natural modular graph are proposed. 1. Донец Г.А. Основы теории числовых графов. – Кировоград: ЧП «Эксклюзив-Систем», 2013. – 280 с. 2. Зыков А.А. Основы теории графов. – М.: Вузовская книга, 2004. – 664 с. Получено 11.02.2015

Схожі ресурси