Дослiдження структури плоских графiв з заданою досяжнiстю тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Академія наук України Інститут кібернетики імені В. М. Глушкова

. ' -

На правах рукопису

ПЕТРЕНЮК Володимир Ілліч

УДК 519.1

ДОСЛІДЖЕННЯ структури ПЛОСКИХ ГРАФІВ З ЗАДАНОЮ ДОСЯЖНІСТЮ

01.01.09 — математична кібернетика

Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Київ 1993

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

Роботу виконано в Кіровоградському кібернетико-технічному коледжі при Кіровоградському інституті сільськогосподарського машинобудування.

Науковий керівник: кандидат фізико-математичних наук ДОНЕЦЬ Г. А.

Офіційні опоненти: доктор фізико-математичних наук АСЕЛЬДЕРОВ 3. М„

кандидат фізико-математичних наук ШАРІФОВ Ф. А.

Провідна установа: Інститут математики АН України.

Захист відбудеться «--------» ------------- 199 р. о ------------

год. на засіданні спеціалізованої вченої ради Д 016.45.01 при Інституті кібернетики імені В. М. Глушкова АН України за адресою:

252207 Київ 207, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автереферат розісланий «------»--------------199 р.

Учений секретар спеціалізованої вченої ради

СИНЯВСЬКИИ В. Ф.

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

роботи^ Визначення числа досяжності деякої

МНОЖИНИ X ТОЧОК ГРАФА С ВПЕРШЕ ЕіВЕДЕНО В РОБОТАХ Н.П.ХОМЕН-

ка. Будемо вважати, ко множина точок X графа С мас число.до- , СЯЖНОСТІ І. ЯКИХ) ІСНУС ГіММАЛЬНЕ вкладення Г, Г :С—»6, ТАКЕ.

ЕО ІС!!УС НАЙМЕНША ЗА ВКЛЮЧЕННЯМ ПІЛМНОЖИНА ) МНОЖИНИ

6(6,1-), ЯКА ЗАДОВОЛЬНЯЄ СПІВВІДНОШЕННЮ:

