URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Малинин Л.И., Малинина Н.Л. Изоморфизм графов в теоремах и алгоритмах
Id: 89875
 

Изоморфизм графов в теоремах и алгоритмах

URSS. 2009. 256 с. Мягкая обложка. ISBN 978-5-397-00480-0. Букинист. Состояние: 4+. Блок текста: 5-. Обложка: 4+.
Обращаем Ваше внимание, что книги с пометкой "Предварительный заказ!" невозможно купить сразу. Если такие книги содержатся в Вашем заказе, их цена и стоимость доставки не учитываются в общей стоимости заказа. В течение 1-3 дней по электронной почте или СМС мы уточним наличие этих книг или отсутствие возможности их приобретения и сообщим окончательную стоимость заказа.

 Аннотация

Книга посвящена эквивалентным преобразованиям графов. Предполагается, что доказанные теоремы решают проблему изоморфизма графов, проблему нумерации графов с помощью эффективных алгоритмов без их

предварительного построения, проблему построения нормальных алгоритмов и т.д. Исследование преобразования вершинных графов в реберные демонстрирует причины возникновения NP-трудных задач с точки зрения теории графов, а также одновременную возможность и невозможность их успешного решения.

Книга предназначена для тех, кто посвятил свою жизнь той области, которая справедливо зовется решением очень трудных задач. Для студентов и ученых, для программистов, создателей сложных моделей и систем.


 Анонс

В книге представлен ряд оригинальных теорем, посвященных решению задачи "ИЗОМОРФИЗМ ГРАФОВ". Удалось доказать необходимые и достаточные условия эквивалентности ориентированных графов. Предполагается, что они могут пролить свет на природу NP-полноты. Решение этой задачи выявило специфические особенности поведения ориентированных графов с контурами. Это позволяет говорить о том, что в общем виде всегда будет P не равно NP.

Однако для той части массовых задач, алгоритм решения которых можно будет представить в виде графа без контуров, появляется возможность строить эффективные алгоритмы. Таким образом, можно предположить, что класс задач, принадлежащих к зоне P, может быть существенно расширен.


 Оглавление

Предисловие
Глава 1. Эквивалентные преобразования графов
 1.1.Двойственность вершинных и реберных графов
 1.2.Квазиканонические вершинные и реберные графы
 1.3.Преобразование матрицы непосредственных путей к квазиканонической форме
 1.4.Канонические вершинные и реберные графы
 1.5.Формирующие вершинные графы
 1.6.Выводы по главе 1
Глава 2. Конвертирование ориентированных графов
 2.1.Инварианты конвертирования
 2.2.Цикломатическое число и классы графов
 2.3.Выводы по главе 2
Глава 3. Типы графов и алгоритмы их построения
 3.1.0 вычислимости
 3.2.Алгоритм I упорядочения дуг и вершин графа без контуров
 3.3.Рекуррентный локальный алгоритм II упорядочения дуг и вершин графа без контуров
 3.4.Упрощенный алгоритм построения графа
 3.5.Эффективная рекурсивность графов с контурами
 3.6.Алгоритм IV упорядочения графа с контурами
 3.7.Поиск гамильтоновых контуров
 3.8.Выводы по главе 3
Глава 4. Построение нормальных вычислительных алгоритмов
 4.1.История вопроса
 4.2.Свойства алгоритмических схем
 4.3.Графическое представление и нормализация алгоритмов. Методы их построения
 4.4.Алгоритмические схемы
 4.5.Выводы по главе 4
Заключение
Литература
Основные обозначения

 Предисловие

"Истина, в конце концов, не остается скрытой"
Леонардо да Винчи

Невозможно начать эту книгу без весьма точной и яркой цитаты из книги Фредерика Брукса "Как проектируются и создаются программные комплексы", которая более известна под названием "Мифический человеко-месяц".

" Ни одна из сцен нашей предыстории не оставляет столь яркого впечатления, как схватка огромных животных с асфальтовой топью. Перед глазами встают динозавры, мамонты, саблезубые тигры, пытающиеся выбраться из топи. Однако чем отчаяннее борьба, тем сильнее сжимаются тиски, и как ни силен, как ни хитер зверь, в конце концов, он погибает.

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

Что же это за топь, в которой постоянно увязают наши лапы?

