Козеренко Сергій Олександрович Графи Маркова одновимірних динамічних систем

Короткий опис

Козеренко Сергій Олександрович, тимчасово не пра­цює: «Графи Маркова одновимірних динамічних систем» (01.01.08 - математична логіка, теорія алгоритмів і дис­кретна математика). Спецрада Д 26.001.18 у Київському національному університеті імені Тараса Шевченка

Київський нацiональний унiверситет iменi Тараса Шевченка
Мiнiстерство освiти i науки України
Київський нацiональний унiверситет iменi Тараса Шевченка
Мiнiстерство освiти i науки України
Квалiфiкацiйна наукова
праця на правах рукопису
Козеренко Сергiй Олександрович
УДК 519.172, 517.938
ДИСЕРТАЦIЯ
ГРАФИ МАРКОВА ОДНОВИМIРНИХ ДИНАМIЧНИХ
СИСТЕМ
01.01.08 – математична логiка, теорiя алгоритмiв i дискретна математика
Подається на здобуття наукового ступеня
кандидата фiзико-математичних наук
Дисертацiя мiстить результати власних дослiджень. Використання iдей,
результатiв i текстiв iнших авторiв мають посилання на вiдповiдне джерело
С. О. Козеренко
Науковий керiвник
Кириченко Володимир Васильович
доктор фiзико-математичних наук, професор
Київ – 2017

