автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Достижимость в частично-ориентированных графах и ее применение

¡2'511 äs &>

КШИСТЗ'йчВО БКСШ5Г0 И СРШЕРО СЯЕЦГИЛЫЮП) ОБРАЗОВАНИЯ РСФСР

РОСТОВСКИЙ ОРДЕНА ГРУДШОК» КРАСНОГО ЗгШЕЯИ ГОСУДАРСГГШШЬЙ УНИВЕРСИТЕТ

СпедпаллзггрозаянкЯ со~ет К 063.5Я.Г2 по фззако-катематяческгм паукам

На прйззх руношся

БАСАНГОВА Essaa Сд.-пезна

УДК 519.I

ДХШШЖСТЬ В ЧАСТйЧНО^ШГОтРОВАБШД; ГРЛЗЛХ И S3 ПР1ПЕЯШИЕ

05.13.16. - врЕ.',энек23 загчислзтельлоЯ теггглт-н, ïîi4ecîtns методов, ивтеиэотчбского г.толз-.гарозаяг,? з naj~F.äX асслздовапгях (информатика, зычяеязгельная тезнзка и оасснатазацпл)

ABT0FE33PA.T глссергааш па ссяснашгз учеасЯ сгепошг гггшдядата фтпнко~глзг::.татт7ео1птх неук

Гзего-ггг-Дспу IS39

у « ? >V /'?

/V -

Работа выполнена s Ростовском ордене. Трудеtoro Красного Знг^зкк государственно:; университете.

Научные руководители: доктор фазгао-цегеисдичоскш: ксук, профессор А.А.Знеоб, ксг-едвдаз фкзиао-йгагвмегеичееккх исус, доцсит Я.И.Ерусаиажк!^

Официеськыа оппоненты:доктор технических наук, профессор И.А.Йодьеовхч, всандидег физиЕо-ц&теиг.'Гичоскш: неук, старший научный сотрудник Д.К.Зсибицкий

Ведущая организация: институт нггештаис СО АН СССР, г. Новосибирск

Зсцитй диссертацаг состоится "¿5" »_ ЙКбййЛ _ _199С

в "ДО__в на. загадана: бпециаяйзпровениого совета К 063.52.

по физЕго-цгл;е:д2.твчсст! ксукси и РТУ по адресу: 344104, г. Росгог-на-Дону.Ер.Стйчкк 200/1 - корпус 2, ЕЦ Я7.

С диссертацией ковко ознакомиться в нсучной библиотек! РГУ /ул. Цушккпская 14В/. р

Авторефар&з разослан ___ ISS9 г.

Ученый секретарь специализированного совата, старший научный сотрудник ^ Х.Д.Даешйагезв

UCTtli,:, Ü " 3

? ''. ОЩШ ХАРАКТЕРИСТИКА РАБОТЫ .....,

T f

- : .Т'.ций '

Актуальность теыы. Чаще всего модельо исследуемых объектов в различных задачах служит ориентированный или неориентированный граф. Значительно рете рассматривается частично-ориентированные граЛк, то есть графы, содержащие одновременно ориентированные ребра (дути) и неориентированное ребра (звенья). Однако для резения многих задач теоретического и практического характера необходимы именно татю графы, так как граф, полученный заменой звеньев парами противоположно направленных дуг, не всегда сохраняет суть исходной задачи.

Кро^з того, загетнув роль в теории и приложениях игра-• ют вопросы ориентируемости, когда требуется кслдс:.ог звену придать направление так, чтобы получзшиЯ орграф обладал па-перед эпдзлнкгя! свойствсни; часто при этом исковая ориентация всего графа достигается на сразу, а пат за аагом, последовательным превращением звеньев в дуги, я тогда промежуточные гра£ы такзе являются частично ориентированны«!!.

Работ, где частичнс-орнентировйннне графы рассматриваются как самостоятельные объекты,"нало. В основном встречаются работы, в которых они используются для решения конкретных задач. Тая, сачзность частично-ориентированных графов рассматривается в книге А.А.Зыкова , ориентация неориентированных графов без петель исследуется в работе Дзс.Шваркрайтера и Р.Персиано. В книге Л.&орда и Д.Фалкорсо-

Зыков A.A. Основы тоорш графо в. ~ I.: Наук а, 1987. -334с.