Приведем еще несколько цитат Джека Ривза [60]."Микропроцессоры поставляются на рынок с ошибками в логике, мосты рушатся, дамбы прорывает, самолеты падают, тысячи автомобилей и прочих потребительских продуктов отзываются с рынка производителем -- все это не раз происходило на нашей памяти, и все это результат ошибок проектировщиков. Проектирование программы -- это упражнение на управление сложностью. Сложность заложена в самих проектах, в компаниях, которые ими занимаются, и в индустрии в целом. Проектирование программ очень напоминает проектирование систем. Оно охватывает множество технологий и зачастую включает ряд дополнительных дисциплин. Спецификации ПО подвижны, они могут меняться часто и сильно в ходе процесса проектирования. Группы разработчиков также неустойчивы и меняются в ходе процесса... Все это усложняет проектирование ПО и повышает вероятность ошибок".

Что же так мешает превращению программирования в инженерную дисциплину? Не открывая Америку, можно сказать, что это тот самый пресловуто известный комбинаторный взрыв, о котором мы знаем уже довольно давно, с которым сражаемся каждый день, занимаясь программированием.

Проблемы в разработке эффективных алгоритмов для трудных задач вызвали к жизни теорию вычислительной сложности, в которой задача "Изоморфизм графов" (ИГ) до сих пор стоит особняком. Гораздо более интригующими выглядят задача коммивояжера, проблема четырех красок и т.д. Однако возможно, что именно в задаче ИГ скрыты те проблемы, которые являются доминирующими в понимании NP-полноты.

Задача ИГ является открытой, то есть на данный момент не доказана принадлежность этой задачи ни к классу P, ни ее NP-полнота. Напомним, что класс P вмещает все те проблемы, решение которых считается быстрым, то есть полиномиально зависящим от размера входа. В класс NP входят задачи, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа, а это значит, неэффективные для большинства задач. Вопрос о равенстве или неравенстве этих двух классов считается одним из самых сложных в области теоретической информатики, так как на него уже много десятилетий не найдено удовлетворительного ответа.

На данный момент времени не существует полиномиального алгоритма решения общего случая задачи ИГ, хотя разработано множество алгоритмов решения задачи ИГ для отдельных классов графов с заданными ограничениями на их структуру. Задача ИГ привлекает большое число исследователей, поскольку алгоритмы ее решения могут быть использованы в огромном числе естественнонаучных приложений, например, криптографии или построении моделей сложных процессов и систем.

Моделирование представляет собой один из основных методов познания, является формой отражения действительности и заключается в выяснении или воспроизведении тех или иных свойств реальных объектов, предметов и явлений с помощью других объектов, процессов, явлений, либо с помощью абстрактного описания в виде изображения, плана, карты, совокупности уравнений, алгоритмов и программ [61]. А основой всего системного анализа, центральным этапом исследования или проектирования любой системы является построение математических моделей [17].

Построение моделей или моделирование сложных процессов во всех случаях связано с решением проблемы формирования модели, которая должна быть адекватной исследуемому явлению и должна допускать вычисление всех необходимых характеристик. Понятие адекватности модели имеет в виду соблюдение подобия между исследуемым явлением и моделью. Подобие модели означает, что она должна в необходимой степени отражать все те свойства реального явления, которые подлежат изучению. Только в этом случае выводы, полученные с помощью модели, можно переносить на изучаемое явление.

Сложные процессы, которые являются предметом исследований в анализе систем, характеризуются явно выраженной дискретной логической структурой, и поэтому могут быть названы дискретно-непрерывными. Моделирование таких процессов требует соблюдения не только физического, но и структурного подобия между изучаемым процессом и его моделью. Оказывается необходимым применение не только критериев физического подобия, построенных на теории размерности, но и различных математических инвариантов, имеющих в своей основе понятие математического изоморфизма. Если попробовать отождествить такие сложные процессы с топологическим пространством [15], то это позволяет определить для таких процессов критерии структурного подобия или топологические свойства, соблюдение которых при переходе к модели является необходимым условием структурного подобия модели и процесса.

