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

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

Определение. Пусть Х». = (С»,С~,...,С ) произвольное множество элементов, называемых цветами. Отображение С: 1' — ~ 1С»,С~,...,С ), где Ъ'' — — множество вершин графа С, называется раскраской (вершинной) графа С. Раскраска называется правильной, если для любого ребра (и», и~)»= Е выполняется С(и») ф С(и2). Теорема 3.7. Вершины любого планарного графа можно правильно расЧ>асить в не более чем 5 цветов. Доказательство (индукцией по числу вершин р). 1) Базис индукции: р = 1 очевидно. 2) Пусть для р < ро утверждение справедливо и пусть С = (11, Е) планарный граф с ~1'~ = ро.

По следствию 3 из теоремы 3.5 в С есть вершина г степени не более 5. Рассмотрим укладку на плоскости графа С без пересечения ребер. Удалим из С вершину г и все инцидентные ей ребра. Получим планарный граф С| с числом вершин ро — 1. По предположению индукции его вершины можно правильно раскрасить в 5 цветов С|, С~,Св, С|, С;,. Пусть в С вершина е смежна с |||, .г~,..., в|, (||де й5). Рассмотрим 2 варианта: а) Среди цветов вершин в|, г~~,..., ||у,.

в С нет цвета С; (1|5). Тогда вершине г припишем цвет С; и получим правильную раскраску графа С в 5 цветов. б) Степень вершины в равна 5 и среди вершин и|, г~,..., в; в С~| есть все 5 цветов. Без ограничения общности будем считагь, что в укладке графа б ребра (г„с| ), (г, 6~) ~ (6~ 'в3) ~ (в; 64) ~ ( с>~ 'вэ ) выходят из || в порядке по часовой стрелке и что С(||;) = С;, г = 1,...,5. Пусть | | —— множество всех вершин в С|, до которых можно дойти из г| по ребрам графа С|, используя только вершины цветов С| и Св.

Возможны 2 варианта: б1) ||в ~ Г|. Тогда в 1'| поменяем цвета С| — ~ С~, Св -+ С|. Так как вершины из |''| не смежны с другими вершинами цветов С| и Сз, то останется правильная раскраска и среди ~а|,. г~,..., вг не будет цвета С|. Тогда вершине г припишем цвет С|. б2) вв Е 7|. Это значит, что в С| есть цепь из г| в гв, все вершины которой имеют цвета С| и Сз. Эта цепь вместе с ребрами (ав, г) и (г, в|) образует цикл в С, причем вершины в~ и г4 лежат по разные стороны от этого цикла. Это значит, что из в~ нельзя пройти в а4 в графе С| только по вершинам цветов С~ и С4. Пусть 1~ ---- множество всех вершин в С|, до которых можно дойти из ||~ по ребрам графа С|, используя только вершины цветов С~ и С4. Тогда с~ ф 1'~ и далее поступаем как в 61).

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

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

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