(*>ОХ. XX £Х)(і=і<і,і)[(Г(Х )сзз МГ(Х)=е' ,Г< X. ))]

V V V V “ 1 V

де г-гссх> ,

Вкладеннп і будемо називати вкладенням.шо реалізує і. Під точкою графа С будемо розуміти або вершин» ,або точку деякого йог о ребра. Будемо говорити, ио грач> й має задану досяжНоть, г'.као задано множну X та число і. Цікаво визчити структурі* властивості плоских гра«йв з заданою досяжністю. В надрукова- '

МІХ РОБОТАХ З ЦЬОГО ПИТАННЯ ЗВЕРНЕМО УВАГУ НА ТАКІ ЗАДАЧІ!

і. ( х - гс(Х) = і );

II. ( X Є (Ги С1} (ЫХ> > 1). .

В роботі досліджено деякі ЧАСТКОВІ ВИПАДКИ ЗАДАЧІ II,

ПОВ'ЯЗАНІ З НАВЕДЕНИМИ НИЖЧЕ ВИЗНАЧЕННЯМИ ДЛЯ РЕБЕР ПЛОСКОГО ГРАЧ’А. Будемо говорити- ио ребро и,и є є1, істотне від-НССНО^ СС° > ПРИ ОПЕРАЦІЇ видалення ребра, якш виконується НЕРІВНІСТЬ Є4*) < ^((Г ) , ТА неістотне відносно )

ПРИ ОПЕРАЦІЇ ВИЛАЛЕІИЯ РЕБРА \1 ЯКЩО ВИКОНУЄТЬСЯ РІВНІСТЬ

1С-и(С<>) “ Усв>- . ■

Будемо говорити- іпо ребро и.и є істотне відносно )

ПРИ ОПЕРАЦІГ СТЯГУВАННЯ РЕБРА, ЯКЩО ВЖОНУЄТЬСЯ НЕРІВМСТЬ Іац<С») < 1 £(С” ),ТА НЕІСТОТНЕ відносно ^((3°) ПРИ ОПЕРАЦІГ СТЯГУВАННЯ РЕБРА и.ЯКЕІО ВИКОНУЄТЬСЯ РІВНСТЬ 1(^(0" ) = ІдСС* ).

Будемо говорити- ио ребрэ и, и є Є1,істотне відносно 1с(С° ). якщо воно істотне відносно )при операціях стягування

та видалення ребра и. ДЕ І =^СС° )•

Мета_роботи. Подана робота має на меті-, вивчення властивостей плоских грл«йв,кожне ревро яких істотне відносно і при операціях стягування або видалення ребра и, ДЕ І - 1^(0“ >,ЧИ ПРИ ОБОХ шгх операціях;

ОПИС ВСІХ ПЛОСКИХ З-МііімАПЬИИХ ГРЛ<ЙЕ1 С, ТАКИХ , ИОІ^ (й" )”3,

І кожне ребро істотні: відносно 0° )при операціях стягування та ВИДАЛЕННЯ ребра; .

ПОБУДОВУ ПОЛІІіОМІАПЬНОГО АЛГОРИТМУ для ЗНАХОДЖЕННЯ ВСІХ НЕ-

ізсмор-изе: 3-мі!2маііі.»ги>; гг-аччч та ного реалізацій в лрогра-

МІОМУ ЗАСОБІ.

.-МСТОЛ^ЛОСМШЛі В РОБОТІ ВИКОРИСТАН МСТОДИ ТЕОРІЇ ГРАФІВ ТА МАТЕМАТИЧНОЇ КІБЕРНЕТИКИ

_ДАУКОВА_тВ_ИЗНА. В РОБОТІ ВПЕРШЕ ВЖОНАНО ДОСЛІДЖЕННЯ СТРУКТУРИ ПЛОСКИХ ГРАЧІВ. КОЖНЕ РЕБРО, ЯКИХ ІСТОТНЕ ВІДНОСНО ЧИСЛА ДОСЯЖНОСТІ МНОЖИНИ ВЕРШИН ПРИ ОПЕРАЦІЯХ ВИДАЛЕННЯ ТА СТЯГУВАННЯ РЕБРА. СТРУКТУРИ ПЛОСКИХ ГРАЧІВ ІЗ ЗАДАНИМ ЧИСЛОМ ДОСЯЖНОСТІ ДЕЯКОЇ МНОЖИНИ ТОЧОК,ЯКА НСТИГЬ ХОЧА Б ОДНУ ТОЧКУ ГРА9А. А ТАКОЖ ОТРИМАНО ХАРАКТЕРИЗАЦІЮ 3~МІИМАЛЬНИХ ПЛОСКИХ ГРАЧІВ

ТеорЯОТНа.Т&.лєаіп'ИУУа дінйсть ..

Вперше розпочато систематичне вивчення структури плоских грачів з заданою досяжнстюРезультати дослідження можуть використовуватися ДЛЯ РОЗВ'ЯЗАННЯ ЗАДАЧ! II У ЗАГАЛЬНОМУ ВИПАДКУ. Отримано повний список нйзомор«жих З-пнмальних гра<йв за допомогою програмного засобу. Метод побудови можливо вико-рі«стати для побудови 4-міммальних ГРАЧІВ

-Апробауі.я. добоіи.Основна частина роботи доповідалася на

СЕН НАРАХ З ТЕОРІЇ ГРАЧІВ ПРИ ІНСТИТУТАХ МАТЕМАТИКИ ТА КІБЕРНЕТИКИ АН України у 1982-1984 та 1967-1990 роках відповідно ТА НА 4-МУ МІЖДЕРЖАВНОМУ СЕМІНАР» З ДИСКРЕТНОЇ МАТЕМАТИКИ

1393 року.

_Оублікауі]..За ттою дисертації опубліковано 7 праць. .Структура _т а .обсяг _ дисертад(і. Дисертація мас вступ, три розділи, додаток та список літературиЗагальний обсяг роботи складає 119 сторінок. Список літератури сягас 28 найменувань.

^ісх.роботи. .Вступ містить обгрунтування актуальності обраного напряму дослідження, вжладено мету роботи та скорочений згіст розділіаРозділ 1 МІСТИТЬ результати дослідження властивостей плоских грачів,кожне ребро яких істотне відносно ЗАДАНОГО ЧИСЛА досяжності множини вершин при операціях стягування ТА видалення ребра

Структура плоских грачів з заданим числом досяжності наведена у пропозиції 1.0.0:

. Я<ЮО С“БЛОК, ї - І£((3°>. то для кожної ПАРИ

ДЕ ‘"і, ІСНУС НАЙМЕНША ЗА ВКЛЮЧЕННЯМ ЧАСТИНА Г РАФА Є, ЯКА ЗАДОВОЛЬНЯЄ УМОВУ:

[<< (Г^азс г ) л ( їГпСаз^ де ) * о ))„

VI.) V J І > V

(( С*^3^<= ІҐ.УЧ Я;" п (вв^З-) *о ))Л

(( ні} М )Ь '

Критерій істотності ребра відносно заданого числа досяжності МНОЖИНИ ВЕРШИН ПРИ ОПЕРАЦІЇ ВИДАЛЕННЯ РЕБРА ОТРШАНО В ТЕОРЕМ 1.1 ДПЯ ДОВЕДЕННЯ ЯКОЇ ВЖОРИСТАН ДОПОМІЖНІ ТВЕРДЖЕННЯ ТА ЛЕМИ 1.1» 1.2. ХАРАКТЕРИЗАЦІЯ ЗВ'ЯЗНИХ ГРА«ИВ, то МАЮТЬ КОЖНЕ РЕБРО ІСТОТНИМ ВІДНОСНО ЧИСЛА ДОСЯЖНОСТІ РІВНОГО З ПРИ ОПЕРАЦІГ ВИДАЛЕННЯ РЕБРА, НАВЕДЕНА В ТЕОРЕМ 1.2:

Нехай Є-простий зв-язний граф.кожне ребро якого істотне відносно ІД-З.при операції видаленню ребра. Тоді висонусться ОДНЕ з наступних тверджень»

1) й * к;!

2) ІСНУЄ ^перетворення графа В ГРА» Є ЗАДАНЕ таким

ЧИНОМ!

9» ( X Г=і( ^

ЩО ЗАДОВОЛЬНЯЄ ТАКЖ УМОВАМ:

а5(уо(і=^Я(С.5« ^ к<1))ї

БХЇ^У^Д-ПРОСТИЙ ланцюг ДОВШНОЮ П-1 ГРАФА й .

ДЕ {уіі .ПРИ П-0 ПРОСТИЙ ЛАНЦЮГ ВИРОДЖУЄТЬСЯ В ТОЧКУ уи« •.

а)С({ц)}^1) -простий ланцюг графа С;

ЗАСНУЄ ^ПЕРЕТВОРЕННЯ ГРАКА С#+ Є3 У ГРАФ С.ИО ЗАДОВОЛЬНЯЄ ТАКИ1 УМОВАМ:

а) Со-!?-ОБРАЗ ГРАФА Є1+ Є2 ЗГІДНО З ТВЕРДЖЕННЯМ 2)»

Б>Са*КІ>,;

В> 6(<2в^і"1 )-ПРОСТИЙ ижл ДОВЖИНОЮ П. МОЖЛИВО» Э ДІАГОНАЛЯМИ, ГРАФА (МОЖЛИВО, ЦЕ ГРАНМДЯ ЗОВНІШНЬОЇ ГРАМ ГРАФА Гіц (С0 ), ДЕ ВКЛАДЕННЯ Г «

РЕАЛІЗУЄ 1,1«3, Пе:Со—► б .{г^іДс (Ги є* ;

Г) Са({2э]}Д >-ПРОСТИЙ ЦУКЛ В С^и (^;

Д) С({2^Д)-ПРОСТИЙ ЦЖЛ ГРАФА Є, МОЖЛИВО, З ДІАГОНАлями.

Ця ТЕОРЕМА СТАЛА ОСНОВОЮ АЛГОРІТГМУ ПОБУДОВИ СПІКХУ 3-МЛ-МАЛЬНИХ ПЛОСКИХ ГРАЧІВ. НАВЕДЕНОГО В ПАРАГРАФ 1.4. ДЕ'ПІД 3-МЯМАЛЬИП ГРАФОМ БУДЕМО РОЗУМТИ ПЛОСКИЙ ГРАФ. У ЯКОГО КОЖНЕ РЕБРО ІСТОТНЕ ВІДНОСНО 1.1-3. ДЛЯ ПОБУДОВИ ВСІХ НЕІЗО-ЗОМОРЧНИХ 3-ПНМАПЬНИХ ГРА«ЯВ ВИКОРИСТАНО КОРЕКТНИЙ АЛГОРИТМ, РЕАЛІЗОВАНИЙ У ПРОГРАМНОМУ ЗАСОБІ, КОРОТКО ОПИСАНОМУ У ДОДАТКУ 1. ДІАГРАМИ ТАКИХ ГРАЧІВ НАВЕДЕНО У ДОДАТКУ 2.

Розділ 2 ПРИСВЯЧЕНО ДОСЛІДЖЕННЮ СТРУКТУРИ ПЛОСКИХ ГРАЧІВ з ЭАДАЮ*» ЧИСЛОМ ДОСЯЖНОСТІ ДЕЯКОЇ МНОЖИНИ Гх точок.

Головний РЕЗУЛЬТАТ-ТЕОРЕМА 2.2 =

Нехай X -множина точок плоского блоку G така, пю '

X п G-о. X - Е‘щ1Х. , tG(X)-t Д>1.

Для ДОВІЛЬНИХ X^.Xj .ДЕ i<j. ВИКОНУЄТЬСЯ РІВНСТЬ

tQ<Xri Х^-2. ТОДІ І ТІЛЬКИ ТОДІ» КОЛИ ІСНУЄ ЧАСТИННИЙ ПІДГРАФ Н._;

ГРАКА G. НАВЕДЕНИЙ В ОЗНАЧЕНЬ* 2.3.

Для ПОВНОТИ ВИКЛАНЕННЯ НАВЕДЕМО ЦЕ ОЗНАЧЕННЯ ТА ТАКІ ПОЗНАЧЕННЯ :

БУДЕМО ГОВОРИТИ,ШО ВІДНОСНО Хд ЧАСТИНА Н ГРАКА G СТЯГУВАТИМЕТЬСЯ ДО Н, ЯКЩО ІСНУС ^-ПЕРЕТВОРЕННЯ:

9 ( НЧ<аіЛг)^).ЕЇг1 <аи * а*» *

ТАКЕ, шо У<ХН)«ХН . де к>0. Хи-Х n (Н*и Н1);

БУДЕМО ПОЗНАЧАТИ ЧЕРЕЗ К* ї>-0БРАЗ ГРАФА St4<y# >»24.ОТРИМАНИЙ В РЕЗУЛЬТАТІ ТАКОГО ^-ПЕРЕТВОРЕННЯ:

у ( St4(y,>z4. г,:, (у. * av>> * < .{а*}‘=1>.

ДЕ г4-ПРОСТИЙ ЦЖЛ ДОВЖИНИ 4 . ДЕ 2*- {а^}“г1. St4(ye ЗІРКА

З ЦЕНТРОМ В ТОЧЦІ Ув . 3t*(ye >“ty*>u..

Означення 2.3. Будемо позначати через Н мчастинний піл-

ГРАФ ГРАФА G . ЯКИЙ ЗАДОВОЛЬНЯЄ УМОВУ

( Хлзз/ЧНГи >о) ~ (Хпаз.пСН*.и HV>о).

де si,sj« 6(G.f). який стягується відносно Хд , Хц — X.uXj,

. ДО ОДНОГО З НАВЕДЕНИХ НИЖЧЕ ГРА<НВ. ДЕ ДЛЯ k.k«{i,j>.

Xk-X^slcn<HtjuH‘j).

1. Kj, ,. У ЯКОГО ВЕРШИНИ СТЕПЕН 2 МАЮТЬ СВОЇМИ ПРООБРАЗАМИ

ТОЧКИ ШО ЗАДОВОЛЬНЯЮТЬ СПІВВІДНОШЕННЯ

• <Vk)(k=i,j)[({ Х^Д/ОС^МСх. .}■.„« Хл«.)]:

2. К4. у якого точки, то належать несумжним реб-

РЕБРАМ, МАЮТЬ ПРООБРАЗИ ^, Хг,ДЕ Xj:

3. К4,УСІ ВЕРШИНИ якого МАЮТЬ СВОГНИ ПРООБРАЗАМИ ТОЧКИ X.., і»шм. ШО ЗАДОВОЛЬНЯЮТЬ СПІВВІДНОШЕННЯ

■ (Vk)(i,.i.j)[({xv.}.*slnXk»'0W{xi.}*.!S1cXi«jXi>ls

4. К*,у якого дві точки yt. уг. У,е(а*уо), У2є<а‘цо). мають

ПРООБРАЗИ Х1.Х2.Ш0 ЗАДОВОЛЬНЯЮТЬ СПІВВІДНОШЕННЯ

5. К*'^, ОТРИМАНОГО ШЛЯХОМ НАСТУПНОГО ^-ПЕРЕТВОРЕННЯ :

І ТАКОГО,ШО ЙОГО ВЕРШИНИ &*.&, МАЮТЬ СВОЇМИ ПРООБРАЗАМИ ТОЧКИ \ • *2 • ВІДПОВІДНО , ЯКЕ ЗАДОВОЛЬНЯЄ СПІВВІДНОШЕННЯ (Ук)(к-і,і)((хі.}*=1п х^и).

Аналогічний результат отршано для незв'язних та одлозв'-язних плоских ГРАчіа Побудовано також алгоритм обчислення числа досяжності деякої спеціальної множини X ТОЧОК ПЛОСКОГО БЛОКА Є, У ЯКОМУ обчислення числа досяжності ЗВОДИТЬСЯ до виділення частини Н графа Є гомеоморчноі одному з гракв наведених в означенИ 2.3.

Розділ 3 містить такі результатиДосліджено проблему побудови алгоритму, шо за поліноИальний час виявляє наявмсть 3-ВЛАСТИВОСТІ у вхідного плоского скінченного графа С без кратних ребер та петель. Під З-властийстю графа С розуптимемо вжонання нерівності І >^3.Знайдено необхідну та достатню умову наявності 3-властивості у графа С з вжористанням списку 3-мнмальних гРА«аОтрипАМ допонжні алгоритми К23Д4 ТА голови алгоритми А та В. доведено IX КОРЕКТНІСТЬ та полі-НОМІАЛЬНА СКЛАЛИСТЬ. Ці ДВА АЛГОРИТМИ А ТА В С СКЛАДОВИІИ ЧАСТИНАМИ ШУКАНОГО АЛГОРИТМА. На ОСНОВІ РЕЗУЛЬТАТІВ. ОТР'ПА-НИХ У РОБОТАХ АВТОРА, ОДЕРЖАНО НЕГАТИВНУ ВІДПОВІДЬ НА ПИТАННЯ ПРО УНГРАЧІЧНСТЬ З-МНМАЛЬНОГО ГРАФА.

Податок 1 містить скорочеН дай про програмний засіб “Автоматизована система побудови спеціальних плоскж грачів", а додаток 2 мстить список діаграм всіх низоморчних 3-ми -мальних ‘ гРА«йа

1. Введен і поняття про ребра, істоти відносно числа досяжності ПРИ ОПЕРАЦІЯХ СТЯГУВАННЯ або видалення ребра або при обох цих операціях.

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

2. Введено поняття заданої досяжності графа Є.вивчено структуру плоского графа з виділеною множиною ТОЧОК X, ЯКА МІСТИТЬ хоча б одну внутрішню точкку ребра, та певниі числом

досяжності tg(X )•

3.Повноти ОПИСАМ 3-ММГІАЛЬгі ПЛОСКІ грачи. наведено алгоритм ПОБУДОВИ УСІХ НИЭОМОРЧНИХ 3-МММАПЬНИХ ГРАЧІВ* реалізований У ПРОГРАМНОМУ ЗАСОБІ. СКОРОЧЕНО ОПИСАНОМУ У ДОДАТКУІ, А В ДОДАТКУ 2 РОЗПШЕНО СПИСОК ТХ ДІАГРАМІ

4. Побудовано полноміальшй алгоритм встановлення наявності У ВХІДНОГО ПЛОСКОГО ГРАКА БЕЗ КРАТНИХ РЕБЕР ТА ПЕТЕЛЬ ЧАСТИННОГО підграка, гомеоморкного деякому 3-мінмальному граку-

s.Встановлено ВЛАСТИВІСТЬ НЕУМГРА<ЙЧНОСГП ЗтММАЛЬНИХ ГРАЧФ.

РЕ2УІШІ^И_ІШ2КХАиіиш^іЖРВІіШ_Й. ТАКИХ РОБОТАХ»

1.Петренюк В.И. Об одном классе плоских грачов/Кировогр.ин-т. с.-млАшинастроЕНИ5»-Кировоград . 1385.-35 с.-Деп.в УкрНИИНТИ 09. 08.85.ИІ760-Укв6.

2.ГІЕТРЕНКК an О структуре плоских грачов с заданньм числом ДОСТИДОЮСТИ некоторого множества их точех Аировогр.ин-t.C.-X. машиностроения-Кировог рал, 1986. -31с.-Деп.в УкрНИИНТИ 22.09.86, N2246-VK 88.

3.Пепгренюк ЕИ Список З-гининальньх плоских граков/Кировогр. ин-т.с.-хлАШИНоатроЕНИя-КировогрАД,1386.-7а-ПЕП.в УкрНИИНТИ 31.10.86.H2450-VK 86.

4.ПЕТРШ0К ЕИ. Об одном подходе к описанию унигракові/Киро-еюг р.ин-т. а-х. машю юстроени»-Кировог рад . 1983. -51с.-Детш УкрНЮИТИ 12.11.88.н2570-Ук 86.

й.Петренюк ЕИ Об одном подходе к описажю унирачовіі/Киро-е»гр.ии-т.с.-х.машиностроеяи5»-Кировоград. 1336. -28с,-Дт.в УкрНИИНТИ 1^.11.86.»*2569-Ук 86.

Б.Петренюк ЕИ Об алгоритме установления 3-свойства плоских траков Дировогр.№і-т.а-хлАсиносггроЕкия-КнровогРЛд, 1990. -23 а -Деп. в УкрНИИКТИ 11.03.90 к428-У к 90.

7.Петренюк ЕИ. Характеризация спехіиальних плоских граков/Ки-Ровогр.ин-т.й-хлАгиюстроЕния-Кировоград, 1330.-30 с.~Деп.в УкрНИИНТИ 17.04.80.н1754-Ук 90.