Розкладання графів

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМ.В.М.ГЛУШКОВА

УДК 519.112

РОЗКЛАДАННЯ ГРАФІВ

01.05.01 - теоретичні основи інформатики та кібернетики

Автореферат

дисертації на здобуття наукового ступеня кандидата

фізико-математичних наук

ПРОТАСОВА Ксенія Дмитрівна

Київ 2006

Дисертацією є рукопис.

Робота виконана на кафедрі інформаційних систем факультету кібернетики Київського національного університету імені Тараса Шевченка.

Науковий керівник: Доктор фізико-математичних наук, професор Провотар Олександр Іванович, Київський національний університет імені Тараса Шевченка, завідувач кафедри інформаційних систем факультету кібернетики

Офiцiйнi опоненти:

Доктор фізико-математичних наук, професор Донець Георгій Панасович Інститут кібернетики НАНУ, завідувачвідділом 110 „Економічна кібернетика”

Доктор фізико-математичних наук, професор Банах Тарас Онуфрійович Львівський національний університет імені Івана Франка, кафедра геометрії і топології механіко-математичного факультету

Провідна установа: Дніпропетровський національний університет, м. Дніпропетровськ.

Захист відбудеться "__24_" __березня__ 2006 р. об (о) __12_ годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетики ім. В.М. Глушкова НАН України.

Автореферат розісланий "_14__" ___лютого___ 2006 р.

Вчений секретар спеціалізованої вченої ради Синявський В.Ф.

розкладність графа алгебраїчний

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми.

Розкладання графів - це спеціальні розбиття множин їх вершин. Проблематика розбиттів є досить традиційною в сучасній теорії графів. До неї відносяться, зокрема, хроматична теорія графів, Рамсеївська теорія графів, блочні декомпозиції, $H$ - декомпозиції, факторизаційна теорія, реалізації розбиттів графів. Вказані напрямки викладено в монографічній літературі, наприклад, Ф. Харарі "Теория графов", М. "Мир", 1973; R. Diestel "Graph Decomposition", Clarendon Press, Oxford, 1990; P.Грэхем "Начала теории Рамсея", М. "Мир", 1984. Спорідненими з теорією розбиттів графів є і деякі області інформатики, як от алгебраїчна теорія кодування. Серед вітчизняних науковців, що займалися розкладаннями графів, слід назвати Г. Донця, А. Петренюка, Т. Банаха, І. Протасова. Деякі загальні підходи до дослідження різних математичних конфігурацій (графи, числа, групи і т. д.) розглядалися в роботах О.І. Провотаря.

Кожне розбиття множини вершин графа природно ототожнити з деяким розфарбуванням цієї множини. В свою чергу, кожне розфарбування - це деяке відображення множини вершин у множину кольорів. А тому виникає класифікація розфарбувань за типом відповідних відображень. Ця класифікація дає чотири типи розфарбувань: ін'єктивні, сюр'єктивні, бієктивні (або калейдоскопічні) та невироджені. Точні означення подано далі у змісті роботи. Дослідження ін'єктивних розфарбувань - це по суті хроматична теорія графів, що почалася з проблеми чотирьох фарб і є яскравою сторінкою теорії графів. Дослідження невироджених розфарбувань - провідна тема в теорії Рамсея. Неформально, в теорії Рамсея доводиться, що при розбитті досить багатої комбінаторної структури хоча б одна з частин розбиття теж має нетривіальну комбінаторну структуру. Сюр'єктивні розфарбування систематично досліджувались в топології у зв'язку з розбиттями топологічних просторів на щільні підпростори (Е. Х'юїт, С. Шелах, Я. ван Міл, Є. Зеленюк, І. Протасов)

В інформатиці єдиною відомою калейдоскопічною конструкцією є коди Хемінга. Ці коди можна трактувати як калейдоскопічні розфарбування гіперкубів. А тому природно виникає задача поширити коди Хемінга на графи, відмінні від гіперкубів. Оскільки систематичних досліджень сюр'єктивних та калейдоскопічних розфарбувань графів не проводилось, тема дисертації видається актуальною.

Мета роботи.

Вказати способи розкладання графів, визначити або оцінити показники розкладності.

Дослідити калейдоскопічні графи - регулярні графи скінченного степеня, максимально розкладні відносно сім'ї куль одиничного радіуса, а також дослідити їх алгебраїчні супутники калейдоскопічні групи і напівгрупи.

Побудувати розкладання графів за допомогою узагальнених циклів і променів, дослідити клас квазігамільтонових графів.

Методи дослідження. Застосовуються розкладання графів за допомогою опірних дерев, незалежних множин, узагальнених циклів та інші.

Наукова новизна.

Розроблено нові методи розкладання графів: індуктивний, розкладання за незалежними множинами, розкладання за кістяками, трансверсальний спосіб, розкладання за узагальненими циклами та променями.

Доведено теорему про врівноважені розбиття графів.

Знайдено деякі необхідні та деякі достатні умови калейдоскопічності графів, вказано два способи побудови калейдоскопічних графів з використанням графів Келі груп.

Досліджено будову вільної калейдоскопічної групи та вільної калейдоскопічної напівгрупи, описано групу калейдоскопічних автоморфізмів Хемінгових графів.

Доведено квазігамільтоновість реберних графів, графів-розв'язок, графів інтервалів, графів Келі скінченних груп, описано квазігамільтонові дерева.

Введено нові поняття: врівноважені розбиття графів, калейдоскопічні графи.

Теоретичне та практичне значення. Результати дисертаційної роботи мають головним чином теоретичне значення. В роботі досліджені калейдоскопічні графи. Виникає задача поширити коди Хемінга на калейдоскопічні графи. Крім того, сюр'єктивні розфарбування систематично досліджуються в топології, а тому результати роботи в області дослідження сюр'єктивних та калейдоскопічних розфарбувань і визначення показників розкладності можуть бути застосовані в інших областях математики. В генетиці вивчаються графи інтервалів, які досліджувалися в роботі. Крім того, результати досліджень можуть бути використані в теорії ігор.

Апробація.

Четверта міжнародна алгебраїчна конференція в Україні, Львів, 2003 р.

Міжнародна Граве - конференція в Київському університеті, Київ, 2002 р.

