Покрытие множества слов цепями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На почвах рукописи УДК 519.117+519.175

Владимир ПОКШТИЕ МНОЖЕСТВА СЛОВ ЦЕПЯМИ 01„01„09 - математическая кибернетика

Автореферат

диссертации на соискание ученой стелена кандидата фазико-ште - 'тичеокак наук

Новосибирск 1990

Работа выполнена в Институте математики Сп Ш СССР.

Научный руководитель: кандидат Физико-математических наук

А.А.Евдокчмов

Официальные ояпояенты: доктор физико-м^ематических наук

професс т В.КоЛеонгьев,

кандидат физико-математических надк научный сотрудник АоИ.Сэрдахов

Ведущее предприятие: Московский государственный университет., механико-матемг-'ичвскай факультет

Защита состоится "__" ___ 1990 р. в 16 часов

на заседании Специализированного совета К 002.23.01 а Институте математики СО АН ССо> по адресу: 630090. Новосибирск, 90, Университетский пр., 4, Институт математики.

С дай. .ертацией* можно ознакомиться в библио* еко Института математики СО АН СССР.

Автореферат разослан "_н_;_ 1990 г.

Ученый секретарь Спациализирошг"того совета кандидат ( зико-м^тематических • тук

ОБЩАЯ У'РАлГЕРИОТИКА РАБОТЫ

Ат льность ^емы. Многие задачи, исследуемые в. дискрет-Г1м анп.тизе и прэдстапл щие интерес как 4 теорем гаском, так. ;/■; и г* прикладном отношении, могут быть сформулированы как задачи о покрыв, аи множества нек горикг системами его подмнс -.вста«Х ка- 1 честве лримг. а мокно отметить такие ь-ввстные вадачи, как за.-дача минимизации да. локкгпвшк. нормал ьных ^ошбулевых функций, > задача о ширине и глубпэ матриц из чулей и единиц, за-ччд покрытия ит. графах и другие. К этому классу задач откооитоя и • л- ¡, дача покрытия клокаства с ог цепями, где в качества пэхрывае-м го множества рассматривается ят^изв6лтчое множество .лоч'фих-сированной длины д , ч алеьонтамк"'покрытия яняяглоя посдэдо- ; вателъ..ости слов, упорядоченных по отношению порекр'^ая.

За* • ча покрытия мчояес .ва слов цепями вбзкикаэт пря "кзу-. ченик свойств конечных и бесконечных .илвольных пос..эдода,пель-ностей и взаимосвязи -тих войств со структурой мн-жества под-слов последовательностей. Установление таких связей оказывает" -я общественным в исследовании взаимос тзи структур« функцио- '/ нирования /Щ~пс ледовательност^й в геяетш'.^, в нексорнх заг- ; дачах теории кодирования п синтеза.управляющих оиогем я , ряд* • ■ других вопросов. •' • . / , , .

Исследование заг~чи покрн-'ия множества слол гопями'* тесно.'> ^вязано с изучением структуры л свойств г; фовдеЕрейна, которые определяются отношением г.ерзкрытпя на множество всех слов фиксированной длкнч в т - буквенном алфавите, где т>а. Исследование структур и свойсив графо. де БрейН- представляет и; ерес в связи их использс анием в изучена? последовательно- :' стеи, пороадаь,«ых регистрами оддаа, при анализе хг -¡в^осл,, чай-них лоследоВслтельносте.., при построении моделей кошуникацяон-ш сетей связи ; в некото1>ых д^угл-х областях. п работе исследуется циклическая структура рифов , э ьпейла, а также находятся для "Ил оценки числ- незалкс1_..ости.

Цель работы. I. Исследование задачи покрытия и.. озготва слоч цепями и ее обобщен: - з& лчи покрытия множества дуг ор»:-енамро! ли графоь маршрутами. 2. К учокие структуры я свойотв; графов дэ Г зйна.

Методы ;:сс. дования. Р. диссертации чспрльзоваяы в основном кзтоды и розулм :ы комбинаторного ана;. зг и .еории г, «фов.