Вышесказанное позволяет принимать в качестве модели дискретно-непрерывного процесса ориентированный граф без контуров. Ориентированный граф имеет ряд числовых характеристик, среди которых важное место занимает цикломатическое число графа, которое равно наибольшему числу циклов в графе. Если сложный процесс может быть одновременно представлен графом и описан системой уравнений, то число независимых переменных в системе уравнений равно цикломатическому числу графа. Следовательно, цикломатическое число играет особую роль при построении моделей сложных процессов и систем.

Два класса графов: реберные и вершинные дают два типа сетевых моделей: обыкновенные и сопряженные. Такой терминологии в теории построения сетевых моделей до сих пор не существует, однако она представляется весьма удобной. Практика применения и изучение обоих классов сетевых моделей показывают, что они обладают различными свойствами.

Вкратце эти свойства можно выразить так. Обыкновенные сетевые модели (графическое отображение -- реберные графы) имеют большую наглядность и допускают для анализа и расчета их характеристик применение простых и универсальных алгоритмов, которые работаю по принципу рекуррентных последовательностей, однако они отличаются чрезвычайной сложностью построения. В свою очередь, сопряженные сетевые модели (графическое отображение -- вершинные графы) отличаются простотой построения при соблюдении требований структурного подобия практически при любой размерности, однако даже при сравнительно малой размерности отличаются сложность и трудоемкостью построения алгоритмов расчета их характеристик, что означает отсутствие у них свойства эффективной рекурсивности. Все это в теории графов подтверждается тем, что для реберных графом решение многих задач располагается в области P (полиномиальных алгоритмов), тогда как решение тех же задач, но для вершинных графов, находится в области NP (экспоненциальных алгоритмов).

Создавшееся противоречие естественным образом приводит следующей постановке задачи: найти регулярный способ преобразования вершинных графов в реберные графы при условии сохранения выбранных критериев подобия, которые и являются инвариантами такого преобразования.

Настоящая книга посвящена решению этой проблемы.

Кроме того, в книге делается попытка показать, где лежат корни проблем переборных задач.

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

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

Доказано, что любая матрица непосредственных путей может быть приведена к канонической или квазиканонической форме путем применения найденного преобразования к тем элементам матрицы, которые не удовлетворяют требованиям основных теорем и доказано, что процесс последовательного преобразования матрицы является сходящимся.

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

Доказаны условия существования в графе гамильтонова цикла.

Была также рассмотрена операция, которая позволяет уменьшить порядок исходной матрицы, не нарушая системы бинарных отношений, и доказана теорема о свертывании системы бинарных отношений без нарушения эквивалентности.

Во второй главе исследовался переход от квазиканонической или канонической двойственной матрицы смежности к операторной матрице. Он отображает в матричной форме операцию построения реберного графа по заданному вершинному графу. Матрица может быть квазиканонической или канонической, поэтому будем различать квазиканоническое или каноническое конвертирование. При прямом каноническом конвертировании цикломатическое число остается постоянным, а при квазиканоническом -- увеличивается.

Прямое конвертирование позволяет построить последовательный ряд графов, вершины которых соответствуют все более длинным упорядоченным последовательностям вершин исходного графа.

Однако этот прием в тех случаях, когда общее число путей и контуров в графе велико и число вершин графов по мере их последовательного конвертирования растет очень быстро, оказывается неудобным для поиска всех или части путей заданного вида.

Доказана теорема об инварианте конвертирования. Предложено разделение графов на три класса и выявлены необходимые и достаточные признаки этих классов. Доказаны теоремы, которые позволяют по конфигурации графа точно установить, к какому классу он принадлежит.

В третьей главе описаны алгоритмы, разработанные с использованием тех преобразований графов, которые были доказаны в виде теорем в первой и во второй главах, и которые по своим свойствам являются локальными, поэтому их сложность является не более чем полиномиальной. Некоторые алгоритмы являются линейными. На основе этих алгоритмов были созданы работающие программы.

Четвертая глава посвящена применению принципов преобразования графов к преобразованию различных алгоритмических схем.

Все вышесказанное, особенно то, что относится к конвертированию графов, с достаточной степенью точности объясняет существование так называемых NP -- полных задач. Попытка создать локальный алгоритм поиска гамильтоновых контуров в общем случае не удалась, хотя применение приведенных выше преобразований графов позволило значительно уменьшить количество вариантов перебора.