Міжнародна конференція "Geometric Topology", Львів, 2004 р.

Міжнародна конференція "V International Algebraic Conference", Одеса, 2005 р.

XIV Міжнародна конференція "Проблемы теоретической кибернетики", Московський державний університет ім. М. В. Ломоносова, Пенза, 2005 р.

Семінари кафедри інформаційних систем Київського національного університету.

Семінар відділу 110 "Економічна кібернетика" в Інституті кібернетики імені В.М. Глушкова НАН України

Особистий внесок. Всі результати дисертації належать пошукачу.

Публікації. Всі основні результати дисертації опубліковані в [1], [2], [3], [4]. У співавторстві надруковано навчальний посібник [6], науково - популярна стаття про квазігамільтонові графи [5] та тези спільної доповіді на конференції [8]. Деякі результати дисертації включено також до монографії [Protasov I., Banakh T. Bаll Structures and Colorings of Groups and Graphs, Math. Stud. Monogr. Ser., V.11, 2003].

Структура та обсяг. Дисертація складається зі вступу, огляду основних результатів, трьох розділів, висновків та списку використаних джерел. Загальний обсяг -- 120 сторінок.

ЗМІСТ РОБОТИ

Для обґрунтування актуальності досліджень розкладань нам необхідно ввести деякі комбінаторні означення та позначення.

Нехай X довільна множина, деяка сім'я підмножин множини X, кардинал. Пара (X,) називається гіперграфом. Якщо сім'я двоелементних підмножин, гіперграф (X,) називається графом. Розфарбуванням множини X k кольорами називається сюр'єктивне відображення : X > k. Розфарбування називається

ін'єктивним, якщо звуження _F ін'єктивне для будь-якої підмножини F;

сюр'єктивним, якщо звуження _F сюр'єктивне для будь-якої підмножини F;

бієктивним або калейдоскопічним, якщо звуження _F бієктивне для будь-якої підмножини F;

невиродженим, якщо звуження _F не є константою для всіх підмножин F.

Сім'я називається калейдоскопічною, якщо множина X допускає калейдоскопічне розфарбування. Інші три типи розфарбувань приводять до таких кардинальних інваріантів гіперграфа (X,):