на рассматривается задача нахождения потока в часткчно-ориектированной сзт;:. Вопросы существования баз исследуются в работах Х.Уракова. Эйлеровы цепи к циклы в частично-ориентированных графах ц их приложения рассматривается е работа:-: С.Цоя и С.МДхая, А.И.Сердюкова, Т.Еворрека. Задача, относящиеся к ограниченной связности в частично-ориентиро ванных графах, рассматриваются в работах Д.Джеффри, Хьюнг-Суна, С.I.Кузьмина, В. И.Ильина ц С.С.Катаевой.

Цель работы. Исследование вопросов сглесанной достают,зости вершин в частично-ориентированных Грефах, а иненнс

1) разработка метода, сводящего нахождение смешанных целей различных видов к каховденив орцепей на вспомогатеш ной ориентированном графе;

2) применение этого ызтода к задаче нахождения максимального потока специального вида в частично ориентированной сети к к задача нахождения смешанных циклов в одной классе бесконечных частично-ориентированных графов.

Научная новизна. В диссертации получены следующие с; ноеино новые результаты:

1) доказана сводимость смешанной связности различных ецдов с дополнительными-условиями на чередование дуг к звеньев к связности вспомогательного ориенткроважого графа;

2) получен критерий существования эйлерова сизпанног< цикла в частично-ориентированном графе, являвшийся обобщением теореи существования эйлерова цикла в ориентированно;

йорд Л., ^алкерсон Д. Истоки в сетях: Пер. с англ. -М.:Нир, 1966,- 276с.

о

неориентированной графах;

• 3) показана сводимость нахоядения максимального потока э смешанным цепям в частично ориентированной сети к нахож-знию некоторого потока по дугам на вспомогательном оргра-з;

4) доказано существование бесконечного множества смешных циклов с ограничением на порядок прохождения звень-в в бесконечных частично ориентированных графах специально класса, что доказывает существование шварцевских про-гранств Кёте с кратно-правильными базисам любой кратное-

in.H^i00

Приложения. Результаты диссертации имаят приложение теории базисов пространств Нётв, а таете практическое зкменэние при определении ofiscaa иапсталышх перевозок, ми есть запреты на последовательность прохождения участ-зз сети.

Апробация. Результаты диссертации докладывались на совместной цикле расширенных заседаний научно-исследова- . зльских егдинаров по дискретной математике (ШЦ АН УССР) по графам и гкперграфам (АН MGCP, КГУ), в цикле заседа-ifl семинара по комбинаторной математике в г.Самарканде [984г.), на U республиканской конференции'молодых ученых г.Элисте (1987г.), научных сегглнарах по теории графов в зековском, Кишиневской, {¿таской и Ростовской университете. Результаты диссертационной работы внедрены в системе травления по постазкаи продукции КАСС?.