Исследования по преобразованию графов показывают, что все они, относительно операции конвертирования, делятся на три класса. Поэтому, с высокой степенью вероятности можно предположить, что любая массовая задача, относительно конфигурации графа, ее представляющего, будет также разделяться на три класса.

Если индивидуальная задача будет принадлежать к классу голономных графов, то создание эффективных алгоритмов их анализа может быть весьма вероятным. Однако мы, скорее всего, никогда не будем иметь возможности создавать эффективные алгоритмы для индивидуальных задач, которые будут отображаться прогрессивно-гетерономными графами.

Уже хорошо, что теперь по виду графа можно сделать определенные заключения. Хотя, возможно, что для каждого отдельного типа массовых задач, можно будет выявить более конкретные специфические особенности конфигурации графа, который ее представляет. Представляется, что мы никогда не будем в состоянии решить проблему NP -- полноты в общем случае.

Дело в том, что при преобразовании графов, а это всегда происходит при разработке программ, для некоторых, специфических по конфигурации графов, особые участки графов превращаются в сложные вершины, которые, в свою очередь, при дальнейшем преобразовании, порождают независимые циклы. Этот момент, как нам кажется, является ключевым при всех попытках решения проблемы NP задач в общем случае.

В этой ситуации есть некоторый обнадеживающий момент. Исследования по преобразованию графов показывают, что для определенных конфигураций графов все их преобразования будут проходить с точностью до цикломатического числа, то есть для некоторых частных конфигураций массовых задач, возможно, представится возможность создавать алгоритмы, отличающиеся от метода полного перебора. Однако, возможно, этот тезис потребует отдельных исследований для различных типов массовых задач.


 Об авторе

Леонид Иванович МАЛИНИН (1922--1999)

Заслуженный деятель науки и техники, действительный член Академии космонавтики, профессор, доктор технических наук. Полковник, ветеран Великой Отечественной войны. Закончил Военно-воздушную инженерную академию им. Н.Е. Жуковского, работал в военном научно-исследовательском институте. Основные интересы: проектирование авиационной техники. Автор более 190 научных работ.

Наталия Леонидовна МАЛИНИНА

Доцент, кандидат физико-математических наук. Доцент кафедры вычислительной математики и программирования Московского авиационного института. Основные интересы: автоматизация процесса проектирования, проблемы сложности и надежности создания программ, построение моделей сложных процессов. Автор 21 опубликованной научной работы.


 Abstract

The book is devoted to equivalent conversions between graphs. We assume that the proved theorems solve the problem of graph's isomorphism; the problem of the graph's numbering with the help of the efficient algorithms without their preliminary definition, the problem of constructing normal algorithms, etc. The analysis of the conversion of the vertex graphs into the edge graphs shows the grounds of the appearance of the NP-complete tasks from the point of view of the graph theory, and synchronous ether the opportunity or impossibility of their successful solution.

The book is assigned for those, who devote their life-time to such an area, which is truly called as the solution of very difficult tasks. It is assigned for both the students and the scientists, for either the programmers or the developers of both complicated models and systems.


 Advertisement

The book presents a number of original theorems, devoted to the solution of the GRAPH ISOMORPHISM problem. The proof of both necessary and sufficient conditions of the directed graphs' equivalence turned out well. It might be suggested that they are illuminating the nature of the NP-completeness. The solution of this problem brought out the specific features of the directed graphs with the contours. It allows to say that P is not equal NP in general.

But the possibility appears to create the effective algorithms for that part of the mass' problems, the algorithms of which can be presented with the help of the graph without the contours. That's why we can suggest that the area of the tasks, belonging to the P zone may be widen considerably.


 Table of contents

Foreword
Chapter 1. The equivalent graphs' conversions
 1.1.The duality of the both vertex and edge graphs
 1.2.The quasicanonical both vertex and edge graphs
 1.3.The transformation of the matrix of the direct paths to the quasicanonical form
 1.4.The canonical both vertex and edge graphs
 1.5.The forming vertex graphs
 1.6.The conclusions on the chapter 1
Chapter 2. The conversion of the directed graphs
 2.1.The invariants of the conversion
 2.2.The cyclomatic number and graphs' classes
 2.3.The conclusions on the chapter 2