ж_sur () = sup { k : існує - сюр'єктивне розфарбування : X > k};

ж_inj () = min { k : існує - ін'єктивне розфарбування : X > k};

ж_non()=min { k : існує - невироджене розфарбування : X > k}. (кінець таблиці 1)

Якщо X не допускає -невироджених розфарбувань, ми вважаємо, що ж_non () = 1. Число ж_inj () природно назвати хроматичним числом гіперграфа (X,). Дійсно, для звичайного графа (X,) ж_inj () це найменше число кольорів, яких достатньо для розфарбування множини X вершин графа, такого що будь-які дві суміжні вершини графа різнокольорові. Визначення або оцінки хроматичних чисел графів один з центральних розділів теорії графів, значною мірою сформований проблемою чотирьох фарб.

Знаходження або оцінки чисел ж_non - провідна тема в теорії Рамсея. Про сюр'єктивні та калейдоскопічні розфарбування відомо значно менше. Найбільш систематично такі розфарбування досліджувались в топології, проте деякі відомі конструкції в інформатиці (наприклад, коди Хемінга) по суті є калейдоскопічними. Для того, щоб подати відповідну інтерпретацію, ми скористаємось комбінаторною термінологією, що виникла в топології.

Нехай (X,F) - гіперграф. Підмножину AX назвемо F - щільною, якщо AF для будь-якої підмножини F. Кожне - сюр'єктивне розфарбування ч : X k визначає розбиття X на k щільних підмножин { ч ^-1(): < k} і навпаки, кожне розбиття X на k щільних підмножин породжується деяким -сюр'єктивним k-розфарбуванням. Число ж_sur () назвемо показником розкладності (або просто розкладністю) гіперграфа (X, ).

Для зв'язного графа Gr(V,E) з множиною вершин V i множиною ребер E природно визначена метрика на множині його вершин, а отже і сім'я куль B_r(Gr) радіуса r. За означенням, підмножина A V має індекс r, якщо A щільна відносно сім'ї куль B_r(Gr) , а індекс ind A - це найменше число r, для якого підмножина A є щільною відносно B_r(Gr). t Розкладання графа Gr відносно сім'ї B_r(Gr) - це розбиття множини його вершин на підмножини індексу r.

Код Хемінга H_{n} - це деяка підмножина вершин гіперкуба G_n (яка існує тоді і тільки тоді, коли 2ⁿ ділиться на n+1). Гіперкуб G_n можна розглядати як граф з множиною вершин {0,1}ⁿ і множиною ребер між вершинами, що відрізняються одною координатою. В хроматичній термінології, для існування коду Хемінга H_n в G_n необхідно і достатньо, щоб існувало розфарбування множини вершин {0,1}ⁿ (n+1)-им кольором, таке що в кожній кулі одиничного радіуса існували вершини кожного кольору (і ця калейдоскопічна властивість істотно використовується як для кодування, так і для декодування). А тому ми приходимо до задачі дослідження калейдоскопічних графів як узагальнених кодів Хемінга. В кожному такому графі є деяка підмножина кодових вершин. Якщо по уявному каналу зв'язку передається одна з кодових вершин і при цьому гарантовано не більше одної помилки при прийомі (тобто замість кодової вершини може з'явитись деяка суміжна вершина), то калейдоскопічність графу дозволить виявити цей дефект і ліквідувати його.

Ми вкажемо ще на одну популярну в теорії графів тему, що виявилась пов'язаною з розкладністю. Якщо в графі Gr є гамільтонів цикл довжини n і r -- дільник числа n, то пофарбувавши вершини цього циклу періодично r -кольорами, ми отримаємо розкладання графу з досить гарними властивостями. Про гамільтонові графи написана не одна тисяча сторінок як в теоретичній, так і в прикладній інформатиці. Проте у відповідних текстах майже ніколи не зустрічається теорема про те, що куб кожного скінченного зв'язного графу є гамільтоновим.

Про квазігамільтонові графи відомо небагато. Відмітимо лише дуже нетривіальну теорему Флейшнера: кожен блок (= двозв'язний граф) квазігамільтонів. Оскільки квазігамільтоновість теж тісно пов'язана з розкладаннями, ці графи теж є одним з ключових об'єктів нашого дослідження. Для докладного викладу змісту роботи нам необхідні деякі означення і позначення.

Нехай Gr(V,E)граф з множиною вершин V і множиною ребер E. Ми розглядаємо лише графи без петель і кратних ребер. Візьмемо довільну підмножину UV і довільну підмножину ребер E E, кінці яких належать підмножині U. Граф Gr(U,E) називається підграфом графа Gr(V,E). Якщо E=E(U х U), тобто E містить усі ребра графа з кінцями в підмножині U, то граф Gr(U,E) називається індукованим підграфом графа Gr(V,E) і позначається Gr[U]. Кожен підграф Gr(V,E) графа r(V,E)$ називається його фактором. Фактор зв'язного графа, що сам є зв'язним графом, називається остовним фактором. Остовний фактор, що є деревом, називається кістяком} графа. Під деревом ми розуміємо зв'язний граф без циклів.

Нехай Gr(V,E) довільний граф, x,y V. Якщо вершини x,y належать до різних зв'язних компонент графа Gr(V,E), покладемо d(x,y)=?. Якщо вершини x,y лежать в одній зв'язній компоненті графа Gr(V,E), позначимо через d(x,y) довжину найкоротшого шляху від вершини x до вершини y. Таким чином визначена природна метрика на множині вершин зв'язного графа.

Для довільних вершини xV, підмножини AV і невід'ємного цілого числа m позначимо B(x,m) = {yV: d(x,y) m }, B(A,m) = a A B(a,m). Підмножини B(x,m) та B(A,m) називаються кулями радіуса m навколо вершини x та підмножини A. Позначимо через Bm(Gr) сім'ю усіх куль радіуса m з центрами в вершинах графа.

За означенням підмножина AV має скінченний індекс, якщо знайдеться таке невід'ємне ціле число m, що V=B(A,m). Найменше невід'ємне ціле число m, для якого справедлива ця рівність називається індексом підмножини A і позначається ind A. Очевидно, що ind A m тоді і тільки тоді, коли підмножина A перетинається з кожною кулею з сім'ї Bm(Gr).

Відстань Хаусдорфа dist (A,B) між будь-якими двома підмножинами скінченного індексу множини вершин графа Gr(V,E) визначимо такою формулою

dist (A,B)=max{max_aA min_bB d(a,b), max_bB min_{a A} d(a,b)}.

Зауважимо, що dist (A,B) ind A, dist (A,B) ind B. За означенням, розбиття P множини вершин графа Gr(V,E) має скінченний індекс, якщо знайдеться невід'ємне ціле число m, таке що ind P не перевищує m для всіх підмножин P розбиття P. Найменше невід'ємне ціле число m , для якого виконуються ці нерівності називається індексом розбиття P і позначається ind P . Очевидно, ind P не перевищує k тоді і тільки тоді коли кожна підмножина P, яка належить P, щільна відносно сім'ї куль радіуса k навколо всіх вершин графа.

Для невід'ємного цілого числа m назвемо m - розкладанням множини вершин графа Gr(V,E) розбиття множини вершин V індексу, який не перевищує m. Під m - розкладанням ми також будемо розуміти спосіб побудови відповідного розбиття.

Нехай Gr(V,E) граф, m невід'ємне ціле число. Припустимо, що граф допускає деяке m -розкладання. Позначимо через res (Gr,m) супремум |P| по всіх можливих m - розкладаннях P множини V . Очевидно, що res (Gr,m) не перевищує числа вершин в кожній кулі радіуса m . Зокрема, res (Gr,1) не перевищує числа с(Gr)+1 , де с(Gr) локальний степінь графа. При цьому локальний степінь (або просто степінь) вершини v це кількість ребер, що виходять з цієї вершини, а с(Gr)=min v V с(v).

Число res (Gr,m) називається числом розкладності (або розкладністю) графа Gr відносно сім'ї куль B m(Gr). Визначення або оцінка розкладності - одна з основних задач дисертації.

Більшість результатів дисертації подано у хроматичній термінології.

Нехай X, C довільні множини, |C|=k . Довільне сюр'єктивне відображення ч : X C називається k - розфарбуванням множини X з множиною кольорів C. Кожне k - розфарбування ч : X C задає розбиття множини X на k непорожніх підмножин

X= _{c C} ч ^-1(c).

Навпаки, кожне розбиття множини X= _бI X_б на непорожні підмножини можна ототожнити з |I| -розфарбуванням ч: X I , визначеним за правилом ч(x)=б тоді і тільки тоді, коли x X_б. Індексом розфарбування ч: V C множини вершин графа Gr(V,E) назвемо індекс відповідного розбиття

V= _{c C} ч ^-1(c).

Дисертаційна робота складається з трьох розділів. В роботі та авторефераті використовується двохіндексна нумерація результатів (перший індекс вказує на номер параграфу дисертаційної роботи, а другий - порядковий номер відповідного твердження.)

Перший розділ розбито на три параграфи. В $\S$1 запропоновано три способи розкладання графів: індуктивний спосіб, розкладання за кістяками, розкладання за незалежними підмножинами.

Індуктивний спосіб полягає в тому, що послідовно визначається деяка спеціальна нумерація множини вершин графа, а потім, спираючись на цю нумерацію, будується розкладання графу. Цим способом доведено таку теорему.

Теорема 1.1. Нехай Gr(V,E) зв'язний граф, r натуральне число, |V| r . Тоді існує r -розфарбування ч: V {1,2,...,r}, таке що кожна куля B(v, k) , vV , k{0,1,...,r-1} містить принаймні k+1 вершину, що пофарбовані різними кольорами.

Наслідком цієї теореми є нерівність res (Gr, r-1) r, за умови, що граф Gr зв'язний і має принаймні r вершин.

Підмножина Y множини вершин графа Gr(V,E) називається незалежною, якщо жодні дві різні вершини з Y несуміжні. Методом незалежних підмножин доведено такі теореми.

Теорема 1.2. Нехай Gr(V,E) зв'язний граф, r натуральне число. Якщо радіус графа Gr(V,E) більший за 2^r-1-1 , то множину вершин V можна розбити на підмножини V₁, V₂, ..., V_r+1 , такі що

ind V₁=1, ind V₂ 3, ..., ind V_i 2ⁱ-1, ..., ind V_r 2^r-1, ind V_r+1 2^r-1.

Теорема 1.3. Множину вершин будь-якого нескінченного зв'язного графа можна розбити на зліченне число підмножин скінченного індексу.

Для кожного нескінченного кардинала k вказано зв'язний граф Gr(V,E), такий що V=k, але множину вершин V не можна розбити на незліченне число підмножин скінченного індексу.

Теорема 1.5. Нехай Gr(V,E) - граф, m - натуральне число, k - деякий кардинал. Якщо кожна куля радіуса m в графі Gr(V,E) містить принаймні k вершин, то множину V можна розбити на k підмножин так, що індекс кожної підмножини розбиття не перевищує 3m.

Зокрема, якщо кожна одинична куля містить k вершин, то множину вершин V можна розбити на k підмножин індексу 3.

Теорема 1.6. Нехай Gr(V,E) граф, m₁, m₂,...,m_n натуральні числа. Припустимо, що кожна куля радіуса m_i містить щонайменше 2ⁱ вершин для всіх i{1,2,...,n}. Тоді множину вершин V можна розбити на підмножини V₁, V₂, ..., V_n так, що

ind V_i 2(m_i + 2m_i-1 + 2² m_i-2 +...+ 2^i-1 m₁) для всіх i{1,2,...,n} .

Теорема 1.7. Нехай Gr(V,E) - нескінченний граф, m₁, m₂,... - послідовність натуральних чисел. Припустимо, що кожна куля радіуса m_i містить принаймні 2ⁱ вершин для всіх натуральних чисел i. Тоді множину вершин V можна розбити на зліченне число підмножин V₁, V₂, ... так, що

ind Vi 2(m_i+2m_i-1+2² m_i-2+...+ 2^i-1m₁)

для всіх натуральних чисел i.

Теорема 1.7. стосується нескінченних графів. В параграфі 1 доведено ще три теореми, щодо розкладань нескінченних графів.

Теорема 1.4. Для кожного нескінченного зв'язного графа Gr(V,E) існує розфарбування ч : V , таке що | ч (B(x,k)) | k+1 для всіх x V, k .

Теорема 1.8. Нехай Gr(V,E) - нескінченний граф, k - граничний кардинал, |V|=k. Припустимо, що для кожного кардинала k<k знайдеться натуральне число m, таке що кожна куля радіуса m має принаймні k вершин. Тоді множину вершин V можна розбити на k підмножин скінченного індексу.

На прикладі показано, що умова граничності кардинала k є істотною. Граф Gr(V,E) називається k-регулярним (k -деякий кардинал), якщо з кожної вершини графа V виходить рівно k ребер, тобто с(v)=k для всіх vV. Регулярні графи інколи називаються однорідними.

Теорема 1.9. Нехай k - нескінченний кардинал, Gr(V,E) - k-регулярний граф. Тоді множину вершин V можна розбити на k підмножин індексу 1.

В параграфі 2 першого розділу вивчаються врівноважені розкладання. Поняття врівноваженості досить природне, якщо множина вершин графа скінченна. Нехай X - скінченна множина, X=n, r - натуральне число, r<n. Тоді число n однозначно подається у вигляді n=rs+t, де t - остача від ділення n на r. Розбиття множини X на r підмножин назвемо врівноваженим, якщо існує така нумерація

X₁,X₂,..., X_t,X_t+1,...,X_r

Підмножин розбиття, для якої

|X₁|=|X₂|=...= |X_t|=s+1, |X_t+1|=|X_t+2|=...=|X_r|=s.

Зокрема, якщо r - дільник числа n, то r-врівноважене розбиття множини X - це розбиття X на r частин одної потужності. В хроматичній термінології, розфарбування множини X називається врівноваженим, якщо відповідне розбиття множини X є врівноваженим.

За теоремою 1.1, для кожного скінченного зв'язного графа Gr(V,E) і кожного натурального числа r |V|, існує r-розфарбування множини V індексу r-1. Як показують прості приклади, наведені в параграфі 2, побудувати врівноважені розфарбування, що задовольняють теорему 1.1, взагалі кажучи, неможливо.

Основним результатом параграфа 2 (і, можливо, дисертації в цілому) є така теорема.

Теорема 2.1. Для будь-яких натуральних чисел r, n , r n і довільного зв'язного графа Gr(V,E) , |V|=n , існує врівноважене r - розбиття індексу r множини V .

Ця теорема неочевидна і для тріодів - дерев з кореня яких відходить 3 променя. Доведення теореми 2.1 складається з п'яти лем і ілюструє спосіб розкладання графів за допомогою їх кістяків.

Застосуємо теорему 2.1 до врівноважених розбиттів груп. Нехай G - скінченна група з одиницею e, S - система твірних групи S, |S|=r, S^-1=S, e S. З теореми 2.1 випливає таке твердження.

Теорема 2.2. Існує врівноважене розбиття G=A₁ A₂ ... A_r, таке що G=A_i S^r для всіх i{1,2,...,r}.

Для того, щоб вивести теорему 2.2 з теореми 2.1 застосовуються графи Келі груп.

Нехай G - довільна група з одиницею e, S - деяка підмножина групи G, причому eS, S^-1=S. Множиною вершин графа Келі Cay(G,S) групи G, визначеному підмножиною S, є множина G, а дві вершини g₁, g₂ пов'язані ребром тоді і тільки тоді, коли g₁^-1 g₂ S, g₁g₂. Очевидно, що граф Келі Cay(G,S) зв'язний тоді і тільки тоді, коли S - система твірних групи G.

Якщо S - підгрупа групи G, то вказати врівноважене розбиття, що задовольняє теорему 2.2 просто - кожен лівий суміжний клас G за підгрупою S пофарбуємо кольорами $1,2,...,r і позначимо через A₁,A₂,...,A_r підмножини кольорів 1,2,...,r. А тому, теорему 2.1 можна розглядати як деякий графовий аналог теореми Лагранжа.

Для r=2 теорема 2.1 посилюється таким твердженням.

Теорема 2.3. Нехай Gr(V,E), - скінченний зв'язний граф, |V|=n, n 2. Тоді існує врівноважене розбиття V=V₁ V₂, таке що ind V₁=1, ind\ V₂ 2.

Далі в параграфі 2 запропоновано три підходи до означення врівноваженості розбиття вершин нескінченного зв'язного графа. Ми опишемо лише один з цих підходів.

Нехай Gr(V,E) - зліченний зв'язний граф. Послідовність (A_{n})_{n\in\omega} скінченних підмножин множини V вершин графа Gr(V,E) назвемо покривною, якщо

(i) V=_nA_n;

(ii) A_n\subset A_m, якщо n m;

(iii) кожен індукований підграф Gr[A_n], n є зв'язним.

Зафіксуємо деяку покривну послідовність (A_n) _n множини вершин зліченного зв'язного графа Gr(V,E). Візьмемо довільну підмножину BV і розглянемо послідовність (p_n(B)) _n, визначену так p_n(B)=|B А_n| / | А_n |.

Якщо ця послідовність має границю, то ця границя p(B) називається щільністю підмножини B відносно покривної послідовності (A_n) _n.

У загальному випадку, верхня та нижня щільності підмножини BV відносно покривної послідовності (A_n) _n. визначається як lim{n\rightarrow \infty}\sup p_{n}(B), lim_{n\rightarrow \infty}inf p_{n}(B).

Отже, підмножина BV має щільність відносно покривної послідовності (A_n) _n тоді і тільки тоді, коли \lim_{n\rightarrow \infty}\sup p_{n}(B)=\lim_{n\rightarrow \infty}\inf p_{n}(B).

Розбиття V=V_{1} V_{2} ... V_{n} множини вершин зліченного зв'язного графа Gr(V) назвемо врівноваженим відносно покривної послідовності (A_n) _n , якщо кожна підмножина розбиття має щільність і p(V₁)=p(V₂)=...=p(V_r)=\frac{1}{r}.

Теорема 2.4. Для кожного зв'язного локально скінченного графа Gr(V,E) і кожного натурального числа r, |V| 2, існує розбиття індексу r множини V на r підмножин, врівноважене відносно деякої покривної послідовності скінченних підмножин множини V.

Відкритим залишається таке запитання. Нехай Gr(V,E) - локально скінченний зв'язний граф, x_{0} V і A_{n}=B(x_{0},n), n. Чи для кожного натурального числа r існує r-розбиття V=V_{1}V_{2}...V_{r} множини V, врівноважене відносно покривної послідовності (A_n) _n?

В параграфі 3 досліджуються врівноважені розбиття орієнтовних графів.

Нехай Gr(V,E) - граф з множиною вершин V і множиною орієнтовних ребер E V ^х V. Знову ж, вважаємо, що граф Gr(V,E) не має петель і кратних орієнтовних ребер. Для довільних вершини xV, підмножини AV і невід'ємного цілого числа покладемо \overrightarrow{B(x,m)}={y V: iснує орієнтовний шлях довжини m від x до y}, \overleftarrow{B(x,m)}={y V: iснує орієнтовний шлях довжини m від y до x}.

\overrightarrow{B(A,m)}= _{a\in A}\overrightarrow{B(a,m)},

\overleftarrow{B(A,m)}= _{a\in A}\overleftarrow{B(a,m)}.

В цих позначеннях враховується, що x\in \overrightarrow{B(x,m)}, x\in \overleftarrow{B(x,m)} для всіх x\in V, m\in\mathbb{N}{0}.

В цьому параграфі доведено дві теореми.

Теорема 3.1. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття V=V_{1}\cup V_{2}, таке що \overleftarrow{ind \ V_{1}}=1, \ \ \overleftarrow {ind V_{2}}\leq 2.

Теорема 3.2. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття множини вершин $V=V_{1} V_{2}$, таке що \overrightarrow{ind \ V_{1}}=1, \ \ \overleftarrow{ind V_{2}}\leq 2.

Ці дві теореми застосовуються для побудови спеціальних розбиттів напівгруп. В другому розділі вивчаються регулярні графи, максимально розкладні відносно множини куль одиничного радіуса. Розділ складається з двох параграфів 4 і 5.

Для натурального числа s s -регулярний граф Gr(V,E) називається калейдоскопічним, якщо множину V його вершин можна розбити на s+1 множин індексу $\leq 1$. Іншими словами, регулярний граф скінченного степеня s називається калейдоскопічним, якщо множину його вершин можна пофарбувати s+1 кольорами так, що кожна куля одиничного радіуса містить вершини усіх s+1 кольорів. Правильний n-кутник (як граф) є калейдоскопічним тоді і тільки тоді, коли n ділиться на 3. Серед п'яти платонових графів калейдоскопічними є лише тетраедр, куб і ікосаедр.

Для того, щоб з'ясувати калейдоскопічність узагальнених призм, ми вводимо спеціальні циркулянти.

В параграфі 4 запропоновано два загальні способи побудови калейдоскопічних графів, що використовують графи Келі груп.

Опишемо лише один з них.

Нехай G -- група з одиницею e, S\subseteq G, S^{-1}=S, eS. Пара (S,Y) підмножин групи G називається калейдоскопічною, якщо eY і G=SY,

SSY^-1Y=SS YY^-1={e}.

Теорема 4.1. Якщо (S,Y) -- калейдоскопічна пара в групі G, то граф Келі Cay(G,S) калейдоскопічний.

Теорема 4.2. Нехай G - група з одиницею e, s - натуральне число,

S G, e S, S=S^-1, |S |=s

і S - система твірних групи G. Припустимо, що граф Келі Cay(G,S) допускає калейдоскопічне розфарбування i покладемо Y={g G: ч(g)= ч (e)}. Тоді (S,Y) -- калейдоскопічна пара в групі G.

Калейдоскопічна пара (S,Y) називається Хемінговою парою, якщо Y - підгрупа групи G. Це означення обґрунтовується в прикладі 4.6, в якому коди Хемінга пов'язуються з калейдоскопічністю.

Для кожної калейдоскопічної пари (S,Y) групи G визначається стандартне калейдоскопічне розфарбування графа Cay(G,S).

Теорема 4.3. Нехай (S,Y) -- калейдоскопічна пара в групі G, ч -- стандартне калейдоскопічне розфарбування графа Келі Cay(G,S). Тоді такі два твердження рівносильні:

(i) (S,Y) - Хемінгова пара;

(ii) якщо g₁ g₂ G, s S і ч (g₁)= ч (y₂), то ч (s g₁)= ч (s y₂).

Закінчується параграф 4 такою теоремою.

Теорема 4.4. Для довільної скінченно породженої групи H знайдеться скінченно породжена група G з Хемінговою парою (S,Y), така що підгрупа Y ізоморфна H.

Доведено також, що в кожній Хемінговій парі (S,Y) підгрупа Y має бути скінченно породженою.

В параграфі 5 вивчаються калейдоскопічні напівгрупи, групи і автоморфізми.

Нехай s - натуральне число, s>1, Gr(V_{1},E_{1}), Gr(V_{2},E_{2}) - калейдоскопічні графи степеня s, \chi_{1}: V_{1}\longrightarrow\{0,1,...,s\}, \chi_{2}: V_{2}\longrightarrow\{0,1,...,s\} - їх калейдоскопічні розфарбування. Сюр'єктивне відображення f: V_{1}\longrightarrow V_{2} називається калейдоскопічним гомоморфізмом, якщо

(i) \chi_{1}(x)=\chi_{1}(f(x)) для всіх вершин x\in V_{1};

(ii) якщо (x,y)\in E_{1} то (f(x), f(y))\in E_{2}.

Регулярне дерево Tr(V,E) степеня s з визначеним калейдоскопічним розфарбуванням \chi: V\longrightarrow\{0,1,...,s\} називається вільним калейдоскопічним деревом степеня s.

Теорема 5.1 Нехай Tr(V,E) - вільне калейдоскопічне дерево степеня s з калейдоскопічним розфарбуванням \chi: V\longrightarrow\{0,1,...,s\}, Gr(V^{\prime},E^{\prime}) - довільний калейдоскопічний граф степеня s з калейдоскопічним розфарбуванням \chi^{\prime}: V^{\prime}\longrightarrow\{0,1,...,s\}. Тоді існує калейдоскопічний гомоморфізм f: V\longrightarrow V^{\prime}.

Ця теорема означає, що кожен калейдоскопічний граф можна отримати факторизацією (або склеюванням) ребер вільного калейдоскопічного дерева.

Нехай s - натуральне число, s>1, X=\{0,1,...,s\}. Калейдоскопічна напівгрупа KS(X) в алфавіті X - це напівгрупа, визначена співвідношеннями xx=x, xyx=x для всіх x,y\in X. Напівгрупу KS(X) можна розглядати як множину усіх непорожніх слів в алфавіті X без факторів xx, xyx. Для кожного x\in X позначимо через KS(X,x) множину усіх слів, що починаються і закінчуються літерою x. Ця підмножина є підгрупою KS(X) і називається калейдоскопічною групою. Показано, що калейдоскопічна напівгрупа KS(X) діє транзитивно на множині вершин калейдоскопічного графа степеня s, а калейдоскопічна група діє транзитивно на підмножині вершин кольору x.

Теорема 5.2. Калейдоскопічна група KS(X,x) є вільною групою з множиною вільних твірних}

W=\{xyzx:yz\in X, \ x\neq y, \ x\neq z, \ y\neq z\}.

Теорема 5.3. Калейдоскопічна напівгрупа KS(X) ізоморфна сендвіч-добутку L(x)\times KG(X,x)\times R(x) в якому множення визначається за правилом

(l_{1}, g_{1}, r_{1})(l_{2}, g_{2}, r_{3})=(l_{1}, g_{1} \varphi(r_{1}, l_{2})g_{2},r_{2}), \noindent де} \varphi(r_{1}, l_{2})=r_{1} l_{2}.

Теорема 5.4. Група калейдоскопічних автоморфізмів вільного калейдоскопічного дерева степеня s ізоморфна вільній групі KG(X,x), де X=\{0,1,...,s\}, x\in X.

Теорема 5.5. Нехай G - група з Хемінговою парою (X,Y). Тоді група калейдоскопічних автоморфізмів графа Cay(G,X) ізоморфна Y.

Теорема 5.6. Кожна скінченно породжена група ізоморфна групі клейдоскопічних автоморфізмів деякого Хемінгового графа.}

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

Нехай Gr(V,E) гамільтонів граф з гамільтоновим циклом v1, v2,...,vn. Візьмемо довільний дільник r числа n і пофарбуємо вершини кольорами 1,2,...,r періодично зліва направо. Позначимо через Vi множину усіх вершин кольору i, i{1,2,...,r}. Одержимо врівноважене розбиття V= V1 V2 ... Vr індексу, який не перевищує r/2. Таким чином, для гамільтонових графів теорему 2.1 можна істотно посилити. Зрозуміло, що не в кожному скінченному зв'язному графі є гамільтонів цикл. Але в кожному скінченному зв'язному графі є "цикл коника", тобто нумерація v_{1}, v_{2},..., v_{n} множини вершин V, така що d(v_{1}, v_{2})\leq 3, d(v_{2}, v_{3})\leq 3,..., d(v_{n-1}, v_{n})\leq 3, d(v_{n}, v_{1})\leq 3.