Научная новизна. Найдена слоасяость кратчайшего локры/ия • произвольного шоке, .ва иов цеп-иг. Да. j описание алгоритм* для: построения кратчайших покрытий, сложность ко. *>рого лолкно-мкальна;' Дока? эдо прздаоложение Л.Ираии и Т.. Бонда о наибольшем í числе топаряс нртересе кзади чя гамильтоновы,* циклов в графах ' де Брейна ¿' д шравитом и& 3-х, f~x и 5-ти. *'укв. Для . рафов

дэ рейла над две íhh: алфавитом получе! совпадают j по поряд-!' ку, верхняя и • нкеняя оцзяки дляь^сла независимости. ¡ SE. ~ическаа пег-ость. Результаты диссертации мог" ока-

! заться полезный при иссл' човаяии сл аности минимальных покры-' тий и алгоритмов их построения, мя задач типа разбиения и я<" , тнтия pasjwwüx мь^кеста. Прс еденные исследования графов де Брейна даго более полное п едстаа.^ние об их ¿войсгвах' и структуре. -

Апробация ра^от и Основные результаты диссертад"и доклг-давалдсь на Всесоюзных семинарах по дискретно!' математике и ое пь/локенаям (Москва, 1984, .198? гг.) на Всесоюс -ой школе-семи-иаре по горай ~эв (Новосибирск, Í989), да научных семинарах

им т у ур, км со ан "оср.

Публикации. По теме диссертации опубликовано шесть работ. . Структура я объеп рабг^ы. Диссертационнол работа состог"1 „яз введения,' четырех глав и списка литературы. 0*ъем работы -78 машинописных стрш. .ц. Сдисок литератур* содержит 44 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Бо введении обсуждается актуальность работы, дается обзор основных результатов и коротко излагается содержание дассерта-"цкн ло главам и параграфам.

• Лерлая глава нссит в основном справочный характер. В §§ I и 2- .чачи основные опре^зле: я и ооозначени.^ сформ„ ля* ^вана j-слеи'емая задача по. .¿ытия мшжества слов цепями, дана ое reo» метрическая интерпретация•

Густъ - множество всех слов длины п, , в алфавите ■¡-tn~\и. 1."m-i}, /.i>¿. Будем i-оворить, что слово <£' ■■■ ci,.,. ^ находится- в отношении следови^ш со оловом и.060SHP -ать^ -*м , если ¿¡,..¿„=¿0,...^-,.

Последовательность слов л^ТЦ,, ¿= г, ¿,

в которой £s для - ex I = /...., , ~ называемся •

цеиию. Г'тгь 4/s . ViiosecTBO «eneii являе: я

покрытием множества слоп л/ , если каждое слово m л/ ' принад-ле~".т некоторой цепи Се, -f*. l & £, а ка.^ая цепь сод». ^зит слова лишь лз множества .V Число цепей в покрытии "чзыдао^ся его сложностью. ' •

Задача покрыт:*'7 мн^кества слов пенями заключается в .нахождении для произвольного мяо; зтва слов ./ кратчайшего (наименьшего по \ аату депей) покрытия к опре. .злен; ' его сложности

em. ■:;

Графом де Брейна ß{m,n) 'называется ориеетиров-чний'граф ■ 1 •<• /f+f с мнокеотиом вершин , ложь*-пом дуг в ковром

лершх : £ и ß соединены дугой (Л, $) , еелл £ -*J3. II |>

ßfm,n) однородный и cor "жит ровно m деталь.

Задачу покрыта., мнокестза .лов c.">il. л на rpaijrx д. Брейча можно интерпретировать как задачу покрытия маршрутами множества дуг подарка, порожденного мяожг" твои // .

Через Вtm,п) обозначается грз* 3/,n,/z) с удаленными петлями, терез >rm,n.) л Zf-n,n.) числ независимости сс-ответс. jeHHO градов ßtm, п; и- ßtm.n) . Полагав л) ~ « /пегх £fA')

С..еду2 ;ая ^еоре.уд, доказакньл в § 3 "^лавы I »устань'ыгйваег свяэ менду сложностью кратч -Ишк покрытий и числом нез; зися-мости гр. )ов де Бройна.

.'ЕОРЕМА 1.1. Дг- произвольны: m>z ; и nr i сарааедлк-

яч равенство

В связи о теоремой I.I возникает вопрос об „лен" х величины X,.n,.i) . Этомг вопросу посвящена последняя глав' дне-

