Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 73
Текст из файла (страница 73)
Функционал качества определяется минимальным числом удаленных ребер. Запрещенные фигуры (циклы нечетной длины) образованы следующими множествами ребер: Ф„= (а, 6, с), Ф, = (а, 6, »(, е, 1). Способ преобразования — удаление ребра — имеет стоимость 1; конкретный способ преобразования обозначим указанием удаляемого ребра. Семантическая таблица имеет вид табл. 5.1.
Минимальным является, например, покрытие и = (а). Следовательно, удаляя ребро а, получаем двудолькый граф (рис. 5.б,е); Фм 'й», при этом достигнут минимум»р(Фь) = 1. 1 1 а В общем случае способ преобразования 1 1 ь может быть связан не с элементами носителя 1 с или сигнатуры модели, а с некоторыми ее 1 , компонентами. Поэтому в общем случае се- 1 с мантическое эквивалентирование предпола- 1 гает построение иерархической системы таблиц некоторой глубины Й, определяемой количеством уровней в способах преобразований. Покрытие столбцов строками первой таблицы указывает, какие компоненты запрещенных фигур должны быть изменены при приведении модели Ф, к интерпретируемому в терминах модели Фь виду.
Определение подкомпонент, которые надо изменить для изменения найденных на предыдущем шаге компонент, сводится к покрытию вто- комоыюкгы рой таблицы, построенной аналогично, и т. д. до построения Й-й таблицы, строки или столбцы которой соответствуют элементам носителя или сигнатуры, которые необходимо измени~ь при приведении модели Ф, к интерпретируемому в терминах модели Фь виду Элемекты носителя (рис. 5.9). (сн~нвтуры1 модели Для определения минимально- Ркс. 5.9 го числа элементов носителя или сигнатуры, соответствующих элементам Й-й таблицы, необходима генерация всех множеств, 15.1. Принципы карактеризоционного анализа 403 Гл,5, Прикладная теорил алгоритмов 402 каждое из которых состоит из покрываемых строк (столбцов) в последней, Й-й таблице.
Эха генерация соответствуех перебору всех покрытий (Й вЂ” 1)-й таблицы. Для получения всех пакрыхий (Й вЂ” 1)-й таблицы необходима генерация всех покрытий (Й вЂ” 2)-й таблицы и т. д. Таким образом, для нахождения минимального решения необходим перебор всех сочетаний покрытий первых Й-1 таблиц. Эта процедура принципиальна содержит перебор. Таким образом, определение сложности решения являехся минимальным по трудоемкосхи стандартным процессам.
Эхот процесс на много порядков менее трудоемок, чем процесс факхической генерации всех эквивалентных структур при поиске минимального решения синтаксическим эквивалентированием, Способы преобразования запрещенных фигур, будучи по охношению к ним однозначными, по отношению к модели в целом могут быть как однозначными, хак и неоднозначными. Например, способ преобразования запрещенных фигур для двудольного графа (нечетных циклов), основанный на удалении ребра, однозначен и для модели в целом. Рассмотрим способ преобразования нечетных циклов, заключающийся в расщеплении одной нз вершин и на две несмежные вершины о и о', каждая из которых инцидентна одному из двух ребер з и у расщепляемой вершины (рис. 5.10, о); обозначим способ преобразования как и(х, у). Рне. Ь,10 Этот способ преобразования используется в семантическом эквивалентировании при декомпозиции информационной системы с требованием максимального быстродействия, х.
е. максимального параллелизма обработки информации. Такое требование обуславливает размещение всех разделов данных, соохветсхвующих смежным вершинам, на разных дисках, т. е. приводит к дублированию некоторых разделов. Данный способ преобразования запрещенной фигуры для модели в целом (графа) не однозначен. Дело в том, чхо преобразование запрещенной фигуры при расщеплении вершины о, инциденхной ребрам х и у, фиксирует только то, что новая вершина а инциденхна ребру з, а новая вершина а' — ребру у.
Для графа в целом это означаех расщепление вершины о на о и о' с соответствующим разбиением окрестности Го (рис. 5.10), при котором х и у попадают в разные новые окрестносхи. Рассмахриваемый способ преобразования не указывает распределения всех вершин по новым окрестностям.
Семантическая таблица для графа (см. рис. 5.6,6) при таком способе преобразования имеет вид табл. 5.2 вз~ ~рт В случае неоднозначных способов пре- ~ в, ь образований необходимо проверить все в, ь,е 1 покрытия семантической таблицы. Рас- вв внг 1 '-СМатрнМ Хрн ПОКрЫтня: П1 — (О1(а, Ь)), вз Ь,У 1 'пз — †(оз(Ь, с), из(Ь, ~)), хз = 1оэ(о, с), ,оз(е, У) ). Первое покрыхие, имеющее ми- 1 .'цимальную мощность, дает минимальное решение (рис. 5.10,6). Но и вхорое покрытие, имеющее мини,мальную мощность, также определяет минимальное решение. Оба 1дреобразования, входящие в пю расщепляют из. Охвех на во,прос, сколько новых вершин дают эти расщепления вместе, дают ,построение и раскраска специального графа, который построен на множестве ребер, инциденхных аз (рис.
5.10,е). Раскраска графа (Ь1, (с, у) определяет числа вершин после расщепления ,,и разбиение окрестности Гоэ. Полученное решение минимально :(рис. 5.10, г). Преобразование, соответствующее кэ (рис. 5.10, д), не минимально. Таким образом, если применяются способы преобразований, неоднозначные для модели в целом, то необходимо для каждого покрыхия строить специальные графы и определять их минимальд1ую раскраску. Поэтому особенно актуальны оценки хроматиче:,ского числа графа (см.
гл. 3), которые позволяют бысхро отсеять большую часхь покрытий, соответствующих графам с большим хроматическим числом. Важны также "быстрые" методы раскраски графов. В целом семантическое эквивалентирование "при минимальном (неизбежном) переборе позволяет получить аб'Юолютно оптимальное решение.
На основе семантического эквивалентирования получаем двухйюнтурную структуру быстродействующего пакета прикладных й1рограмм (рис. 5.11), в котором с помощью модуля "Характер" бдроисходит автоматическая настройка на оптимальную стратегию жри проведении преобразования Ф, -+ Фь. Это придает "интел'лекхуальность*' пакету прикладных программ и позволяет отнести Модобные пакеты к классу систем искусственного интеллекта.
404 %" ! е Х1 рудо ванне ге хт ° 3 Рис. 5.11 Гл. 5. Прикладная теория аягоритмоо В предыдущих главах были рассмотрены характеризационные проблемы вложения графа в плоскость, в булево пространство, характеризации параллельно-последовательной структуры диаг- раммы Хассе, раскраски графов, частичного упорядочения мографа, проектирования логических схем в несвязных базисах. Остановимся теперь на характеризационных проблемах, в том числе на проблемах проектирования многавыходных логических схем, разложения графа переходов в частичное декартово произведение, а также на характеризационных проблемах, возникающих при проектировании оптимальных размещений данных в информационных системах. Характеризация моделей позволяет выявить объективные причины, определяющие сложность решения и трудоемкость его поиска.
$5.2. Характеризаиия и методы оптимального размещения данных в памяти ЭВМ Для современных информационных систем характерны не только большие объемы, но и сложность хранимых данных. Сложность данных проявляется в том, что они находятся в различных взаимосвязях. Таким образом, сложные данные представляются в виде набора некоторых элементарных объектов и совокупности о ношений, связывающих объекты данных. Иначе говоря, сложны информационные системы формализуются такими понятиями, как граф и мограф. Это подтверждается богатым практическим опытом построения информационных систем.
Часто возникает необходимость хранить в "чистом виде" графовые структуры, например, при использовании в базах данных моделей данных, основанных на графах. Объекты данных хранятся отдельно от своих связей, которые представляются графом. Известно несколько способов задания графов: с помощью матриц инциденций и смежности, перечислением окрестностей вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
