В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU)

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики В. Б. Алексеев, С. А. Ложкин ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, СХЕМ И АВТОМАТОВ Учебное пособие но курсам "Введение в дискретную математику" и 'Основы кибернетики' Москва 2000 УДК 519.95 ББК 22.176 А 47 Алексеев В.Б., Ложкин С.А. "Элементы теории графов, схем и автоматов" (учебное пособие для студентов) М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР Х 040777 от 23.07.1996), 2000 г. 58 с.

В программу курсов "Введение в дискретную магемагику" (1 курс) и "Основы кибернетики" (3--4 курс), которые являются обязательными для студентов, обучанпцихся по специальности 01.02 ----- прикладная математика, входят различные вопросы теории графов, схем и автоматов. В основных учебных пособиях по данным курсам некоторые из этих вопросов отсутствуют. Методическая разработка призвана восполнить указанный пробел. В ее первой части рассматриваются некоторые свойства деревьев и планарных графов. Во второй части разработки описываются различные типы схем и усганавливаются связи между ними„изучается сложность реализации этими схемами некоторых функций.

В третьей части рассматриваются автоматы и их реализация схемами, а также эксперименты с автомагами. Рецензенты: Лупанов О.Б., чл.-корр.РАН, профессор Сапоженко А.А., д.ф.-м.н., профессор Печатается по решению Ученого Совета факультета вычислительной матемагики и кибернетики МГУ им.М.В.Ломоносова. 18 В 1~ 5-89407-087-2 © Издагельский отдел факуль вета вычислительной магематики и кибернетики МГУ им.М.В.Ломоносова,2000 Введение ОГЛАВЛКНИК Часть 1. Графы Ц1 Основные понятия теории графов ~2 Деревья ~3 Планарные графы 'Часть 2.

Схемы ~4 Формулы и схемы из функциональных элементов. Задача синтеза и простейшие способы ее решения ~5 Реализация некоторых 'управляющих" систем функций алгебры логики в классе СФЭ ~6 Реализация некоторых "арифметических" систем ФАЛ в классе СФЭ ~7 Метод Шеннона для синтеза СФЭ. Верхняя и нижняя оценки функции Шеннона и сложности некоторых ФАЛ Часть 3. Автоматы ~8 Автомагные функции. Их реализация схемами из функциональных элементов и элементов задержки ~9 Эксперименты с автомагами.

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

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

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

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

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

В Я4 — 7 мы мы рассмотрим, как решается задача синтеза для схем из функциональных элементов -- для преобразователей без памяти, реализующих некоторые системы булевых функций. В Я8--9 рассматриваются автоматы-преобразователи с памятью, работающие по тактам в дискретном времени. Кроме задач анализа и синтеза авгоматов, которые рассматриваются в ~8, изучаются также эксперименты с автоматами Я9), что тесно связано с тестированием вычислительных устройсгв. Часть 1.

Графы ~ 1. Основные понятия теории графов Определение. Графом с(' «в широком понимании) называется любая пара (1', Е), где 1г = (! )„(2,...~ — множа(тно элементов любой природы, а Е = (е),е~,...) — семейство пар элементов нз Г. причем допускаются пары вида.(с;.(:,;) и одинаковые пары. Если нары В !' рассма!'рина)от('я как н(уиОрядОченнь(е, тО ! "ра(1) назынаетс(! нео1)не)()г)((1)анании. если как у(ю1)ядОч('нные„')О г1гаф называе)ся о1)()ент:щ)оаанным (оргрс)фон). Эг(((мен"!'ы множес !'Ва 1' назывгнО'гся с(е1)нхиналш гре)фа, и пары из Š— его ребрами; н орграфе онн нж)ывакптя ор)(ентиронаннык(и ребрами или дугами.

Говорят. что ребро е = (((,(:) н неориентиронанном графе соединяет нершины и и с, а н ориентированном графе дуга е = (((„()) идет из вер)нины а н вершину г. Графы можно условно изобража!'ь следуюв(им образом. Вершины будем изображагь точками, а каждое ребро «дугу) (((, с1) б Е— линией, соединяюц(ей точки„соотнетствукяцие (; и в . Если «!';.

( )— ду(а, то на эгой Линии будем указЫна(Ь с)1геЛку О! с! к «р На рис. 1.1 приведены неор((енгирован)п)й и Ориенгированный графы 6 = «1',Е), где 1 = (1,2„3„4),„Е = (е(,е2,(:в,с4.с;,,св„е() и е! —— «1.2), е2 — — (-,3), в = (3,4), е4 = (4,2), ен — — (1,4), .б — — (4,2), с'; = (1, 1).

Рис. 1.1. Пара вида «(„,()!) называется г)етлс(и, н вершин(. (ч. Если и ра (в;, !);) вс)ре-)ае)ся н Е Оолее ~Д~~~~ раза, .)О говорят ~((о «с- е ) краг))нос ребро. В графах на рис. 1.1 «4, 2) — кр)тгное ребро, е-, — петля. Замечание. Часто в литературе под графом понимается граф без петель и кратных ребер. В этом случае граф с кратными ребрами называют мультиграфом, граф с кратными ребрами и петлями исевдографом. Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих об:ьектов. Наи1эимер, струкгура молекулы является графом, в котором вершинами являются атомы, а ребра,ми — — валентные связи. Блок-схема алгоритма представляет собой орграф, в кото1эом ве1эшинами являются отдельные операгоры, а дуги указывают переходы между ними.

Другие примеры графов: элементы и соединения в электрллческой цепи, схема перекрестков и дорог, множество предприятий с указанием двухсторонних связей между ними. группа людей с указанием их психологической совместимости, структура управления с указанием обьектов и их подчиненности друг другу и т. д. Определение. Говорят. что вершины и; и и смежны в графе С = (1;Е), есллл в Е входит пара (в;,и.) элли (с|э,и;). Говорят, что ребро (дуга) (х;, о ) инллидентно вершинам и; и в . Определение. Степенью вершины в неориентированном графе называется число ребер, инцидентных данной вершине, при этом петли учитываются дважды. Вершины степени О называют изоллэрованными,.