Втс тя глаза поезящена "С1:ледопчшш задач., покрытия миг-кества дуг ; шзвольных орграфов т ршру зми, которая яавдэгся обобщение... зада...-покрытия мко$кстза с. ов цепями.

В § I этой глава .уводят--г необходимые предваряй ¿лъние. CL ден"з ч дается жределенле шоже""за допустимых пар.

Разобтем множен, j' вершин V орграфг (I (v, С к:v г^л множества; R = 'v*Vi 6Cxr)>o}f S = L v-V / cTftr)=ojJ

741 v,4 V i S'ftr) < о J, ' i де Sttr) - a. tvr -ttro-). Два'вврсшны veV и u*eV с^шзуюг .ару Li?, it?J в rpai-j h- (V, и}, если v & T t иге. R ив графе имеется путь ' из v. в иг. Произвольное множество пар А называется допустим -м. в графе <?/К и), роли зсакдая вершила у« V входит не болое чв! б lads)/ пар этого множества. Обозначим .ерез ' у тот'ъ кемйох юге допустимого мнокг -тва пар в . рафе G(v,U\ ; ь через £(&) - сложность кратчайшего покрытия множества дуг эт "о графа мах-футами.

i / , В,4 2 приведены некоторые всп^ югательные утверждения. ■, . Б § 3 сформулирована основная теорема второй гла^ы дг -

• : ТЕСРЕИА 2,5. Пусть G-(V,U) - произвольный свя^-шй' ор-, .раф. Тогда ' ' ; .

' а) / если - сильно связный;

б). £f£\ г 2. maje. ii' v), о}.-.лМ*), если граф

-

у; :„£(}/, 1/J 'олрЧо онязный*^.. -

¡1. rf Г этом ке, параграфе Дано списание построения вс^омога-V тельного яадерафа графа C(VS </)» который затем иопо. -.зуется I в ¡i 4 при доклзетельотве основной теоремы. 1 , : В . 5 5 главы 2 найдены досыгшмые верхняя и нижняя оценки мо1№остч наибольшего допустимого многесх-а пар произвольного .. орграфа, опис я полиномиальный алгоритм нахождения этого мно-5ес;ва пут г сведения данной задачи к задаче нахождения наи-dcurouaro паросочетаниявдвудольном графе.

§ 6 дззгоя оласааио аолиномиалгн^го алгоритма пострс .кратчайшего докрыли мнокеотва дуг произвольного орграфа

. Itevipcipurr ЛИ. .'■■'.'

; /',r,v. Треть.! глаза диссертации посвящена нахождению наибольше-. -то гасла Аоп, а) попарно не пересекающихся по дугам га, мктьтояовых циклов г^^фа Зш,п). ' Вопрос о вео- хч! .з А/т, г; 6tti поставлен Л.Hi ли и Д.Бондам л связи с исследованием гра^ фав £itii,n.) как.модел>чых объектов коммуникационных сетей связч. Величина . Л т,п.) характеризует надегшозть та-юй ое-

■ а1)

* Опртчф сильно связный, если любая я' та его вершян рас палоюъа а некотором ->иен?ировя.нном цикле. Связный от ^ называется сласо евнза-м, если с .л не является сильно свиным.

ти. Ими были указаны и получены следующие зкачь.ля 'уякцля : я-гль/.) : = 1; А(= \

А/з. 2)-!. Н1 основании этих результатов А.^ва-на я Д.Бонд: зысказали прздаолокение, что л'- ,'.

m-z < А <т, л). • .' у.'-\ , ' •;■,■':

В § I главы 3 приводится полная П( лай ака; »той &~дачя и форм)лир* тгся основные > ззульта -л этой главы. ; д

В § 2 изучается с .ец: ушюе разбиение пгоже гза дуг гр&Д' ,,. 1(т,п) Б-.1 поданс-;естза, наз; .иные блоками, описывается'структура пересечения блоков с гшйг"ьтоно ыш листам,., - приводится/ условие неперес^каемоог* г^чильтоношх цикло~. V '

В § 3 доказана нижняя оценка дая наибольшего числ' попарно не пресекающихся гамяльтоковшс цикл«э;з графах де Брейня •• -Зш.п.) - яря т»$ ' и . • ■•'

ТРОРЕМА, 3.^. Для любых т* з & л*г отраведливо неравенство . 9 2 . :.

