Головна Головна -> Реферати українською -> Дисертації та автореферати -> ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ

ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ

Назва:
ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ
Тип:
Реферат
Мова:
Українська
Розмiр:
20,12 KB
Завантажень:
434
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13 
Київський національний університет
імені Тараса Шевченка
Семенюта Марина Фролівна
УДК 519.17
ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ
01.01.08 – математична логіка, теорія алгоритмів
і дискретна математика
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2008
Дисертацією є рукопис.
Робота виконана на кафедрі геометрії Київського національного університету імені Тараса Шевченка, Кабінет Міністрів України.
Науковий керівник: доктор фізико-математичних наук, професор
КИРИЧЕНКО Володимир Васильович,
Київський національний університет
імені Тараса Шевченка, м. Київ,
професор кафедри геометрії.
Офіційні опоненти: доктор фізико-математичних наук, професор
Кривий Сергій Лук’янович,
Інститут кібернетики імені В. М. Глушкова НАН України, м. Київ,
провідний науковий співробітник відділу мікропроцесорної техніки;
кандидат фізико-математичних наук, доцент
ГАНЮШКІН Олександр Григорович,
Київський національний університет
імені Тараса Шевченка, м. Київ,
доцент кафедри алгебри та математичної логіки.
Захист відбудеться 26 травня 2008 року о 14 годині на засіданні спеціалізованої вченої ради Д .001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, проспект акад. Глушкова, 2, корпус 7, механіко-математичний факультет.
З дисертацією можна ознайомитись у Науковій бібліотеці імені М. Максимовича Київського національного університету імені Тараса Шевченка (м. Київ, вул. Володимирська, 58)
Автореферат розісланий 22 квітня 2008 року
Учений секретар
спеціалізованої вченої ради В. В. Плахотник
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
В теорії розкладів графів вивчаються задачі існування, побудови, переліку розкладів. Історія досліджень в цьому напрямку починалася з публікацій про існування і побудову кіркманових та штейнерових систем трійок. У 1847 році Т. П. Кіркман розв’язав задачу існування систем трійок, що пізніше названі штейнеровими (ШСТ), ним також була поставлена задача про знаходження умов існування кіркманових систем трійок (КСТ). КСТ – це такі ШСТ, які допускають розбиття сукупності своїх трійок на паралельні класи, кожен з яких є розбиттям основної множини на трійки. Необхідну умову існування КСТ встановив Кіркман, а її достатність довели в 1971 році Р. Чоудхурі і Р. Вільсон. В 1960 році Х. Ханані знайшов спектр порядків штейнерових систем четвірок, а в 1966 році А. Роса довів необхідну і достатню умову існування пентагональних систем. По суті, нинішня теорія розкладів є широким узагальненням згаданих понять і результатів. Перші результати вказаного напрямку одержані в теоретико-множинній термінології і пов’язані з вивченням таких комбінаторних конфігурацій, як схеми блоків. З іншого боку, ці конфігурації мають витоки геометричного характеру: у скінченній проективній геометрії ведуться подібні дослідження. Наприклад, Р. Брук і Г. Райзер в роботі “The nonexistence of certain finite projective planes” вивчають скінченні системи точок і прямих – скінченні проективні площини – із застосуванням теорії матриць. Початок сучасної теорії графів заклав у 1937 році Д. Пойа, а конфігурації з точок і відрізків одержали назву “графів” у 1936 році. Назва “граф” запропонована угорським математиком Д. Кьонігом. Оформлення теорії графів, як окремої математичної дисципліни, привело до розширення і переосмислення згаданого класу комбінаторних задач: стало можливим розглядати розклади графів різних видів на підграфи. В статті “Graph factorizations, general triple systems, and cyclic triple systems” Р. Стентона та I. Гулдена прослідковується еквівалентність комбінаторних задач і задач теорії графів. В сучасній термінології ШСТ порядку n – це розклади повного графа Кn на 3-цикли. Вивчення та розв’язання проблем існування розкладів графа Кn на m-цикли описано в 1999 році в роботах М. Андерсена “Decomposing graph into fixed length cycles”, М. Шайна “Cycle decompositions of Кn and Кn–I”.

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



Реферат на тему: ДОСЛІДЖЕННЯ РОЗКЛАДІВ ТА НУМЕРАЦІЙ ГРАФІВ

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