Послідовність (x_n)_n різних вершин нескінченного зв'язного графа називається квазіпроменем, якщо d(x_n, x_n+1) 3 для всіх n. Граф, що має квазіпромінь, який проходить через усі його вершини, називається квазіпроменевим графом (скорочено qr -графом). Кожен нескінченний зв'язний граф розкладається на qr -графи. Це розкладання застосовується для побудови розбиттів скінченного індексу.

Для нескінченного зв'язного графа Gr(V,E) позначимо через U(Gr) множину вершин скінченного степеня і покладемо W(Gr)=V\backslash U(Gr).

В параграфі 6 вивчаються квазіпроменеві графи.

Теорема 6.2. Нехай Gr(V,E) - qr-дерево з непорожньою множиною W(Gr). Тоді підграф Gr[W(Gr)] зв'язний, а кожна зв'язна компонента графа Gr[U(Gr)] скінченна.

Теорема 6.3. Для довільного зліченного зв'язного графа G існує qr-граф Gr(V,E), такий що підграф Gr[W(Gr)] ізоморфний G. Якщо граф G - дерево, то за граф Gr(V,E) теж можна взяти деяке дерево.

Теорема 6.4. Нехай Tr(V,E) - зліченне дерево, W(Tr)={w}. Дерево Tr(V,E) має квазіпромінь, що проходить через усі його вершини тоді і тільки тоді, коли після вилучення вершини w дерево розпадається на скінченні дерева.

