Головна Головна -> Реферати українською -> Дисертації та автореферати -> Екстремальнi розклади повних графiв: iснування, перелiк

Екстремальнi розклади повних графiв: iснування, перелiк

Назва:
Екстремальнi розклади повних графiв: iснування, перелiк
Тип:
Реферат
Мова:
Українська
Розмiр:
28,86 KB
Завантажень:
67
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19 
Національна академiя наук України
Iнститут кiбернетики ім. В.М.Глушкова
Петренюк Анатолiй Якович
УДК 519.1
Екстремальнi розклади повних графiв:
iснування, перелiк
01.05.01 - теоретичнi основи iнформатики
та кiбернетики
Автореферат дисертацiї
на здобуття наукового ступеня
доктора фiзико-математичних наук
Київ 2002
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики ім. В.М.Глушкова Національної академії наук України.
Науковий консультант : доктор фізико-математичних наук
Донець Георгій Панасович,
Інститут кібернетики імені В.М.Глушкова Національної академії наук України,
завідувач відділом
Офіційні опоненти:
доктор фізико-математичних наук, професор, академік Національної академії наук України Шор Наум Зуселевич , Інститут кібернетики імені В.М.Глушкова Національної академії наук України, завідувач відділом,
доктор фізико-математичних наук, професор Анісімов Анатолій Васильович, Київський національний університет імені Тараса Шевченка, завідувач кафедрою,
доктор фізико-математичних наук, професор Асельдеров Зайнутдін Макашаріпович, Інститут математичних машин і систем Національної академії наук України, провідний науковий співробітник.
Провідна установа:
Дніпропетровський державний університет, кафедра обчислювальної математики та математичної кібернетики, м. Дніпропетровськ.
Захист відбудеться 22 листопада 2002 р. об 11 годині на засіданні
спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова
Національної академії наук України за адресою:
03680 МСП Київ – 187, проспект Академіка Глушкова,40.
З дисертацією можна ознайомитися в науково-технічному архіві Інституту.
Автореферат розісланий 10 жовтня 2002 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність проблеми. Більше як 150 років тому, у 1847 р. Т.П.Кіркман довів, що системи, які зараз називаються штейнеровими системами трійок порядку n, існують тоді і тільки тоді, коли
n=1 або 3(mod 6).
Близько 100 років тому де Паскуаль установив факт, що існують тільки дві неізоморфні штейнерові системи трійок порядку 13.
Ці дві події можна вважати початком величезної низки досліджень і результатів, що складають тематику, до якої належить і ряд робіт автора дисертації. Основні задачі цього напряму у загальному вигляді зручно формулюються в термінах теорії графів.
Маємо мультиграф H та сімейство звичайних графів G={g1, g2,..., gk}. Розкладом мультиграфа H на графи з сімейства G називають розбиття множини ребер графа H на такі підграфи (компоненти розкладу), кожний з яких ізоморфний одному з елементів множини G. Такі розклади називають (H, G)-розкладами.
Загальна кількість компонент у розкладі називається розміром (або рангом) розкладу.
Стосовно розкладів формулюються і розв'язуються такі задачі.
Задача 1.1(задача існування). Задано H та G. Чи існують (H, G)-розклади?
Ця задача буде розв'язана позитивно, якщо розв'язана наступна задача побудови.
Задача 1.2. Задано H та G. Побудувати (H, G)-розклад.
Дослідження розкладів графів на підграфи із заданої множини розпочалося у 70-х роках XX ст. Серед багатьох дослідників назвемо Л.Байнеке, Ф.Харарі, Д.Босака, А.Роса, С.Знама, Р.Вільсона, Ш.Хуанг. Із різних аспектів цієї теми існує багато публікацій, і їх потік не виснажується.
(H, G)-розклади та щойно сформульовані задачі узагальнили задачі про 1-факторизації, штейнерові системи трійок (тобто (Kn,{K3})-розклади), неповні зрівноважені блок-схеми та ін., що на той час уже стали класичними. Класичні розклади мають істотні застосування у плануванні експериментів, при побудові ефективних кодів тощо. Природно чекати здатності до застосувань і від більш загальних розкладів.
Одне із застосувань розкладів повного графу на певні 5-вершинні підграфи описане у статті Ч.Колбурна і П.Вана (C.J.Colbourn, P.J.Wan, 2001). Робота колективу авторів (Colbourn C.J., Dinitz J.H., Stinson D.R., 1999) присвячена застосуванням комбінаторних схем у різних галузях людського життя
Типовою задачею існування є задача про існування T-факторизацій повного графа, або (Kn,T)-розкладів, про яку йдеться в розділах 3-5.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19 



Реферат на тему: Екстремальнi розклади повних графiв: iснування, перелiк

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок