Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 79
Текст из файла (страница 79)
Таблица 5.12 Покрываем столбцы строками таблицы (табл. 5.12), в которой каждой строке взаимно однозначно соответствует пустЯ подграф, столбцу — вершина, а на пересечении з-й строки и 1-го столбца стоит 1, если у-я вершина содержится в носителе г-го пустого подграфа, и 0 в противном случае. Число допустимых состояний графа 01 ие превышает 3; следовательно, мощность покрытия этой таблицы также не должна быть больше 3. Запрещенных фигур по первой компоненте (квазиполных графов квазиплотнос- 15.5. Харакпзе иэаниз раэгозкение графа переходов 435 434 ли полученный граф (рис.
5.32,в) запрещенные фигуры, выделим полные подграфы плотности 4. Опять воспользуемся приведенным выше алгоритмом, который модифицируем так, чтобы в ярусе располагались несмежные вершины, причем взвешивались вершинами, смежными с ними. Пути, длина которых меньше 4, обрываем (рис. 5.32, г). Кроме выделенных полных подграфов плотности 4, носители КОТОРЫХ ИМЕЮТ СООтВЕтетВЕННО ВИД (Я! ЯЗ Яб, Яа), 1>51, 54 ЯЭ Яв)> (от Бз> ое> Ы 1о2> 54> Яе Ят), граф сцепления при раскраске по второй компоненте содержит еще шесть запрещенных фигур — квазиполных графов квазиплотностн 4 (рис. 5.33). Т а блик а 5.13 Каааииоаиые граФы каааиглатиасти 4 Ребра 2 2 б о (Я>/! 1,...,а! (Зз (зз Рис, б.эт Построим семантическую таблицу (табл.
5.13). Каждой ее строке взаимно однозначно соответствует ребро запрещенной фигуры, столбцу — запрещенная фигура и 1 1, если з-е ребро содержится в у-й фигуре, (~> у) (О в противном случае. Третья и седьмая строки образуют минимальное покрытие. Следовательно, при удалении из графа сцепления соответствующих им ребер (51, 0а) и (52, Ят) возможна раскраска графа тремя цветами (см. рис. 5,32, 6). В результате получаем двухкомпонент- Гл.5. Прокладкою теорие олгорип>мое ти 4) граф сцепления не содержит; следовательно, такие покрытия существуют, поскольку хроматическое число графа равно его квазиплотности. Эти покрытия имеют следующий вид: И!11'зт> 'т»» Е)> 1'т1>»3> 'ьв)> 1'тт> 'за)У> П2(1о!> 'з»> 'зт)> 1оз> та> оа)> (тэ> '24)У ° Для определенности выберем первое покрытие.
Ему соответствуют раскраска графа сцепления, представленная на рнс. 5.32, а. Согласно этой раскраске функции переходов >рба, где з — номер 0 1 компоненты разложения, у —.состояние (краска), из которого осуществляется переход, >с — состояние (краска), в которое осуществляется переход первого сомножителя графа переходов С1, имеют следующий вид: рзоо = 0Ч1, »о!01=2ЧЗЧ4Ч5Ч6, у!02 =9Ч10, >рыо= 1ЧЗЧ7Ч8ЧО >рыт= 5Ч10 >рыз =4Ч9, >Р!20 = 6, >ргт! = 2 Ч 5 Ч 7, >рг22 = 8. Для того чтобы произведение графов удовлетворяло условию автоматности, перед раскраской графа сцепления по второй компоненте необходимо соединить ребрами вершины, соцветные по первой компоненте (рис.
5.32,5). Чтобы установить, содержит (Я>, Я») (о> оь) (31, Яь) (Я», Яь) (Я», Яь) (оь> ов) (Яз',Я,) (б.,б.) (оз,ов) (оз, от) (ов, от) (д.',3.) (дз ~») (Яь> Яв) (оз, оь) (Яь, Яв) (Я», от) (3> оз) (Бт, лв) (Я>, Яз) (Я»> Яа) 1 0 1 о 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 О 1 0 . 0 1 0 0 0 0 0 0 О 1 0 1 1 0 1 О О 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 о о о 0 0 1 0 1 О О О 0 0 1 0 О 0 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 ! О 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 О 1 О 0 0 0 1 0 0 0 0 0 1 1 1 1 О 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 436 Рнс. 5.34 Рис. $.33 Рис. З.З$ Гл.б.
Прокладкою теорию алгоритмов ную раскраску графа сцепления (см. рис. 5.32, а, 6): Я! (1! 1)! Ят (О! О)! Яз (1! 2)! Яв (О! 2)! Яв — (1, 0) Яв — (О 1)! Ят (2 0) Яа — (2, 1). Удаление ребер (Яд, Яа) и (Яэ, Я71 означает, что состояния Яд и Яа исходного графа переходов не должны быть сцеплены входным вектором 8 (см.
рис. 5.32, а), а состояния Ят и Ят — вектором 2. Для расцепления этих векторов введем в соответствующих че- тырех переходах дополнительные разряды, по которым эти векторы будут отличаться. Это возможно осуществить, используя связи между компонентамн (в данном случае состояние первой компоненты) либо организуя специальный развязываюшнй блок памяти.
В первой компоненте спектра состояниям Яг и Яа сопоставлены соответственно краски 1 и 3. Для расцепления этих состояний вектор 8, взвешивающий переход из состояния Ят, расширяем до вектора 8' = 8 Яы, вектор 8, взвешивающий переход из состояния Яа, расширяем до вектора 8" = 8 Яю, где Яы Яю — значения разрядов, в которых отличаются иоды красок 1 и 3 первой компоненты спектра (рнс.
5.34, а). Для расцепления состояний Ят и Ят соответственно имеем 2' = 2 Я!о, 2и = 2 Я! з. Специальный блок памяти в данном случае представляет один элемент памяти а (рис. 5.34, б), в котором одно из состояний (например, нулевое) сопоставляется состояниям Яв и Ят, другое— состояниям Яа и Ят. В этом случае 8' = Зсе, За = Зсг, 2' = 2а, 2о = 2а. Значение специального развязываюшего блока памяти т 5.5. Характеризачил разложению графа переходов 437 фиксируется при переходе в состояние, однозначность выхода из которого определяется состоянием этого блока.
В результате получаем следующие функции возбуждения графа переходов, определяющего второй сомножнтель разложения: <ртоо =1ЧЗЧ10, !рил =2'Ч7Ч9! ~рэоэ =2оЧЗЧ8, ~рюо = 0 Ч 5 Ч 8" Ч 9, !рты — — 6, !рюа = 3 Ч 4 Ч 3', <разо = 7, ' ч!тю =1Ч4Ч6, !ртю = ОЧ5. Полученная абстрактная параллельная декомпозиция заданного автомата со связными сомножителями приведена на рис.
5.35. 438 Гл.5. Прикладнал тгорш влгоритмоа Для выяснения, возможно ли разложение рассматриваемого автомата и частичное декартово произведение несвязных между собой сомножителей, рассмотрим раскраску графа сцепления с учетом характера переходов сцепленных состояний. Такой учет позволяет не принимать во внимание связь в графе сцепления, если нз соответствующих сцепленных состояний переход осуществляется в соцветные вершины.
Следовательно, перед расширением входного вектора для расцепления внутренних состояний необходимо проверить возможность устранения этой связи одинаковой раскраской тех состояний, в которые сцепленные состояния переходят. Построим таблицу переходов заданного автомата (табл. 5.14), каждой строке которой взаимно однозначно соответствует значение входного вектора, столбцу —. внутреннее состояние, а в клетке (т', у) таблицы находится идентификатор внутреннего состояния, в которое автомат переходит из т-го состояния под воздействием 1-го входного вектора. Таблица бд4 Несвязное разложение имеет место, если (согласно покрытию семантической таблицы) связность пар 1'.Бм Бе) и (Бг, Бт) не учитывается из-за возможностей соцветности пар вершин (54, Бт) и (Бм Бзу.
Состояния 54 и Бт сцеплены, и чтобы они были соцветны, необходима соцветность вершин 51 и Бг, в которые эти состояния переходят. Соцветия Бы Бг сцеплены, и чтобы они были соцветны, необходима соцветность вершин Бз н 54. Состояния Бз, Яа не сцеплены, следовательно, могут быть соцветны. Раскрашиваем вершины Бз, 54 в один цвет. Тогда согласно свойству транзитивности отношения соцветности получаем, что каждое из подмножеств Ко = (Бы Бг, Ба), гьг = (Бз 54, Бт), Кг = ~Бб, Бв) состоит нз соцветных вершин. При найденной раскраске графа сцепления второй компоненты разложения состояния Бг, Бт являются несоцветными.
Следовательно, и второе противоречие, обуславливающее недетерминиро- г 5.6. Семантическое ослабление функциональной связности 439 ванность графа переходов второго сомножителя, также устранено. Окончательно получаем следующие функции возбуждения второй компоненты разложения: ~ртов = 0 Ч 1 Ч 2, <ргог = 3 Ч 8, <ргог = 5, <рггоаабЧ7Ч10 ргы=ОЧ2Ч5, <рггг=1, ~ргго = 6 Ч 9, <рггт = 4 Ч 8, <рггг = 10. Таким образом, имеем несвязное разложение заданного автомата, определяемое полученными системами и двухкомпонеитной раскраской вида Бг — (1> 0), 54 — (О! 1), Бт — (2, 1), Бг — (О, 0), 5б — (1~ 2)~ Ба (21 0), Бз — (1~ 1), Бв — (О, 2) В общем случае для построения параллельной абстрактной декомпозиции абсолютно минимальной связности необходимо оценить каждую раскраску по первой компоненте раскрасками по второй и выбрать многокомпонентную раскраску, удовлетворяющую заданным количествам вершин графов сомножителей и их условиям связности.
Разложение графа переходов на и компонент аналогично. 3 5.6. Семантическое ослабление функциональной связности памяти автомата Рассмотрим предельную параллельную абстрактную декомпозицию автоматов, когда подавтоматом является элемент памяти. Семантика этой декомпозиции будет семантикой функциональной связности элементов памяти. С учетом структуры квазиполных графов и двузначности булевой логики рефлексивная семантика функциональной связности элементов памяти автомата определяется следующим утверждением. Теорема 5.5. Графы сцепления, не содержащие циклов нечетпной длины, определяют кодирование, при котором элементы памятпи функционально несвязны. Этот критерий позволяет последовательно определять значения разрядов в кодах внутренних состояний аналогично тому, как это делалось при поиске параллельной абстрактной декомпозиции. Рассмотрим семантическое кодирование внутренних состояний автомата, заданного графом переходов 0 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