В ~4 — 8 мы рассмотрим, как решается задача синтеза для некоторых конкретных видов схем. ~ 4. Формулы и схемы из функциональных элементов. Задача синтеза и простейшие способы ее решения В ~8, с. 14 — 20~ дано индуктивное определение формулы и реализуемой ею функции алгебры логики ~ФЛЛ). С содержательной точки зрения формула представляет собой слово, построенное из символов "базисных" ФАЛ, символов булевых переменных ~БП) и разделителей. которое задает последовательность выполнения операций супер- позиции. Нано»~|и[[к[ зто оп1»еделение и р|и смо [1»[[з| способ п1|едс |вяления фо1зыул с помощью де1»евьев.

Пусть Х вЂ” счетный упорядоченный а||финит БП. и пусть у нас имеется счетный алфавит функциональных символов (ФС) для ооозначения ФАЛ [г[ этих БП. Две ФАЛ считакт[|си, как обычно ~8~, 'БП одинаковые отображения области значений этих БП, т. е. единичного куба В", где В = ~0,1), а и — число БП, во множество В. Функция, существенно зависящая от всех своих БП„называется су|[1естнеииой.

Пусть, далее, В = ~р[»у»,..., ~[) — система 'исходных ' ФАЛ или, иначе, базис, |где ФАЛ р,, |' = 1,...,1»„завися[: от Ц» Ц1„БП и является существенной ФАЛ„если Й; 2. Предпоз[агается, что система базисных ФАЛ полна в алгебре логики, и допускается„в общем случае, наличие в ней "лишних" ФАЛ, после ~"„»[аз[ения которых оставшаяся система по-прежнему является по.»и|ой 1см. 18)). Предполагается также, что все ФС»["„[ = 1,...

„6, различны, хотя, возможно„некоторым из них соответствуют равные ФАЛ. Сопоставим каждому ФС »|„, 1 = 1,...,6. функциональный элемент 1ФЭ) Г;» имеющий 1; входов, причем входу с номером [ соответствует [-я БП х ФАЛ д;, и один выход, на котором зта ФАЛ реализуе|гя 1[м. рис. 4.1.а). Упрощенный вариант изображения ФЭ К; В Виде Вершины графа. с пометкой: ч» В когорук» Входят»[г; упорядоченных, т. е. пронумерованных числами 1» ..„Й;, ду|; показан на рис.

4,1.б. При этом предпола|»ается что ду|»а с номером 1„1ф;„соотве[ствус[ г-му входу ФЭ с». В дальнейшем мы, как правило. не будем делагь суп|ественных различий между ФС [-; и ФЭ с.';. Чаще всего ъ[ы будем имев ь»[е.»[о с базисом В| '~~~~- ~ — »1 где базиснь[ыи яв.'[я[О Г('я ФАЛ »г[ ° х»„[г[ ~/ х» и [:[. Дадим индуктивное определение формулы над Б и реализуемой ен| ФАЛ [э[о определение в о|личие от 18) неявно предполагает наличие в В ФАЛ, тождественно равной БП).

Любая БП»г из Х считается формулой глдбииь[ О над В, которая реализует ФАЛ, равную х[, Если для всех [» [ = 1»... » Й.;, определена формула У глубины д. над оазисом Б, которая реализует ФАЛ Д от БП из Х„то запись вида У = д;~У(....,У;.,) является формулой глдб(»иы»»+ 1 над Б, где »» = н)ах~у„....

щД, которая реализует ФА,1 ~ от БП из Х такзю, что ~ = (т".;®,...,/ц). 'З.акт ")аИИСЬ ВИДа 1:11 .»2) 1:».1')» т2) ('4.3) являетс»1 формулой глубины 3 над пази(1ом БВ, кото1)ая реализуе) ФЛЛ»С1 .:Б:»2. Все записи. полученные В резу»1ьтате указанного индуктивного построения, и только они, считаклся формулам(»,над Б. Важным ча(-»ным случаем фо1)мул иад базисом БВ являются (см.„например, ~8~) диз'ьюнктивные нормальные формы ~ДНФ). Напомним тпо чюбу(о Ф ") с1 1'~» 1 1 ) мо)кно преч( 1 Ви г) е() ( овир ниенной ДНФ: где, как обычно,,е = .т и»с = .г., а Л» — множ()ство тех набо1)ОВ (т, о (= В" „для которых ~~о') = 1.

Нндукйией по 1»1уб)(не Каждой формуле г»1убины (» н(1Д Б мож- нО СОНОстаВи'гь узап)1)ядот(енное кОрнеВОе дер(.'ВО глубины (1 Вс(» ре',бра которого ориентированы к корню, каждому листу соп(н.тавлена БП из Л, а каждой Внутре)иней Верин(не — ФС из Б. 'Хак, (1)орм~»»е 1»;; соочветствует "тривиальное" дерево с единственной Вери»иной, явля»оп(ейся корнем и листом одновременно, которой сопоставлена БП 1. (см. ри(. 4.2.а). Формуле У вида (т4.1) соответствует дерево П с корнем (, показанное на рис. 4.2.6. где Х~;, ) = 1,..., Й;, — дерево с корнем С)., кото1юе соо гветствует Фо!)муле У . Гра(1), когЧ)ЫИ получается из ДЕ4)ЕВа В„СООТВЕГСтвуЮ»ПЕ)ГО фОрМтуЛЕ У, В ~)ЕЗуЛЬта)Е 'СКЛЕИВННИ»1'" листьев с ОДН(»Иковым(1 пометками, ~~~~~~~~~~ к(з(»з(»де1)ее(омт со(тгп(»етсгиеую(»т(»м формуле У.

На рис. 4.3.а показано дерево, а на рис. 4.3.6 — квазидерево, кО! Орые'. Соотве1етгвук)г форму»»е (4.3). Ъ)мс Гимт '1ТО (г)орму»1а НО Сопо("гавленНОму ей де1)еву ИЛИ КвазИде))еву ВОС('танавли Вается однозначно. Рассмогр))м:Геперь более общу Го 1ГО грайненик) с «~)ормулами мод(.".ль МОдель схем из «1)унециональных злем()н'1ов ~СФЗ), в кО'ГОрОй последовательность операций суиерпозицни оазисных ФАЛ задается г помощью ориентированного ациклического графа, обобщакнцего ква- зидерево.

и 1'д(.' ВОзмОжнО мнОГок1)агнОе и(,'иользОвание Н1)ОМ(..'жутОЧ- ных результатов. Пусть Х и У вЂ” счетные упорядоченные попарно не иересекак)щиеся алфавиты БП, причем БП из Х ~У) считак)тся ((чодными ~соответсгвенно, аьи;однй(м(1) БП. Пусть ио-прежнему Б, Б=~~)()-~! 1, — полный базис, где ФА,.1 ();, 1 = 1„...,6, зависиг от А..;, А'.; 1, БП и является существенной ФАЛ, если Л;; 2. По аналогии с упорядоченными деревьями ориенги1)ованнный граф С называе.гся уГ(орядоченным, если дуги, входящие в каждук) его йе1)щину (..

упорядочены, т. е. Нронумероваг(ы числами 1,2,..., И.+~(). ОГ)ределен((е. Схемой из функц((ональньк):. элементное над б()тисом Б называется ори(чггированный ациклический упорядоченный граф,, Ве~)нп(ны еОтОроГО ИОмечены гледук)11«им О«)1)азом: 1) каждый исток Б помечен некоторой БП из Х, причем различные истоки помечены различными БП; 2) каждая Ог.;1ичная О1 ис гока йе1ииина е (.хемы, (к)мечена ФС ()) гце 1" = 0+ОН)' 3) некоторые вершины Е помечены выходными БП из Г' так, что ОднОЙ и 'ГОй ж(1 йе$)шине МОже'Г бьГ1'ь сОНО«"(авлено нескОльеО БП из У, но 1)1)зиым йе1ниинам не можеч быть соиос"Гайлеиа одна: и га же БП.

При атом входные ~вь«ходные) БП, которые приписаны каким-либо ве1нги)нам ..', сч)гге(кггся ((тодньои(1 1соо Гй(-'Гс)венпо, ((~~:.«)дньл(11) БП .:~, а 'Ге ве1энн!Иы, ко'ГО1эыы Они со!юс'Г»1ВЛ»'ны. »э:11(эдом(1 »со(э'Гветс'ГвеннО, аыа;(!дами) СФЭ У.'. Заметим„что квазидерево, соотве Гс!Ву!(эщее формуле над базисом Б, становится СФЭ над с(„если его корню пришиать выходнукэ БП. В связи с .-.этим формулы над Б будем считать частным случаем СФЭ над Б. На рис 4.4.а показан пример СФЭ над базисом БВ с входными БП х1, ха и Выходными БП =1, а, которая получена из квазидерева, приведенно! О на рис. 4.3.б„а на ри«.