Chapter 3. Both the graph's types and the algorithms of their construction
 3.1.On the computability
 3.2.The algorithm I of the sorting of the both vertexes and edges of the graph without the contours.
 3.3.The recurrent local algorithm II of the sorting of the both vertexes and edges of the graph without the contours
 3.4.The reduced algorithm of the graph's construction
 3.5.The effective recursiveness of the graphs with the contours
 3.6.The algorithm III of the sorting of the graph with the contours
 3.7.The search for the Hamilton circuit
 3.8.The conclusions on the chapter 3
Chapter 4. The construction of the normal computing algorithms
 4.1.The history of the problem
 4.2.The characteristics of the algorithmic schemes
 4.3.The pictorial representation and the normalization of the algorithms. The approaches for their construction
 4.4.The algorithmic schemes
Corollary
Bibliography
Table of symbols

 Foreword

"The truth in the long run will not remain hidden"
Leonardo da Vinchy

It is impossible to begin this book without quite an exact and bright quotation from the book of Frederic Brooks "Essays on Soft Engineering" which is more known as "The Mystical Man-Month".

"None of the scenes of our history leaves behind such as bright impression as the battle of the huge beasts with the asphaltic swamp. Both the dinosaurs, mammoths, sabretoothed tigers, trying to get out of the swamp, flash out. But the more desperate the battle is, the stronger the clamps are clenched. And regardless of the beast's strengths and crafts, the beast eventually perishes.

The software development of the complicated systems for the last ten years was that asphaltic (residual) swamp in which many both huge and strong beasts were stuck in. Nearly all the active systems did not fit to their specifications, to their dedications; they do not keep within their schedules and budget. Both big and small groups of the developers, the huge and the flexible ones, inevitably found themselves in the trap of the asphaltic swamp. Nothing seemed difficult -- any paw can be dragged out. But the accumulation of the synchronous and associated factors leads to the deceleration of the traffic... "

What is this swamp in which our paws stick constantly?

Let us remember some quotations from Jack Reeves: "The microprocessors are delivered to the market with the bugs in the logic, the bridges collapse, the dams break, the planes fall, thousands of motor vehicles and other consumer products are recalled from the market by their producers. We remember that it happened scores of times, and it is the result of the developers' errors. The design of the programs is the exercise in the administration of the complexity. The complexity is inserted in the projects, in the corporations, which are engaged in these projects and in the industry on the whole. The design of the programs resembles the design of the systems. It includes many techniques and often includes a number of additional disciplines. Specifications of programs' complexes are flexible; they may change very often and considerably in the process of the design. The groups of the designers are also unstable and are changing in the developing process... The design of the program is complicated by these factors and the probability of buds is increasing".

What prevents the software development to turn into the engineering discipline? We will not discover America, if we say that it is that same much talked-about combinatorial explosion. We have known about it for a long time. We are fighting against it every day when we are engaged in the programming.

The problems in the design of effective algorithms for the intractability tasks called into being the theory of the computing complexity, where the problem of the "Graph's Isomorphism" yet stays at a distance from the other ones. The problem of "The Sales Man" and "The Four Colors Theorem" and others seem more intriguing ones. But it is possible that exactly in the "Graph's Isomorphism" problem all these problems are hidden, which dominates in the interpretation of the NP-completeness.

The problem "Graph's Isomorphism" appears to be the open one. It means that for the given moment its attachment neither to the P-class, nor its NP-completeness is proved. Let us remind that class P contains all the problems, the solution of which is considered to be quick, that is, it depends polynomial from the length of the extent of the entry. The problems, for the solution of which we know only such algorithms, which depend exponentially on the length of the extent of the entry, are members of the class NP. It means that for the majority of the tasks the algorithms are ineffective. The question whether P and NP classes are equal or not is considered to be the most complicated one in the sphere of the theoretical informatics. The satisfactory answer to this question has not been found for many decades.

The polynomial algorithm for the solution of the generalized case of the problem "Graph's Isomorphism" does not exist for the time being. On the other hand, we've got many algorithms for the solution of the problem "Graph's Isomorphism" for the individual cases of the graphs with the given limitations on the graph's structure. The problem "Graph's Isomorphism" attracts many researchers, because its algorithms may be used in the great amount of the scientific applications, for example, in the cryptography or in the sphere of the construction of the complicated processes or models.