Для формулювання основного результату параграфу параграфі 6 потрібні додаткові позначення.

Нехай Tr(V,E) - дерево з виділеним коренем x. Розглянемо множину U_{x} цих вершин скінченного степеня, суміжних з вершиною x. Для кожної вершини y\in U_{x} позначимо через T_{y} дерево з коренем y, одержане вилученням ребра (x,y).

Теорема 6.5. Нехай Tr(V,E) - зліченне дерево, W - множина усіх вершин нескінченного степеня. Припустимо, що \mid W \mid\geq 2 і граф Gr[W]$ локально скінченний. Дерево Tr(V,E) є qr-графом тоді і тільки тоді, коли виконуються такі умови:

(i) граф Gr[W] зв'язний;

(ii) для кожної вершини x\in W множина \{T_{y}: y\in U_{x}\}

складається із скінченних дерев;

(iii) для кожної вершини $x\in W$ множина $\{T_{y}: y\in U_{x}\} містить нескінченну підмножину одноелементних дерев або нескінченну підмножину дерев, кожне з яких T_{y} має кінцеву вершину, суміжну з коренем} y.

В параграфі 7 вивчаються квазігамільтонові графи. Скінченний зв'язний граф Gr(V,E) називається квазігамільтоновим, якщо існує нумерація x₁, x₂, ..., x_n множини його вершин, така що d(x₁, x₂) 2, d(x₂, x₃) 2, ..., d(x_n-1, x_n) 2, d(x_n , x₁) 2. Про квазігамільтонові графи відомо небагато. Відмітимо лише дуже нетривіальну теорему Флейшнера: кожен блок квазігамільтонів. Оскільки квазігамільтоновість теж тісно пов'язана з розкладаннями, ці графи теж є одним з ключових об'єктів нашого дослідження.

