Построение n-мерных паттернов как задача построения и раскраски n?дольных графов и их миноров

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 876. 5
І.І. СКРИЛЬНИК, ст. викладач, ПНТУ (м. Полтава)
ПОБУДОВА Я-МІРНИХ ПАТТЕРНІВ ЯК ЗАДАЧА ПОБУДОВИ ТА ПОФАРБУВАННЯ Я-ДОЛЬНИХ ГРАФІВ ТА ЇХ МІНОРІВ
У статті розглядається проблема побудови я-мірних паттернів. Вирішення цієї задачі зводиться до пофарбування я-дольних графів та їх мінорів виду Кп. Доведено, що будь-який я-дольний граф може бути стягнутий у зірку виду Кп. Показано зв'-язок я-мірних паттернів із я-дольними графами, а також, що степінь вершин графа визначає у кінцевому випадку множину оптимальних розв'-язків при побудові паттерну.
Ключові слова: паттерн, мінор, я-дольний граф, зірка, пофарбування графа.
Постановка проблеми. Наочність, ефективність та перспективність
застосування я-мірних паттернів у різних галузях науки та техніки ставить конкретні завдання по їх оптимальній побудові. Розв'-язання цієї проблеми носить комплексний характер. Одним із шляхів ії вирішення є застосування теорії пофарбування графів, зокрема, я-дольних та їх мінорів виду Кп.
Аналіз літератури. У [1 — 3] автори вирішують прикладні задачі побудови я-мірних паттернів та їх конкретне застосування у галузі управління, економіки, фінансовому аналізі. У [4] реалізовано евристичні алгоритми в системах захисту, обробленні інформації. У [5] автори довели, що задача розподілу гомогенних робочих ресурсів є поліноміальною. У [6 — 9] розроблено методи побудови я-мірних паттернів без накладених обмежень. У [10] автор дає огляд останніх досягнень у теорії графів, викладено такі актуальні розділи, як мінори та пофарбування графів.
Мета статті - показати, що побудова я-мірних паттернів зводиться до пофарбування я-дольних графів та їх мінорів виду Кп.
Побудова и-мірних паттернів методом пофарбування п-дольних графів та їх мінорів виду Кп. У загальному випадку я-мірні паттерни являють собою таке розбиття масиву п х п елементів на я типів К, К, • • •, Кп, що для
кожного типу К може бути побудований набір функцій Ф (Кі), і = 1, я. Однією із необхідних умов реалізації я-мірного паттерну за заданим набором типів {К1,К2,Кя} є справедливість умови Ф (Кі) ФФ (К^) для і ф ].
Одним із підходів до побудови я-мірних паттернів є методи, що ґрунтуються на властивостях хроматичного числа графів та їх пофарбуванні.
Покажемо, що будь-який n-мірний паттерн можна представити у вигляді n-дольного графу та навпаки.
r-Дольним графом (r-partite graph) називається такий граф G (V, E), якщо
V допускає таке розбиття його вершин V = {иьи2,иn} на r класів, при якому кінці кожного (и, U), i ^ j ребра лежать у різних класах. При цьому
вершини із одного класу розбиття повинні бути попарно несуміжними [10].
r-Дольний граф, у якому кожні дві вершини із різних класів суміжні називається повним.
Повні r-дольні (complete r-partite) графи для всіх r разом називаються повними багатодольними графами [10].
Пі - Пг
Повний r-дольний граф К … К позначається через Кщ,… Якщо
п1 =… = nr = s, то пишемо К[, якщо s = n = r, то КП називається n-дольним графом. Так, К[ є повний r-дольний граф, у якому кожен клас вершин складається із s вершин. Слід зазначити, що Krs можна отримати шляхом заміни кожної вершини в Kr на незалежну s-множину. Позначення Krs як раз і містить підказку на таку заміну [10].
Графи виду K1n називаються зірками (star) [10]. На рис. 1 зображені зірки
К3, К4, К5. Для них кожна вершина становить окремий клас. Відповідно зображені графи є 3-, 4- та 5-пофарбованими.
Рис. 1. Зображення графів-зірок виду К3, К4, К5
Із зірками пов'-язаний окремий напрям дослідження графів. Оскільки, у
зірках кожна вершина зв'-язана з усіма іншими вершинами графа, то
мінімальна кількість кольорів, у які вони можуть бути пофарбовані, становить п.
Оцінка найменшої та найбільшої степені кожної вершини графа виду КП становить:
Л тп = п-1- (!)
?тх = п 2 — п- (2)
?тп ^ Л^ ?тах. (3)
152
Теорема 1. Будь-який п-дольний граф може бути стягнутий у зірку виду Кп.
Доведення. Нехай задано граф О = (У, Е). Позначимо е = (хі, х ^) ребро у графі О = (У, Е) таке, що вершини х та х ¦ є суміжними при і Ф у. Позначимо також О/е граф, отриманий із О шляхом стягування ребра е у нову вершину ие, яка стає суміжною із вершинами хг та х ¦. Формально О/е є граф (У'-, Е'-) із множиною вершин
V '- = (V {Хі, хі }) }, (4)
де ие & lt-? У ^ Е, і множиною ребер
Е '-= {(х*, хг) є Е |{(х*, хг) ^ (Хі, ху) = 0}}^ и{(ие, Хг) | (Хі, хг) є Е (е) або (ху, хг) є Е (е)}. (5)
Якщо граф О є п-дольним, то він має п х п вершин. Враховуючи означення про п-повні графи при п = г та беручи до уваги (3), приходимо до висновку, що граф О може містити при наймі п2 — п ребер, які можуть бути стягнуті за допомогою (5). Оскільки, степінь будь-якої вершини в графі є однаковою для всіх вершин, то операція стягування ребра (5) не змінює степінь вершин, а перерозподіляє вершини по класам. При стягуванні ребра е згідно (4) відбувається зменшення також кількості вершин у графі. Наприклад,
при першому стягуванні граф виду КЩ перетворюється у граф КЩ-1, або Кп-1,п. Далі, виконуючи (4) та (5), отримуємо графи Кп-2п, Кп-3п, Кп_і п, К1п. Або в загальному випадку можна записати
О (У (і), Е (і))/еі = (V (і-1) {Хі-1,х^}, Е (і-1) Єі), (6)
де 1 & lt- і & lt- п2 — п, та і Ф у для двох суміжних вершин.
Таким чином, стягування ребер ег призводить до перетворення п-дольного графа виду КЩ у граф-зірку Кп за п2 — п ітерацій. Отже, теорему доведено.
Наслідок 1. Якщо для п-дольного графа О існує мінор виду Кп, то мінімальна кількість кольорів, у яку може бути пофарбований граф О, дорівнює ^(о) = п. У цьому можна легко переконатися, виконуючи індукцію
|О| - |х|, де X = 2_п. Граф Кп = X є мінором графа О, якщо він може
бути отриманий послідовним стягуванням ребер, тобто якщо існують графи Оп, ., О 2 і ребра е, є О такі, що О = О, О 2 = X, а О може бути
0 п-п 11 0 п-п 1
знайдений за допомогою (4). Слід відмітити, що кожен підграф графа є його мінором. Відповідно до теореми 1 та беручи до уваги наслідок 1, будь-який
мінор може бути отриманий спочатку видаленням вершин і ребер, а потім стягуванням ребер. І навпаки, будь-який г- чи п-дольний граф, отриманий
шляхом видалення та стягування, є мінором останнього. Але не всі мінори
п-дольного графа є п-пофарбованими.
З точки зору знаходження хроматичного числа лише мінори X представляють практичний інтерес. Тому, побудова п-мірних паттернів може бути зведена до знаходження такого графа Кп, який задовольняє умовам існування паттерну із заданим набором типів {И1,., Иі, ., Нп }:
Ф (Н) ФФ (Ну), і Ф і- (7)
З і, і / Ф (Иі) п Ф (Иу) Ф 0. (8)
Розглянемо можливість існування такого графа Кп, для якого справедливими є умови (7) та (8). Оскільки, граф Кп є мінором графа КЩ = О^ 2, то відповідно природним є питання отримання графа кщ із
його мінору К. Теоретично таке зворотне перетворення можливе, беручи до уваги теорему 1. Тому, іншим наслідком цієї теореми є зворотне перетворення графа.
Наслідок 2. Граф-зірка виду Кп може бути перетворений на п-дольний граф КЩ- хроматичне число новоутвореного графа буде дорівнювати п.
Нехай існує граф ОХ = Кп. За означенням зірки такий граф має 5 = п вершин. Здійснимо перетворення наступним чином. До кожної вершини додамо гілок у кількості п -1, які складаються із однієї вершини. У результаті отримаємо граф ОХ = (У& quot-, Е& quot-):
V& quot- = V и{х& quot-, х& quot-. },
7 (9)
Е & quot- = Е и{х& quot-, х& quot-},
1 & lt- і & lt- п 2 — п, 1 & lt- і & lt- п 2 — п. (10)
Або для кожної к-ої вершини графа ОХ можна записати так:
V& quot- (хк) = хк ^ хк+1. ^ хк +і ^ х'-к+і & gt-
хк єV, У к, 1 & lt- к & lt- п, (11)
1 & lt- і & lt- п -1, 1 & lt- і & lt- п -1, де х''к+і та X& quot-+у є вершинами гілок доданих до хк. Для кожної пари новоутворених вершин введемо ребра е& quot-:
ек = (хк-1+/,., хк+іX к =1,., п- 1 & lt-і & lt-п-1, 1 & lt-і & lt-п-1. (12)
Відповідно, оскільки вершини х^, хі+г та х^± є суміжними, то
перерозподіл вершин по класам (долям) Кп1,…, Кпп графа ОХ& quot- здійснюється наступним чином:
Кпк = {Хк1,…, Хк+і, Хк+і }- к = 1,…, п, 1 & lt-(і, і)& lt- п-1. (13)
Отже, отримано граф ОХ & quot- = КЩ. Хроматичне число такого графа становить х (ОХ& quot-) = п. Розглянемо приклад такого перетворення. Нехай задано граф-зірку К3, що зображений на рис. 1. Відповідно введемо позначення ОХ = К3. Виконуючи перетворення (9), (11), отримуємо граф ОХ із гілками, що зображений на рис. 2.
Л& quot-і+і+і
Рис. 2. Граф О Х, отриманий шляхом перетворення
Далі, виконуючи операції (10), (12), з'- єднуючи вершини сусідніх гілок отримуємо граф ОХ& quot- = К 3 (рис. 3).
Рис. 3. Граф О Х & quot- із з '- єднаними вершинами
Остаточно, перерозподіляючи вершини по класам (долям), отримаємо тридольний граф К3 із долями К& quot-1 = {хк1- хк+і, хк+1+^}, К& quot-2 = {хк, хк1+^,
хк+і+,}& gt- К& quot-3 = {хк+1& gt- хк+і & gt- хк1+г}-
Рис. 4. Тридольний граф К3, отриманий із мінору К3
Відповідно, хроматичне число обох графів буде дорівнювати трьом, тобто %(ОХ) = %(Ох& quot-) =3 • Операції (9) — (12) можна назвати реконструкцією я-дольного графа за його мінором Кп.
Зв'-язок я-дольних графів із паттернами полягає у наступному. Якщо задано я-дольний граф О = (У, Л) із набором вершин V = {иІ5и2,. и*.} та набором ребер, А = {а, а2, …, а}, для якого існує розбиття множини V на я класів. Нехай С = с1, с2, су} - набір кольорів, у які граф О може бути пофарбований:
С: V^{сі, с2, су}. (14)
Згідно із наслідком 1 існує мінімальний набір кольорів Р, у які граф О буде пофарбований. При цьому хроматичне число графа буде дорівнювати я.
Покажемо зв'-язок я-мірних паттернів із я-дольними графами. Нехай задано Л = {Х1Д, Х12, ., Xі п, ., Xп п } елементів, що утворюють я-мірний
паттерн. Якщо існує деякий набір типів К = {К1, К2, ., Кя }, які можна поставити у відповідність елементам паттерну, то всі елементи будуть класифіковані. Зв'-язок між однотипними елементами паттерну в межах даного класу виражається функціональною залежністю Ф (Кг). Тоді у загальному випадку задача побудови я-мірного паттерну зводиться до встановлення сукупності залежностей Ф (К) між усіма елементами, так що:
Л: КФ (К). (15)
Таким чином, співвідношення (15) можна трактувати як задачу пофарбування я-дольних графів.
У випадку накладання обмежень, проблема побудови я-мірних паттернів може бути сформульована як задача побудови я-мірного паттерну за заданими класами Ф (К) або їх відомими частинами.
З іншого боку, практичний інтерес представляє зв'-язок я-мірних паттернів із мінорами К я-дольних графів. Встановимо таку залежність на наступному прикладі.
Нехай задано інформаційно-графову структуру (c)(Я), де Я = {к1, к2, йу} є набором властивостей деякого об'-єкта, для якого побудовано інформаційно-графову структуру. Така структура є також я-мірним паттерном, що містить Л = {Х115 Х12,., Xіп,., Xпп } елементів, які
відповідають за певні властивості об'-єкта. При цьому залежність
Л: Н ^(c)(Я) (16)
встановлює однозначний зв'-язок між елементами інформаційно-графової структури та набором властивостей об'-єкту, для якої вона побудована:
Л: Я ^ {Xц (йу)}-
1 і і (17)
V/, V/ 1 & lt- (і,і) & lt-я, у = 1,|Н|.
Нехай також існує паттерн Ф (К), за допомогою якого можна розкласти інформаційно-графову структуру на шари (c)(Я) о Ф (К) =
= (c)1(Я1)^… ^(c)п (Нп) таким чином, щоб Я1 ^… = Ня = Я. Тобто розкладання паттерну (c)(Я) не призводило до виникнення нових властивостей об'-єкта, або:
(c)(Я): Ф (К) ^{X/(йу)}. (18)
Якщо такий паттерн Ф (К) існує, то кількість шарів, на які може бути розкладений паттерн (c)(Я) буде завжди однаковою при заданому наборі розкладаючих типів {К1, ., Кп } та дорівнюватиме я.
Це можна записати наступним чином:
(c)(Я)оф (к) = (c)(я)и (c)1 (Н)и. и (c)п (я) — я = 1,… ,|к|. (19)
Слід відмітити, що розкладання інформаційно-графової структури на шари не призводить до її зникнення, а навпаки вона зберігається в одному із шарів.
Далі, розкладаючи кожен із шарів на підшари, отримуємо наступні структури:
(c)(Я) о Ф (К) = (c)(Я) и (c)1(Я) и. и © п (Я) —
(c)1(Я) о Ф (К) = (c)1(я) и © і (Я) и. и © п (Я) —
(c)(Я) ¦
(c)1(Я) ф11 ф12 •• ф1п
© і (Я) о Ф (К) = ф 21 ф 22 •• ф 2п

© п (Я)_ _ф п1 ф п2. •• ф пп
© і (я) о Ф (К) = © і (я) и. и © я (Я).
Позначимо кожну нову структуру як ф/. Тоді (20) буде представляти собою комбінацію елементів ф -. У матричному вигляді можна записати:
(21)
Оскільки Ф (К) за умовою є таким паттерном, що не призводить до появи нових елементів у множині Я, то права частина рівняння (21) буде представляти собою також паттерн, для якого виконуються умови (7) — (8) і в якому класами є не елементи Xг¦7¦ (Ну), а інформаційні структури (c)і.
При цьому такий паттерн є гетерогенний, в якому існує залежність між структурами (c)і:
(c)(Я): Ф (К)П ((c)).
Тут П ((c)) є я-вимірним паттерном, який можна зобразити у вигляді матриці:
-(c)1 ©. … (c)¦
© … © ©,
П ((c)) =
(c)(c)
(c)
Таким чином, беручи до уваги (14) та (15), приходимо до висновку, що П ((c)) є пофарбуванням деякого я-дольного графа, у якому елементи ф// є
вершинами цього графа, а структури (©, (c)1,…, (c)і,…, (c)п) є класами
(долями) графа.
Такий узагальнений я-дольний граф зображено на рис. 5.
Оскільки кожен елемент у матриці із рівняння (21) є комбінацією шарів (c)(Я) ^(c)1(Н) и. и (c)г- (Я) и. и (c)п (Я), то можна записати наступну рівність:
(c)(Н)=Фы =-=ф"і- (c)1(Н) = Ф11 =Ф2и = - = Ф"2- (c)ДЯ)=фі2 = … = ф"".
(c)1
ф11 ф2п … фп2
Рис. 5. и-Дольний граф як графічне зображення п-мірного паттерну
Отже, отриманий граф може бути стягнутий у зірку виду К", у якій вершинами є відповідні шари паттерну (c)(Н), отримані шляхом його розкладу за допомогою Ф (К). Такий граф-зірка буде и-пофарбованим при п = |К|. Хроматичне число и-дольного графа та його мінору Кп дорівнює відповідно |К|. Мінор (граф-зірка) Кп зображено на рис. 6.
© = (c)(^і)
Рис. 6. Граф-зірка виду Кп, отриманий для паттерну (c)(Н)
Слід зазначити, що дана проблема потребує комплексного підходу. Частіше за все необхідно будувати паттерн Ф (К), маючи мінімальний набір типів. Потрібно розробити спеціальний універсальний алгоритм, який би дозволяв будувати паттерни виду Ф (К). Такий алгоритм повинен враховувати
особливості кодування розв'-язку та представлення паттерну у вигляді и-дольного графа. При побудові паттерну може виникати потреба в накладанні додаткових обмежень, окрім умов (7) — (8).
Висновки. Таким чином, проблема побудови n-мірного паттерну зведена до пофарбування n-дольних графів та їх мінорів виду Kn. Степінь вершин
графа визначає у кінцевому випадку множину оптимальних розв'-язків при побудові паттерну.
Отримані результати можуть бути використані при алгоритмічному підході побудови паттернів, які спрощують розв'-язання задач проектування обладнання для мобільного та радіозв'-язку, машинного планування розкладів, соціальної психології, оптимальному розподілу ресурсів.
Список літератури: 1. Glover F. A Template for Scatter Search and Path Relinking. School of Business, U.S. A: University of Colorado, Technical Report, 1998. — P. 3 — 54. 2. ArkinM., SilverbergB. Scheduling jobs with fixed start and end times // Discrete Applied Mathematics. — 1987. — 18. — P. 1 — 8. 3. de Wera D. Introduction to timetabling // European Journal of Operational research. — 1985. — 19. -P. 151 — 162. 4. Mikhail J. Atallan. Algorithms and Theory of Computation Handbook. U.S. A, New York: CRC Press, 1999. — 1312 P. 5. Valls V., Perez A., Quintanilla S. A graph colouring model for assigning a heterogeneous workforce to a given schedule // European Journal of Operational Research. -1996. — 90. — P. 285 — 302. 6. Byskov J.M. Enumerating maximal independent sets with applications to graph colouring // Operations Research Letters, 32 (2004). — Elsevier B.V. — 2004. — P. 547 — 556. 7. Karger D., Motwani R., Sudan M. Approximate graph coloring by semidefinite programming // J. ACM. — 1998. — V. 45. — № 2. — P. 246 — 265. 8. de KlerkE., PasechnikD. V. On approximate graph colouring and MAX-k-cut algorithms based on the-function // Journal of Combinatorial Optimization. -№ 8 (2004). — Netherlands: Kluwer Academic Publishers, 2004. — P. 169 — 185. 9. Pittel B. On the probable behavior of some algorithms for finding the stability number of a graph // Mathematical Proceedings of the Cambridge Philosophical Society. — 1982. — 92. — P. 511 — 526. 10. Дистель Р. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — 336 с.
УДК 519. 876. 5
Построение w-мерных паттернов как задача построения и раскраски w-дольных графов и их миноров / Скрыльник И. И. // Вестник НТУ «ХПИ». Тематический выпуск: Информатика и моделирование. — Харьков: НТУ & quot-ХПИ"-, 2008. — № 24. — С. 151 — 160.
В статье рассматривается проблема построения n-мерных паттернов. Решение этой задачи сводится к раскраске n-дольных графов и их миноров вида Кп. Доказано, что любой n-дольный граф может быть стянут в звезду вида Ки. Показана связь n-мерных паттернов с n-дольными графами, а также, что степень вершин графа определяет в конечном итоге множество оптимальных решений при построении паттерна. Ил.: 6. Библиогр.: 10 назв.
Ключевые слова: паттерн, минор, n-дольный граф, звезда, раскраска графа.
UDK 519. 876. 5
w-Dimensional patterns design as the problem of w-partite graph coloring and its minors / Skrylnik I.I. // Herald of the National State University & quot-KhPI"-. Subject issue: Information science and modelling. — Kharkov: NSU & quot-KhPI"-, 2008. — № 24. — P. 151 — 160.
The problem of n-dimensional pattern design is investigated. The resolving of this problem is regarded as the problem of n-partite graph coloring and its minor Kn. It is shown that any n-partite graph can be reduced to the graph-star Kn. The relationship between n-dimensional patterns and n-partite graphs is proved and it is shown that the vertex degree defines the range of optimal n-dimensional pattern constructions. Figs: 6. Refs: 10 titles.
Key words: pattern, minor, n-partite graph, graph-star, graph coloring.
Поступила до редакції 18. 04. 2008

ПоказатьСвернуть
Заполнить форму текущей работой