Публикации. По теме диссертации опубликовано воезмь ifioT, из которых две ( (.2 3 ? [ 4 ]) выполнены в со-зторстве с Я.М.Ерусал-злсгли, озущесгвияпяц постакозку ря-

да, задач и одна ([ б ] ) с и.11.Д?аг;1лоЕ-^г, где автору прц-кадлеглг "графовая" часть.

Сбьех диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Общий сбъсг. дассертацш состагяяе? 104 страшеда. Списоа литературу вклвчге? 55 на.-именований.

СОДЕЗДШ РАБОТЫ

Во введении дается краткое списание предыата исследования, а Т£1Е;з краткий обзор приманенных ¡лзтсдов и получзн ных результатов.

В перзой главе рассматривается понятие сцезашюй свяа поста ь частично-ориентированном графа к различные виды скеяаякой достигкмости. Определяется понятие скепакного пу тн в чаетично-ораентированной Грефе к три типа смешанной связности: слабой, односторонней и сильной. Крема того, рассматривается ограниченная стеганная связность частично-ориентированного графа, то есть достижшосгь воршш с до-поянятелькьши условиям: на порядок, прохождения дуг н звен: ев. Вводится три основных вида ограниченной достизшыости: О/У -стесанная достигиыость, при которой дуг;: и звенья дояхны строго чередоваться, 0-смешанная достшкаюсть, при которой никакие два дуги но йогу? идти подряд, н, наконец, Д/-смезанная достикшость, когда никакие два зван не цогут идти подряд. Подробно описывается /V -сыааанна связность, используггцаяся в практических щзилозбнкях. Тал: как в отличие от обычной сосланной достижимости, ^/-сломанная досгиеиьюстъ ввршны Зу. из и ЛЛ-сыкианне

достижимость всрзяны из ^ не влечет Д'-снеяанной ДОСТИЖИМОСТИ веретны из , то вводится понятие

транзитивной А/-с;епанноЯ связности. Описывается метод, сводящий Л''-резанную достнжмосгь вершин частичио-ориентирозшшого гра$а " Сг к достетмости Берлин некоторого вспомогательного орграфа . Приводится алгоритм построения вспомогательного орграфа, имевший сложность порядка , где ^ - число вершин частично-ориентированного графа С- . Показано, что задача нахождения сильных транзитивных . // -смзаанньж компонент графа & сводится к задаче нахождения силышх компонент вспомогательного орграфа Ьл/((г) . Описан алгоритм нахождения сильных транзитивных /V-смеаанкых гохпснен? графа & . Показано тастэ, что два друт:гх гида ограниченной смолзнноЗ достетсмост:! - Ш/-смс™анная и 0-смепанкая - сгодятся г. дос?;ггс.:ост:! згр1—21 состгетствугз-

Еспог здгггеяьки: оргрзфоз гнолсгнчпо случат Л/ -сг-'сзгл-кой езлсностп. Деки алгоритм построоитгл гепемогателы"-::: орграфоэ, гкеацзэ слсгногть &(&*) . Крг:<э того, рассматривался другиз з:щы смегаансЯ ограниченной досткг.имзст;;, показало, "то все перечисленные вц^х ограклчгнной дости-тзгго&та част::чао-ср:«нтирзв8нкого графа, СЕяза-и-гыз а порядке:! прехездзвия дут 15 зг.скьаз, сводится г. трем о с но г

Вторая глаза поеггденз сгплз-.:

ти::сз в частячяо-с^нз^г'.рэзгн^г,: —г; з"лерога г.*.:в чзгтгг/кэ-сгиейглогзккг: тс фа с пнклами ор::окг;:ро:г~зсгс' п ¡:?ср::с.'гл:>г.и-

ного гргфоз, обобщением потерт:;: он яззггзгел. Дсгзсза щ.-:-

терий существования эйлерова шатанного цикла, обобщало известные критерии существования эйлерова цикла в ориеь рованнои и неориентированной графах. Необходимыми и дос точными условиями являются: I) связность графа 2) четность степени 17х калдой вершины х е-X , 3) любой части Н ^ G" графа G- выполняется нзравенм IU^ - 1Гц | , где - число звеньев в

11 4 И и « сБязывапцих И с графом & 4 И i ^н" - чи ло дуг множества И4 Иц , выходящих из И , - и ло руг, входящих в Н . Так, первые два условия Крите рия - связность графа и четность степеней вершин - coi дают с аналогичными условиями для ориентированных к неориентированных Грефов, а третье условие теряет схлсл г отсутствии дуг ( 'U0f> = ft ) и превращается в условие р венства- полустепеней захода и исхода при отсутствии зве ев ( ^кр -0") . Сорыуяпровка простая, но Е.т:гор;х1^;чос: неэффективная. Ранее критерий существования эйлерова.: си тачного цикла. Сыя получен Л.И.Сердюх-оЕЫ.: в другой форзл-с

Рассгатривазтск тшко эйлеровость чаетичио-ориегаЕ роваишх графоЕ в условиях Д/-смезашэГ. свябноегк. цзствовакие эйлерова • Д/ - сданного цикла сводится существов&киз квазкейлорова контура на вспомогательном

оргрсфе Lfi/l G-J .

Третья глава посвящена транспортной задача на час? но-ориенгированкнх гргфаг. Рассматривается задача hc:xoz дения потока, но не обычного, а такого, который коа:о представить в виде сукьаа потоков по /V -айзашша с аяи от источника к стоку. Подобная задача рассматривая! в книге горда к Сслгерсона , где кроме ооычного потов