Характеризацію квазігамільтонових дерев дає така теорема.

Теорема 7.1. Скінченне дерево Tr(V,E) є квазігамільтоновим тоді і тільки тоді, коли існує такий шлях x₁, x₂,...,x_d в дереві, після вилучення якого дерево розпадається на ізольовані вершини.

Далі доводяться деякі достатні ознаки квазігамільтоновості, перша з яких є аналогом теореми Дірака про гамільтонові графи.

Теорема 7.2. Нехай Gr(V,E) скінченний зв'язний граф, |V|=n. Якщо |B(x,2)| n:2+1 для будь-якої вершини x V, то граф Gr(V,E) є квазігамільтонів.

Ще дві теореми доведено з застосуванням нової конструкції з'єднання скінченного набору графів за деяким деревом.

Теорема 7.3. Реберний граф будь-якого скінченного зв'язного графа квазігамільтонів.

Теорема 7.4. Граф розв'язок будь-якого скінченного зв'язного графа квазігамільтонів.

Теорема 7.5 Зв'язний граф інтервалів квазігамільтонів.

Теорема 7.6. Граф Келі будь-якої скінченої групи квазігамільтонів.

Завершується параграф 7 теоремою, що характеризує дерева з квазігамільтоновим шляхом. Впорядкована послідовність v_{1}, v_{2},...,v_{n} множини V вершин зв'язного графа Gr(V,E) називається квазігамільтоновим шляхом, якщо d(x_{1},x_{2})\leq 2, d(x_{2},x_{3})\leq 2, ...,d(x_{n-1},x_{n})\leq 2.

Введено дві операції (операція A і операція B) приєднання дерев.

Теорема 7.7. Скінченне дерево Tr(V,E) має квазігамільтонів шлях тоді і тільки тоді, коли Tr(V,E) є квазігамільтоновим древом або Tr(V,E) можна одержати з деякого квазігамільтонового дерева послідовним застосуванням операцій A, B приєднання квазігамільтонових дерев.

ВИСНОВКИ

Розроблено нові методи розкладання графів: індуктивний, розкладання за незалежними множинами, розкладання за кістяками, трансверсальний спосіб, розкладання за узагальненими циклами та променями.

Доведено теорему про врівноважені розбиття графів.

Знайдено деякі необхідні та деякі достатні умови калейдоскопічності графів, вказано два способи побудови калейдоскопічних графів з використанням графів Келі груп.

Досліджено будову вільної калейдоскопічної групи та вільної калейдо-скопічної напівгрупи, описано групу калейдоскопічних автоморфізмів Хемінгових графів.

Доведено квазігамільтоновість реберних графів, графів розв'язок, графів інтервалів, графів Келі скінченних груп, описано квазігамільтонові дерева.

Введено нові поняття: врівноважені розбиття графів, калейдоскопічні графи.

ОСНОВНІ РЕЗУЛЬТАТИ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО В ПРАЦЯХ

[1] Протасова К.Д. Врівноважені розбиття графів // Доповіді НАН України. - 2003. - № 6.- с. 21-25.

[2] Протасова К.Д., Квазігамільтонові графи // Вісник Київського ун-ту. - 2003. - №1. - с. 45-50.

[3] Protasova K.D. Kaleidoscopic graphs // Matem. Stud., - 2002. - №18. - р. 3-9.

[4] Protasova K.D. On Square-Hamiltonian Graphs // Algebra and Discrete Math. - 2005. - №3. - р. 56-59.

[5] Протасов I.В., Протасова К.Д. Про коника - стрибунця і теорію графів // У світі математики. - 2005. - №3. - Том. 11. - р. 1- 4.

[6] Протасов I.В., Протасова К.Д. Розкладність графів: Навчальний посібник. - Київ: Видавничо-поліграфічний центр "Київський університет" - 2003. - 72 c.

[7] Protasova K.D. Balanced partitions of graphs // Міжнародна матем. конф. присвячена сторіччю від початку роботи Д.О.Граве в Київському ун-ті. - Київ. - 2002.- с. 42-43.