ЗМIСТ
ВСТУП 13
Роздiл 1. ПОПЕРЕДНI ВIДОМОСТI 35
1.1. Неорiєнтованi графи . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.2. Орiєнтованi графи . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3. Типи вiдображень мiж графами . . . . . . . . . . . . . . . . . . 43
1.4. Графи Маркова вiдображень топологiчних та комбiнаторних
дерев в себе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Висновки до роздiлу 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Роздiл 2. ВIДОБРАЖЕННЯ ДЕРЕВ В СЕБЕ 53
2.1. Кiлькiсть дуг в графах Маркова . . . . . . . . . . . . . . . . . . 53
2.2. Опис вiдображень iз заданими графами Маркова . . . . . . . . 60
2.3. Побудова гомоморфiзму з Tn у Matn−1(F2) . . . . . . . . . . . . 66
2.4. Ребернi розмiтки i блукання на деревах . . . . . . . . . . . . . . 68
2.5. Передпорядок Маркова . . . . . . . . . . . . . . . . . . . . . . . 76
2.6. Лiнiйнi та метричнi вiдображення . . . . . . . . . . . . . . . . . 81
2.7. Розтягуючi та антирозтягуючi вiдображення . . . . . . . . . . . 90
2.8. Кiлькiсть дуг в графах Маркова для блукань . . . . . . . . . . . 104
2.9. Орiєнтацiї дерев та помiченi графи Маркова . . . . . . . . . . . 111
Висновки до роздiлу 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Роздiл 3. ПОБУДОВА ДЕРЕВ ДЛЯ ЗАДАНИХ ВIДОБРАЖЕНЬ 121
3.1. Вiдображення з малими перiодами . . . . . . . . . . . . . . . . . 121
3.2. Iснування дерев для розтягуючих перестановок . . . . . . . . . 131
3.3. Iснування дерев для лiнiйних та метричних вiдображень . . . . 133
3.4. Слабка та сильна зв’язнiсть графiв Маркова . . . . . . . . . . . 138
12
Висновки до роздiлу 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Роздiл 4. М-ГРАФИ 146
4.1. Перiодичнi орграфи як М-графи . . . . . . . . . . . . . . . . . . 146
4.2. Нижня оцiнка на кiлькiсть дуг в перiодичних орграфах . . . . . 147
4.3. Деякi властивостi М-графiв . . . . . . . . . . . . . . . . . . . . . 151
4.4. Операцiї над M-графами . . . . . . . . . . . . . . . . . . . . . . 162
4.5. Турнiри як М-графи . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.6. M-графи з трьома вершинами . . . . . . . . . . . . . . . . . . . . 173
Висновки до роздiлу 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
ВИСНОВКИ 179
Список використаних джерел 181
ДОДАТОК 188
Список опублiкованих праць . . . . . . . . . . . . . . . . . . . . . . . 188
Апробацiя результатiв дисертацiї . . . . . . . . . . . . . . . . . . . . . 190
13
ВСТУП
Актуальнiсть теми. Одним iз основних аспектiв комбiнаторної динамiки є дослiдження iснування перiодичних точок топологiчних динамiчних
систем та опис структури вiдповiдних їм орбiт. Центральним результатом
даної тематики є вiдома теорема Шарковського [12] (доведена О. М. Шарковським у 1964 роцi), яка повнiстю описує спiвiснування перiодiв перiодичних точок неперервного вiдображення одиничного вiдрiзку в себе. У 1978
роцi Ф. Страффiним [69] було запропоноване чисто комбiнаторне доведення теореми Шарковського, яке було завершене Ч-В. Хо та Ч. Моррiсом [43]
у 1981 роцi (див. також роботу [31]). Це доведення базувалося на розглядi циклiв деякого орiєнтованого графа, який будується за даною перiодичною точкою. А саме, нехай f : [0, 1] → [0, 1] – неперервне вiдображення, а
x ∈ [0, 1] – його перiодична точка перiоду n. Розглянемо орбiту цiєї точки
orbf (x) = {x, f(x), . . . , f n−1
(x)} = {x1 < · · · < xn} та її природнiй порядок.
Вiдповiдний перiодичний граф є орграфом з множиною вершин {1, . . . , n−1}
та множиною дуг {(i, j) : min{f(xi), f(xi+1)} 6 xj < max{f(xi), f(xi+1)}}.
Кожне число 1 6 i 6 n − 1 вiдповiдає мiнiмальному вiдрiзку [xi
, xi+1], а
iснування дуги i → j в перiодичному графi означає, що вiдрiзок [xi
, xi+1] “накриває” [xj
, xj+1] пiд дiєю f. Дослiджуючи цикли перiодичного графа, можна
отримати iнформацiю про iснування перiодичних точок iз заданими перiодами. Схожа конструкцiя переноситься й на вiдображення скiнченних топологiчних дерев, а також комбiнаторних дерев (зв’язних ациклiчних графiв) в
себе. Вiдповiднi орграфи називаються графами Маркова. Таким чином, перiодичнi графи є частковим випадком графiв Маркова для дерев-ланцюгiв та
їхнiх циклiчних перестановок.
За допомогою графiв Маркова можна отримати аналоги теореми Шарковського для дерев загального вигляду [20]. При цьому, ентропiя кусковолiнiйного вiдображення, побудованого за орбiтою даної перiодичної точки,
може бути обчислена через спектральний радiус матрицi сумiжностi вiдпо-
14
вiдного графа Маркова [26]. Також за допомогою графiв Маркова будується “майже iн’єктивний” гомоморфiзм iз напiвгрупи Tn всiх вiдображень
n-елементної множини в себе у матричну напiвгрупу Matn−1(Z) (а також i
у Matn−1(F2)), звуження якого на групу перестановок Sn є точним та незвiдним зображенням останньої [20, 21, 37].
Абстрактнi властивостi перiодичних графiв вивчалися в роботах В. А. Павленка [8, 9, 10]. Зокрема, у роботi [8] було пiдраховано кiлькiсть попарно неiзоморфних перiодичних графiв iз заданим числом вершин. Теоретико-графовi
критерiї перiодичних графiв та їх породжених пiдграфiв було отримано в
роботах [9] та [10] вiдповiдно.
В данiй дисертацiйнiй роботi вивчаються як вiдображення комбiнаторних
дерев в себе, так i самi дерева за допомогою графiв Маркова та дослiджуються теоретико-графовi властивостi графiв Маркова.
Зв’язок роботи з науковими програмами, планами, темами. Робота виконана у рамках державної бюджетної науково-дослiдної теми №11БФ
038-03 “Застосування алгебро-геометричних методiв в теорiях груп, напiвгруп, кiлець, зображень до задач прикладної алгебри та захисту iнформацiї”
(номер державної реєстрацiї 0111U005264) i №16БФ038-01 “Якiсний аналiз
та керування еволюцiйними системами складної структури” (номер державної реєстрацiї 0116U004752) кафедри геометрiї, топологiї i динамiчних систем механiко-математичного факультету Київського нацiонального унiверситету iменi Тараса Шевченка, що входить до комплексного тематичного плану науково-дослiдних робiт “Сучаснi математичнi проблеми природознавства,
економiки та фiнансiв”.
Мета i завдання дослiдження. Метою дисертацiї є вивчення властивостей вiдображень комбiнаторних дерев в себе за допомогою вiдповiдних
їм графiв Маркова та дослiдження теоретико-графових властивостей графiв
Маркова. Завданням дослiдження є опис вiдображень дерев iз заданими графами Маркова, отримання точних формул та оптимальних оцiнок на кiлькiсть дуг та кiлькiсть дуг в середньому в графах Маркова для деяких класiв
вiдображень, опис структури лiнiйних, метричних, розтягуючих, антирозтягуючих вiдображень, блукань та автоморфiзмiв дерев, отримання критерiїв
15
iснування дерев для заданих вiдображень скiнченної множини в себе, на яких
цi вiдображення мають наперед задану властивiсть, опис структури класу Мграфiв.
Об’єктом дослiдження є вiдображення скiнченних комбiнаторних дерев та орiєнтованi графи.
Предметом дослiдження є властивостi вiдображень дерев в себе, якi
виражаються через вiдповiднi їм графи Маркова та теоретико-графова структура графiв Маркова.
Методи дослiдження. Основними методами, якi використовуються
при дослiдженнях в дисертацiйнiй роботi, є методи теорiї графiв та комбiнаторики.
Наукова новизна одержаних результатiв. Усi результати, отриманi
в дисертацiї, є новими. Основнi з них наступнi:
— отримано оптимальнi верхнi та нижнi оцiнки на кiлькiсть дуг в графах
Маркова i описано вiдображення, на яких цi оцiнки досягаються;
— пораховано кiлькiсть дуг в графах Маркова в середньому для класiв загальних вiдображень, перестановок, циклiчних перестановок та
блукань на деревах;
— описано вiдображення, графи Маркова яких є повними, повними двочастковими, диз’юнктними об’єднаннями циклiв та кожна дуга яких
є петлею;
— введено поняття передпорядку Маркова та дослiджено його максимальнi елементи;
— отримано критерiї для лiнiйних та метричних вiдображень в термiнах
графiв Маркова;
— доведено, що кожне дерево з не менше нiж трьома вершинами допускає розтягуюче вiдображення зi слабко зв’язним (сильно зв’язним,
якщо дерево мiстить досконале парування) графом Маркова а також
антирозтягуюче вiдображення iз сильно зв’язним графом Маркова;
— пораховано кiлькiсть слабких компонент та кiлькiсть дуг в графах
Маркова для блукань на деревах та отримано оптимальнi оцiнки на
цю кiлькiсть в термiнах самих дерев;
16
— описано вiдображення скiнченної множини в себе, для яких iснують
дерева, на яких цi вiдображення є лiнiйними, метричними, розтягуючими, антирозтягуючими, блуканнями, автоморфiзмами дерев та зi
слабко або сильно зв’язними графами Маркова;
— отримано оптимальну нижню оцiнку на кiлькiсть дуг в перiодичних
орграфах;
— доведено, що частково функцiональнi та оберненi до них орграфи є
М-графами;
— доведено гiпотези Сеймура та Кассетти-Хаггквiста для М-графiв;
— наведено достатнi умови того, що диз’юнктне об’єднання М-графiв
також є М-графом;
— доведено, що орграф, який отримується iз М-графа подвоєнням або
оберненим подвоєнням довiльної вершини, також є М-графом;
— описано всi М-графи, якi є турнiрами та наведено повний список Мграфiв з трьома вершинами.
Практичне значення одержаних результатiв. Отриманi в роботi
результати мають теоретичний характер i можуть бути застосованi у подальших дослiдженнях з комбiнаторної динамiки та теорiї графiв. А також можуть бути використанi при читаннi спецкурсiв з теорiї динамiчних систем та
теорiї графiв.
Особистий внесок здобувача. Усi результати дисертацiйної роботи
отриманi здобувачем самостiйно. За результатами дисертацiї опублiковано
п’ять наукових робiт у фахових виданнях та одна стаття в електронному
виданнi.
Апробацiя результатiв дисертацiї. Результати дисертацiйного дослiдження доповiдались на:
1. XIII Мiжнароднiй науково-практичнiй конференцiї студентiв, аспiрантiв та молодих вчених “Шевченкiвська весна – 2015” (м. Київ, 1-3 квiтня 2015 р.);
2. IV Всеукраїнськiй науковiй конференцiї молодих вчених з математики
та фiзики (м. Київ, 23-25 квiтня 2015 р.);
3. XIV Мiжнароднiй науково-практичнiй конференцiї студентiв, аспiран-
17
тiв та молодих вчених “Шевченкiвська весна – 2016” (м. Київ, 6-8 квiтня 2016 р.);
4. V Всеукраїнськiй науковiй конференцiї молодих вчених з математики
та фiзики (м. Київ, 25-26 квiтня 2016 р.);
5. XVII Мiжнароднiй науковiй конференцiї iм. акад. Михайла Кравчука
(м. Київ, 19-20 травня 2016 р.);
6. Мiжнароднiй конференцiї “Геометрiя i топологiя в Одесi – 2016” (м.
Одеса, 25-31 травня 2016 р.);
7. XV Мiжнароднiй науково-практичнiй конференцiї студентiв, аспiрантiв та молодих вчених “Шевченкiвська весна – 2017” (м. Київ, 4-6 квiтня 2017 р.);
8. VI Всеукраїнськiй конференцiї молодих вчених з математики та фiзики (м. Київ, 21-22 квiтня 2017 р.);
9. Мiжнароднiй науковiй конференцiї “Алгебраїчнi та геометричнi методи аналiзу” (м. Одеса, 31 травня - 5 червня 2017 р.);
10. Мiжнароднiй конференцiї молодих математикiв, присвяченiй 100-рiччю
з дня народження академiка Ю. О. Митропольського (м. Київ, 7-10
червня 2017 р.);
11. XI Мiжнароднiй алгебраїчнiй конференцiї в Українi, присвяченiй 75-
рiччю В. В. Кириченка (м. Київ, 3-7 липня 2017 р.);
12. XVIII Мiжнароднiй науковiй конференцiї iм. акад. Михайла Кравчука, присвяченiй 125-рiччю вiд дня народження М. Кравчука (м.
Луцьк-Київ, 7-10 жовтня 2017 р.);
13. Засiданнi наукового семiнару вiддiлу топологiї Iнституту математики
НАН України (м. Київ, 2013 р.);
14. Засiданнях наукового семiнару кафедри геометрiї, топологiї i динамiчних систем механiко-математичного факультету Київського нацiонального унiверситету iменi Тараса Шевченка (м. Київ, 2015-2017 рр.).
Публiкацiї. За результатами дисертацiйної роботи опублiковано 18 наукових публiкацiй. З них
— 6 статей [48]–[53] у фахових виданнях, серед яких двi статтi [48], [53] у
науковому фаховому виданнi України включеному до наукометричної
18
бази Scopus, три статтi [49], [50], [52] у фахових iноземних виданнях
та одна стаття [51] в електронному журналi;
— 12 тез доповiдей на наукових конференцiях [1]–[7], [54]–[58].
Структура та обсяг роботи. Дисертацiя складається з анотацiї, вступу, 4 роздiлiв, якi мiстять пiдроздiли, висновкiв, списку використаних джерел,
який мiстить 74 найменування та додатку. Повний обсяг роботи складає 191
сторiнку, в тому числi 168 сторiнок основного тексту.
У вступi обґрунтовано актуальнiсть теми, вказано зв’язок роботи з науковими програмами, планами, темами, встановлено мету i завдання, об’єкт,
предмет та методи дослiдження, наведено наукову новизну та практичне значення отриманих результатiв, особистий внесок здобувача та короткий змiст
роботи.
Перший роздiл носить допомiжний та систематизуючий характер i мiстить основнi означення понять та деякi твердження, якi будуть використовуватися в роботi.