в частично-ориентированной сети, в которой по звеньям поток разрешается только в одном из двух направлений, исследуется так называемый цепной потоп или поток по цепяи из цноаества направленных цепей от источника к стоку. Приводится один из способов получения потока по.цепяи ( в форые "дуги-цепи") из данного потока ( в форме "вертины-дуги"). В данной работе рассматривается поток по А/-сме-паннки цепяи от источника к стоку. Такую задачу нельзя свести к обычной транспортной задаче на частично-ориентированных сетях, тек как в сети вообще монет не существовать таких цепей. На множестве А/ -смешанных цепей, идущих от источника к стоку, определяется поток ^ . На вспоиогательнои ориентированном графе (тез назы-

ваемом графа Л/-с!.!еп:слных цепей) задается поток А , удовлетворяющая дополнительна условие. С псу-ст-ьэ этой фушегргл А. определяется поток 0 на нисаество ор-цепей из источника 1о в сток X,; . Нетзду всс." тре::л фор^ает потока *{ , А и . ^ существует связь. Показана эквивалентность трех задач: о нахо~дс»пт накси^тлького потока " по л/-спезсянш цепяи из а ^ в сети 6~ , о няхоэдекш максимального потока ^ по орцепям из в Тл/ в оргрсфз О") ио нЕКоздеиш .«¿аксинального

потека -Л по дугш з Си гТГЙ)

Приводится алгоритм! ксхсэдення иагссилалъного потока по //-спезанньг.- цешгл з графа О" .

Задача нахождения 1;акс:^:глънсго потока по А/-сг-'ешан-ннм цепгпл в част'дчт-ориентжоЕакной сети х-кеет непосредственное прмлзкекиз на практике а виде задачи распределения ресурсов при реалпегцяп гарантированного кеггпдезеного

снабжения по система управления Кагаакснабсбыт ШСС).

В четвертой главе рассматривается задача существования к нахождения А/-смешанных: циклов в одном классе '¿Z бесконечных частично-ориентированных графов специального вида, необходимость в которых возникла в связи с приложениями в теории базисов пространств Кёте. Основны- результатом главы является теорема, доказываэщая, что любой граф G- 6 ^ содержит хотя бы один //-смешанный цикл. Задача нахождения Д/ -смешанного цикла такке решается с по-кощью вспомогательного орграфа L/j (6-J [ 5 ] .

Данная зедача возникла в связи с приложениями в теории базисов пространств Кёте, а шенно: с решением задачи существования базиса в бесконечномерны:-: пространствах, постав-денной Банахов в 20-:-: года;:. В общей виде проблема до сих пор ке релена. Пытаются вгделить наиболее ва~ные класса и доказать судзстЕование в них базиса. Один из тшзсс кяас-сов - пространства с правильны:.:;! базисам: (банаховы, пространства степеншк рядов и др.). Доказательство существования баз:-:са в зтсм классе сводится i: задаче сучЗСТЕЭЕания /V -cixsaaics: циклов в специальном классе бесконечных чаг-ткчн-ор;гснг::рога.ч.'г?: Х'рафcs, подробно исследованных в чет-ЕортоП глазе- ьастолпзГ. payer;;, Идея использования чг.зп"!-. но-оряз£П-лроз:лк-":: rpajos ьозшткаст при пзр-

гого егопа доказательстве едхнетшгазет:: vzvzt-

7,:еп::£ базиса на коулононгн в св&рцзвзксм црэс??£нз?:ге Кь-те. Ожсгц схс-у доказательства ед'.истзенности. Рассматривается сварцееохое пространство Кёте Д , такое ч:'0 X - х'1©/^©,,,© /■• '' < где л ^ - подпространства о еллъно разяячньл.:;: иззезиальк^ст прагшгькып! базиса';;: i^nj

1-1, 4 . л пусть дано некоторое разлсг'.еше базиса на К ::с:псиент . Сбознат-г,сл 0.-^ - блс:: с.\:гт.кпх элементов по-сяедозательносгк (^а } :

Заметил, что осля в каяоЯ-лябо подпоследовательности (ксм-

аоненте) стоят рядом дза блока , 3 . то их могло

автомат цчесзся объединить з один. Если ™е встречалгея ря-и х.

дсм блоки , + м (т^л), то ;г:с нет ко дополнить блоками 0.].+ ^ , взять?« из друт;пс подпоследовательностей С сн« при этен остаются правильный). Тогда :гслно заключить, что исходный базис исаио перестроить таз, расставил блс::и з К бесг.снэчнлс рядов, что полуде: разложение базиса на ::с::лс!:?::т:;, удоглетзарягодяе уелогняи:

1°. В хгтде?! ряду сохраню?ся порядо:: следозакая блс.тоз

и I

(т.е. бло:: Я.^ должен стоять лослз блока , ссля

они пеладазт з одни ряд :* ¿-2. 7 ).

2°. Пря любе:: I = 1,2.) •.., К. по :,:ояьп:е:5 мерз дна ряда