Modeling appears to be the basic method of the cognition. It appears to be the form of the reflection of the reality and concludes in the ascertainment of the either that or other characteristics of the real objects, subjects and phenomena with the help of the other objects, projects, phenomena, or with the help of the abstract definition in the form of either the representation, or the plan, or the chart, or the package of either the equations or both the algorithms and programs. The foundation of the whole system analysis, the central stage of the research or the design of any system appears the construction of the mathematical models.

Both the construction of the models or the modeling of the complicated processes in all cases is bind with the solution of the problem of the building of the model, which might be adequate to the event under the consideration and might allow calculating all the necessary characteristics. The concept of the model's adequacy means the compliance of the similarity between the effect under study and the model. The similarity of the model means that it must reflect all the characteristics of the real phenomenon, which might be examined to the necessary extent. The conclusions which were received with the help of the model might be transferred on the effect under consideration only in this case.

Complicated processes, which appear to be the objects of the research in the system analysis, are characterized by the obviously evident logical structure and that's why may be named as discretely continuous ones. The modeling of such processes demands for the compliance not only physical similarity, but also for the compliance of structural similarity between the examined process and its model. It becomes necessary to apply not only the criteria of the physical similarity, which are founded on the dimensionality theory, but also with the help of different mathematical invariants, which are founded on the concept of mathematical isomorphism. If we try to identify such complicated processes with the topological space, it will allow defining for such processes criteria of either the structural similarity or the topological features. The observance of them on transferring to the model appears to be the necessary condition of the structural similarity between the model and the process.

Everything mentioned above allows to accept the directed graph without the contours as the model of the discretely continuous process. The directed graph has some numerical characteristics. The main place in this row is occupied by the cyclomatic number, which is equal to the greatest number of graph's contours. If the complicated process may be at the same time presented with the help of the graph and be defined by the system of the equations, then the number of the independent variables in the system of the equations is equal to the cyclomatic number of the graph. So, the cyclomatic number plays a special role at constructing the models of the complicated processes and systems.

The two classes of the graphs: edge and vertexes give us two types of the net models: ordinary and conjugate. Such terminology in the theory of constructing the net models still does not exist, but it seems very suitable. The practice of the usage and analysis of both the classes of the net models shows that they possess different features.

Briefly these features are stated in the following way. The ordinary net models (the pictorial representation -- the edge graph) have the large visualization and allow the application of both the simple and the universal algorithms for their analysis and calculation of their characteristics. The algorithms work by the principal of the recurrent sequences. But such models are characterized by extreme difficulty of their construction. In its turn the conjugate net models (the pictorial representation -- vertex graphs) are characterized by simplicity of their construction in compliance of the demand of the structural similarity practically at any dimension. But even at comparatively small dimension they are characterized by the complexity and the laboriousness of the construction of the algorithms of the calculation of their characteristics. It indicates the fact of the absence of the property of the effective recursiveness. In the graph theory it is checked out by the fact that the solution of many problems is located in the P area (polynomial algorithms) whereas the solution of the same problems, but for the vertex graphs, is located in the NP area (exponential algorithms).

The generated violation naturally brings us to the following statement: to find the regular mode of the transformation of the vertex graphs into the edge graphs at the condition of keeping the selected criteria of the similarity which appear to be the invariants of such a transformation.

The presented book is devoted to the solution of this problem.

In addition an attempt has been done to show where the roots are of the problems of the enumeration of possibilities.

The duality of the connected finite directed graphs was examined in chapter one. Both the necessary and sufficient conditions of the matrix of the direct paths to have the dual nature were ascertained. The conditions were the following: the matrix of the direct paths must be at the same time the adjacency matrix of the vertexes of the vertex graph and the adjacency matrix of the edges of the edge graph at the condition that the cyclomatic numbers might be either equal (the canonical adjacency matrix) or different (the quasicanonical adjacency matrix).

The theorems are proved for the case of the directed graphs because any undirected graph may be turned into a directed graph by means of the operation of redoubling. The conversion of the arbitrary matrix of the directed paths to either the canonical form (the equality of the cyclomatic numbers) or quasicanonical one (the cyclomatic numbers are different) was found. It is shown that this conversion is conservative as regards the binary relations in the initial pair and does not disturb such criterion of the structural similarity as the system of the binary relations.

