Наводиться характеризация двох класів гіперграфів: М-ациклических і деревовидних. Встановлено зв'язок між цими класами: гіперграф М-аціклічен тоді і тільки тоді, коли двоїстий до нього гіперграф є деревовидним. Цей зв'язок дає можливість об'єднати арсенал відомих поліноміальних алгоритмів, що дозволяють розпізнавати приналежність гіперграфу до зазначених класiв і будувати дерева з'єднань, дерева декомпозицій і дерева реалізацій гіперграфу.

Анотація наукової статті з математики, автор наукової роботи - Бикова Валентина Володимирівна


The characterization of two classes of hypergraphs: M-acyclic and tree has been given. The link between these two classes: a hypergraph is M-acyclic if and only if the hypergraph dual to it is a tree was established. This relationship provides an opportunity to join the arsenal of known polynomial algorithms allowing detecting hypergraph belonging to these classes and building the trees of compounds, decompositions and trees of hypergraph realization.


Область наук:

  • Математика

  • Рік видавництва: 2010


    Журнал: Известия Томського політехнічного університету. Інжиніринг ГЕОРЕСУРСИ


    Наукова стаття на тему 'М-ациклічні та деревовидні гіперграфах'

    Текст наукової роботи на тему «М-ациклічні та деревовидні гіперграфах»

    ?СПИСОК ЛІТЕРАТУРИ

    1. Романов В.Г. Зворотні задачі математичної фізики. - М .: Наука, 1984. - 264 с.

    1. Кабаніхін С.І. Зворотні і некоректні завдання. - Новосибірськ: Сибірське наукове видавництво, 2009. - 457 с.

    2. Атаманов Е.Р., Мамаюсупов М.Ш. Некласичні задачі для псевдопараболіческіх рівнянь. - Фрунзе: Ілім, 1990. -100 с.

    3. Пакір С. Зворотні задачі для псевдопараболіческіх рівнянь // Дослідження з інтегро-диференціальних рівнянь. - Бішкек: Ілім, 1994. - Вип. 25. - С. 49-53.

    4. Аблабеков Б.С. Зворотні задачі для псевдопараболіческіх рівнянь. - Бішкек: Ілім, 2001. - 180 с.

    5. Матанова К.Б. Про одну зворотній задачі для псевдопараболіческого рівняння // Наукові праці Ошгу. - Ош: Редакц.-изд. відділ «Билим», 1999. - Вип. 2. - С. 137-145.

    6. Матанова К.Б. Про існування і єдиності рішення однієї оберненої задачі // Зворотні і некоректні завдання математичної фізики: Докл. Міжнар. конф., посвящ. 75-річчя акад. М.М. Лаврентьєва, 20-25 серп. 2007 - Новосибірськ, 2007. - С. 137-145.

    7. Джураев Т.Д., СОПУ А. До теорії диференціальних рівнянь в приватних похідних четвертого порядку. - Ташкент: Фан, 2000. - 144 с.

    8. Асилбек Т.Д. Початково-крайові задачі для гіперболічних рівнянь четвертого порядку: Дис. ... канд. фіз.-мат. наук. 01.01.02. - Бішкек, 2002. - 121 с.

    9. Колмогоров А.Н., Фомін С.В. Елементи теорії функцій і функціонального аналізу. - М .: Наука, 1968. - 496 с.

    Надійшла 10.02.2010 р.

    УДК 519.17

    М-ациклічні та деревовидних гіперграфах

    В.В. Бикова

    Інститут математики Сибірського федерального університету, м Красноярськ E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Наводиться характеризация двох класів гіперграфів: М-ациклических і деревовидних. Встановлено зв'язок між цими класами: гіперграф М-аціклічен тоді і тільки тоді, коли двоїстий до нього гіперграф є деревовидним. Цей зв'язок дає можливість об'єднати арсенал відомих поліноміальних алгоритмів, що дозволяють розпізнавати приналежність гіперграфу до зазначених класiв і будувати дерева з'єднань, дерева декомпозицій і дерева реалізацій гіперграфу.

    Ключові слова:

    Реалізація гіперграфу деревом, дерево з'єднань гіперграфу, деревоподібна декомпозиція задач дискретної оптимізації, поліноміальні обчислення. Key words:

    Tree realization hypergraph, tree compounds hypergraph, tree decomposition of problem discrete optimization, polynomial computations.

    Вступ

    Теорія гіперграфів - один з розділів сучасної дискретної математики, що має велике прикладне значення. Дана теорія має групою завдань, що не мають аналогів в теорії графів і є в більшості своїй КР-важкими. До цієї групи завдань, зокрема, відносяться завдання пошуку для гіперграфу декомпозицій і реалізацій з заданими властивостями [1 -4]. Необхідність практичного вирішення цих завдань в умовах, коли розмірність задач велика, ставить питання про виділення класів гіперграфів, для яких вони полиномиально можна розв'язати. Такі класи, наприклад, утворюють М-ациклічні та деревовидні гіперграфах.

    Клас М-ациклических гіперграфів має низку цікавих властивостей. Основне з них - це існування для зв'язкового М-ациклического гіперграфу дерева з'єднань. Поняття дерева з'єднань було введено в роботі [4] і використано там для побудови монотонних планів з'єднань і програм повної редукції реляційних баз даних. Тим часом, подібні дерева (їх на-

    викликають деревами декомпозиції, деревами клік) широко вживають при вирішенні задач дискретної оптимізації методами локальної декомпозиції і динамічного програмування [2, 3]. Локальна оптимізація, здійснювана відповідно до деревом декомпозиції, дає можливість вирішувати багато КР-важкі завдання дискретного програмування з розрідженій матрицею обмежень за поліноміальний час [3].

    Каскадний гіперграф - гіперграф, для якого існує реалізація деревом. Деревоподібна реалізація відноситься до мінімальних (по числу ребер) реалізацій гіперграфу. Необхідність побудови мінімальних реалізацій з'являється, зокрема, при проектуванні інтегральних та вакуумних схем [1]. Доведено, що в загальному випадку задача пошуку мінімальної реалізації є КР-важкою [5], але в класі деревоподібних гіперграфів вона може бути вирішена за поліноміальний час [6-8]. Для деревовидних гіперграфів полиномиально можна вирішити є також завдання розпізнавання біхроматічності гіперграфу і можливості бути реалізованим гіперграфу на пло-

    скостити [9, 10]. Дана робота присвячена встановленню зв'язку між класами М-ациклических і деревовидних гіперграфів.

    Визначення необхідних понять

    Використовуємо термінологію і позначення, прийняті в [7-12]. Нехай заданий гіперграф H = (X, V) з кінцевим безліччю вершин X і ребер V. В загальному випадку V - кінцеве сімейство довільних підмножин безлічі X. При Х = 0 і Ц = 0, гіперграф Н = (0,0) вважається порожнім . Нехай щх)-безліч ребер, інцидентних в Н = (Х, Ц) вершині хех, а Х (і) - безліч всіх вершин, інцидентних в Н = (Х, V) ребру і е V. Число | V (х) | визначає ступінь вершини х, а число Х (і) | - ступінь ребра і. Елемент гіперграфу ступеня 0 вважають голим, ступеня 1 - висячим. Два ребра і, уе Vкратние в Н = (Х, Ц), якщо Х (і) = Х (у). Ребро вкладено і в ребро V, коли Х (і) сХ (\). Якщо | Х (і) | = 2 для кожного ІЄП і в V немає кратних ребер, то Н = (Х, Ц) - звичайний граф.

    Існують різні способи завдання гіперграфу. Так, довільний гіперграф Н = (Х, V) однозначно визначається родинами множин {Х (і) / ІЕЦ}, {Ц (х) / хех}. Якщо Х = {х1, х2, ..., х "}, і>1 і Ц = {и1, і 2, ..., ії}, т>1, то ( «, т) -гіперграф Н = (Х, Ц) однозначно описується матрицею інціденцій А (Н) = {А6}, де а ^ = 1 при х; БХ (і;) і а = 0 при х ^ Х (і) (/=1,2,...,і; у = 1,2, ..., т).

    Гіперграф Н * = (Х *, V *) з матрицею інціденцій А (Н *), отриманої Транспонированием матриці інціденцій А (Н) гіперграфу Н = (Х, Ц), називається двоїстим гіперграфах для Н. гіперграф Н * повністю зберігає відносини суміжності і інцидентності між елементами гіперграфу Н. Тому він успадковує всі його властивості, засновані на цих відносинах, і однозначно визначає Н.

    Універсальним способом завдання гіперграфу є кенігово уявлення. Кенігово уявлення гіперграфу Н = (Х, Ц) - це звичайний двочастковий граф К (Н), що відображає ставлення инцидентности різних елементів гіперграфу, з безліччю вершин хіп і частками Х, V. Очевидно, що К (Н) = К (Н *) . Багато структурні властивості гіперграфу визначаються через однойменні властивості кенігова уявлення. Так, гіперграф Н вважається зв'язковим, якщо зв'язний граф К (Н).

    Частково структурні особливості гіперграфу Н = (Х, V) описують асоціювання з ним звичайні графи Ц (2) (Н) і Ь (Н). Граф Ц (2) (Н) представляє відношення суміжності вершин, а граф Ц (Н) - відношення суміжності ребер гіперграфу Н. Граф Ь (Н) = (і, Е) вважають поміченим, якщо кожному його ребру {і;, і; } їЇ поставлена ​​у відповідність мітка - безліч / = Х (і,) ПХ (і) Ф 0. Число / розглядають як вага ребра {і;, і;}. Граф Ь (Н), для кожного ребра {і;, і;} якого вказана вага / = Х (і) ПХ (і) 1 називають зваженим ребровим графом гіперграфу Н.

    Серед безлічі структурних властивостей гіперграфів розрізняють симетричні і подвійні

    властивості. Властивість а симетричне, коли їм володіють (не володіють) гіперграфах Н і Н * одночасно. Властивості а і 3 називають подвійними, якщо з того, що Нпрісуще властивість а, виходить, що Н * задовольняє властивості 3, і навпаки, коли Н відповідає властивості 3, то Н * задовольняє властивості а.

    Позначимо через Н клас всіх непустих зв'язкових гіперграфів. Далі будемо розглядати гіперграфах тільки з цього класу. У цих умови: якщо Н = (Х, Ц) еН, то Н * = (Х *, Ц *) БН; Н = (Х, Ц) і Н * = (Х *, і *) не містять голих елементів; Ц (2) (Н), ЦН), Ц (2) (Н *), ЦН *) - зв'язкові графи.

    Характеризація М-ациклических гіперграфів

    Визначення М-ациклического гіперграфу засноване на понятті бесхордового циклу. Традиційно цикл гіперграфу Я визначають через простий цикл кенігова уявлення К (Н) [7, 11]. Тут вживається інше трактування цього поняття [4, 12]. Нехай заданий (і, т) -гіперграф Н = (Х, Ц) і деяка послідовність його ребер Р = (і'і2, ..., іьіт), 3<до<т. Використовуючи позначення / = Х (і;) ПХ (іт), /=1,2,...,к, цю послідовність можна представити як Р = (и1 / 1, і 2 / ь ..., ик / к , ик + 1). Послідовність Р задає в гіперграфах Н М-цикл (цикл по Д. Мейеру [4]) довжини до, якщо:

    • и1, і 2, ..., ик + 1 - різні ребра гіперграфу Н (різні як елементи сімейства V, при цьому не виключена наявність серед них кратних і вкладених ребер);

    • кожні два сусідніх ребра в Р суміжні, т. Е. / Ф 0 для будь-якого /=1,2,...,к;

    • / Ф / + для всякого /=1,2,...,к;

    • і = ши //

    Якщо все безлічі /х/2,.../к попарно різні, то Р - простий М-цикл гіперграфу Н. М-цикл Р = (и1, / 1, і 2, / 2, ..., ик, / к , ик + 1) вважається бесхордовим, якщо для будь-якої трійки множин //>/. (1<а<Ь<з<к) з Р в гіперграфах Я ні ребра і такого, що / аі / Ьч / Ссх (і). Коли хоча б для однієї трійки /// (1<а<Ь<з<к) таке ребро і існує в Н (і грає роль «хорди» і не обов'язково належить Р), то Р - хордові М-цикл гіперграфу Н. Цікаво, що бесхордовий М-цикл завжди простий. Гіперграф Н, який не містить бесхордових М-циклів, називається М-ациклічним [4, 12]. Зрозуміло, що якщо гіперграф М-аціклі-чен, то він або взагалі не містить М-циклів, або все його М-цикли хордові. Наявність бесхордового циклу призводить до М-циклічності гіперграфу.

    Всякий звичайний граф без циклів М-аци-клич, а з циклами - М-циклічний. Дійсно, в кожному простому циклі графа для довільної трійки множин / а / т / (1<а<Ь<з<к) обов'язково | / Аі / ьі / 1 = 3. Тим часом, будь-яке ребро графа містить тільки дві вершини. Таким чином, М-ациклічності не є прямим узагальненням теоретико-графового поняття «хордального», хоча є деяка аналогія. Нагадаємо, що

    звичайний граф називається хордального, якщо всякий його цикл довжиною до>4 володіє «хордою» -ребром, що з'єднує дві несуміжні вершини цього циклу [7].

    Зауважимо, що властивість М-ациклічності несиметрично: двоїстий гіперграф Н * = (Х, і) володіє або не володіє властивістю М-ациклічності незалежно від того, чи є М-ацікліче-ським відповідний йому гіперграф Н = (Х, і) . Це легко встановлюється за допомогою спеціально підібраних прикладів.

    М-ациклічності гарантує для гіперграфу багато бажані структурні властивості. Найбільш важливі з них - це успішне завершення алгоритму Грехема і існування дерева з'єднань. Цей факт констатує теорема 1.

    Теорема 1 [4]. Для довільного (п, т) -гіпер-графа Н = (Х, і) еН наступні висловлювання еквівалентні:

    1) Нявляется М-ациклічним гіперграфах;

    2) алгоритм Грехема завершується успішно;

    3) для Нсуществует дерево з'єднань;

    4) дерево з'єднань гіперграфу Н - остовное

    дерево найбільшої ваги зваженого реберного графа Ь (Н).

    Алгоритм Грехема [4] - елімінаційна схема послідовного застосування до гіперграфах операцій: СУВ - слабке видалення голих і висячих вершин (без видалення ребер, які їм інцидентні); СУР - слабке видалення кратних, вкладених ребер (без видалення вершин, які їм інцидентні). Позначимо через гвё (Н) гіперграф, отриманий в результаті застосування алгоритму Грехема до гіперграфах Н. Кажуть, що алгоритм Грехема для Н завершується успішно, якщо гвё (Н) = (0,0). Припустимо, що крок алгоритму зводиться до виконання однієї операції СУВ або СУР. Оскільки на кожному кроці вихідний гіперграф Н втрачає частину своїх елементів, тому число кроків алгоритму звичайно. Показано [4], що алгоритм Грехема завжди призводить до одного й того ж гіперграфах гвё (Н) незалежно від порядку і числа видаляються елементів на кожному кроці. Крім того, операції СУВ і СУР зберігають зв'язність гіперграфу. Все це свідчить про рекурсивном характер алгоритму Грехема і спадковості властивості М-ациклічності щодо операцій СУВ і СУР (всі гіперграфах, отримані з М-ациклического гіперграфу шляхом застосування до нього цих операцій також М-ациклічності).

    Алгоритм Грехема простий в реалізації і має поліноміальних тимчасову складність. Справді, найбільше число кроків алгоритму виникає в разі, коли операції СУВ і СУР усувають тільки один елемент гіперграфу. З огляду на, що трудомісткість одного кроку становить 0 (пт2), то для виконання алгоритму Грехема в гіршому випадку досить 0 [пт2 (т + п)] умовних одиниць часу. Таким чином, еквівалентність висловлювань 1) і 2) теореми 1 дає поліноміальний спосіб перевірки М-ациклічності гіперграфу.

    Еквівалентність висловлювань 1) і 3) теореми 1 встановлює полиномиально перевіряється необхідна і достатня умова існування дерева з'єднань: для гіперграфу Н = (Х, і) е Н дерево з'єднань існує тоді і тільки тоді, коли гіперграф Н є М-ациклічним. Наведемо визначення дерева з'єднань [4]. Нехай Ь (Н) = (і, Е) - реберний граф гіперграфу Н = (Х, і) Єні хех. Ланцюг Р = (і "і ++ 1, ..., і) графа ЦН), що випливає з вершини і в вершину і, називається х-ланцюгом, якщо хех (і,), хех (іт), ..., хех (і). Нехай Т] ои (Н) - кістяк графа Ц (Н) = (і, Е). Дерево Т] ои (Н) називається деревом з'єднань гіперграфу Н, якщо для будь-якої пари і "щеи і будь-якого хех (і) ГХ (і) ф0 в Т] ои (Н) існує х-ланцюг, що веде з и1 в і. Еквівалентність висловлювань 1) і 4) теореми 1 вказує поліноміальний спосіб знаходження дерева з'єднань за допомогою відомих теоретико-графових алгоритмів побудови максимального (мінімального) остова графа [7].

    Як приклад розглянемо гіперграф Низ роботи [7. С. 310]. Процес застосування до нього алгоритму Грехема наведено на рис. 1. Алгоритм завершується успішно, оскільки ке (Н) = (0,0). Значить, даний гіперграф М-аціклічен.

    Єдиний М-цикл Р = (і3 / 35, і 5/54, і4 / 43, і3) гіперграфу Н є хордових, т. К. / З5Ч / 54Ч / 4з = {х4} ^ {х4, х5} і {х4, х8} = {х4, х5, х8} = Х (і4). Цей цикл легко виявляється в реберном графі Ц (Н), зображеному на рис. 2. Остов найбільшої ваги графа Ц (Н) визначає дерево з'єднань Т ^ Н), ребра якого на рис. 2 відзначені пунктиром. Це одне з трьох можливих дерев з'єднань.

    Теорема 2 [9]. Гіперграф Н = (Х, і) еН М-аци-клич тоді і тільки тоді, коли він комплектний, а граф Ц (2) (Н) хордальний.

    Дана теорема характеризує М-ацікліче-ський гіперграф Н через структурні особливості асоційованих з ним графів Ц (2) (Н) і Ь (Н). Проаналізуємо спочатку властивість комплектності. Гіперграф Н = (Х, і) називають комплектним, якщо для будь-якого УеХ, що породжує в Ц (2) (Н) повний підграф, в Н існує ребро іси таке, що Усх (і) [11]. Очевидно, що всякий комплектний гіперграф не містить голих вершин. Властивість комплектності двояко по відношенню до властивості умові Хеллі. Цей факт доведений в роботі [11]. Кажуть, що гіперграф Н = (Х, і) має властивість Хеллі, якщо для будь-якого підродини його попарно суміжних ребер іси існує принаймні одна спільна вершина, инцидентная кожному ребру з і '. Так, гіперграф Н, рис. 1, комплектний і відповідає умові Хеллі (отже, Н * також комплектний).

    Нагадаємо деякі теоретико-графові поняття, які вживаються далі. Нехай заданий звичайний граф О = (У, Е). Клікою графа Про називають підмножину РСУ, в якому будь-які дві вершини суміжні, т. Е. Породжений підграф О (С) повний. Кліка максимальна, якщо вона не міститься ні в якій іншій кліці. Граф клік -

    Мал. 1. a) Вихідний гіперграф H. Процес застосування до H алгоритму Грехема: Ь) результат СУВ х, х2, xз, х6, x9; з) результат СУР і, ц, і 5; d) результат СУВ x5, х7; е) результат СУР і3; д) результат СУВ х4, х8

    >..........Л

    Мал. 2. Зважений реберний граф 1 (Н) гіперграфу Н з рис. 1

    граф перетинів всіх максимальних клік графа О (дві вершини суміжні в графі клік тоді і тільки тоді, коли відповідні їм максимальні кліки мають непорожнє перетин). Дерево клік - остовно підграф графа клік, що є деревом і задовольняє належному умові: для будь-яких його двох клік С;, С і всякої кліки Ск, що лежить на шляху з С1 в С виконується включення СПС / ОСК [7].

    На рис. 3 зображений граф Ь {2] (І) суміжності вершин гіперграфу Н з рис. 1. Граф клік для Ь {1) (І) представлений на рис. 4. Цей граф з точністю до нумерації збігається з реберним графом Ь (Н) (рис. 2). Зауважимо, сам гіперграф Нпрі цьому не містить кратних і вкладених ребер.

    Л ^ б Ху

    Мал. 3. Граф 1а) (Н) суміжності вершин гіперграфу Н з рис. 1

    Мал. 4. Граф клік для 1а (Н)

    Твердження 1. Якщо (і, т) -гіперграф Н = (Х, Ц) 1Н комплектуючі та в ньому немає кратних і вкладених ребер, то граф клік для Ь {1) (Н) ізоморфний реберному графу Ь (Н). У загальному випадку (при наявності кратних і вкладених ребер) має місце изоморфное вкладення графа клік в Ь (Н).

    Доведення. Справедливість першої частини твердження випливає безпосередньо з визначення комплектності гіперграфу: коли Нкомплек-тен і в ньому немає кратних і вкладених ребер, то кожною максимальною кліці С1 графа Ь {2] (Н) відповідає точно одна вершина ц реберного графа Ь (Н) і С = Х (і), 1</<т. Якщо тепер в гіперграф Н = (Х, і) вставити додаткове ребро ц таке, що Х (и]) Ох (і)) і ц е і, то це не призведе до зміни

    графа клік для Ь (2) (Н), а тільки додасть в Ь (Н) додаткову вершину, відповідну ребру і.

    Розглянемо гіперграф Н *, двоїстий до гіперграфах Н з рис. 1 Даний гіперграф комплектний (рис. 5). У ньому є кратні і вкладені ребра: і (х3) сі (х7), і (х1) = і (х2) = і (х6) сі (х7), і (х,) сР (х4), Ц (х5) сР (х4), і (х,) сР (х4), і (х9) сі (х5). Реберний граф Ь (Н *) гіперграфу Н * зображений на рис. 6. Остовне дерево найбільшої ваги графа Ь (Н *) задає дерево з'єднань гіперграфу Н *. Ребра одного з них на рис. 6 виділені пунктиром.

    Мал. 5. гіперграфах двоїстий до гіперграфах H з рис. 1

    міально перевіряється властивість гіперграфу;

    • граф клік для Ь (2) (Н) містить дерево клік, яке будується як кістяк найбільшої ваги графа клік [14];

    • завдання розпізнавання хордального будь-якого графа полиномиально можна вирішити [14]. Це вірно, зокрема, і для Ь (2) (Н). Твердження 2. Якщо в М-ациклічному гіперграфах Н = (Х, Ц) Ш немає кратних і вкладених ребер, то його дерево з'єднань ізоморфно деякому дереву клік для Ь (2) (Н). У загальному випадку (при наявності кратних і вкладених ребер) має місце изоморфное вкладення, т. Е. Для будь-якого дерева клік графа Ь (2) (Н) завжди знайдеться дерево з'єднань, в яке воно ізоморфно вкладено.

    Справедливість цього твердження випливає з хордального Ь (2) (Н) і еквівалентності визначень дерева з'єднань гіперграфу Н і дерева клік для Ь (2) (Н). Затвердження 2 враховує, що для гіперграфу може існувати кілька різних дерев з'єднань, точно також як і для графа клік - кілька різних дерев клік.

    Характеризація деревовидних гіперграфів

    Нехай заданий гіперграф Н = (Х, і) Ш .. деревоподібна реалізацією (реалізацією деревом) гіпергра-

    Мал.

    Зважений реберний граф L (H *) гіперграфу H *

    Граф Ь (2) (Н *) суміжності вершин гіперграфу Н * (рис. 7) містить тільки дві максимальні кліки С1 = {и1, і 2, і3 |, С2 = {і3, і4, і 5}, які відповідають в Ь (Н *) вершин х7, х4 відповідно. Таким чином, тут спостерігається изоморфное вкладення графа клік в реберний граф гіперграфу.

    Щ і 2 Щ

    Мал. 7. Граф L2) (H *) суміжності вершин гіперграфу H *

    Друга вимога теореми 2 - хордального графа Ь (2) (Н) - визначає ще ряд важливих характеристик:

    • Ь (2) (Н) = (Х, Е) має найбільше | Х | = і максимальних клік, і всі вони можуть бути знайдені за поліноміальний час [13]. Значить, коли граф Ь (2) (Н) хордальний, комплектність - Поліно-

    фа Н вважають будь-ациклический зв'язний граф МДА,; (Н) = (Х, Е) з безліччю вершин X і з безліччю ребер Е, що задовольняє умовам [6, 7]:

    • будь-яке ребро е = {х1, х2} їЇ міститься в деякому ребрі іеі гіперграфу Н;

    • для будь-якого ребра іеПподграф Тих (і), породжений безліччю Х (і), є зв'язковим. Гіперграф, для якого існує реалізація

    деревом, називають деревовидним. Необхідні і достатні умови існування древовидно-сти встановлює наступна теорема.

    Теорема 3 [6,7]. Для гіперграфу Н = (Х, і) Еh існує деревоподібна реалізація тоді і тільки тоді, коли Н = (Х, і) задовольняє властивості Хел-ли, а реберний граф Ь (Н) хордальний.

    З'ясуємо зв'язок між М-ациклічності і дере-вовідностью гіперграфу.

    Затвердження 3. Для довільного гіперграфу Н = (Х, і) і двоїстого до нього гіперграфу Н * = (Х, і *) справедливі рівності: Ь (2) (Н) = Ь (Н *), Ь (Н) = Ь (2) (Н *).

    Доведення. Безлічі вершин в графах Ь (2) (Н) = (Х, Е) і Ь (Н *) = (Х, Е *) збігаються. Таким про-

    разом, доказ співвідношення L (2) (H) = L (H *) зводиться до встановлення рівності множин E = E *. Справді, нехай {x, y} eE. За визначенням вершини x, y eX суміжні в L (2) (H), якщо H має ребро ие Uтакое, що x, yeX (u). Це означає, що ребро u інцидентне в H вершин x, y, т. Е. Ие U (x) і ueU (y). Звідси ueU (x) nU (y) ^ 0. Значить, L (H *) містить ребро {x, y} eE * і EcE *. Доведемо тепер зворотне включення. За визначенням графа L (H *) для довільного ребра {x, y} cE * вірно U (x) nU (y) ^ 0. Тоді для будь-якого ие U (x) nU (y) ^ 0 виконуються відносини приналежності: xeX (u), yeX (u). Отже, {x, y} eE і E * cE. Отже, E = E *. Рівність L (H) = L (2) (H *) двояко рівності L (2) (H) = L (H *). Таким чином, твердження 3 доведено.

    Справедливість твердження 3 ілюструють рис. 2, 3, 6, 7.

    Оскільки комплектність і властивість Хеллі -двойственние властивості гіперграфів, то з урахуванням затвердження 3 вірна наступне формулювання теореми 3.

    Теорема 4. гіперграфах H = (X, U) eH допускає деревоподібну реалізацію тоді і тільки тоді, коли двоїстий до нього гіперграф H * = (X *, U *) комплектний, а граф L (2) (H *) хордальний.

    У такому формулюванні критерій існування деревовидної реалізації (п, т) -гіперграфа легко перевіряється за допомогою алгоритму Грехема з тимчасової складністю O [nm2 (m + n)]. З теорем 2-4 випливає подвійність властивостей М-ацікліч-ності і деревовидних.

    Теорема 5. гіперграфах H = (X, U) eH M-аціклічен тоді і тільки тоді, коли двоїстий до нього гіперграф H * = (X *, U *) є деревовидним.

    Затвердження 4. Нехай гіперграф H = (X, U) eH і двоїстий до нього гіперграф H * = (X *, U *) деревовидний. Тоді будь-яке дерево з'єднань Tph (H) гіперграфу H є деревовидної реалізацією гіперграфу H *, і навпаки, будь-яка деревоподібна реалізація TJH *) гіперграфу H * - дерево з'єднань для H.

    СПИСОК ЛІТЕРАТУРИ

    1. Батищев Д.І., Старостін Н.В., Філімонов А.В. Багаторівнева декомпозиція гіперграфових структур // Інформаційні технології. Додаток. - 2008. - № 5. - С. 1-31.

    2. Журавльов Ю.А., Лосєв Г.Ф. Околиці в задачах дискретної математики // Кібернетика і системний аналіз. - 1995. -№2. - С. 32-41.

    3. Щербина О.А. Деревоподібна декомпозиція і завдання дискретної оптимізації (огляд) // Кібернетика і системний аналіз. - 2007. - № 4. - С. 102-118.

    4. Мейер Д. Теорія реляційних баз даних. - М .: Світ, 1987. - 608 с.

    5. Азаренка А.С., Сарванов В.І. Екстремальні реалізації гіперграфів // Доповіді АН БРСР. - 1986. - Т. 30. - № 10. -С. 887-889.

    6. Левін А.Г. Про побудову мінімальних реалізацій гіперграфів // Дискретна математика. - 1990. - Т. 2. - Вип. 3. - С. 102-114.

    7. Емелічев В.А., Мельников О.І., Сарванов В.І., Тишкевич Р.І. Лекції з теорії графів. - М .: Наука, 1990. - 384 с.

    8. Мельников О.І. Реалізації гіперграфу деревами мінімального діаметра // Дискретна математика. - 1997. - Т. 9. -Вип. 4. - С. 91-97.

    Доведення. За теорем 1, 5 гіперграф H є М-ациклічним і для нього існує дерево з'єднань Tjo! N (H). Покажемо, що Tjok (H) - деревоподібна реалізація для H *. Граф Tjoh (H) - кістяк графа L (H). За твердженням 3 L (H) = L (2) (H *), тому Tjoh (H) - кістяк графа L (2) (H *). Розглянемо довільне ребро {u, v} дерева Tjoh (H). Для нього, як ребра графа L (H), X (u) nX (v) ^ 0. Тоді в гіперграфах H * існує ребро xeX (u) rX (v) таке, що ue U (x) і ve U (x). Отже, ребро {u, v} дерева Tjoh (H) міститься в ребрі x гіперграфу H *. Тепер виберемо в H * довільне ребро x. Нехай Tjon (x) - підграф дерева з'єднань Tjoh (H), породжений безліччю U (x). Цей граф завжди зв'язний, т. Е. Будь-які дві його вершини u, ve U (x) з'єднані ланцюгом. Дійсно, за визначенням дерева з'єднань в Tjoin (H) існує x-ланцюг P, яка веде з u в v. Оскільки P є x-ланцюгом, то P повністю лежить в TjcJx). Всі вимоги, задані в визначенні деревовидної реалізації, виконані. Значить, Tjoh (H) = Trai (H *). Аналогічним чином доводиться і зворотний висловлювання затвердження 4.

    Дане твердження встановлює взаємно однозначну відповідність між безліччю різних дерев з'єднань гіперграфу H і безліччю різних деревовидних реалізацій двоїстого гіперграфу H *.

    висновок

    На підставі доведених вище теореми 5 і тверджень 1-4 можна сформулювати основний результат цієї роботи: М-ациклічності і гілки - подвійні властивості гіперграфу, при цьому будь-яке дерево з'єднань гіперграфу служить деревовидної реалізацією для двоїстого гіперграфу і навпаки. Це результат дозволяє застосовувати поліноміальний алгоритм Грехема для пошуку деревовидних реалізацій гіперграфу, точно також використовувати для знаходження дерев з'єднань всі відомі ефективні алгоритми побудови деревовидних реалізацій [5-8].

    9. Бикова В.В. Поліноміальні достатні умови біхрома-тичності гіперграфу // Вісник КрасГУ. Серія фіз.-мат. науки. - 2006. - № 7. - С. 98-106.

    10. Бикова В.В. Поліноміальні достатні умови можливості бути реалізованим гіперграфу на площині // Известия Томського політехнічного університету. - 2009. - Т. 314. - № 2. - С. 15-20.

    11. Зиков А. А. гіперграфах // Успіхи математичних наук. -1974.- Т. 29. - Вип. 6. - С. 89-154.

    12. Бикова В.В., Купріянова Т.В. Порівняльний аналіз M-аци-кліческіх і комплектних гіперграфів // Проблеми оптимізації та економічні програми: Тези доп. Міжнар. конф. - Омськ: Омська. держ. ун-т, 1997. - С. 31.

    13. Dirac G.A. On rigid circuit graphs // Anh. Math. Sem. Univ. Hamburg. - 1961. - № 25. - P. 71-76.

    14. Shibata Y. On the tree representation chordal graphs // J. Graph Theory. - 1988. - № 12. - P. 421-428.

    надійшла 01.02.2010р.


    Ключові слова: реалізація гіперграфу деревом /дерево з'єднань гіперграфу /деревоподібна декомпозиція задач дискретної оптимізації /поліноміальні обчислення /tree realization hypergraph /tree compounds hypergraph /tree decomposition of problem discrete optimization /polynomial computations

    Завантажити оригінал статті:

    Завантажити