содержат бесконечное число бло:соз .

3°. Никакие два бясха с оданахоЕПС! вврхкги икдопсамл кв

могут быть соседними з однси ряду.

4°. Элементы блоков каздого ряда образует,так называемую, правильную последовательность.

Доцустиу, что существует еаэ едко разбиение базиса на компоненты, удовлетворявшее услоЕияи 1° - 4°.Для решения проблем единственности нуглю показать, что полученный базис кисет компоненты, отличающиеся от первоначаль-

3)

Здесь и далее термина см. 'и книге - Драгилез Ц.Ц. Базисы а пространствах Ноте.-Ростов н/Д:йгд-во Рост.ун-та, 1933.-144с.

кого.не более, чем конечныы числом членов. Ранее без использования частично-ориентированных графов это удалось доказать лишь для п & 2. , Ситуацию можно описать с помогцью бесконечного частично-ориентированного графа следующим образом: возьием базисы [ ^п ) , ¡- - ^ ^ подпространств Xе - это К бесконечных последовательностей; элементам каждой из этих последовательностей поставим в соответствие верешш и располоаиы их в К бесконечных рядов (так как блок содеряиг конечное число смежных элементов, то будеы считать его элеизнтоц последовательности). Введем звенья вида } С=Ь(рис.1):

Рис Л.

Вершины полученного графа переставим так, чтобы удовлетворялись условия, соответствующие условиям 1° - 4°. Первоначальные К. бесконечных маршрута будут "перепутаны". Соседние вершины в новггх рядах соединим дутгам в направлении слева направо. Получим частично-ориентированный односторонне бесконечный граф & - К*" ) ; на рис.2 дан фрагмент графа (г при к ~ 3

Ríe.2.

Полученный частично-оризктированшй граф должен содержать янпь конечное число У\/-avc^ajciL-:: циклов, так как в противном случае нарушается условие, что последователь-кости (^rv) сильно различны . Однако из своПств построенного графа & , следует, что он:содержит бесконочное число попарно нспересекавщихся Д/ -сгазанкык циклов. Полученное противоречие доказывает, что всякий базис з X с коиюкентаст шлеет единственное разложение на

компоненты. С лс;..'оцью частично-ориентированных графов доказывается такг.е, что для кандого Я ( 1 ¿ л — °° ) существует ггеарцевское пространство Кёте с П. -кратнопра-еильны! баанссы [ ? 1. ^еи самый, проблема сущестЕэвания базиса рспепа для класса пространств с правильный бази-са!л. Позднее .на основе полученного результата В.П.Кондаковым релена вторая проблема - единственность базиса в пространствах с правильными базисами.

•Автор приносит глубокую благодарность своиы научным руководителям А.А.Зыкову и Н.М.Ерусалиыскоцу за постоянную поддержку и внимание к работе.

Основные результаты диссертационной работы опубликованы в следуицях статьях:

1. Басангова Е.0. Сиепанные циклы в бесконечных частично-ориентированных графах.- Н., 1982,- 21с,- Деп. в ЕИНШ 29.04.82, № 2084-62.

2. Басангова Е.О., Ерусалиыский Я.М. Смешанная дости-кишсть на частично-ориентированных графах. //Вычислительные систекы и алгоритмы. Ростов-на-Дону, РТУ.- 1983.-

С.135-140".

- 3. Басангова Е.О. Смешанные эйлеровы цепи. М.,1985.-11с.- Деп. в ВИШИ 19.02.85, № 1280-85.

A. Басангова Е.О., Ерусалимский Я.М. Различные виды смешанной достижимости. // Алгебра и дискретная математика. Элиста, КГУ.- 1985.- С.70-75.

5. Басангова Е.О. 00 одной транспортной задаче на частично-ориентированных графах, ///лгебра и дискретная математика. Элиста, КГУ.- 1985.- С.61-70.

6. Басангова Е.О., Драгилев М.М. О пространствах Кете с кратно-лравильньая базисами. //Математические зачетки. -1985.- т.39,вш.5.- С.727-735.

7. Басангова Е.О. Компоненты сильной связности частично-ориентированных графов. М., 1988.- 12с.- Деп.в ВИНИТИ 01.04.88, № 2516-В88.

B. Басангова Е.О. Алгоритм нахондения максимального потока в частично-ориентированной сети.// Дискретные структуры и их прилокения. Элиста, КГУ.- 1988.- С.23-28.