Из этой теоремы в естественной ¿¿рхнс Л оценки /1(г\<г)&. т-1 вытекают два еле. -.етв^я.

СЛЕДЗТВЙВ л, Ддя любого п.»: /. >

-. А п.) £ . ,,/

СИДСШШ 2. Дня любого. п*2 г

24 А<■■/,п) * з.''XI ^

Четверты:' параграф пооаяще.чдоказательству равенств . для любого ' V

- В § 5 приводится доказательство следугг"зй ни; 1ей ткегти. !

■. ТЕ0Н2МА 3.7. Пусть /л • простое число и /я >> Тогда; ,/-.'&{/тт,1г)? 3 ' . ДЛЯ любого '

' > Заключи.* -мьная, четверга глава диссертации пс. вящена \ хождению оценок дая чг - та независимое, и графов . 3/2,/с ). Сзязь этого вопроса с задачей покрытия шожеоа^а: слов цепями указана1! в гитавв'Т. Г-, Ч1 ,

Основным результатом этой глявы являе*"!я доказательств ? оледуиций оценки числа : зависимости л(г.п.). \

ТЕОРЕМА ч.З. Для любого справедливо н*р£~енстзо

с* ¿п( -М), 1 е-»о при

Доказательство теоремы собственно опирается на псссрое-¿i:.if лике, -07 ук-даи г-^фа Р'т, г> У, в которой вершины распо-■гага. ся а соответствии с приянсаиныглк им номерам. Такая ук-гса^л 3/гп,п-) пс полнот описать способ увелип*...яя не-KOTop'i-ч не з азпслглах. v.«c к.е от в и ".в! ть iu мог ость. Указанная в теорема 4„3 > .порядку совпадает с приведенной в § I

зт1 глава двявзй 'йЦ^даой,.

-ОСНОВНЫЕ Р53УЛТТАТ" РАБ0Ш

I. Найдем слоеность кратчайшего покрытия -роизвольного множества "лов «елями.

\ Дано описание алгоритма для построения кратчаГ'его по-кр. :ля множества .cJíob цоаямк, с^скно-^ъ которого полиномиальна.

0. Духаздя,с ,;ред.^локенио А.Ивана Д.Бонда о нак..аль-dM ч .ело i парко неявресе.-акхцг "ся га'лильтоновкх циклов в графах дз Е'-ййна над -ц*аш-1том аз 3-х 4~>. s 5-ти оукв.

. Г л: от (совдедаидкз по поряд:./ никляя и зерх.^яя оцек-ч для числа í'^SwSíc' «qst. ;двс .шах графов де БреГ.-я.

"о тем«, дассстещги онубликоаана ведущие раб^н:

1. Ню В. " о крыт i: -'пожес^^а слов '•адямл // '.-'атот дискрот-. .. то зализа в с .еякг слсетостк управляют систем. - Новоси-

б^ск, lí - Вып. 33. - С 59-' 3.

2. Ню В., Евдокамов' \.А. Покры ;е графоь.....аег тает // джг iSirfor ai.".газа в "'»тизациа управляющих егтет^л. -

J.JBOCH^'PCK, Il ,3. Вып. 40. - 72-8Г

3. Ню Ч. ) числе внутренней устойчивости графа перекрытий ело! // Выделить.л ая техника и. жг^етл&я математика. Ï..3. докл. р^люгалйкой н* -чно-гехяической конференции, Новосибирс:, isa"4 -Kobo бирск, IS& - С. 4<1.

• 4. На В. Чкс. в. утренней устойчивости (ч.в.у.) гра'" • : сокрытий двоичных слоз шш п ,/ Уи Всесоюзная конференция по пр^лемаг. •¿еоре,т,,*.ч ;кой кибернетики, Кркуюг 1985 г.: "Тез. до*«..- .'р^утск, _9dó. - Г 155.

5. Ню В. Число независимости графа де Б^йна /, Кз-здк ;: с1фе"яс"о ана-лз? в синтезе управляющих систем. - Новосибирск, 1986. - Бкп, 44.— С. 58-68.

6; Ню Г. О числе попарно ортогональных гвлшльтоноеых да: ■ ..ов в графах де Брейке - Нопосйб1»-ч;к, 1939. - 2Г> с, - (Прй-принт / АН СССР. Сиб. отд-е» Ин-т мате!, тик ; й' ¿7).