Алгебраические системы и некоторые их приложения в теории информации и автоматизации проектирования, страница 9

Рассмотрим воэмакиые геометрические интергретаиии структурного числе для параметра», раиного 1, 2 и 3. Геамет ическая интерп етзиия 1х чиСел пе вага пййядка Прежде чем дать геометрическую интерпретаиню структурного числе первого порядка, определим миагозначную функиию 'я „Ф' нв множестве ребер Е графа»>ест,>(,(г> со значениями иэ множества Ф натуральных чисел: ,у" .' ~ — Л~, (3.26) но таким образом, чтобы функиия ~ргггр, / - Ю (3.27 ) была биекиией. *уикищо (3.26) в дальнейшем будем называть описывающей, Пусть зедены простой неориентировзнный грф без петель /ссЕХ> и структурное число первого порядке .4Г -">г, Тогда, если столбиы структурнога числят взаимно однозначно соответствуют аставиым деревьям графа /; тек, что каждый сталбеи представляет собой множество значений описывекщей функции соответствующего остовнаго дерева, та граф / неэывается геометрическим иэображением числе Я и записывается в виде 'Е ~М кь Е.Х.Ю й — ~,Ы- Ь иия иии)шаниви, ставящая в соответствие каждому ребру н иЯ пару вершин д',»ь (4 ) .

15 ГсОБ (Я/. (3.28) Заметим, что геометрическим иэображением структурного чиода сцужят не один искомый граф Г, а всв графы подобных структур (21 . Если простой граф Г= Е,Х > с вершинами Л' ° нХ/г = / >г) связен и ГгюЬ/>у), то Я=,О~фР,® ( З.29) где Р - однострочное структурное число, геометрический образ которого б- =ОЬ! Р ) есть базисный подграф, т,е. звезда графа Г образованная ребрами, янпидеитными вершние Х~', Можно ут- верждать и обратное, что если число Я=Рс)Рг(В...Ф Р>тг, где Ру - однострочное простое сгруктуриое число, н аС ~ ветре чается самое большое в двух структурных числах Р и /', то ж это необходимо и достаточко дпя существования связного гео- метрического изображения структурного чяспа в виде графа.

Предположим теперь, что если сч'опбцы структурного чиспа Я взаимно однозначно соответствуют дополнениям остовных де ревьев графа / так, что каждый стопбец представляет собой мно- жество значений описывакяцей фунянии соответствуюшего допол- нения остовного дерева, то граф Г называется обратным геомет- рическим иэображением числа Я и запнсывается в виде / =СОс5/'Я) . (З.ЗО) Если простой граф Гж~Г К> связан, пикломатическое число )/(Г)х/и и ГцСОЬ(Я/, тоЯ=РФ~~~В„ВРт, где Р- » однострочное струк- турное число, геометрический образ которого с> = с ОЫ Рг' / есть базисный подграф, т.е. независимый цикл графа Г .

Нетрудно видеть, что если задано структурное число Я, столбцы когорого гредставпяют собой множество значений описы- ваюшей функции соответствующего остовного дерева графаГ, то задано и дополнительное сгрукгурное число Я, столбцы которо го представляют собой множество эначенвй описывающей функции соответствуюшего допоцнения остовного дерева графа Г, т.е, Я=~Я /а„=ПР ~ ~/2 ы а бЯ ~ . (З.ЗЦ Кроме того, ОЬ(Я) =СОВ ('Я) =/ . и если Г к б - графы дуэльной структуры, тоОЬ(Я/сГ а ООЬ(Я,) =б'. Пйжей 1.

По графу, изображенному на рис. З.1,а, найти структурно~ число Я, геометрическим изображением которого он является. По структурному чисцуЯ найти дополнительное струк- турное число и разложить ого на базисные подграфы, (*ис, 3.1 По базисным подграфам, т,е, по звездам графа Г, составляем соответствукхпие ям структурные числа: =(1,4, З~,Р =(1, 5, 2],Я (4, 5, 6), Рц (3, 6, 2) .

По найдып~ым структурным числам и выражейыо (3.29) находим структурное число Я=~~ФР~О~~~=РВРу®Р~ =РЭРэЭРцоРВРЫ~~х ~11111111 222223341 — 22233345 33344455 45645666 45656566 По выражеишо (3.31) находим дополнительное структурное число 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 ) Я 5445443354433222 66 566 554 66 56 564 3 =(4 3 638(1 4 5)й(2 5 6]=(4 3 6)О(1 4 5)(в (1 2 33= =(4 3 6~Э(2 5 6~6~1 2 3)-(.1 4 5)(й (2 5 6)(х)[1 2 3) . Па рис. 3.1,в изображен дуальиый к Г граф С=гол~-'4~ядЫЖ, ои построен по правилу Кауэра (10), которое иллшстрируется рис. 3,1,б. Геоме ическая инте и талия ст ных чисел второго порядка Пусть задана пара структурных чисел второго порядка ;4'ад~>~ и простой односторонне связный орграф I = Е,Хя~ с вершинами сеХ~г'= Г П ~ и дугами Р.

ьГ~' ~' = у 7п ) . гУ Функпяя яипидсипии (д орграфа/ ость икьекпия (р:Е л (3.32) т шопах отру. туон «.; с. э.у" можеоыть: тэ.~*э: . "; .с..: .чооептсп э столбпах гп 'кт',",но~ о п~"- эл да Тогда, если столбцы структурного числа Я взаимно одноэнач- 2 к но соответствуют факторам однородного подграфа орграфа Г так, что каждый столбец представляет собой множество значе- ний описываюшей функции фактора, а столбпы структурного ч,ос- ла Ю~ взаимно однозначно соответствуют факториельным соеди- нениям оргрефа Г так, что каждый столбец представляет собой множесгво значений описываюшей функции факториального сое- динения, то граф Г называется геометрическим изображением Л структурного числа С' =Я ОЮ и записывается в виде Ге ОЬ (С2).

(З.ЗЗ) Пусть теперь простой связный орграф Г содержит оС вхо- дов и 9 выходов (входы и выходы могут быть фиктивными) и Я = аГ~,Хй,~>есть простой односторонне связный подграф гра- фа Г от ~-го входа к,у -му выходу. Всего таких подграфов в графе Г 1=с<;гЭ, т.е. й = й,х . Тогда оргреф Г называется гео- метрическим иэображением структурного числа ~у ~~ ~ 8 (~ ' ' ~С 2 2 2 2 (3.34) и записывается так; Г= Об ('С~). (3 ЗЗ) Если орграф ~~х~ЕшХе, ф >-однородный одностороние связ- ный подграф орграфа Г=(Е, Х, (ух, а столбцы структурного чио- ла Яа представляют собой множество значений описываюшей функции факторов орграфа /~, то гпе /~~; - однострочное структурное число, геометрический об- раз которого с9~,.

зоЬ Й~~; ) есть базисный подграф, т.е. полу- звезда исхода орграфа ~~, образованная цугами, шшидентными вершине с и исходяшими иэ нее, Р~=!Хд ~ . Заметим, что в ~ложении (3.36) однострочные структур- ные числа Рд~ ( в = З.,/~) могут соответствовать другим баэись ным подграфам, а именно поцузвеэдам орграфа Г, образованным лугами, инцндентными вершине М и заходяшими в нее. др~ььп ~раб'. бр у р .3.2,6, найти структурное число '7э, геометрическим образом которого являются факторы орграфа, По базисным подграфам, т,е.

по полузвездам исхода оргра- фа 6р, составляем соответствуюшие им структурные числа: Орграф называется однородным, если в нем нет вершин с полустопонью захода и полустепенью исхода, равной нулю, Першина с цолустогонью захода, равной нулю, называется вхо- дом, о с полустгпонью исхода, равной нулю, - выходом оргра- Ф ° Л 2 Р =|'2 «2,3 | Р~а,З' 3,4| Рт« ° 4,«1 .

По этвм структурным числам и выражению (3.36) находим структурное число > ~" ~«2~2 2 З~~Е~«З 3» «З|4»»фа44» «4 2ф«3 3» «3 4» '4,4» е 4,2» Геометрический образ каждого столбца (т,е, факторы орграфа 6'а ) показан на рнс„3,2|в,г, де а, С~ С~. д ° Ф' ав, У~ ~и> 2) / |у, г аз 3 ау к ф д, ~«~ Пример 3.

Составить структурное число ь', геометричесд ким йзображением которого является орграф «, изображенный на рис. 3,2|а. По факториальному соединению орграфа «/, изображенному на рис, 3„2,д, составляем число 8~, но так како" еЯ //Ю то получаем с 1,2 > «2|З» с 3,3» «4,4> «2>2> с 3,3» «4,4 > с 2,3» «3,4 > «4„2» Геоме вческая инте талия ных чисел т етьего пйряйка Пусть задана пара структурных чисел третьего порядка 'Яу, В и> и односторонне связный орграф/"о «««,Х||/' "с вер- шинамиС еХ/х= / /г/и дугами Р" ел |«/>l»»| /, Определим много«/ значную )|ункдию/ на множестве дуг Е орграфа Г со значениями из прямого произведения множестваА и множества|у натуральных чисел 43 (3.38) у ' ~ чю ~~(~ «/)/ (3.37) яо таке: образом, чтобы функция ~: пр,у/ — (р была биекпией.

Фуихдшо (3.37) в дальнейшем будем называть опясываюшей, а орграф Г - мультвграфом, Тогда, если столбцы структурного числами~ взаимна однозначно соответст вуют факторам однородного подграфа мультнграфа/ так, что каждый столбец представляет собой множество значений опнсьмвакшей функции фактора, а столбцы структурного чиспа Ю д взаимно однозначно соответствуют факториапьяым соединениям мультяграфа Г так, что каждый столбец представпяет ссбой множество значений описываюшей фуикцни фахторяальиого соединения, то мультвграф / называется геометрячоскшл иэображением структурного чисда Су=я ~Ми записывается в ваде Я Г=ОЬ(С 3 ).

(З.ЗО) Пусть топерьмультиграф Г связен и содержит оь входов и /3 выходов (входы н выходы могут быть фиктивными), а под- графГ««Ей,Хй> графа Г есть простой односторонне связный орграф ог ч -го входа к ~ -му выходу. Тогда> если ппшо гаких подграфов Г/к в мультиграфеГ равно /, то мультнграфГ называется геометрическим иэображением структурного числа С'=С,%СИЗ(./... (/С,' (3.40) н записывается как г =а,6(с у~, (3.41) Если мупьтиграф Г' <Е,,Ма~ - однородный одностороане связный подграф мупьтиграфа Г, а стопбцы структурного чисаа Я„представпшот собой множество значеннй опнсьшаюшей функции факторов мупьтиграфа ~~, то где Р~ух- - однострочное структурное чиспо, геометрический об- раз которого ~90ф' ч 4Ъ.

- ((/э~~) б зисный подграф, абра-' ха у (7~ «7 зоваиный дугами, иипи- 1 деитнымн вершине г в г з исходяшимн иэ нее„' (Ц Иу П«]Ха), т.е, попузвеэРис. З,З да исхода (попуэвеэда захода) мультиграфа Гд. р а„ч у ~еуы, е у ~ а.э. найти структурное число, 50 По полуэвездам исхода составляем одкострочные структур- Ы 2сзе2 с 7 з с 3,4,7>) /~=Гс4,1 4ъ1, к выражению (3,42) находим /~~~=~с 1,2,1 > ' 1,2,66; По этим сгруктурным числам с 1,2>6 > с 2,3,2> с 3,4,7> с 4,1,4 > с 1>2$1 > ~Л с232> с 3,4,3> с4,1,4 > с 1,2,6> с 2,3,2> с 3,4,3> с 4В1,4 > х 1,2,1 > с 2,З,2 > х З,4,7 > к 4г1г4 > Рассмотрим еше одну геометрическую внтерпретацию структурных чисел третьего порядка, Пусгь задано структурное чио- лоЯЗ я односторонне жязиый орграф беэ петель/= сс, Х,1/ > с вершинами г'аХ//=б/г/я дугамяР аР (~ 1,/тг).