Доведення існування півобертових Т-факторизацій повного графа порядку N=20

Доведення існування півобертових Т-факторизацій повного графа порядку N=20

При доведенні існування півобертових Т-факторизацій графа Kn для будь-якого півсиметричного дерева порядку n=20 використовується поняття правильної нумерації дерева порядку n=10, тобто такої нумерації його вершин, за якої довжини всіх ребер (що обчислюються як абсолютні різниці номерів кінців ребра)...

Full description

Saved in:
Bibliographic Details
Date:2010
Main Author: Петренюк, Д.А.
Format: Article
Language:Ukrainian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Series:Теорія оптимальних рішень
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/46679
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Доведення існування півобертових Т-факторизацій повного графа порядку N=20 / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 72-78. — Бібліогр.: 3 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-46679
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-466792025-02-09T22:39:46Z Доведення існування півобертових Т-факторизацій повного графа порядку N=20 Доказательство существования полуоборотных т-факторизаций полного графа порядка N=20 Proving of existence of 20-order half-rotational factorisations of complete graph Петренюк, Д.А. При доведенні існування півобертових Т-факторизацій графа Kn для будь-якого півсиметричного дерева порядку n=20 використовується поняття правильної нумерації дерева порядку n=10, тобто такої нумерації його вершин, за якої довжини всіх ребер (що обчислюються як абсолютні різниці номерів кінців ребра) є різними і складають послідовність натуральних чисел 1, 2,…, n–1. При доказательстве существования полуоборотных Т-факторизаций графа Kn для любого полусимметричного дерева порядка n = 20 используется понятие правильной нумерации дерева порядка n = 10, т. е. такой нумерации его вершин, при которой длины всех ребер (вычисляемые как абсолютные разности номеров концов ребра) различны и составляют последовательность натуральных чисел 1, 2, ... , n–1. To prove the existence of half-rotational T-factorisations of complete graph Kn for every halfsymmetrical tree of oder n = 20, a notion of 10-order tree proper enumeration is used. Proper tree enumeration is a tree vertexes enumeration where all the edges lengths (which are calculated as absolute values of the edge ends differences) have different values and are the set of natural numbers 1, 2, ... , n–1. 2010 Article Доведення існування півобертових Т-факторизацій повного графа порядку N=20 / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 72-78. — Бібліогр.: 3 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46679 591.1 uk Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description При доведенні існування півобертових Т-факторизацій графа Kn для будь-якого півсиметричного дерева порядку n=20 використовується поняття правильної нумерації дерева порядку n=10, тобто такої нумерації його вершин, за якої довжини всіх ребер (що обчислюються як абсолютні різниці номерів кінців ребра) є різними і складають послідовність натуральних чисел 1, 2,…, n–1.
format Article
author Петренюк, Д.А.
spellingShingle Петренюк, Д.А.
Доведення існування півобертових Т-факторизацій повного графа порядку N=20
Теорія оптимальних рішень
author_facet Петренюк, Д.А.
author_sort Петренюк, Д.А.
title Доведення існування півобертових Т-факторизацій повного графа порядку N=20
title_short Доведення існування півобертових Т-факторизацій повного графа порядку N=20
title_full Доведення існування півобертових Т-факторизацій повного графа порядку N=20
title_fullStr Доведення існування півобертових Т-факторизацій повного графа порядку N=20
title_full_unstemmed Доведення існування півобертових Т-факторизацій повного графа порядку N=20
title_sort доведення існування півобертових т-факторизацій повного графа порядку n=20
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2010
url https://nasplib.isofts.kiev.ua/handle/123456789/46679
citation_txt Доведення існування півобертових Т-факторизацій повного графа порядку N=20 / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 72-78. — Бібліогр.: 3 назв. — укр.
series Теорія оптимальних рішень
work_keys_str_mv AT petrenûkda dovedennâísnuvannâpívobertovihtfaktorizacíipovnogografaporâdkun20
AT petrenûkda dokazatelʹstvosuŝestvovaniâpoluoborotnyhtfaktorizaciipolnogografaporâdkan20
AT petrenûkda provingofexistenceof20orderhalfrotationalfactorisationsofcompletegraph
first_indexed 2025-12-01T11:47:08Z
last_indexed 2025-12-01T11:47:08Z
_version_ 1850306337131462656
fulltext 72 Теорія оптимальних рішень. 2010, № 9 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ При доведенні існування півобер- тових Т-факторизацій графа Kn для будь-якого півсиметричного дерева порядку n=20 використову- ється поняття правильної нумера- ції дерева порядку n=10, тобто такої нумерації його вершин, за якої довжини всіх ребер (що обчис- люються як абсолютні різниці но- мерів кінців ребра) є різними і складають послідовність натура- льних чисел 1, 2,…, n–1.  Д.А. Петренюк, 2010 ÓÄÊ 591.1 Ä.À. ÏÅÒÐÅÍÞÊ ÄÎÂÅÄÅÍÍß ²ÑÍÓÂÀÍÍß Ï²ÂÎÁÅÐÒÎÂÈÕ T-ÔÀÊÒÎÐÈÇÀÖ²É ÏÎÂÍÎÃÎ ÃÐÀÔÀ ÏÎÐßÄÊÓ N=20 Півобертова деревна факторизація повного графа [1] полягає у тому, що граф порядку 2n розкладається на n ізоморфних компонент, кожна з яких є півсиметричним деревом по- рядку 2n. Півсиметричне дерево містить центральне ребро, що з’єднує два ізоморфних дерева порядку n (симетричні половини) (рис. 1, а). Для отримання такого розкладу слід виконати вписування дерева, якому ма- ють бути ізоморфні всі компоненти розкладу, в коло. Таке коло містить 2n точок, що мають номери 1,..., 2n та розбивають його на 2n–1 дуг. Вписування необхідно виконати таким чином, щоб існувало рівно по два ребра од- накової довжини (довжини ребер вирахову- ються як різниці номерів вершин-кінців да- ного ребра), і при цьому кожні такі два ребра були симетричні одне одному відносно центра кола. Таке вписування називають правильним (рис. 1, б). Правильне вписування півсиметричного дерева в коло зводиться до вписування його симетричної половини (тобто дерева порядку n) в півколо, такого, що довжини всіх ребер вписаного в півколо дерева є різними та утворюють послідовність натуральних чисел 1,…, n–1 (рис. 2). Таким чином, задача знаходження півобе- ртової факторизації повного графа порядку 2n з компонентами, ізоморфними даному пі- всиметричному дереву порядку 2n, зводиться до відшукання такої нумерації вершин симе- тричної половини даного півсиметричного дерева, при котрій жодні два ребра не мають однакової довжини (тобто різниці ДОВЕДЕННЯ ІСНУВАННЯ ПІВОБЕРТОВИХ Т-ФАКТОРИЗАЦІЙ... Теорія оптимальних рішень. 2010, № 9 73 номерів кінців ребра є різними для всіх ребер), та довжини ребер є натуральни- ми числами 1, 2,..., n–1. Таку нумерацію називатимемо правильною. Проблема правильної нумерації відома як проблема А. Роса [2] (він називав таку нумера- цію „граціозною”). РИС. 1. Півсиметричне дерево порядку 18 та його правильне вписування в коло РИС. 2. Вписування дерева порядку 9 (симетричної половини) в півколо Відомо, що правильну нумерацію допускають всі ланцюги, зірки, а також гу- сениці – дерева, що після видалення всіх вершин порядку 1 перетворюються на ланцюги (рис. 3). РИС. 3. Правильна нумерація гусениці Д.А. ПЕТРЕНЮК 74 Теорія оптимальних рішень. 2010, № 9 На основі цих даних легко доводиться Теорема. Якщо до вершини з номером 1 правильно занумерованого дерева приєднати гусеницю, то отримане дерево допускає правильну нумерацію. Усе це дозволило довести, що правильну нумерацію допускають усі дерева порядку 9k = , а отже, півобертову факторизацію допускають усі дерева порядку 18n = . Також було показано [3], що можлива така правильна нумерація ланцюга, за якої номер 1 отримує друга або третя від кінця ланцюга вершина. Це доводить існування правильної нумерації для дерев, які отримуються шляхом приєднання гусениці до ланцюга у другій або третій вершині від краю ланцюга. Визначення. Кометою називатимемо дерево, отримане шляхом приєднання ребра до кожної висячої вершини зірки довільного порядку, тобто подвоєнням променів зірки (рис. 4). Комета допускає правильну нумерацію. Алгоритм отримання такої нумерації полягає в наступному. Спочатку центральній вершині комети присвоюють но- мер 1. Першій висячій вершині присвоюють номер 2, а вершині, що лежить на другому промені комети ближче до центра (вона має степінь 2) присвоюють но- мер 3. Далі нумерація продовжується „хвилями”, тобто обираються по черзі ни- жні (висячі) та середні вершини, аж поки не буде занумеровано вершину на останньому промені комети. Після цього рухаємося аналогічним чином в зво- ротному напрямку, нумеруючи по порядку вершини, що ще не мають номера. На рис. 4 наведено приклад правильної нумерації комети. РИС. 4. Правильна нумерація комети У даній роботі доводиться існування півобертових факторизацій для всіх де- рев порядку 20n = . Перелік усіх неізоморфних дерев порядку 10k = було отри- мано за допомогою комп’ютера шляхом перебору. Цей перелік показано на рис. 5. Більшість дерев – гусениці, для яких доведено існування правильної нумера- ції. Номери дерев, що не є гусеницями, на рисунку обведено колом. Розглянемо ці дерева. Спочатку вкажемо на дерева, що отримуються приєднанням гусениці до ланцюга або комети. ДОВЕДЕННЯ ІСНУВАННЯ ПІВОБЕРТОВИХ Т-ФАКТОРИЗАЦІЙ... Теорія оптимальних рішень. 2010, № 9 75 Д.А. ПЕТРЕНЮК 76 Теорія оптимальних рішень. 2010, № 9 РИС. 5. Перелік дерев порядку 10 ДОВЕДЕННЯ ІСНУВАННЯ ПІВОБЕРТОВИХ Т-ФАКТОРИЗАЦІЙ... Теорія оптимальних рішень. 2010, № 9 77 Дерева 9, 17, 21, 24, 34, 39, 42, 54, 56, 64, 73, 76, 89, 93, 94 можна отримати приєднанням гусениці до комети, показаної на рис. 6, а (приєднання гусениці відбувається до центральної вершини комети, що на рисунку має номер 1). На ньому показано також правильну нумерацію цього дерева. Дерева 23, 38, 53 представляють собою комбінацію гусениці та комети, зо- браженої та правильно занумерованої на рис. 6, б. Дерева 40, 50, 55, 77, 85, 92, 90 представляють собою комбінацію гусениці та ланцюга, показаного на рис. 6, в. На рисунку вказано також правильну нумера- цію ланцюга, при якій номер 1 отримує вершина, до якої приєднується гусени- ця. За теоремою всі перелічені дерева допускають правильну нумерацію. РИС. 6. Комети та ланцюг, що є компонентами дерев 9, 17, 21, 24, 34, 39, 42, 54, 56, 64, 73, 76, 89, 93, 94 (а); 23, 38, 53 (б); 40, 50, 55, 77, 85, 92, 90 (в) Усі інші дерева можна представити як поєднання гусениці з деревом (компо- нентою), що не належить до вищерозглянутих типів. Такі компоненти та їх пра- вильну нумерацію показано на рис. 7. За теоремою всі перелічені дерева допускають правильну нумерацію. РИС. 7. Компоненти дерев 36, 48, 71, 75, 81, 82, 83 Д.А. ПЕТРЕНЮК 78 Теорія оптимальних рішень. 2010, № 9 Таким чином, доведено існування правильної нумерації для всіх дерев по- рядку 10. А це, в свою чергу, доводить існування півобертових факторизацій для всіх півсиметричних дерев порядку 20. Ця методика, за допомогою комп’ютера, може бути використана для дове- дення існування T-факторизацій вищих порядків. При цьому можна програмно вилучати з розгляду ланцюги, гусениці, комети та їх комбінації, що відповіда- ють теоремі. Користуючись нагодою, хочу висловити подяку Д. Дурачу за надану ним програму генерації дерев. Д.А. Петренюк ДОКАЗАТЕЛЬСТВО СУЩЕСТВОВАНИЯ ПОЛУОБОРОТНЫХ Т-ФАКТОРИЗАЦИЙ ПОЛНОГО ГРАФА ПОРЯДКА N=20 При доказательстве существования полуоборотных Т-факторизаций графа Kn для любого по- лусимметричного дерева порядка n = 20 используется понятие правильной нумерации дерева порядка n = 10, т. е. такой нумерации его вершин, при которой длины всех ребер (вычисляе- мые как абсолютные разности номеров концов ребра) различны и составляют последователь- ность натуральных чисел 1, 2, ... , n–1. D.A. Petreniuk PROVING OF EXISTENCE OF 20-ORDER HALF-ROTATIONAL FACTORISATIONS OF COMPLETE GRAPH To prove the existence of half-rotational T-factorisations of complete graph Kn for every half- symmetrical tree of oder n = 20, a notion of 10-order tree proper enumeration is used. Proper tree enumeration is a tree vertexes enumeration where all the edges lengths (which are calculated as absolute values of the edge ends differences) have different values and are the set of natural numbers 1, 2, ... , n–1. 1. Петренюк А.Я. Півобертові деревні факторизації повних графів // Український ма- тематичний журнал. – 2001. – 53, № 5. – С. 710–716. 2. Rosa A. On certain valuations of the vertices of a graph // Theory of Graphs, ed. P. Ro- senstehl, Gordon and Breach, New York. – 1967. – P. 349–355. 3. Донец Г.А. Об одной задаче нумерации вершин деревьев // Математичекие машины и системы. – 2010. – № 1. – С. 17–24. Получено 12.05.2010

Similar Items