[8] Protasov I.V., Protasova K.D. Around Grasshopper Theorem // Четверта міжнародна алгебраїчна конф. В Україні. - Львів. - 2003. - с. 183-185.

[9] Protasova K.D. On the coloring graph games // Четверта міжнародна алгебраїчна конференція в Україні. - Львів. - 2003. - с. 186-187.

[10] Protasova K.D. Automorphisms of kaleidoscopic graphs // International Conference "Geometric Topology". - Lviv.- 2004.- р. 56-57.

[11] Protasova K.D. Partitions of graphs // П'ята міжнародна алгебраїчна конференція в Україні. - Odessa. - 2005. - c. 163.

[12] Protasova K.D. Уравновешенные разбиения графов // XIV Міжнародна конференція "Проблеми теоретичної кібернетики", Московський державний університет імені М.В. Ломоносова. - Пенза. - 2005. - с. 127.

АНОТАЦІЯ

Протасова К.Д., Розкладання графів - рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики і кібернетики - Київський національний університет імені Тараса Шевченка, Київ, 2006.

В дисертаційній роботі введено нове поняття калейдоскопічного графу, що є природнім узагальненням кодів Хемінга. Вказано два загальні способи побудови калейдоскопічних графів на основі графів Келі груп.

Як один із загальних способів розкладання графів, знайдено кілька достатніх ознак квазігамільтонових графів. Зокрема, доведено що будь-який реберний граф скінченного зв'язного графа є квазігамільтоновим, а також раундебаут граф будь-якого скінченного зв'язного графа теж квазігамільтонів. Ці результати не покриваються жодною з існуючих ознак квазігамільтоновості.

Ключові слова: розбиття графів, врівноважені розбиття графів; калейдоскопічні графи, групи, дерева; квазігамільтонові графи, gr-графи, раундебаут граф.

АННОТАЦИЯ

Протасова К.Д., Разбиения графов - рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики - Киевский национальный университет имени Тараса Шевченко, Киев, 2006.

Разбиение графов - это специальные разложения множества их вершин. Каждое разбиение множества вершин графа естественно отождествляется с некоторой раскраской этого множества. В свою очередь всякая раскраска - это некоторое отображение множества вершин во множество цветов. Возникает классификация раскрасок по типу соответствующих отображений. Эта классификация дает четыре типа раскрасок: инъективные, сюръективные, биективные (или калейдоскопичные) и невырожденные. В работе впервые систематически исследуются сюръективные и калейдоскопичные раскраски графов.

В диссертационной работе разработаны новые методы разбиения графов: индуктивный, разбиения по независимым множествам, разбиения по остовным деревьям, трансверсальный способ, разбиения по обобщенным циклам и лучам.

Введены понятия семьи шаров B_{r}(Gr) радиуса r в графе Gr, индекса разбиения вершин графа Gr (ind A -- наименьшее число r, для которого подмножество A плотно относительно семьи шаров B_{r}(Gr)), и понятие показателя разложимости вершин графа res(Gr,m) (наибольшее число частей, на которое можно разбить множество вершин V так, что каждая часть разбиения пересекается с каждым шаром радиуса m). В работе определены и оценены показатели разложимости вершин графа. Доказана теорема об уравновешенных разбиениях графов, которая является основной теоремой диссертации: Теорема 2.1. t Для каких-либо натуральных чисел r, n, r не больше n и произвольного связного графа Gr(V,E), |V|=n, существует уравновешенное r-разбиение индекса не превышающего r множества V.

В диссертации введено новое понятие калейдоскопичного графа -- s-регулярного графа, множество вершин которого можно разить на s+1 множеств индекса 1, иными словами, регулярного графа максимально разложимого относительно семьи шаров единичного радиуса. Калейдоскопичный граф является естественным обобщением кодов Хемминга. Описано два общих способа построения калейдоскопичных графов на основе графов Кели групп. Кроме того, найдены некоторые необходимые и некоторые достаточные условия калейдоскопичности графов. Исследованы способы построения свободной калейдоскопичной группы и свободной калейдоскопичной полугруппы, описана группа калейдоскопичных автоморфизмов Хэмминговых графов.

Как один из способов разбиения графов рассмотрены разбиения гамильтоновых и квазигамильтоновых графов. Квазигамильтонов граф - это граф, в котором существует нумерация его вершин такая, что расстояния между двумя соседними вершинами не превышает 2. Если в графе есть гамильтонов цикл длины n и r - делитель числа n, то покрасив вершины этого цикла периодично слева направо r - цветами, мы получим разбиение графа с достаточно хорошими свойствами. Найдены достаточные и необходимые условия квазигамильтоновых графов. В частности, доказано, что реберный граф конечного связного графа является квазигамильтоновым. Введено новое понятие раундэбаут графа и доказано, что раундэбаут граф какого либо конечного связного графа также является квазигамильтоновым. Кроме того, доказано, что графы интервалов и графы Кели конечных групп также являются квазигамильтоновыми графами. В работе введено понятие квазигамильтоновых деревьев и даны признаки квазигамильтоновости деревьев. Все перечисленные результаты не покрываются ни одним из существующих признаков квазигамильтоновости.

Ключевые слова: разбиения графов, уравновешенные разбиения графов; калейдоскопические графы, квазигамильтоновы графы, gr-графы, раундэбаут граф, разбиения по остовным деревьям, сюръективные и калейдоскопичные раскраски графов.

ABSTRACT

Protasova K.D.: Resolvability of Graphs. - The manuscript.

The dissertation submitted for the Candidate Degree in Physics and Mathematics by specialty 01.05.01 - Theoretical Bases of Computer Science and Cybernetics - National Taras Shevchenko University of Kyiv, Kyiv, 2006.

A new notion of kaleidoscopic graph that is the natural generalization of Hamming codes was introduced here. Two general methods for construction kaleidoscopic graphs based on Kelly graph of groups were described.

Several sufficient conditions of square-Hamiltonian graphs were discovered. In particular it was proved that a line graph of any finite connected graph is square-Hamiltonian graph, as well as round-about graph of any finite connected graph is square-Hamiltonian graph also. These results are not covered none of the one of existing square-Hamiltonian criterion.

...