Список літератури

ВИСНОВКИ
Дисертацiйна робота присвячена дослiдженню властивостей вiдображень
комбiнаторних дерев в себе за допомогою вiдповiдних їм графiв Маркова
та дослiдженню теоретико-графових властивостей самих графiв Маркова.
Зокрема, у дисертацiї отримано наступнi новi науковi результати:
— отримано оптимальнi верхнi та нижнi оцiнки на кiлькiсть дуг в графах
Маркова i описано вiдображення, на яких цi оцiнки досягаються;
— пораховано кiлькiсть дуг в графах Маркова в середньому для класiв загальних вiдображень, перестановок, циклiчних перестановок та
блукань на деревах;
— описано вiдображення, графи Маркова яких є повними, повними двочастковими, диз’юнктними об’єднаннями циклiв та кожна дуга яких
є петлею;
— введено поняття передпорядку Маркова та дослiджено його максимальнi елементи;
— отримано критерiї для лiнiйних та метричних вiдображень в термiнах
графiв Маркова;
— доведено, що кожне дерево з не менше нiж трьома вершинами допускає розтягуюче вiдображення зi слабко зв’язним (сильно зв’язним,
якщо дерево мiстить досконале парування) графом Маркова а також
антирозтягуюче вiдображення iз сильно зв’язним графом Маркова;
— пораховано кiлькiсть слабких компонент та кiлькiсть дуг в графах
Маркова для блукань на деревах та отримано оптимальнi оцiнки на
цю кiлькiсть в термiнах самих дерев;
— описано вiдображення скiнченної множини в себе, для яких iснують
дерева, на яких цi вiдображення є лiнiйними, метричними, розтягуючими, антирозтягуючими вiдображеннями, блуканнями, автоморфiзмами дерев та зi слабко або сильно зв’язними графами Маркова;
— отримано оптимальну нижню оцiнку на кiлькiсть дуг в перiодичних
180
орграфах;
— доведено, що частково функцiональнi та оберненi до них орграфи є
М-графами;
— доведено гiпотези Сеймура та Кассетти-Хаггквiста для М-графiв;
— наведено достатнi умови того, що диз’юнктне об’єднання М-графiв
також є М-графом;
— доведено, що орграф, який отримується iз М-графа подвоєнням або
оберненим подвоєнням довiльної вершини, також є М-графом;
— описано всi М-графи, якi є турнiрами та наведено повний список Мграфiв з трьома вершинами