It was proved that any arbitrary matrix of the directed paths may be brought to either the canonical or the quasicanonical form by means of the found transformation to those elements of the matrix which do not satisfy to the requirements of the main theorems. It was also proved that the process of the consequent transformation of the matrix appears to be converging.

It was proved that any arbitrary system of binary relations specified on a set may be brought to either the canonical or the quasicanonical form by means of the consequent application of the same transformation to those elements of the matrix which do not satisfy to the requirements of the main theorems.

The conditions of the existence of the Hamilton circuit in the graph were proved.

The operation which allows reducing the order of the initial matrix without disturbing the binary relations' system was also examined. The theorem on the reducing of the binary relations' system without disturbing the equivalence was proved.

Chapter two is devoted to the conversion from either the quasicanonical or the canonical adjacency matrix to the operator matrix. It is mapping in the matrix's form the operation of the construction of the edge graph according to the given vertex graph. The matrix may be either the quasicanonical or the canonical one, so we'll distinguish between either the quasicanonical or the canonical converting. At the straight canonical converting the cyclomatic number remains constant, and at the quasicanonical one -- increases.

The straight converging allows constructing the consequent row of the graphs, the vertexes of which correspond to the more lengthy ordered sequences of the vertexes of the initial graph.

But such a method in cases when the total number of both the paths and the contours in the graph increases quickly at their consequent converging appears to be inconvenient for searching of either the part or the whole number of the paths of the given type.

The theorem on the invariant of the converting is proved. It is suggested to divide graphs into three classes. Both the necessary and sufficient conditions of these classes are show up. The theorems are proved according to which we can identify graphs by their configuration.

The algorithms, which are worked out with the help of those transformations, which were described as theorems in the first two chapters and which are local, so their complexity appears to be not more than polynomial, are described in chapter three. Some of them appear to be linear. On the base of these algorithms the working programs were done.

Chapter four is devoted to the application of the transformation's principals to the transformation of the algorithmic schemes. Everything which was mentioned above, especially the fact concerning the converting of the graphs, explains the existence of NP-complete problems with the sufficient degree of certainty. An attempt of the generation of the local algorithm for the searching of the Hamilton circuits does not turn out well in general, but the application of the transformations above allowed decreasing the enumerations.

The investigations on the graph's transformations show that all of those concerning the operation of the conversions are divided into three classes. So, with a high degree of certainty, it may be suggested that any mass problem, depending on the graph which represents the mass problem, also may be divided into three classes.

If the mass problem belongs to the class of the holonomic graphs, the development of the effective algorithms for their analysis might be very probable. But, most likely, we will never succeed in the development of the effective algorithms for the analysis of those mass problems, which pictorial representation will be done by means of the progressive-heteronomous graphs.

But it seems rather optimistic, that by the form of the graph we could make the definite conclusions only by the type of the graph. On the other hand, the more concrete peculiarities of the graph's configurations may be shown up for the concrete types of the mass' problems. It seems that we will never succeed in the solution of the NP-completeness in general.

The point is that at graph's transformations, and it happens every time when we are involved in the programming, for some peculiar graph's configurations, special parts of the graphs are turned into the complicated vertexes. These vertexes in turn at the further transformation generate independent cycles. It seems that this fact is the key point in all the attempts of the solution of the NP - tasks in general.

Nevertheless we have some encouraging point. The researches on the graph's transformations show that for the certain graph's configurations all their transformations will be done accurately within the cyclomatic number. So, for some particular configurations of the mass problems, perhaps we'll have the possibility to develop algorithms, which will differ from the complete enumeration. But maybe this statement must call for independent researches for different types of the mass' problems.


 The authors' data

MALININ Leonid I. 1922--1999, Honoured Science and Technic Worker, the full member of the Academy of Cosmonautics, Doctor of Technics, professor. Colonel, veteran of the Great Patriotic War. Graduated from VVIA named by Zykovskiy, worked at some army research institute. The basic interests: aviation techniques' design. Author of more than 190 research papers.

MALININA Natalia L. Docent, PhD in Computational Mathematics and Programming. Associate professor in Information Technologies. The department of Computational Mathematics and Programming, Moscow Aviation Institute. The basic interests: design automation, both the complexity and the reliability of the software, the compound processes' modeling. Author of 21 research papers.

 
© URSS 2016.

Информация о Продавце