Дискретная математика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ имени ВЛАДИМИРА ДАЛЯ Барабаш В. В. Чалая Е. Ю. КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ (2 семестр) (для студентов специальности «Прикладная математика», «Компьютерные системы и сети») У Т В Е Р Ж Д Е Н О на заседании кафедры прикладной математики. Протокол № 2 от 27. 09. 07. Луганск 2008 УДК 62-501. 7 Курс лекций по дискретной математике (для студентов направления «Прикладная математика», а также «Компьютерные системы и сети») / Сост.: В. В. Барабаш, Е. Ю. Чалая, Луганск: изд. ВНУ им. В. Даля, 2008 - 88 с. Приведены теоретические материалы, необходимые для изучения дисциплины «Дискретная математика». Рассмотрены основные разделы 2 семестра: комбинаторика, теория графов, теория конечных автоматов, элементы теории алгоритмов. В разделе «Комбинаторика» указаны основные комбинаторные правила и формулы, связь между числовой последовательностью, производящей функцией и рекуррентным соотношением, их использование в решении задач. В разделе «Теория графов» рассмотрены основные алгоритмические задачи теории графов, вопросы, связанные с различными видами циклов на графах. В разделе «Теория конечных автоматов» приведен алгоритм минимизации автомата, рассмотрены алгоритмические задачи, решаемые с применением машины Тьюринга. Приведены задачи для самостоятельной работы студентов. Составители: Барабаш В. В., доцент. Чалая Е. Ю., ассистент. Отв. за выпуск Грибанов В. М., профессор. Рецензент Ермаков А. И., доцент. Комбинаторика. Комбинаторика – это раздел математики, в котором рассматриваются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, подчиненных некоторым условиям. Комбинаторика возникла в XVI веке. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики. В ХХ веке, в связи с созданием ЭВМ и повышением интереса к дискретной математике комбинаторика переживает бурный рост. Комбинаторные задачи возникают в анализе и алгебре, геометрии и топологии, в различных разделах математики и в приложениях. §1. Правила комбинаторики. Основные комбинаторные формулы. Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило умножения: Пусть составляются всевозможные строки длины . Пусть первая компонента строки может быть выбрана числом способов, равным . После того, как первая компонента выбрана и независимо от того, как она выбрана, вторая компонента выбирается числом способов, равным . Далее аналогично. Последняя компонента выбирается числом способов, равным . Тогда количество всех построенных строк равно произведению: . Правило сложения: Если некоторый элемент можно выбрать различными способами, а другой элемент выбирается способами, то объект «» можно выбрать способами. Замечание: Правило сложения, как и правило умножения, можно обобщить на случай слагаемых. Можно также отметить, что знак умножения в соответствующем правиле соответствует союзу «и» русского языка. А знак сложения – союзу «или». Причём, союз «или» применяется во взаимоисключающем смысле. Для дальнейшего изложения необходимо ввести следующее вспомогательное понятие. Определение 1: Пусть дано конечное множество из элементов. Всякий набор из элементов данного множества (при этом элементы в наборе могут и повторяться) будем называть - расстановками. Через понятие расстановки вводятся основные определения комбинаторики: сочетания, размещения и перестановки. При этом каждое из этих понятий может быть с повторениями и без повторений. Размещения. 1) Размещения без повторений. Определение 2: Пусть имеется различных предметов. Расстановки из элементов по элементов () называются размещениями без повторений. Обозначают: . Здесь имеется в виду, что элементы в расстановках не повторяются. В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы одним элементом или порядком элементов. Теорема 1: Число всех размещений без повторений вычисляется по формуле: . Пример: Собрание из 25 человек выбирает президиум из 3 человек. Сколько возможно вариантов выбора? . Замечание: Число размещений без повторений можно также находить по формуле: . Если в знаменателе дроби , то принято считать . 2) Размещения с повторениями. Определение размещений с повторениями аналогично предыдущему, но отличается существенно тем, что элементы в подмножествах могут повторяться. Обозначают: . Теорема 2: Число всех размещений из элементов по элементов с повторениями находится по формуле: . Доказать теорему можно индукцией по числу . Примеры: количество телефонных номеров, автомобильных номеров, комбинаций в секретном замке, генетический код. Во всех этих ситуациях в расстановках элементы могут повторяться. Количество комбинаций в секретном замке, число телефонных номеров, число автомобильных номеров, код Морзе, генетический код. Разгадка генетического кода – крупнейшее достижение биологии ХХ века. Информация записана в гигантских молекулах ДНК (дезоксирибонуклеиновой кислоты). Различные молекулы ДНК отличаются порядком 4-х азотистых оснований. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причём каждая аминокислота зафиксирована кодом из 3-х азотистых оснований. В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом столь велико, что ничтожной доли этих комбинаций хватит для зашифровки всего многообразия живых организмов за время существования жизни на земле, оно равно , где – число оснований в хромосоме. Перестановки. 1) Перестановки без повторений. Определение 3: Пусть - конечное множество из элементов. Перестановками из элементов множества называются все размещения из элементов множества . Обозначается: . Согласно определению: . Таким образом: . 2) Перестановки с повторениями. Перестановки с повторениями используются в тех задачах, в которых речь идёт не о единичных объектах, а о видах, классах, сортах элементов. Понятно, что внутри каждого вида элементы повторяются. Пусть имеются предметы различных типов: . Сколькими способами можно переставить местами элемент первого вида, элементов второго вида, ..., элементов последнего вида? Число элементов в каждой перестановке равно: . Перестановки элементов внутри вида не меняет перестановку. Она изменится только в случае межвидовых перестановок. Если бы все элементы были бы различными, то число всех перестановок равнялось бы . Но в силу того, что есть повторяющиеся объекты, получится меньшее число перестановок. Теорема 3: Число различных перестановок с повторениями находится по формуле: , где . Замечание: В комбинаторике если не нужно засчитывать какое-то число способов, то на это число делят. Поэтому в знаменателе дроби стоят числа (число перестановок элементов первого вида, которые не нужно засчитывать), (число перестановок элементов второго вида) и т. д. Перестановки элементов первого типа, второго типа и т.д. можно делать независимо друг от друга, поэтому по правилу умножения элементы данной перестановки можно переставлять способами. Значит, число различных перестановок с повторениями будет равно указанному числу. Например, перестановки букв в словах мама, математика, анаграммы – есть перестановки с повторениями. Сочетания. 1) Сочетания без повторений. Определение 3: Сочетания из элементов по элементов () – это расстановки, отличающиеся друг от друга составом, но не порядком элементов. Обозначают: . Теорема 4: Число сочетаний находится по следующей формуле: . Доказательство: . Следствие: Выведенная формула совпадает с формулой для числа повторений из элементов одного типа и элементов второго типа: . Иными словами справедливо равенство: . Примеры: Выбор делегации, число призеров в соревновании и т. д. Замечание: , . Существенное отличие числа сочетаний от числа соответствующих размещений состоит в том, что для размещений важен состав и порядок элементов в подмножествах, а для сочетаний важен только состав. 2) Сочетания с повторениями. Пусть имеется предметы различных типов. Сколько комбинаций можно сделать из них, если не принимать во внимание порядок элементов? Эту задачу в общем виде можно решать точно так же, как задачу с пирожными. Задача: В кондитерском магазине продаются пирожные 4 сортов: наполеон, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных? Зашифруем каждую покупку с помощью нулей и единиц. Напишем столько единиц, сколько куплено наполеонов, затем пишем 0, чтобы отделить пирожные одного типа от другого и т.д. Тогда каждой покупке будет соответствовать последовательность из семи единиц и трех нулей в различном порядке. Число всех таких покупок тогда будет равно: . Для числа сочетаний с повторениями существует формула: . §2. Свойства сочетаний. Бином Ньютона. Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать следующие свойства сочетаний: 1. . 2. . Доказательство: 1) . 2) . Сочетания можно встретить и в школьном курсе математики. Например, в качестве коэффициентов бинома Ньютона выступают именно сочетания. Формула бинома Ньютона в общем виде и её доказательство приводятся в следующей теореме. Теорема 1: . Доказательство: Применим индукцию по . При : . Пусть формула верна, для случая, когда . В этом случае следующее равенство будем считать выполненным: . Покажем, что формула выполняется для - й степени: . В доказательстве можно также использовать свойство: . Следствие: Рассмотрим некоторые частные случаи формулы бинома Ньютона: 1) если , то . 2) если , то . Определение 1: Коэффициенты бинома Ньютона называются биномиальными коэффициентами. Числовые значения биномиальных коэффициентов вычисляются по формуле числа сочетаний: . Готовые значения этих коэффициентов располагаются в строках треугольника Паскаля. 1 n = 0 1 1 n = 1 1 2 1 n = 2 1 3 3 1 n = 3 1 4 6 4 1 n = 4 1 5 10 10 5 1 n = 5 . . . . . . . . . . . . . . . . . . . . . . . . . Треугольник Паскаля строится следующим образом. Боковые стороны состоят из единиц. Числа, находящиеся внутри, являются суммой вышестоящих чисел. Каждая строка треугольника соответствует некоторой степени для суммы и содержит соответствующие биномиальные коэффициенты. Таким образом, для того, чтобы раскрыть степень суммы , нужно из треугольника Паскаля взять строку, соответствующую данной степени . Эта строка будет содержать нужные коэффициенты , к которым приписываются соответствующие буквенные выражения. Можно заметить, что строки треугольника Паскаля симметричны, поэтому достаточно взять только половину биномиальных коэффициентов и, если нужно, средний элемент. Формула бинома Ньютона применяется, когда нужно возвести в целую степень сумму двух слагаемых. Если же это требуется произвести для суммы трёх и более слагаемых, тогда применяют полиномиальную формулу: Сумма в правой части формулы строится по аналогии с формулой бинома. Она представляет собой сумму слагаемых, состоящих из коэффициента и буквенной части . Сумма этих слагаемых берется по всевозможным разбиениям числа на целых неотрицательных слагаемых , при этом коэффициент находится по формуле числа перестановок с повторениями: . Если числа получаются перестановкой из чисел , то считается, что . Пример: Возвести в пятую степень сумму трёх слагаемых. Здесь учитывается, что 5 можно разбить на 3 слагаемых пятью способами: ; ; ; ; . Тогда для каждого такого разбиения известны числа , . Значит, все коэффициенты можно для каждого случая найти по формуле: . Полученные коэффициенты: , , , , . Буквенная часть также формируется в связи с разложениями числа 5 на 3 слагаемых. Таким образом, получается разложение, приведённое выше. Замечание: Сумма полиномиальных коэффициентов может быть найдена по формуле: . Для коэффициентов из рассмотренного примера можно проверить: , . Рассмотрим - сочетания с повторениями, составленные из элементов типа, например из буквы . Число таких сочетаний равно: . Разобьём все эти сочетания на классы, отнеся к ‑ му классу сочетания, в которых раз входит буква . Остальные мест могут быть заняты оставшимися буквами , число которых равно . Поэтому в - й класс входит столько сочетаний, сколько можно составить сочетаний с повторениями из элементов типов, т.е. . Значит общее число всех таких сочетаний равно: , т.е. . Меняя теперь на и на и используя равенство , получаем зависимость между биномиальными коэффициентами: . Доказать эту формулу можно методом математической индукции по числу слагаемых в правой части. Используя эту зависимость, можно получить формулы для подсчёта суммы чисел натурального ряда от 1 до (при ), суммы квадратов натуральных чисел (при ), сумму кубов (при ). Если , то искомая зависимость имеет вид: . Для имеем: , или окончательно: . Для получаем: , или после преобразований: . Таким образом, можно получить формулы для сумм более высоких степеней натуральных чисел. §3. Числа Фибоначчи. Рекуррентные соотношения. При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок: . Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа. Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 г. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов. Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, поэтому всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее. Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле: . Эта зависимость называется рекуррентным соотношением. Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам). По условию, и , тогда по соотношению имеем: , , и т.д., . Определение 1: Числа называются числами Фибоначчи. Это – известная в математике последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21, ... В этой последовательности каждое последующее число является суммой двух предыдущих чисел. И в рекуррентном соотношении также последующий член находится как сумма двух предыдущих членов. Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд. Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно. Таким образом, число последовательностей с указанными свойствами, равно . Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа . Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму. Это равенство можно доказать иначе. Обозначим: , . Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и . Определение 2: Рекуррентное соотношение имеет порядок , если оно позволяет вычислять через предыдущих членов последовательности: . Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка. Определение 3: Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению. Если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно. Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения. По известным рекуррентным соотношениям и начальным членам можно выписывать члены последовательности один за другим и таким путем мы можем получить любой её член. Но во многих случаях, нам не нужны все предыдущие члены, а необходим один определенный член. В этом случае удобнее иметь формулу ‑ го члена последовательности. Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой. Определение 4: Решение рекуррентного соотношения ‑ го порядка называется общим, если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения. Например, для соотношения общим решение будет . В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны. Тогда найдутся такие и , что Очевидно, для любых , система уравнений имеет единственное решение. Определение 5: Рекуррентное соотношение называется линейным, если оно записывается в виде: , где - числовые коэффициенты. Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. Однако для решения линейных рекуррентных соотношений есть общие правила решения. Рассмотрим сначала соотношение 2-го порядка . Решение этого соотношения основано на следующих утверждениях. Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения. Теорема 3: Если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения . Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка. Пусть дано рекуррентное соотношение . 1) Составим квадратное уравнение , которое называется характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные). 2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные). а) Если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид . Действительно, из теорем 2, 3 следует, что - решение и система уравнений - имеет единое решение, т.к. при условии . Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни: , поэтому общее решение соотношения Фибоначчи имеет вид: . Для начальных условий , и , т.е. для последовательности получаем для констант и систему: и , поэтому . Это выражение для всех натуральных принимает целые значения. б) Рассмотрим теперь случай, когда корни характеристического уравнения совпадают, т.е. , тогда , , т.е. характеристическое уравнение имеет вид . В этом случае и рекуррентное соотношение имеет вид: . Покажем, что наряду с , выражение - также является решением нашего соотношения. Действительно: . И общее решение в этом случае будет равно: . Нетрудно видеть, что и здесь можно подобрать так, что будут удовлетворены любые начальные условия. Замечание: Линейные рекуррентные соотношения с постоянными коэффициентами порядка больше двух, решаются аналогично. Пусть соотношение имеет вид . Составляем характеристическое уравнение: . Если все корни характеристического уравнения различны, то общее решение имеет вид: . Если же, например, , то этому корню соответствуют решения: данного рекуррентного соотношения. В общем решении этому корню соответствует часть . Например, решая рекуррентное соотношение: , составляем характеристическое уравнение вида: . Его корни , . Поэтому общее решение есть: . §3. Производящие функции. Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда ещё трудней решить. Часто эти трудности удается обойти, используя производящие функции. Понятие производящей функции тесно связано с понятием бесконечного степенного ряда. Здесь необходимо знать: понятие ряда, сумма ряда, степенной ряд, сходимость степенных рядов, свойства сходящихся рядов, операции над ними. Эти понятия изложены в любом учебнике по математическому анализу, и мы их опускаем. Определение 1: Пусть дана числовая последовательность: . Образуем степенной ряд с этими коэффициентами: . Если этот ряд сходится в некоторой области к функции , то эту функцию называют производящей для последовательности чисел . Примеры: 1) Для степенного ряда , члены которого можно рассматривать как геометрическую прогрессию, знаменатель . Значит, степенной ряд при условии сходится к своей сумме . Таким образом, получаем: , если . Значит, функция является производящей для последовательности чисел (коэффициенты степенного ряда). 2) Аналогично можно получить: . Значит, функция является производящей для последовательности чисел . 3) Из формулы бинома Ньютона следует: , т.е. функция является производящей для чисел вида , где . С помощью последней производящей функции можно доказать некоторые свойства чисел , т. е. для биномиальных коэффициентов. Например: ; ; (здесь обе суммы конечны и обрываются, когда значения и станут больше ). Кроме того: , , . В последнем равенстве, если , то считают, что . Поэтому меняется от до наименьшего из чисел , . Последнее равенство можно доказать следующим образом: , . Отсюда следует: . Применяя в левой части формулу биному Ньютона и раскрывая скобки в правой части, приравниваем коэффициенты при одинаковых степенях , получаем требуемую формулу. В частном случае, когда , получаем равенство: , . Проиллюстрируем на примерах применение производящих функций к решению некоторых комбинаторных задач. 1) Рассмотрим разбиение числа на слагаемые, каждое из которых равно одному из чисел . При этом слагаемые не повторяются и их порядок не играет роли. Для решения задачи рассмотрим выражение . Раскрывая скобки, получим слагаемые вида , где – некоторые из чисел . Поэтому встретится в сумме столько раз, сколькими способами можно разбить на слагаемые требуемым образом. Например, если надо узнать, сколькими способами можно заплатить 78 копеек, беря не более одной монеты каждого достоинства, то надо составить выражение: , раскрыть скобки и найти коэффициент при слагаемом . 2) Если требуется разложить число на слагаемые , каждое из которых может встречаться в разложении один или несколько раз, тогда количество слагаемых в скобках увеличивается. Например: 1) Сколькими способами можно заплатить 29 коп., используя монеты по 2 и 5 коп? Т.е. надо найти число способов разбить число 29 на слагаемые, равные 2 и 5, причем порядок слагаемых роли не играет, и каждое слагаемое может повторяться несколько раз. Для этого составим выражение: . Ясно, что при раскрытии скобок выражение войдет в разложение с коэффициентом, равным числу решений уравнения . В частности, коэффициент при дает ответ на вопрос задачи. Вместо раскрытия скобок можно поступить иначе: составить производящую функцию. Эта функция представляет собой произведение двух дробей: . Разделив «уголком» числитель на знаменатель, находим коэффициент при выражении . 2) Поступающий в ВУЗ должен сдать 4 экзамена, причем для поступления достаточно набрать 17 балов. Сколькими способами абитуриент может сдать экзамены, чтобы поступить в ВУЗ? Требуется узнать, сколькими способами можно представить число 17 в виде суммы 4-х слагаемых, принимающих значения 3, 4, 5, причем здесь порядок слагаемых имеет значение. Для решения этой задачи можно взять производящую функцию . При раскрытии скобок каждое слагаемое встретится столько раз, сколькими способами можно разбить на сумму 4-х слагаемых, принимающих значения 3, 4 и 5. При этом встречаются члены, получаемые друг из друга перестановкой слагаемых. В выражении можно раскрыть скобки по полиномиальной теореме, а можно следующим образом: . Поэтому . . Перемножая почленно эти выражения, найдем, что коэффициент при равен 16. Значит, разложение можно сделать 16 способами. Между производящими функциями и рекуррентными соотношениями существует тесная связь. Пусть - производящая функция для последовательности чисел . Это означает, что является суммой степенного ряда: . Пусть – многочлены, причем и , значит, дробь – правильная (в противном случае можно выделить целую часть). Раскладывая дробь в ряд, получим: . Раскрывая скобки справа и приравнивая коэффициенты при одинаковых степенях , получаем: При считаем, что . А дальше все соотношения имеют вид: , где , т.к. не имеет членов степени , , … Таким образом, коэффициенты ряда , ,… удовлетворяют рассмотренному рекуррентному соотношению. Коэффициенты этого соотношения зависят только от знаменателя дроби. Числитель нужен только для нахождения первых членов рекуррентной последовательности. Обратно, если задано рекуррентное соотношение и заданы члены , то, вычисляя значения , получим производящую функцию для последовательности чисел . Полученную алгебраическую дробь можно разлагать на элементарные дроби и производить алгебраические преобразования. Теория графов. Введение Зарождение теории графов в XVIII веке было связано с математическими головоломками, и довольно долго учение о графах рассматривалось как несерьезная тема, прикладное значение которой было связано с играми и развлечениями. В этом отношении судьба теории графов схожа с судьбой теории вероятностей, которая также первоначально рассматривалась в связи с ее применениями к азартным играм. В начале XX века графы стали применяться в топологии, и даже в первой половине XX века теория графов считалась главой топологии, этого современного раздела математики. Позже выявились связи теории графов с другими разделами современной математики (например, алгебра, комбинаторика и др.), а различные приложения теории графов к широкому кругу проблем сегодня даже трудно перечислить: это, например, исследования операций и управления, задачи экономики, теории информации, социологии и т.д. Современная теория графов достигла достаточно высокого уровня формализации и удовлетворяет требованиям математической строгости. Настоящая глава посвящена первоначальному знакомству с некоторыми направлениями в теории графов. §1. Основные понятия и определения теории графов. Прежде чем приступить к точным определениям, поясним их наглядно. Любое конечное множество точек (вершин), некоторые из которых соединены попарно стрелками (в теории графов эти стрелки называются дугами), можно рассматривать как граф (рис. 1). Например, граф может изображать сеть улиц в городе, вершины графа — перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.) Отметим здесь два момента. Во-первых, не любой граф можно изобразить на плоскости так, чтобы дуги пересекались только в вершинах (рис. 2). Во-вторых, две вершины могут быть соединены несколькими дугами, идущими в одном направлении (например, таким свойством может обладать схема железных дорог). Такие дуги будем называть кратными, а граф, содержащий кратные дуги, часто называют мультиграфом (рис. 3). Если подчеркивается, что в данном графе нет кратных дуг, то он называется графом без кратных дуг. Определение 1: Мультиграфом или просто графом называется пара объектов: , где - конечное множество вершин, а - конечное подмножество прямого произведения . При этом называется множеством вершин, а - множеством дуг графа . Число указывает на количество дуг (кратность). Покажем, каким образом введенное определение формализует понятие графа, интуитивно описанное выше. Дугу (стрелку), соединяющую вершины , , мы обозначим через , где - начало дуги, - ее конец, а - номер дуги. Например, граф, изображенный на рис. 1, может быть аналитически описан соотношениями: . (*) Отметим, что при нумерации дуг не требуется, чтобы были использованы все номера, начиная с единицы и до числа дуг между данными вершинами. Например, граф на рис. 1 может быть описан так: . (**) Графы, заданные соотношениями (*) и (**), будем считать различными. Для формализации «идентичности» этих графов вводится ниже понятие изоморфизма. Как уже сказано в определении 1, элементы множества называются дугами. Определение 2: Дуга вида называется петлей. На рис. 3 присутствует петля . Несколько сложнее понятие ребра. Иногда на графе в какой-либо прикладной задаче нет необходимости задавать направление связи между вершинами и . При изображении в этом случае связь рисуют без стрелки и говорят о ребре, соединяющем и (рис. 4, а). Будем считать такие ребра объединением дуг и с одинаковыми номерами. Определение 3: Ребром называется подмножество вида . Иллюстрацией может служить рис. 4, б. Видно, что если на графе две вершины связываются дугами с противоположными направлениями, то эти две дуги могут быть заменены одним ребром. Определение 3: Граф называется симметрическим, если для любых номеров из того, что дуга следует, что дуга . Из определения видно, что множества вида для симметрического графа образуют разбиение множества . Множество классов этого разбиения обозначается и называется множеством ребер симметрического графа . Подчеркнем, что определяется только для симметрических графов. В дальнейшем, допуская вольность речи в случаях, где это не может привести к разночтениям. Вместо слов «ребро » будем говорить «ребро ». Определение 4: Полностью неориентированным графом называется пара объектов , где - конечное множество вершин, а - конечное подмножество прямого произведения , состоящее из элементов вида , где содержит ровно два элемента. У полностью неориентированных графов все дуги – есть ребра (нет направляющих стрелок ни на одной дуге). Дадим формальное определение графа без кратных дуг. Определение 5: Графом без кратных дуг называется граф , удовлетворяющий условию: для любых существует самое большее один элемент такой, что . Это означает, что каждая дуга, соединяющая ребра, встречается только один раз. Для описания графов без кратных дуг можно воспользоваться упрощающей символикой - дугу графа обозначать . Таким образом, можно дать другое определение графа без кратных дуг, эквивалентное приведенному выше. Определение 5*: Графом без кратных дуг называется пара объектов , где - конечное множество, а . Покажем, что граф без кратных дуг определяет некоторое отображение (которое также будем обозначать буквой ) . Каждому элементу сопоставим подмножество следующим образом. Считаем, что тогда и только тогда, когда . Верно и обратное: любое отображение определяет граф. Можно дать ещё одно эквивалентное определение. Определение 5**: Графом без кратных дуг называется пара объектов , где — конечное множество, а — отображение. В дальнейшем будут рассматриваться и полностью неориентированные графы без кратных ребер. Ребра такого графа будем часто обозначать или, эквивалентно и говорить о неупорядоченной паре вершин . Определение 6: Дугу и вершину назовем инцидентными, если или (вершина является либо первой, либо второй проекцией дуги ). Ребро и вершину назовем инцидентными, если инцидентны дуга и . Дугу , такую, что , назовем исходящей из , а если , то входящей в . Две вершины и называются смежными, если существует дуга, соединяющая либо с , либо с . Определение 7: Путём в графе называется такая конечная последовательность дуг , , что . Если, кроме того, , то путь называется контуром. Путь называется простым, если из неравенства следует , и элементарным, если последовательность вершин не содержит совпадающих элементов, кроме, может быть, крайних. Интерпретация пути (и контура) в графе очевидна. Путь является простым, если при движении вдоль него одна и та же дуга никогда не приходится дважды, и элементарным, если при этом никакая вершина не встречается дважды. Пусть теперь - симметрический граф. Определение 8: Цепью в симметрическом графе называется такая последовательность , ребер графа , что существует путь в , удовлетворяющий условию для . Цепь называется циклом, если соответствующий путь есть контур. Цепь называется простой (элементарной), если соответствующий путь простой (элементарный). Очевидно, что для любой цепи , существует ровно один путь , такой, что . Это доказывает корректность определений простой и элементарной цепи. Определение 9: Граф называется суграфом графа , если . Граф называется подграфом графа , если . Наконец, граф называется частью графа , если . Таким образом, суграф получается из графа удалением некоторого числа дуг (с сохранением вершин). Подграф получается из графа удалением некоторого числа вершин вместе со всеми дугами, инцидентными удаленной вершине. Часть графа получается из графа применением конечного числа обеих описанных операций. Определение 10: Наименьший симметрический граф такой, что является суграфом , называется симметризованным графом графа . Определение 11: Граф называется сильно связным, если для любых двух вершин , существует путь такой, что . Определение 12: Симметрический граф называется связным, если он сильно связен. Произвольный граф называется связным, если связен его симметризованный граф . Из этих определений прямо следует, что понятия связности и сильной связности совпадают для симметрических графов. Определение 13: Подграф графа называется компонентой связности графа , если а) связен, б) обладает свойством максимальности, т. е. если - некоторый другой связный подграф и , то графы и совпадают. Определение 14: Будем говорить, что ребро является перешейком в симметрическом графе , если при удалении этого ребра количество компонент связности графа увеличивается на единицу. Очевидно, что ребро является перешейком тогда и только тогда, когда не существует простого цикла, содержащего это ребро. Определение 15: Полустепенью исхода вершины называется число исходящих из нее дуг. Полустепенью захода вершины называется число входящих в нее дуг. Степенью вершины называется число . Замечание: Иногда в симметрических графах степенью вершины будет называться число инцидентных ей ребер. Из контекста всегда будет ясно значение числа в каждом случае. Определение 16: Ребро симметрического графа называется тупиком, если степень одной из его вершин равна единице (здесь степень вершины определяется как число инцидентных ей ребер). Определение 17: Пусть — граф, . Матрицей смежности называется матрица , в которой элемент равен количеству дуг из вида . Определение 18: Графы и называются изоморфными, если существуют взаимно однозначные отображения , такие, что . Пример. Графы и , изображенные на рис. 5, изоморфны; их изоморфизм определяется подстановкой второго порядка: . У изоморфных графов матрицы смежности очень похожи. Их можно получить одну из другой с помощью конечного числа перестановок строк и столбцов. §2. Задачи, послужившие основой теории графов. 1. Задача о кенигсбергских мостах. На рис. 6 схематически изображена карта города Кенигсберга, относящаяся к XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мостами. Жители города любили размышлять над проблемой: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту только один раз? Полностью неориентированный граф , отвечающий задаче, представлен на рис. 7. Вершины соответствуют правому и левому берегам реки, вершины - островам, ребра графа — мостам. На языке графов, задача формулируется следующим образом: существует ли в графе простой цикл, содержащий все ребра (эйлеров цикл). Л. Эйлер сформулировал и доказал необходимое и достаточное условие того, чтобы в произвольном полностью неориентированном связном графе существовал эйлеров цикл. Теорема 1: Эйлеров цикл в симметрическом связном графе существует тогда и только тогда, когда степени всех его вершин — четные числа. Доказательство: Необходимость условия теоремы очевидна, поскольку при каждом проходе через вершину, используются ровно два ребра. Достаточность можно доказать индукцией по числу ребер графа. При числе ребер, равном двум, как нетрудно видеть, теорема справедлива. Пусть утверждение теоремы верно для всех графов с числом ребер, непревосходящем числа . Для графа с числом ребер рассмотрим произвольный простой цикл. Хотя бы один такой цикл обязательно существует для графов с четными степенями вершин. Если в графе не имеется ни одного простого цикла, то любое его ребро — перешеек. Удаляя какое-либо ребро графа, инцидентное, скажем, вершинам и , разбиваем граф на две компоненты связности. Каждое ребро в этих компонентах связности — также перешеек. После удаления ребра степени вершин и стали нечетными. Склеим компоненты связности по вершинам , и. Новая вершина, как и все остальные, в полученном связном графе имеет четную степень. Число ребер в получившемся графе равно . По предположению индукции в нем существует эйлеров цикл. Но это противоречит предположению, что в каждой компоненте связности все ребра — перешейки. Если рассматриваемый простой цикл содержит все ребра, то теорема доказана. В противном случае найдутся вершины , принадлежащие парам смежных ребер цикла, такие, что из каждой исходит по крайней мере одно ребро, не входящее в построенный цикл. В силу условия теоремы число ребер, исходящих из вершины и не принадлежащих циклу , обязательно четно. Например, в графе, изображенном на рис. 8,:имеем: где есть вершины , , . Рассмотрим подграф графа , построенный с помощью ребер, не входящих в цикл . Подграф состоит, быть может, из нескольких компонент связности. Степени всех вершин — четные числа. Каждая компонента связности подграфа удовлетворяет предположению индукции, так как содержит меньше, чем ребро. Следовательно, в каждой компоненте существует; эйлеров цикл, содержащий, по крайней мере, одну из вершин . Присоединяя к циклу эйлеровы циклы подграфов , получаем эйлеров цикл графа . 2. Задача о четырех красках. Формулировка этой задачи чрезвычайно проста и не соответствует всей глубине и сложности проблемы: можно ли на любой политико-административной карте раскрасить страны так, чтобы никакие две страны, имеющие общую границу, не были раскрашены одинаковой краской, и чтобы были использованы всего четыре краски? Уточним, что если две страны граничат по точке, то они не считаются имеющими общую границу. В терминах теории графов задача может быть поставлена следующим образом. Дан произвольный полностью неориентированный плоский граф . Можно ли каждую вершину графа раскрасить с помощью одной из четырех красок так, чтобы никакие две смежные вершины (вершины, соединенные хотя бы одним ребром) не были раскрашены в один цвет. Конечно, нетрудно привести примеры графов, которые раскрашиваются в одну, две, три или четыре краски. В §6 будет доказана теорема о том, что любой плоский граф может быть раскрашен с помощью пяти красок. Тем не менее, проблема четырех красок до сих пор не решена. Удалось лишь доказать, что такую раскраску можно осуществить для всех плоских графов с числом вершин, не превосходящим 38. Задача эта приобрела известность с 1878 г., когда английский математик Кэли привел ее формулировку на заседании английского королевского научного общества; добавив, что не мог ее решить, хотя и размышлял над ней длительное время. С тех пор многие выдающиеся математики пробовали свои силы в решении этой задачи. Удивительно, что для графов, нарисованных на торе, листе Мёбиуса или бутылке Клейна, соответствующая задача решена, т. е. установлено необходимое и достаточное число красок для раскрашивания. §3. Алгоритмические задачи. 1. Задачи о кратчайших путях. 1. Путь с наименьшим числом дуг. Пусть задан произвольный граф . Требуется построить такой путь, соединяющий две заданные вершины и , который содержит наименьшее число дуг (путь кратчайшей длины, если считать, что длины всех дуг одинаковы). Если граф содержит небольшое число вершин и дуг, а задачу решает человек, то искомый путь может быть непосредственно «увиден», т. е. найден без применения каких-либо явно осознаваемых правил. При значительном количестве вершин и дуг в графе возникает необходимость в четком описании способа решения задачи. Алгоритм решения. 1°. Присвоить вершине метку 0. 2°. Если и , то присвоить каждой такой вершине метку 1. 3°. Пусть — множество вершин, имеющих метку . Вершинам множества при присвоить метку . 4°. Процесс присвоения вершинам меток прекратить, как только вершина получит некоторую метку . 5°. Рассмотреть вершины , такие, что Замечание: Если на некотором шаге невозможно присвоение метки от значения вершинам в силу того, что множество пусто, и вершина не получила метки, то это означает, что в графе не существует никакого пути, соединяющего вершину с вершиной . Доказательство того, что применение правил алгоритма всегда приводит к решению задачи 1, основывается на том очевидном факте, что вершины множества — это все те вершины, в которые можно попасть из вершины по путям, содержащим ровно дуг, и нельзя попасть по пути длины меньшей, чем . 2. Путь кратчайшей длины. Рассмотрим теперь случай, когда каждой дуге графа сопоставлено положительное число . Это число можно назвать длиной дуги. Длиной пути назовем сумму длин дуг, входящих в путь : . Возникает следующая задача. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной . Алгоритм решения. 1°. Перенумеровать вершины графа так, чтобы вершина получила номер 0. Обозначить вершину через . (При этом вершина совпадет с некоторой вершиной ). 2°. Присвоить каждой вершине метку так, чтобы при . 3°. Найти такую дугу , для которой . (Полагаем, что .) У вершины заменить метку на новую, меньшую метку . 4°. Применять правило 3° до тех пор, пока для каждой дуги не станет справедливым неравенство: . 5°. Во множестве найти такую вершину , что . Аналогично, во множестве найти такую вершину , чтобы было справедливо равенство и т. д. После некоторого числа шагов вершина совпадет с вершиной . Путь — кратчайший, его длина равна . Обоснование алгоритма. Докажем, что после конечного числа применений правила 3° для каждой дуги графа станет справедливым неравенство . Для этого заметим, что на любом этапе метки при , а метка , что можно доказать по индукции. В самом деле, при первом применении правила 3° будет изменена метка у одной из вершин , смежных с вершиной . Эта вершина получит новую метку . Предположим, что после того, как применено правило 3° раз , станет справедливым утверждение, что для . На шаге какая-то вершина получит новую метку . Но в силу предположения индукции , кроме того, ; поэтому . Ясно, что при каждом изменении метка вершины графа уменьшается на положительную величину, не меньшую, чем минимальная разность длин путей графа. Из этих двух утверждений вытекает, что метка-любой вершины графа может изменяться лишь конечное число раз. Так как вершин конечное множество, то правило 3° может применяться лишь конечное число раз. Докажем теперь утверждения, содержащиеся в пункте 5°. Вершина такая, что обязательно найдется в случае, если существует хотя бы один путь, соединяющий с вершиной . Ибо тогда, как нетрудно сообразить, метка . Поэтому — это, например, та вершина, которая послужила для изменения метки в последний раз. Аналогично доказывается существование вершин . По условию дуги графа имеют положительную длину, поэтому метки образуют строго убывающую последовательность неотрицательных чисел, отличающихся друг от друга на величину, большую или равную длине кратчайшей дуги графа. Следовательно, какое-то . (Вершина выделена тем, что ей в силу правила 2° с самого начала присвоена метка и в формировании этой метки не участвуют дуги графа.) Докажем, что путь — кратчайший. Для этого рассмотрим произвольный путь: , соединяющий решину с . Имеем неравенства: Складывая эти неравенства, получаем соотношение: , так как . В то же время, по построению пути имеем: , откуда . Пример. В графе (рис. 9) легко установить, что кратчайший путь, соединяющий вершины и , имеет длину . 2. Алгоритм построения Эйлерова цикла. Обратимся к задаче об эйлеровом цикле, уже рассмотренной нами в предыдущем параграфе. Пусть — связный граф, степени всех вершин которого — четные числа. Теорема 1 §2 гарантирует существование эйлерова цикла. Как фактически построить его? Оказывается, что достаточно выполнять следующие правила. Алгоритм. 1°. Выбрать произвольно некоторую вершину . 2°. Выбрать произвольно некоторое ребро , инцидентное , и присвоить ему номер 1. (Назовем это ребро «пройденным».) 3°. Каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего вычеркнутого ребра. 4°. Находясь в вершине, не выбирать ребра, соединяющего с вершиной , если только есть возможность другого выбора. 5°. Находясь в вершине , не выбирать ребра, которое является «перешейком» (при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру). 6°. После того, как в графе будут занумерованы все ребра, цикл , образованный ребрами с номерами от 1 до , где число ребер в графе, есть эйлеров цикл. Обоснование алгоритма. Пусть мы находимся в некоторой вершине . В исходном графе степень вершины — четное число, поэтому после зачеркивания ребер, по которым мы приходили и уходили из вершины , ее степень — нечетна. Следовательно, существует, по крайней мере, одно незачеркнутое ребро, инцидентное вершине . Если это ребро — единственное, инцидентное вершине , то оно, в силу замечания в 5° алгоритма, не может быть «перешейком», и по нему можно покинуть вершину . Пусть ребер, инцидентных вершине — нечетное число, большее единицы. Докажем, что среди них хотя бы одно ребро не является перешейком. Допустим противное: все ребра, инцидентные вершине — перешейки. Удалим одно из этих ребер, такое, чтобы вершина и оказались в разных компонентах связности. Такое ребро существует, так как в противном случае вершины и были бы связаны более чем одной простой цепью. Это означало бы, что существует простой цикл, содержащий вершины и . Но ребра, входящие в простой цикл, не могут быть перешейками. Рассмотрим компоненту связности , содержащую вершину (и не содержащую вершину ). В графе степени всех вершин, в том числе и вершины — четные числа. Следовательно, в графе существует эйлеров цикл. Ребра, входящие в цикл, не могут быть перешейками. Итак, наше допущение ведет к противоречию. Более того, мы убедились, что среди ребер, инцидентных вершине в графе, полученном из графа удалением пройденных ребер, лишь одно может быть перешейком. Таким образом, доказано, что невозможность выполнить предписания алгоритма может возникнуть только в вершине , если попасть в нее, по крайней мере, во второй раз. В отличие от других вершин степень вершины при -м попадании в нее — четна. Если эта степень равна нулю, алгоритм перестает работать. Докажем, что в этом случае эйлеров цикл уже построен. В самом деле, в силу правила 3° любое ребро может войти в цикл не более одного раза. В силу правил 4°, 5° — пройдены все ребра. Действительно, непройденные ребра определяют в графе компоненты связности. Если эти компоненты можно связать с вершиной цепью из более чем одного зачеркнутого ребра, то среди этих ребер наверняка одно — перешеек; если одним ребром, то была возможность выбора ребра, не ведущего в вершину . 3. Потоки на транспортных сетях. 1. Основная задача теории транспортных сетей. Определение 1: Транспортная сеть есть совокупность двух объектов: 1. Связного графа , обладающего свойствами: 1°) в графе отсутствуют петли, 2°) в графе существует одна и только одна вершина такая, что множество , 3°) в графе существует одна и только одна вершина , такая, что множество . 2. Целочисленной неотрицательной функции , заданной на множестве дуг графа . Вершина называется входом сети, вершина — выходом. Значение функции на дуге называется пропускной способностью дуги. Определение 2: Пусть — множество дуг, заходящих в вершину , a — множество дуг, выходящих из вершины . Целочисленная неотрицательная функция , заданная на множестве дуг графа , называется потоком, если она удовлетворяет следующим свойствам: 1) , 2) . Термины, входящие в определения 1 и 2, наводят на мысль, что при рассуждениях относительно транспортных сетей очень удобно представлять, что по дугам транспортной сети движется некоторая несжимаемая «жидкость». Дуги могут пропускать «жидкость» только в одном направлении и в количестве, не превышающем их пропускной способности. Свойство 1) определения 2 можно понимать как закон сохранения количества жидкости. Вся жидкость, движущаяся по транспортной сети, вытекает из входа сети и стекает в выход. Сколько жидкости поступает из входа сети, столько же стекает в выход, так как из свойства 1) определения 2 следует равенство: . Определение 3: Величина называется величиной потока и обозначается . Задача. На данной транспортной сети построить поток наибольшей величины. Прежде чем изложить алгоритм решения задачи, введем еще два термина. Дуга называется насыщенной, если . Поток называется полным, если каждый путь из вершины в вершину содержит хотя бы одну насыщенную дугу. Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины. 1°. Перенумеровать произвольным образом вершины сети , отличные от входа и выхода . 2°. Построить произвольный поток на транспортной сети (например, положить ). 3°. Просмотреть пути, соединяющие вход сети c выходом . Если поток полный, то перейти к пункту 4°. В противном случае рассмотреть путь , соединяющий с , все дуги которого не насыщены. Построить новый поток : где . Повторить этот процесс до получения полного потока . 4°. Присвоить целочисленные метки вершинам сети и знаки «+» или «-» дугам по следующим правилам: а) входу присвоить метку 0; б) если вершина получила некоторую метку, а — еще непомеченная вершина, то вершине , такой что присвоить метку , а дуге — знак «+»; вершине , такой что , присвоить метку , а дуге — знак «-». Остальные непомеченные вершины и дуги метки и знака не получают; в) повторить процесс, описанный в пункте 4°б) до тех пор, пока не прекратится появление новых отмеченных вершин и дуг. Если в результате процесса 4°б) вершина не получит метки, то поток обладает наибольшей величиной. В противном случае перейти к пункту 5°. 5°. Рассмотреть последовательность отмеченных вершин , каждая из которых имеет метку, равную номеру последующей вершины, и последовательность дуг и (не обязательно путь), соединяющих последовательные вершины из . Построить новый поток : Перейти к пункту 4°. 2. Соотношение между величиной потока и пропускной способностью разреза сети. Введем новые понятия теории транспортных сетей. Определение 4: Пусть множество - такое множество вершин графа, что . Множество дуг, заходящих в , т. е. соединяющих вершины с вершинами, называется разрезом сети . Определение 5: Пропускной способностью разреза называется сумма пропускных способностей дуг, входящих в разрез, т. е. . Лемма: Для любого потока и любого разреза справедливо соотношение: . Доказательство: В силу того, что выход сети , для величины потока справедливы соотношения: . Следствие: Если для некоторого потока и некоторого разреза выполняется равенство , то поток обладает наибольшей величиной. Лемма и следствие необходимы для обоснования рассмотренного алгоритма. Обоснование алгоритма. Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина потока увеличивается, по крайней мере, на единицу. Вместе с тем величина любого потока не может превзойти суммарной пропускной способности дуг, инцидентных выходу сети . Процесс присвоения меток в силу того, что каждый раз получают метку еще неотмеченные вершины, конечен. И, наконец, в п. 5° поток обладает большей величиной, чем . Это вытекает из того, что по определению вершины и правил п. 4°б) дугам, входящим в , может быть присвоен только знак «+». Получаемая по правилу 3° функция — поток. Это непосредственно следует из того, что — путь. В соответствии с правилом п. 5° строится также поток. Чтобы доказать это утверждение, рассмотрим три соседние вершины последовательности . В силу правила 4°б) возможны только ситуации, представленные на рис. 10. Но в этих ситуациях — поток. Пусть процесс, описанный в п. 4°б), приводит к тому, что вершина не получает метки. Обозначим через множество непомеченных вершин. В силу того, что , множество определяет разрез сети. Каждая дуга соединяет помеченную вершину с непомеченной вершиной . Вершина может остаться непомеченной при условии, что . Аналогично, на каждой дуге (выходящей из ) выполняется равенство , поэтому справедливы соотношения: . В силу леммы это означает, что поток обладает наибольшей величиной. Проведенное рассуждение совместно с леммой составляют доказательство следующей теоремы. Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. . В качестве примера применения алгоритма Форда - Фалкерсона рассмотрим транспортную сеть и полный поток , для которого (рис. 11). Применяя правила 4° и 5° алгоритма, можно получить поток с величиной . 3. Задача о назначении на должность (комбинаторная прикладная задача). Пусть в некотором учреждении имеется 6 вакантных должностей и 6 работников . Граф , изображенный на рис. 12, иллюстрирует, какие должности может в силу своей квалификации занимать работник . Пусть выполнено условие: каждый работник может занимать хотя бы одну должность и на каждую должность претендует хотя бы один работник. Можно ли произвести назначение на должности так, чтобы все шесть должностей заняли работники соответствующей квалификации? Один из способов решения этой задачи состоит в рассмотрении вспомогательной транспортной сети . Для ее получения добавим к множеству вершин графа еще две вершины: вход и выход . Соединим с каждой вершиной дугой пропускной способности и каждую вершину с дугой пропускной способности . Припишем дугам исходного графа бесконечные пропускные способности. Получим транспортную сеть , изображенную на рис. 13. Ясно, что если на сети будет существовать поток такой, что , то есть поток, насыщающий выходные дуги (одновременно он будет насыщать и входные дуги ), то требуемое назначение будет возможно произвести. Нужно назначить работника на должность в том и только том случае, когда . §4. Цикломатическое число графа. Деревья. Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов мы и приступим. Все графы данного параграфа предполагаются полностью неориентированными и не содержащими кратных ребер. Условие отсутствия кратных ребер не является существенным и введено, главным образом, для упрощения рассуждений. Прежде чем рассматривать алгоритмические задачи, связанные с циклами, введем важную характеристику графа — цикломатическое число. Определение 1: Пусть граф имеет компонент связности. Цикломатическим числом графа называется число где — число вершин графа, — число его ребер. Одним из свойств цикломатического числа является его монотонность. Дадим строгую формулировку этого свойства. Теорема 1: Пусть граф является суграфом графа , тогда выполняется неравенство: Доказательство: Очевидно, достаточно рассмотреть случай, когда граф получен из графа удалением одного из ребер. В этом случае . Если выбрасываемое ребро является перешейком, то и, следовательно, . Если же выбрасываемое ребро не перешеек, то и тогда . Теорема доказана. Уже из доказательства этой теоремы выясняется смысл цикломатического числа. Видно, что при удалении ребра цикломатическое число уменьшается на единицу в том и только в том случае, когда удаляемое ребро не является перешейком. Но если ребро не есть перешеек, оно обязательно входит в какой-либо цикл. Действительно, из того, что удаление этого ребра не нарушает связность графа, следует, что его концы соединены некоторой цепью в графе с удаленным ребром . Добавляя к этой цепи ребро , получим цикл (например, на рис. 14а). Отмеченное ребро не есть перешеек. А на рис. 14 б) — перешеек. Таким образом, цикломатическое число связано в каком-то смысле с количеством циклов в графе. Следствие 1: Для любого графа выполнено неравенство . Доказательство: Пусть — некоторый граф. Очевидно (граф с теми же вершинами, что и , но без ребер) есть суграф графа . Используя теорему 1, имеем неравенство: . Но для графа справедливо соотношение , откуда следует формула: . Теорема 2: Следующие свойства графа эквивалентны: 1) граф связен и не имеет циклов; 2) граф связен и ; 3) граф связен и ; 4) и . Доказательство: Заметив, что для связного графа равенство влечет равенство ; — равенство , а из условий и (без предположения о связности) вытекает, что , так как и, следовательно, граф связен. Таким образом, свойства 2), 3) и 4) эквивалентны. Покажем, что из свойства 1) следует свойство 3). Если свойство 1) выполнено, то при удалении любого из ребер графа (без удаления вершин) количество компонент связности увеличивается на единицу. Первоначальное количество компонент связности равно единице. После удаления ребер число компонент связности станет равным . С другой стороны, после удаления ребер мы получим граф с тем же количеством вершин , что и у исходного, но без ребер. Число компонент связности такого графа есть , откуда . Докажем теперь, что из свойства 3) вытекает 1). Доказательство проведем от противного. Пусть содержит некоторый цикл. Удаляя ребро этого цикла (любое), мы не нарушаем связности графа. Для полученного графа ' выполнены следующие равенства: . Откуда: , что противоречит следствию из теоремы 1. Теорема доказана полностью. Определение 2: Граф называется деревом, если он обладает одним (и, следовательно, всеми остальными) из свойств 1) - 4). Иногда при определении дерева исключается случай . По определению 2 такой граф является деревом; в ряде случаев такое определение оказывается более удобным. Заметим, что если граф состоит из двух несвязных графов и , то справедливо соотношение: . Докажем теперь характеристическое свойство . Теорема 3: Равенство эквивалентно отсутствию циклов в графе . Доказательство: Пусть граф состоит из несвязных компонент . Тогда имеем равенство: ; кроме того, . Из этих соотношений следует равенство . Поскольку каждый из графов связен, можно применить теорему 2, из которой следует, что в этих графах нет циклов. На графе нет циклов, так как — несвязные компоненты этого графа. Что и требовалось доказать. По аналогии с понятием дерева граф без циклов (возможно, несвязный) иногда называется лесом. С помощью понятия дерева можно сформулировать необходимое и достаточное условие связности графа, соответствующее теореме. Рассмотрим условие связности графа. Приведем теорему, дающую необходимое и достаточное условие связности графа. Теорема 4: (о частичном дереве). Граф связен тогда и только тогда, когда он содержит некоторое дерево в качестве суграфа. Доказательство: Очевидно, что если граф содержит частичное дерево, то он связен. Докажем обратное. Пусть граф связен. Тогда, если , то есть дерево (см. определение 2). Если , то по теореме 3 в графе есть хотя бы один цикл. Удалив одно из ребер этого цикла, мы не нарушим связность графа и уменьшим его цикломатическое число на единицу. Через конечное число таких шагов получим связный суграф с , т. е. дерево. Теорема доказана. Замечание: Суграф графа , являющийся деревом, называют частичным, деревом графа . §5. Эйлерова характеристика. Плоские графы. Определение 1: Пусть задан набор отрезков гладких кривых на плоскости, причем выполнны следующие условия: 1) отрезки и не имеют общих точек, кроме, быть может, концевых (в частности , не самопересекается, хотя набор может быть замкнутым); 2) граф изоморфен , где граф определен равенством: . Здесь — это множество концевых точек отрезков на плоскости, . Тогда набор называется плоской реализацией графа . Разумеется, не каждый граф допускает плоскую реализацию. Например, графы, изображенный на рис. 15, как будет доказано ниже, не допускают плоской реализации. Отметим, что рис. 15а не является плоской реализацией графа, так как не выполнено требование 1) определения 1. Ребра этого графа самопересекаются. Избавиться от этой ситуации не получается даже с помощью перестраиваний графа. Не возможно построить граф, изоморфный данному, не имеющий самопересечений. Определение 2: Граф называется плоским, если он допускает плоскую реализацию. Дадим теперь определение наложения двух плоских реализации графов. Определение 3: Пусть — плоская реализация графа , а — плоская реализация графа . Пусть — части, на которые кривые набора делят отрезок ; определены аналогично. Набор удовлетворяет требованию 1) определения 1 и является плоской реализацией графа , построенного по этому набору. Граф называется наложением графов и (относительно их заданных плоских реализации). В этом параграфе считается, что каждый граф плоский и снабжен фиксированной плоской реализацией. Поэтому различие между графом и его плоской реализацией не проводится. Определение 4: Эйлеровой характеристикой связного плоского графа называется число , где — число вершин графа , — число его ребер, — число областей, на которые делит плоскость (включая и бесконечную область). Теорема 1 (теорема Эйлера): Для любого плоского связного графа справедливо равенство: . Доказательству этой теоремы предпошлем доказательство двух лемм. Лемма 1: Пусть связный плоский граф получен из связного плоского графа наложением на последний ребра с несовпадающими концами. Тогда справедливо соотношение: . Доказательство: Из условия, очевидно, что пересечение графа и ребра не пусто (иначе не мог бы быть связным). Пусть , — концы отрезка , а — точки пересечения и , рассмотрим несколько случаев. Случай 1. Ни одна из точек , , не совпадает ни с одной вершиной графа . Очевидно, что число вершин в графе равно . Если на граф наложить отрезок , то число ребер увеличится на два, а число областей не изменится (рис. 16, а). При последовательном наложении отрезков число ребер увеличивается на два, а число областей — на единицу (рис. 16, б). При добавлении же отрезка число ребер увеличивается на единицу, а число областей не изменяется (рис. 16, в). Это рассуждение показывает, что числа ребер и областей графа равны: . Складывая эти равенства, получаем утверждение леммы. Случай 2. Некоторые из точек являются вершинами графа . Пусть число таких точек . Тогда справедливо равенство: . Рассуждая аналогично случаю 1, заметим, что если конечная точка отрезка есть вершина графа , то увеличивается на единицу, если же конечная точка не совпадает с вершиной, то — на два. При этом для числа ребер графа получим выражение: , и, замечая, что меняется так же, как и в случае 1, — имеем соотношение: . В результате сложения получаем утверждение леммы. При разборе случаев 1 и 2 предполагалось, что точки и не принадлежат графу . Если, например, точка принадлежит графу , то доказательство можно свести к уже разобранному случаю следующим образом. Добавим к отрезку малый кусок так, чтобы он пересекался с только в точке (рис. 17). Нетрудно видеть, что эйлерова характеристика не изменилась, так как . При этом задача сводится к уже разобранной ситуации. Подобным образом поступим и с концом в том случае, если . Легкое видоизменение доказательства позволяет получить тот же результат и при . Детали доказательства предоставляются читателю. Лемма 2: Пусть связный граф получен наложением графа на граф , тогда: . Доказательство. Проведем доказательство методом индукции по числу ребер графа . Базисом индукции является лемма 1. Проведем индукционный шаг. Различаем два случая. Случай 1. В графе имеется, по крайней мере, два ребра, которые пересекаются с ребрами графа . В этом случае, удаляя ребро графа , не являющееся перешейком, получим граф с ребрами такой, что наложение графа на граф связно. Пользуясь индукционным предположением, получаем равенство . Добавляя выкинутое ребро по лемме 1, заключаем, что . Случай 2. Граф пересекается с графом по одному ребру . Если граф — не дерево, то в нем есть цикл. Удаляя ребро этого цикла, не совпадающее с и рассуждая аналогично случаю 1, получим равенство . Если же — дерево, то в нем имеется, по крайней мере, два тупика. Удаляя не совпадающий с тупик, получим, что эйлеровы характеристики графов и совпадают. Доказательство теоремы 1. Рассмотрим два плоских связных графа и (рис. 18). Пусть — дуга, одна вершина которой принадлежит , а другая . Пусть — наложение на . По лемме 2 справедливо равенство: , поскольку связен. Кроме того, наложение графа на граф также связно, а поэтому . Аналогично получим равенство и поэтому эйлеровы характеристики графов и совпадают. Из произвольности графов и получаем, что любые два плоских связных графа имеют одну и ту же эйлерову характеристику. Достаточно подсчитать эту характкристику для простейшего плоского связного графа. В качестве такого графа выберем граф . Для него ; отсюда . Теорема доказана. Замечания: 1. Эта теорема дает основание называть число 2 эйлеровой характеристикой плоскости. 2. Условие связности графа существенно для доказательства теоремы, так как уже для графа имеем равенство и . В качестве элементарного приложения теоремы Эйлера докажем, что графы, представленные на рис. 15, не допускают плоской реализации. Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации. Доказательство: Отметим, что в графе нет циклов длины 3, так как любое ребро ведет из группы вершин в группу . Любой цикл на графе имеет, поэтому, длину большую или равную четырем. Предположим теперь, что допускает плоскую реализацию, тогда для чисел получаем равенства , а из условия следует . Пусть — число ребер, ограничивающих грань с номером ; имеем и , то есть . Полученное противоречие доказывает первую часть теоремы. Допустим, что допускает плоскую реализацию. Тогда из теоремы 1 имеем равенства: . Пусть имеют тот же смысл, что и раньше. Очевидно, и поэтому выполнено неравенство: . Доказанная теорема допускает обращение. Это значит, что она представляет доказательство необходимости в следующем критерии, позволяющем решить вопрос о том, допускает ли граф плоскую реализацию. Теорема 3: (Понтрягин - Куратовский). Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал в качестве подграфов графы или из условия теоремы 2. Доказательство достаточности в этой теореме здесь не приводится. Отметим, что аналогичных критериев реализуемости графа уже для тора не найдено. Если произвольный граф не допускает плоской реализации, то он, возможно, допускает реализацию пространственную, т. е. может быть изображён без самопересечений ребер на пространственном объекте (шаре, торе и др.). §6. Теорема о пяти красках. В § 2 уже встречалась задача о раскраске графов. Напомним ее постановку. Пусть дана географическая карта страны, в которой имеется несколько областей. Требуется окрасить каждую область так, чтобы любые две области, граничащие между собой, были окрашены в различные цвета. При этом «граничащими» областями называются области, которые граничат по некоторой линии (а не в точке). Во введении было показано, что эта задача может быть сведена к задаче о раскраске плоского графа: имея некоторое число красок, раскрасить каждую вершину одной из этих красок таким образом, чтобы любые две смежные вершины имели различную окраску. Задача об определении минимального числа красок, нужных для правильной раскраски графа, которую мы здесь рассмотрим, является одной из первых задач теории графов. В этой главе слово «граф» будет обозначать полностью неориентированный граф без кратных ребер. Оценка хроматического числа плоского графа. 1. Теорема о пяти красках. Теорема утверждает, что любой граф, обладающий плоской реализацией, может быть правильно раскрашен пятью красками. Вспоминая задачу, сформулированную в начале этой главы, видим, что из этой теоремы следует возможность раскрашивания любой карты пятью цветами. Вопрос о том, достаточно ли для любой карты четырех красок, до сих пор не решен. Это так называемая проблема четырех цветов. Примеры плоских графов, не раскрашивающихся тремя цветами, строятся очень легко и будут приведены ниже. Теорема 1: Любой плоский граф 5-хроматичен. Прежде чем доказывать теорему 1, докажем лемму, которая имеет чисто технический характер и будет использоваться при доказательстве теоремы. Лемма 1: В любом простом связном плоском графе без тупиков и перешейков существует вершина степени меньшей или равной пяти. Доказательство: Предположим, что степень любой вершины графа больше пяти. Из этого предположения вытекает следующая оценка для числа ребер графа : . По условию теоремы граф является плоским. Как и раньше, будем отождествлять и его плоскую реализацию. Гранью графа , поэтому, называется любая связная часть плоскости, ограниченная ребрами, принадлежащими к плоской реализации . Количество ребер, ограничивающих каждую грань графа не меньше трех, так как граф не содержит кратных ребер. Отсюда имеем неравенство: . Подставим теперь оценки: в выражение для эйлеровой характеристики графа : . Это противоречит тому, что (по теореме 1 §5). Доказательство теоремы 1: Рассмотрим следующие операции над графом: 1) удаление тупика (вместе с вершиной); 2) склеивание двух ребер, инцидентных одной и той же паре вершин , ; 3) удаление перешейка. Очевидно, что если после проведения любой из указанных операций над графом его хроматическое число стало равным , то хроматическое число исходного графа есть . Кроме того, после применения некоторого количества операций 1) - 3) получается простой граф, состоящий из конечного числа связных компонент, в каждой из которых нет тупиков и перешейков. Если хроматические числа этих компонент есть , то хроматическое число графа есть . Из этих рассуждений видно, что достаточно доказать следующее утверждение: хроматическое число любого простого связного плоского графа без тупиков и перешейков меньше или равно пяти, т. е. такой граф всегда 5-хроматичен. Докажем это утверждение. Оно будет доказываться индукцией по числу ребер графа . При этом будет использована лемма 1. Базис индукции. При теорема верна, так как единственным связным графом без тупиков и перешейков с является треугольник. Треугольник 3-хроматичен, а, следовательно, и 5-хроматичен. Индукционный шаг. Пусть теорема верна для любого графа с количеством ребер . Рассмотрим (простой плоский без тупиков и перешейков) граф с . По лемме 1 в этом графе существует, по меньшей мере, одна вершина степени меньшей или равной пяти. Зафиксируем одну из таких вершин . Будем различать три случая. Случай 1. Пусть . Рассмотрим граф , полученный из графа удалением вершины и инцидентных ей ребер. Число ребер такого графа, очевидно, меньше . Применим индукционное предположение, согласно которому этот граф 5-хроматичен. Рассмотрим какую-либо правильную раскраску с помощью пяти красок. Возвращаясь к графу , видим, что раскраска графа задает раскраску графа , в которой не закрашена вершина . Но эта вершина соединена ребрами не более чем с четырьмя уже закрашенными вершинами. Имеется возможность закрасить ее так, чтобы не нарушить правильность раскраски. В предположениях этого случая индукционный шаг завершен. Случай 2. Пусть , и не все соседние ребра, выходящие из вершины , образуют треугольники (рис. 19). Склеим две вершины, смежные с вершиной , инцидентные двум соседним ребрам и не соединенные между собой ребром (на рисунке и ). Применяя преобразование 2), получим из получившегося графа простой граф, в котором число ребер меньше или равно . Рассмотрим существующую по предположению индукции правильную раскраску полученного графа. Она индуцирует некоторую раскраску графа, в которой вершины, ранее склеенные ( и ) имеют одинаковую окраску. Полученная раскраска будет правильной, так как эти вершины в графе непосредственно не связаны ребром, и в предположениях случая 2 индукционный шаг также завершен. Случай 3. Если и вершина есть центр пятиугольника (рис. 20а). В этом случае обязательно должны существовать две вершины, не соединенные непосредственно ребром, из числа пяти, окружающих (на рисунке это вершины и ), так как в противном случае эти пять вершин образовывали бы второй из графов, упомянутых в теореме 1 §5, и, следовательно, граф не был бы плоским. Удалим вершину с инцидентными ей ребрами (рис. 20б) и склеим и (рис. 20в). Число ребер полученного графа меньше . Рассмотрим его правильную раскраску с помощью пяти красок. Она индуцирует правильную (так как и не соединены ребром непосредственно) раскраску графа , в которой не раскрашена вершина . Заметив, что из пяти вершин, соединенных с вершиной непосредственно, две ( и ) раскрашены одинаково. Выводим отсюда, что эта раскраска может быть дополнена до правильной раскраски графа . В предположениях случая 3 индукционный шаг завершен. Приведем теперь пример плоского графа, для правильной раскраски которого недостаточно трех красок. Такой граф изображен на рис. 21. Доказательство того, что для его раскраски недостаточно трех красок, вполне тривиально и предоставляется читателю. 2. Необходимые и достаточные условия 1-й 2-хроматичности. Необходимые и достаточные условия даются следующей теоремой. Теорема 2: Граф 1-хроматичен тогда и только тогда, когда он не содержит ни одного ребра. Граф 2-хроматичен тогда и только тогда, когда он не содержит циклов нечетной длины. Доказательство: Первое утверждение теоремы вполне очевидно. Для доказательства второго, очевидно, можно ограничиться случаем связного графа . Рассмотрим связный граф и рассмотрим частичное дерево этого графа, полученное удалением из него ребер . Очевидно, что оно может быть раскрашено двумя красками. Если в начальном графе был некоторый цикл нечетной длины, то концы того из ребер , которое участвует в этом цикле, окажутся раскрашенными одинаково, ибо путь по дереву, соединяющий эти две вершины, состоит из четного количества ребер. Таким образом, если бы граф мог быть правильно раскрашен двумя красками, то эта раскраска была бы правильной и для частичного дерева; но тогда концы ребра были бы раскрашены одинаково, что невозможно. Обратно, если граф не содержит циклов нечетной длины, то для любой правильной раскраски частичного дерева концы любого из ребер закрашены по-разному, а, следовательно, индуцированная раскраска графа правильна. §7. Графы правильных многогранников. Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При этом, используя элементы теории графов, многогранники могут быть рассмотрены с точки зрения, отличной от традиционной. Изображение фигур при этом могут стать более простыми и наглядными. Правильные многогранники (платоновы тела) – это выпуклые многогранники, гранями которых являются правильные плоские фигуры. Всего существует пять правильных многогранников: тетраэдр, куб, октаэдр, икосаэдр, додекаэдр. Гранями тетраэдра, октаэдра и икосаэдра являются правильные треугольники, гранями куба – правильный четырёхугольник (квадрат). Гранями додекаэдра есть правильные пятиугольники. Других платоновых тел не существует. Вместо объёмных изображений правильных многогранников можно использовать их плоские изображения (графы). Графы правильных многогранников внешне напоминают сами многогранники. Их можно рассматривать, как проэкции объёмных тел на плоскость, проходящую через произвольную грань. Из рисунка видно, что графы всех правильных многогранников являются симметрическими, связными и плоскими. Они не содержат самопересечений рёбер, кроме пересечений в вершинах. Эйлерова характеристика каждого из этих графов равна 2. Графы правильных многогранников содержат циклы. Их количество можно подсчитать, используя формулу цикломатического числа: . Цикломатическое число – это количество независимых циклов на графе. Оно указывает на число рёбер, которые нужно удалить, чтобы граф стал нециклическим (деревом). Особый интерес представляют задачи, связанные с отысканием на графах циклов различных видов. Гамильтонов цикл – это цикл, проходящий через каждую вершину по одному разу. Эйлеров цикл – это цикл, проходящий через каждое ребро по одному разу (существует не для всякого графа). Теория конечных автоматов Введение. Теория конечных автоматов исследует тематические модели, приближенно отражающие физические или абстрактные явления, причем эти модели могут быть из области психологии, административного управления, связи, лингвистики, теории ЭВМ и т.д. С помощью конечных автоматов можно исследовать нервную систему животных или человека и проектировать ЭВМ. Универсальная ЭВМ состоит из 5 устройств: 1) устройство ввода; 2) устройство памяти; 3) арифметическое устройство; 4) устройство управления; 5) устройство вывода. Последовательность действий машины определяется программой, которая выполняется последовательно. Сама программа может предусматривать пропуск или повторение информации, хранящейся в памяти, т.е. от внутреннего состояния машины. ЭВМ бывают цифровые и аналоговые. Мы здесь рассматриваем цифровые. Все сигналы в такой машине двузначны, т. е. принимают значения из множества . Материальные носители и преобразования сигналов – конечны. Множество состояний любой машины также конечно. §1. Определение автомата Мили. Автомат Мура. Определение: Конечным автоматом называется набор из 5 объектов , где: - входной алфавит; ­ выходной алфавит; ­ множество внутренних состояний; ­ функция перехода (в следующее состояние); ­ функция выхода. Таким образом, конечный автомат описывается тремя множествами и двумя функциями. Обе функции зависят от текущего внутреннего состояния и от входного символа, считываемого в данный момент времени. Автомат действует следующим образом. Конечный автомат, находящийся во внутреннем состоянии , считывает входной символ . Функция принимает на паре значение - первый символ выхода. Функция принимает на паре значение , которое является следующим внутренним состоянием. Пусть входящие символы записаны на входной ленте: **********. Автомат считывает с нее символы один за другим. По прочтению каждого символа автомат печатает выходной символ на выходной ленте и переходит в новое внутреннее состояние. В определении подразумевается, что функции и в описании автомата М всюду определены, т.е. каждая пара из прямого произведения задает их значения. Такое описание автомата является полным, т.е. если задано начальное состояние автомата, то он способен считывать любую последовательность входных символов и выдавать однозначно определенную цепочку символов на выходе. Конечный автомат считается заданным, если заданы множества (конечные), а также даны функции или приведено их описание. Существует три способа задания конечных автоматов: таблица, диаграмма и матрица переходов. Пример 1. Конечный автомат задан следующим образом: ,  , . Значения функций заданы таблицей:  S0 0S1,  (S0, 0)0, S0 S0, (S0, 1)1, S1, 0S2, (S1, 0)1, (S1, 1)S1, (S1, 1)0, (S2, 0)S0, (S2, 0)1, (S2, 1)S2, (S2, 1)0. Пусть на входе дана двоичная последовательность 0101 и автомат находится в состоянии , тогда на выходе получаем последовательность: 0010. Этот автомат можно наглядно представить в виде диаграммы, которая, по сути, является ориентированным графом. Вершины этого графа помечены символами, обозначающими внутреннее состояние. Каждая дуга помечено парой символов (метка) , где - входной символ, вызывающий переход в следующее состояние, а - символ на выходе. Второй способ описания автомата – таблица состояний. Этот способ часто приводится в виде условия задачи. Это просто табличное представление функций и : Текущее состояние Таблица удобнее для вычислений, диаграмма - нагляднее. Например, по диаграмме легко обнаружить состояния, не достижимые из других состояний. Кроме того, автомат можно задать с помощью матрицы. Такая матрица всегда будет квадратной по форме, а размерность её зависит от количества внутренних состояний. Каждая позиция матрицы отвечает за определённый переход из одного состояния в другое. Если какой-то переход существует, то на определённом месте матрицы должна стоять соответствующая метка. Если же некоторый переход отсутствует, то на этом месте в матрице стоит ноль. Пример 2. По приведенному описанию построить конечный автомат. Задать его таблицей и диаграммой. Данный автомат проверяет четность числа считываемых единиц на входе из последовательности нулей и единиц, и выводит на печать символы чёт и нечёт в ответ на запрос, которому соответствует входной символ Q. Согласно условию, алфавит на входе: , алфавит на выходе состоит из символов: . Множество внутренних состояний: , где содержание этих состояний следующее: - считано четное число единиц; - считано нечетное число единиц. Анализируя работу автомата, можно составить таблицу: Текущее состояние   1 Q 1 Q S0 S0 S1 S0 1 чёт S1 S1 S0 S1 1 нечёт Считав символ Q, автомат печатает "чет", если число ранее считанных единиц было четно, и "нечет" - если нечетно. Например, входная последовательность символов имела вид: 0110Q1110Q. Она будет переработана в последовательность: 0110четн1110нечет. Диаграмма для данного автомата может быть составлена с помощью построенной таблицы: Любой конечный автомат Мили может быть преобразован в автомат, в котором выходной символ является функцией только состояния в настоящий момент. Для этого полагают - новый алфавит, , . Отсюда получаем выражение для : или . Такой автомат называется автоматом Мура. Так как автоматы Мили и Мура можно преобразовать друг в друга, то обычно достаточно рассматривать автомат Мили, тем более что число состояний у него меньше, чем у соответствующего автомата Мура. §2. Покрытие и эквивалентность. Морфизмы. Пусть - конечный автомат. Тогда по любой входной строке длины r и по любому начальному состоянию однозначно определяется строка длины r внутренних состояний , которая получается последовательным применением отображения . Точнее: . Аналогично строка на выходе определяется последовательным применением отображения . Поэтому рассмотрим автомат как устройство, перерабатывающее пары, состоящие из состояния и в строки и . С помощью функций и можно определить функции , , которые строятся по функциям и , заданным в описании автомата М. Пример. Автомат задан диаграммой: Пусть входная строка и начальное состояние , тогда , . Увеличение числа внутренних состояний автомата в реальном устройстве приводит к росту количества электронных схем, к уменьшению надежности, к усложнению отладки и т. д. Поэтому число необходимых состояний автомата, предназначенного для выполнения определенных действий, стремятся уменьшить, не ограничивая его возможностей. Этим объясняется важность следующей задачи. Предположим, что входной и выходной алфавиты фиксированы. Возникает следующий вопрос. Можно ли заменить автомат автоматом с меньшим числом внутренних состояний , но с той же функцией, переводящей входы в выходы? Определение 1: Говорят, что автомат покрывает автомат , если входной и выходной алфавиты у них общие и существует функция , такая что для любого положительного числа имеет место условие: . Определение 2: Автомат, который нельзя покрыть меньшим автоматом, называется минимальным. Будем писать: , если покрывает . Теорема 1: Отношение покрытий рефлексивно и транзитивно. Доказательство очевидно. Определение 3: Автоматы и называются эквивалентными, если автомат покрывает и автомат покрывает . В этом случае пишут: . Это означает, что кроме функции со свойством, указанным в предыдущем определении, существует еще функция со следующим свойством: при и . Следствие: Отношение эквивалентности автоматов рефлексивно, транзитивно и симметрично. Пусть и – автоматы с общими входными и выходными алфавитами. Определение 4: Морфизмом называется такое отображение , что и и . Если сюрьективно, то морфизм называется эпиморфизмом. Если - биекция, то морфизм называется изоморфизмом. Теорема 2: Пусть эпиморфизм автомата на . Тогда для любой входной строки и любого начального состояния входная строка автомата совпадает с входной строкой автомата , если начальное состояние равно . Доказательство: Доказательство можно провести индукцией по числу с индуктивным шагом: ; . Следствие: Любой эпиморфизм определяет покрытие автомата автоматом . Изоморфизм автоматов и с общим входным и выходным алфавитами есть биекция , такая, что для всякого начального состояния и всякой входной строки автоматы и выдают одну и ту же выходную строку, проходя через соответствующие промежуточные состояния. Пример. Автоматы, представленные следующими ориентированными графами, изоморфны. §3. Эквивалентные состояния автоматов. В этом параграфе мы решим следующую задачу: по данному описанию автомата построить новый автомат , который покрывает (возможно, эквивалентен ) и имеет наименьшее число состояний среди всех автоматов, покрывающих . Существует эффективный метод решения этой задачи, если функции всюду определены. Для этого сначала определяют эквивалентные состояния автомата, а затем склеивают все эквивалентные состояния в одно. Определение 1: Состояния и называются - эквивалентными, если для всякой входной строки длины имеем: . В этом случае будем писать: . Если , то будем говорить, что состояния и эквивалентны, и писать: . Заметим, что и – действительно отношение эквивалентности. Классы эквивалентности относительно , являются множествами всех пар состояний, перерабатывающих каждый входной символ в фиксированный выходной символ . Это означает, что . Обозначим через отношения эквивалентности (т.е. множество всех пар эквивалентных состояний). Обозначим через дополнение к , т.е. . Пусть, например, даны таблицы состояний автоматов и : Текущее состояние ν 0 1 ξ 0 1 S0 S1 S2 S2 S1 S0 S2 S0 S1 0 1 1 0 0 1 Текущее состояние  0 1  0 1 S0 S1 S0 S1 S0 S0 0 1 1 0 G (E1) = {(S0, S2), (S2, S0), (S0, S0), (S1, S1), (S2, S2)}, G (E1) = {(S0, S1), (S1, S0), (S1, S2), (S2, S1)}. Задача минимизации количества состояний в полностью описанном автомате сводится к определению попарно эквивалентных состояний и последующему их склеиванию. Оказывается, что эффективнее всего начать с выявления неэквивалентных состояний. Чтобы показать это, определим новые функции и . Определение 2: Положим: . Это означает, что есть последнее состояние автомата, начавшего работу в состоянии , прочитавшего входную строку длины . Положим далее: . Это означает, что есть последний символ выходной строки автомата, начавшего работать в состоянии и считавшего ту же входную строку . Теорема 1: Если , то либо , либо для подходящей строки имеем . Доказательство: Утверждение означает, что для подходящей строки . При необходимости мы можем укоротить входную строку так, чтобы входные строки, отвечающие и , отличались только последними символами. Пусть это уже сделано. Если после этого , то . Если же , то . Но при условии . Таким образом, последние выходные символы автомата, считавшего , различны, если он исходил из начальных состояний и соответственно. Чтобы выходы отличались, то есть должно быть выполнено условие: . Иначе последний входной символ даст один и тот же символ на выходе. Теорема 2: Если , но для всех , то для подходящего элемента . Эту теорему можно переформулировать так: если , то для подходящего элемента имеем: . Эта теорема утверждает, что состояния и , эквивалентные относительно всех входных последовательностей длины , могут стать неэквивалентными относительно последовательностей длины только в том случае, когда имеется символ , переводящий и соответственно в состояния , не эквивалентные относительно подходящей входной последовательности длины . Это означает, что на шаге достаточно исследовать состояния в и установить, найдется ли пара , переходящая в пару со свойством . В этом случае . Если мы уже определили , то состоит из и таких упорядоченных пар , что для некоторого имеем: . В общем случае нужно исследовать каждый раз только . Таким способом мы сумеем рекуррентно определить и, наконец, - дополнение к в булевой алгебре подмножеств . Доказательство: Доказательство теоремы проводится непосредственно. Если пара лежит в , то она лежит в . Значит нужно рассмотреть лишь такие пары , что для некоторой строки имеем , а для всех строк имеем . Но в точности те пары, которые переводятся в , -м входным символом и стало быть, в , некоторым символом . Лемма: Если , то для всех . Действительно, дальнейшие шаги не добавят новых пар состояний, т.к. согласно теореме 2, дополнение состоит из тех пар, которые переводятся подходящим символом в дополнение . Пример: Пусть задана таблица состояний некоторого автомата. Текущее состояние След. состояние 0 1 Выход 0 1 S1 S1 S2 1 0 S2 S1 S3 1 0 S3 S5 S1 1 0 S4 S4 S2 1 0 S5 S4 S3 1 1 Для этого автомата . Иными словами: . Первое разбиение на классы эквивалентности: , . Вход 0 переводит в состояние , в : , . Поэтому вход 01 дает Следующие результаты: и . Отсюда и . Аналогично: и , так что имеет место условие: . Далее, входной символ 1 переводит состояние в , а переводит в состояние . Другими словами: и . Поэтому , т.к. и . Аналогично: , откуда следует: . Таким образом, разбивает на классы эквивалентности: , , , . Дальнейший перебор показывает, что . Таким образом, и , а остальные пары состояний неэквивалентны. §4. Процедура минимизации конечных автоматов. Актуальность проблемы минимизации конечных автоматов уже была приведена выше. В реальном устройстве (калькулятор, компьютер) увеличение числа внутренних состояний ведёт к увеличению числа микросхем, что в свою очередь может привести к росту стоимости, к более частым поломкам. Значит, уменьшение числа внутренних состояний автомата без ограничения его возможностей ведёт к экономии и надёжности в работе. Процедура минимизации основана на рассмотрении отношений эквивалентности между упорядоченными парами. Рассмотрим автомат, заданный таблицей внутренних состояний: Следующее сост. Выход Процедуру минимизации начнем с нахождения множества пар эквивалентных состояний и . Введем в рассмотрение разбиение , которое разобьет все состояния в таблице на два класса эквивалентности: , . В записи классов эквивалентности для краткости мы пишем 1 вместо S1 и т.д. При составлении этого предварительного разбиения мы ориентируемся на выходную последовательность. Это разбиение определяет график соответствующего отношения эквивалентности. Т.к. отношение рефлексивно и симметрично, то его график легко восстанавливается по множеству тех пар , для которых при всех значений входного символа . Обозначим через подмножество, состоящее из пар , удовлетворяющих условию: , для которых . В общем случае через будем обозначать множество упорядоченных пар со свойством . Для нашего разбиения имеем: , Т.к. и - это классы эквивалентности относительно , то имеем следующие соотношения: , , , и т.д. Множество состоит из элементов множества и еще пар , и . Например, входной символ переводит пару в пару , а эта последняя пара принадлежит . Добавление этих пар к определяет новое разбиение на классы эквивалентности: : , , . Определим теперь множество . Оно состоит из элементов множества и еще пар и . Например, входной символ переводит пару в пару , а эта последняя пара принадлежит множеству . При разбиении имеем следующие классы эквивалентности: , , , . Множество состоит из элементов множества и из пар , , , , , . Поэтому разбиение состоит из следующих классов эквивалентности: , , , , . Дальнейший перебор показывает, что и . Конструкция покрывающего автомата теперь несложна. Каждый класс эквивалентности последнего разбиения становится состоянием нового автомата. Можно ввести новые обозначения. Например, обозначим через , - через и т.д. В итоге получается автомат с пятью состояниями, покрывающий наш первоначальный автомат с девятью состояниями. Поскольку выходы для каждого начального состояния в фиксированном классе эквивалентности не зависят от этого состояния при односимвольных входах, то таблица состояний нового автомата, в частности ее выходы, прямо считываются с таблицы состояний первоначального автомата. Чтобы построить функцию перехода в следующее состояние, выберем то состояние в каждом классе , в котором некоторый элемент входной последовательности переводит состояние в некоторое состояние из класса . Положим . Заметим, что это предписание однозначно определено: все состояния переходят в состояние после считывания символа из входной последовательности . На следующем примере показан результат этой процедуры, примененной к автомату, рассмотренному раньше. Следующее сост. Выход Этот автомат уже является минимальным. Это значит, что он не содержит эквивалентных состояний. Замечание: На практике не обязательно перечислять все пары из множеств и . На каждом шаге процедуры достаточно смотреть, переводит ли некоторый входной символ пару из класса в разные классы эквивалентности и . Если да, то на следующем шаге состояния и следует развести по разным классам. Пример. Рассмотрим конечный автомат с пятью состояниями, заданный таблицей. Следующее сост. Выход Имеем , , , . Это приводит к разбиению : , . Тогда функция перехода при считывании единицы имеет вид , кроме того . Однако , поэтому (т.к. и ). Следующее разбиение состоит из классов эквивалентности: , , . Дальнейшего измельчения не происходит, т. к. функция переводит каждый элемент класса эквивалентности в тот же класс. Итак, состояния и можно склеить в одно состояние , а состояния и - в состояние . Состояние обозначаемтеперь . Новый минимальный автомат, покрывающий предыдущий, можно изобразить в виде: Следующее сост. Выход §5. Машина Тьюринга. Понятие конечного автомата возникло из близкого понятия, введенного в 1936 г. логиком Тьюрингом. Тьюринг рассмотрел гипотетическую машину, имеющую конечное множество внутренних состояний и одну бесконечную ленту, разделенную на ячейки, которые машина может передвигать вправо или влево на одну ячейку за такт. В каждой ячейке машина может записывать символ из конечного алфавита . Первоначально лента должна быть пустой, кроме конечного числа ячеек, заполненных заранее. (Эти заранее заполненные ячейки можно представлять программой запуска машины). Особенности машины Тьюринга, отличающие ее от конечного автомата, состоят в следующем: 1) лента машины Тьюринга бесконечна; 2) машина Тьюринга может двигаться вдоль ленты в любом направлении. Таким образом, машина Тьюринга имеет потенциально бесконечную память, которой она пользуется в ходе вычислений. Кроме того, каждую ячейку машина может просматривать многократно. Формальное определение машины Тьюринга следующее. Определение 1: Машина Тьюринга – это пять объектов , из которых: 1) - есть конечный алфавит символов, которые могут быть записаны в ячейках и являются одновременно входными и выходными: ; 2) - есть конечное множество внутренних состояний, ; 3) -функция перехода в новое состояние, она действует из в ; 4) - функция выхода, ; 5) - функция, регулирующая движение ленты, она действует из во множество . Машина Тьюринга работает по определенным тактам следующим образом. Она начинает работать, находясь в начальном состоянии . После считывания первого символа последовательности из ячейки машина переходит в новое внутреннее состояние, определяемое функцией . Затем записывает в ячейке новый символ, являющийся значением функции , перемещает ленту вправо (П) или влево (Л), или остается на месте и прекращает работу (останов.) в зависимости от значения функции . Таким образом, работа машины состоит в повторении следующего цикла: считывания символа из ячейки, переход в новое внутреннее состояние, впечатывание нового символа в эту ячейку, выбор которого определяет функция (может оказаться, что это тот же самый символ), сдвиг ленты вправо или влево, либо остановка. Лента бесконечна в обоих направлениях, однако вначале (и, значит, после любого такта) заполнено лишь конечное число ячеек. Алфавит машины Тьюринга обычно состоит из символов . Символ # служит для обозначения пустых ячеек, символы необходимы для записи чисел. Для того чтобы записать на ленте ненулевое число, нужно в ячейки вписать столько единиц, какова величина числа. Ноль служит для записи одноименного числа, а также выступает в качестве разделителя между числами. Но некоторых задачах алфавит может быть произвольным. Пример. Машина Тьюринга дана следующим описанием. Она считывает входную последовательность, состоящую из нулей и единиц, печатает символ Ч, если число считанных единиц четное и Н, если нечетное. Строке из нулей и единиц предшествует и последуют пустые ячейки, обозначаемые символом #. Символы Ч и Н печатаются в первой пустой ячейки вслед за входной строкой. Решение: Таким образом, алфавит имеет вид: . Множество внутренних состояний: , где - начальное состояние, - число считанных единиц четно, - число прочитанных единиц нечетно. Так задаются множества. Функции можно задать следующим образом: Остановка машины происходит после того, как будут выданы нужные результаты. Функции удобно рассматривать, пользуясь обозначениями Тьюринга. В этом случае машина Тьюринга описывается множеством строк следующего вида: . В каждой такой строке каждый символ определяет один из пяти тактов работы машины: - текущее состояние машины; - считываемый из ячейки символ; - следующее состояние машины, ; - символ, печатаемый в ячейке, ; - одна из команд: . Набор строк подобного вида называют программой работы машины Тьюринга. В этих обозначениях описанная выше машина задается так: , , , , , , , , Программы работы машины Тьюринга содержат все известные алгоритмические моменты (циклы, ветвления). Следующий несложный результат показывает, что машины Тьюринга умеют делать все, что умеют конечные автоматы. Теорема: Пусть - конечный автомат. Пусть и определены основные функции для всех : , , Тогда машина Тьюринга ставит в соответствие входным строкам те же выходные строки, что и автомат . Доказательство: Любую входную строку автомата можно записать на ленте машины так, чтобы входной символ был записан в -й ячейке. Описанная выше машина Тьюринга напечатает на выходе символ в -й ячейке, перейдет в состояние и передвинется в -ю ячейку. Добравшись до -й ячейки, она остановится. Замечание: Если входной алфавит конечного автомата содержит пробел, он должен обозначатся специальным символом в алфавите , чтобы избежать неоднозначности. Значения функций , мы не определили, ибо для нас они безразличны. Мы получили не полностью описанные автоматы с безразличными состояниями. Машины Тьюринга обладают большими возможностями, чем конечные автоматы. Можно, например, описать машины Тьюринга, вычисляющие разные функции от чисел, подаваемых на вход. Стандартным представлением неотрицательного числа в машине Тьюринга является последовательность из единиц, стоящих подряд. Два таких числа отделяются нулем. Например, строка ##111011## представляет упорядоченную пару чисел (3,2). Строка ##110111101## представляет собой последовательность чисел (2, 4, 1). Пример: Следующая машина Тьюринга складывает два неотрицательных целых числа, поданных на вход: , , , , , , , Машина превращает две последовательности единиц, разделенные нулем, в последовательность единиц, представляющую число, равное сумме чисел на входе. Можно описать машину Тьюринга, способную сложить три целых числа, четыре целых числа или любое число, даже неограниченное наперед целых чисел. §6. Не полностью описанные автоматы. До сих пор мы рассматривали полностью описанные автоматы. Практически функции и обычно бывают лишь частично определены. Системы обычно проектируются по частям и некоторые входные строки либо вообще не встречаются, либо встречаются в ситуациях, в которых выход нас не интересует. Поэтому некоторые позиции в таблицах состояний (или ребра в диаграммах состояний) отсутствуют. Такие позиции называются безразличными, в таблицах их обозначают прочерком. Сначала казалось, что следует как-нибудь заполнить безразличные позиции в таблице и затем минимизировать получившийся полностью описанный автомат. Предполагалось, что выбор наименьшего из получившихся минимальных автоматов добавит искомый автомат. Однако для многих не полностью описанных автоматов процедура такого вида не приводит к минимизации. Пусть задан не полностью описанный автомат. Выходы 0 1 0 1 S0 S1 S2 0 1 S1 - S1 1 0 S2 S0 S1 - 1 Если для этого автомата считать, что выход в состоянии считавшего 0, был иногда 0, а иногда 1, то автомат можно свести к двум состояниям. Если же настаивать, чтобы выход был всегда одним и тем же, то редукция невозможна. Алгоритмы и рекурсивные функции. Введение. Уже в математике древнего мира появились вычислительные процессы чисто механического характера, с помощью которых, действуя по инструкциям, можно было из заданных величин получать искомые. Такие правила, инструкции в математике стали называть алгоритмами. Примерами алгоритмов являются, например, правила сложения, вычитания, умножения и деления многозначных натуральных чисел, записанных в десятичной системе исчисления, алгоритм Евклида для нахождения наибольшего общего делителя натуральных чисел, решение системы линейных уравнений методом последовательного исключения неизвестных, отыскание целых корней многочленов с целыми коэффициентами и т.д. В наше время отмечают следующие характерные черты алгоритмов: 1) Дискретность алгоритма, т.е. вычисления согласно алгоритму производят по шагам, с четким предписанием: 1)…, 2)…, и т.д. (по программе). 2) Детерминированность алгоритма, т.е. величины, получаемые в процессе вычисления на любом последующем шаге, однозначно определяются величинами, полученными на предшествующем шаге. 3) Элементарность шагов алгоритма, т.е. правила, инструкции, по которым выполняется каждый шаг, должны быть четкими, понятными, не допускающие неопределенности. 4) Направленность алгоритма, т.е. должно быть указано, что считается результатом алгоритма и в том случае, если указанный вычислительный процесс не дает результата. 5) Массовость алгоритма, т.е. возможность применения для решения бесконечного числа однотипных задач. Отмеченные характерные черты алгоритма, конечно, не дают математически строгого определения алгоритма, т.к. точный смысл ряда терминов, встречающихся в них, не установлен. И хотя понятие алгоритма в математике возникло очень давно, и у математиков не возникало споров относительно того, является ли какая-то описанная вычислительная процедура алгоритмом или нет, точного определения алгоритма не существовало до середины тридцатых годов ХХ века. Дело в том, что для построения конкретного алгоритма, точное определение алгоритма не обязательно, но для доказательства того, что для решения какой-то задачи не существует алгоритма, необходимо строгое определение его. Рассматривая конкретные алгоритмы, можно сделать вывод, что мы находим способы вычисления некоторой целочисленной функции. На этом пути, продолжая работы Д. Гильберта, К. Геделя, Черч и Клини дали строгое определение рекурсивной и частично рекурсивной функции, которые являются формализацией интуитивного понятия алгоритма. С помощью этих понятий Черч доказал алгоритмическую неразрешимость проблемы тождественной истинности для формул исчисления предикатов первой степени. С другой стороны, вычисления согласно предписанию алгоритма можно рассматривать как механическую работу, которую можно поручить «машине». Работая в этом направлении, Пост и Тьюринг, независимо друг от друга, дали строгое определение «машины», способной выполнять конечное число простых операций. Работы Поста и Тьюринга появились одновременно с работами Черча и Клини. Оказалось, что класс функций, вычислимых на машинах Тьюринга, совпадает с классом частично-рекурсивных функций. §1. Основные понятия и определения. Алфавит, слова. Введем понятие ленты, разделенной на равные участки, называемые ячейками или клетками. Будем считать ленту конечной в любой данный момент, но неограниченно надстраиваемой в обе стороны, так, что у каждой ячейки есть соседние справа и слева. Одно из возможных состояний ячеек будем называть исходным. Ячейки, находящиеся в этом состоянии, будем называть пустыми. Произвольное конечное множество букв назовем алфавитом. Конечная последовательность ячеек, занятых некоторыми буквами назовем словом. Длиной слова называется число занятых ячеек. Пусть А, В – слова, записанные в алфавите, не содержащем самих символов А и В. Тогда АВ – слово, получающееся, если сначала выписать слово А, а затем приписать справа слово В. Слово АВ называется композицией (или произведением) слов А и В. Удобно ввести еще пустое слово, композиция которого с любым словом считается по определению равной этому последнему слову. Пустое слово не следует путать с пустой ячейкой. Слово А называется подсловом слова В, если В можно представить в виде , где С и D – некоторые (возможно пустые) слова. Слово А может входить несколько раз в слово В, при этом говорят о первом, втором и т.д. вхождении слова А в слово В. Функции. Термы. Если некоторым элементам множества Х поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из множества X во множество Y. Множество тех элементов из Х, у которых есть соответствующие образы во множестве Y, называется областью определения функции, а те элементы из Y, которые соответствуют некоторым элементам из Х, называются множеством значений функции. Если область определения функции совпадает с множеством Х, то функцию называют всюду определенной. Две функции f и g из Х в Y называются равными, если они имеют одну и ту же область определения и значения их совпадают в каждой точке области определения. Частичные функции из множества во множество Y называют частичными функциями от n переменных или n-местными функциями (частичными) из Х в Y. Частичная функция из прямого произведения в Х, называется n-местной частичной операцией на Х. Для записи различных выражений пользуются особым формальным языком. Алфавит этого языка состоит из символов трех групп. Символы первой группы называются предметными символами. В качестве таких символов обычно употребляют буквы a, b, x, y, … или те же буквы с индексами. Символы второй группы называются функциональными, будем их обозначать , и т.д. Буква – n – местный функциональный символ. Верхний индекс опускают, если известно, от какого числа переменных этот функциональный символ зависит. Символы третьей группы – это левая и правая скобка и запятая. Слова особого вида, записанные в этом алфавите, называются термами. Термы длины 1 – это однобуквенные слова, составленные из букв, являющихся предметными переменными. Далее пользуемся индукцией. Пусть для некоторого термы длины, меньшей S, определены. Тогда слово длины S называется термом, если оно имеет вид , где - термы меньшей длины, а f – это n – местный функциональный символ. Например, если а, х – предметные символы, а f, g – одноместный и двуместный функциональные символы, то слова x, f(a), g(x, a), g(f(x), g(a, x)) являются термами длины 1, 4, 6, 14 соответственно. По определению, задать значение предметного символа – это значит указать некоторое непустое множество, называемое основным множеством и сопоставить с рассматриваемым символом некоторый элемент этого множества, который называется значением данного символа. Задать значение n-местного функционального символа – это значит сопоставить с ним какую-нибудь частичную n–местную операцию, определенную на основном множестве. Теперь по индукции можно определить значение терма. Если в качестве значений функциональных символов взяты частичные операции, определенные не всюду на основном множестве, то и значение терма может оказаться неопределенным. При записи термов пользуются сокращениями. Если, например, x, y – предметные символы, f – символ двуместной операции, то терм f(x, y) обычно пишут в виде xfy. В частности, если двуместные операции обозначаются символами +, , -, то термы ,сокращенно обозначают . Дальше всюду под числами понимаем 0 и натуральные числа 0, 1, 2, 3, … Множество этих чисел будем обозначать N. Частичные функции, определённые на прямом произведении , направленные в N будем называть k-местными числовыми частичными функциями. Для краткости будем называть их просто функциями. Символы +, *, - будем считать двуместными функциональными символами, фиксированными значениями которых являются обычные арифметические операции. Во множестве натуральных чисел первые две операции всюду определены, а операция вычитания – частичная. Далее нам будут необходимы следующие числовые функции , имеющие по определению следующие значения: , , . Эти функции будем называть простейшими. Верхние индексы говорят, от какого числа переменных эти функции зависят. Поэтому вместо символов , будем писать S, O. Результатом функции S есть первоначальное число, увеличенное на единицу. Функция О обнуляет исходную числовую последовательность. А последняя функция J выбирает из предъявленной числовой последовательности число, стоящее на определённом месте. Эти функции можно комбинировать, получая более сложные функции. Кодирование. Теория алгоритмов имеет дело со словами в конечном алфавите. Однако многие объекты нельзя рассматривать как слова в некотором алфавите. К таким объектам, например, можно отнести рациональные числа, алгебраические числа и т.д. Тем не менее, некоторые из таких объектов могут быть закодированы в подходящем конечном алфавите. Например, взяв алфавит из двух символов 0, 1, можно закодировать любое натуральное число, взяв его двоичную запись. При двоичном кодировании не всякое слово в алфавите 0, 1 служит кодом натурального числа (например, 001). §2. Примитивно рекурсивные функции. Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле, мы получим функции, также вычислимые в интуитивном смысле. Частичные функции, которые можно получить при помощи этих операторов из простейших функций , , , называются частично рекурсивными. Основная гипотеза Черча состоит в том, что класс частично рекурсивных функций совпадает с классом функций, допускающих машинное или алгоритмическое вычисление. Суперпозиция частичных функций. Пусть заданы n частичных функций от одного и того же числа m переменных, определенных на множестве Х со значениями во множестве Y, и пусть на множестве Y определена частичная функция f от n переменных со значениями во множестве Z. Введем частичную функцию g от m переменных на множестве X со значениями во множестве Z, полагая по определению, что выполняется равенство: для произвольных переменных . Говорят, что функция g получается операцией суперпозиции или подстановки из функций . Оператор подстановки будем далее обозначать символом . В качестве множеств X, Y, Z далее всюду будет браться множество натуральных чисел N. Например, значение терма не определено, а значение терма , где - символы простейших функций, определенных в предыдущем параграфе. Оператор примитивной рекурсии. Пусть заданы числовые частичные функции: n-местная g и (n+2)–местная функция h. Тогда (n+1)–местная частичная функция f получается из функций g и h примитивной рекурсией, если для всех натуральных значений имеем следующие соотношения: , . (Напомним, что N = 0, 1, 2, 3, …, поэтому это определение верно и для случая, когда ). Например, одноместная частичная функция f получена примитивной рекурсией из постоянной одноместной функции, равной числу а и двуместной частичной функции h, если , . Теорема 1: Для любых частичных n–местной функции g и (n+2)–местной функции h (n=0,1,2,…) существует одна и только одна частичная (n+1)–местная функция f, получаемая из g и h примитивной рекурсией. Доказательство: Действительно, если функция f существует, то по определению последовательно находим: , , …………………………………… , и поэтому f определена однозначно. Из этих соотношений видно, что если для некоторых значение неопределенное, то и для всех значения будут также неопределенные. Если функции g и h заданы, то приведенные равенства можно принять за определение функции f. Теорема доказана. Из доказательства предыдущей теоремы видно, что если мы каким-то образом «умеем» находить значения функций g и h, то значения функции f можно вычислить при помощи процедуры механического характера. Для нахождения значения достаточно последовательно найти числа: , , , …………………, . Полученное на (m+1)-м «шаге» число и будет искомым значением функции f в точке . Изложенный процесс вычисления будет продолжаться неограниченно только в том случае, когда неограниченным окажется процесс вычисления одного из выражений , ,…, , т.е. когда хотя бы одно из этих выражений будет иметь неопределенное значение. В этом случае и значение будет неопределенным. Определение: Пусть задана система G каких-то частичных функций. Частичная функция f называется примитивно рекурсивной относительно G, если f можно получить из функций системы G и простейших функций конечным числом операций подстановки и примитивной рекурсии. Функция f называется просто примитивно рекурсивной, если ее можно получить конечным числом операций подстановки и примитивной рекурсии, исходя лишь из простейших функций . Операции подстановки и примитивной рекурсии, применяемые к всюду определенным функциям, дают в результате снова всюду определенные функции. Поэтому, в частности, все примитивно рекурсивные функции всюду определены. Из определения также следует, что примитивно рекурсивные функции будут примитивно рекурсивны относительно любой системы функций. Наконец, из определения также следует, что операции подстановки и примитивной рекурсии, примененные к частичным функциям, примитивно рекурсивным относительно какой-нибудь системы функций G, дают в результате снова функции, примитивно рекурсивные относительно G. Согласно определению одноместные функции и многоместные функции примитивно рекурсивны. Для n-местной функции имеем представление и поэтому - примитивно рекурсивна. Произвольная n-местная постоянная функции допускает представление в виде терма , записанного при помощи символов примитивно рекурсивных функций и предметных переменных. Двуместная функция удовлетворяет соотношениям: , . Следовательно, функция возникает из примитивно рекурсивных функций , операцией примитивной рекурсии и поэтому функция примитивно рекурсивна. Двуместная функция xy удовлетворяет примитивной рекурсии: , с начальными примитивно рекурсивными функциями , поэтому функция xy примитивно рекурсивна. Рассмотрим функцию , причем будем считать, что . Соотношения , представляют собой рекурсивную схему с начальными примитивно рекурсивными функциями . Поэтому функция также примитивно рекурсивна. В математическом анализе иногда встречается функция (сигнум или знак числа х), равная (+1) для положительных вещественных чисел х, (-1) - для отрицательных х, и 0 для чисел . Мы рассмотрим эту функцию для натуральных значений х. По определению: Введем противоположную функцию: Эта функция совпадает с разностью . Функции и удовлетворяют примитивным рекурсивным схемам: Поэтому они примитивно рекурсивны. В области натуральных чисел разность естественно считать частичной двуместной функцией от переменных , определённой лишь для , т. к. отрицательные числа не входят в рассматриваемую область. Но примитивно рекурсивные функции всюду определённые. Поэтому вместо обычной разности вводят усеченную разность, определяемую следующим образом: В отличие от обычной разности усеченная разность в области натуральных чисел всюду определена. Функция удовлетворяет примитивно рекурсивной схеме: с примитивно рекурсивными начальными функциями и . Поэтому функция примитивно рекурсивна. С другой стороны, из определения усечённой разности следует, что для любых имеем: . Это означает, что двуместная функция получается примитивной рекурсией из функций и . Обе последние функции примитивно рекурсивны. Поэтому и функция примитивно рекурсивна. Наконец из примитивной рекурсивности функций и вытекает примитивная рекурсивность функции . Можно доказать примитивную рекурсивность ряда арифметических и других числовых функций. §3. Частично рекурсивные функции. Оператор минимизации. Рассмотрим некоторую n - местную частичную функцию . Допустим, что существует какой - либо «механизм» для вычисления значений функции , причём значение функции тогда и только тогда неопределённое, когда этот механизм работает бесконечно, не выдавая определённого результата. Фиксируем какие-нибудь значения для первых аргументов функции и рассмотрим уравнение . (1) Чтобы найти натуральное решение этого уравнения, будем вычислять при помощи нашего «механизма» последовательно значения для значений . Наименьшее значение , для которого получится равенство: , обозначим следующим образом: . (2) Описанный процесс нахождения значений выражения (2) будет продолжаться бесконечно в следующих случаях: а) значение не определено; б) значения для определены, но отличны от , а значение не определено. в) значения определены для всех и отличны от . Во всех этих случаях значение выражения (2) считается неопределённым. В остальных случаях описанный процесс обрывается и дает наименьшее решение уравнения (1). Это решение является значением выражения (2). Например, мы уже ввели операцию усечённой разности: Поэтому, по определению символа , для всех имеем . Аналогично , . Значение выражения – неопределенное, т.к. уже значение терма - неопределенное, хотя уравнение имеет решение . Этот пример показывает, что для частичных функций выражение (2) строго говоря, не есть наименьшее решение уравнения (1). Если функция всюду определённая и уравнение (1) имеет решение, то (2) есть наименьшее решение для (1). Значение выражения (2) при заданной функции зависит от выбора значений параметров и потому оно является частичной функцией от аргументов x1. Эту функцию обозначим: , где символ операции, переводящей функцию в . Если функция – одноместная, то функцию обозначают и называют обратной функцией. Таким образом, . Для многоместных функций запись не употребляется. Оператор называют оператором минимизации. Например, из записи следует, что . Определение: Частичная функция называется частично рекурсивной относительно системы частных функций , если может быть получена из функций системы и простейших функций конечным числом операций подстановки, примитивной рекурсии и минимизации. Частичная функция называется частично рекурсивной, если она может быть получена из простейших функций конечным числом операций подстановки, примитивной рекурсии и минимизации. Таким образом, частичная рекурсия называется частично рекурсивной, если она является значением операторного терма, записанного с помощью операторных символов и символов простейших функций. Из определения вытекают следующие свойства частично рекурсивных функций: 1)Каждая частичная функция, примитивно рекурсивная относительно системы функций , являются и частично рекурсивной относительно . В частности, все примитивно рекурсивные функции частично рекурсивны. 2)Класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определённые, а среди частично рекурсивных функций встречаются и функции, не всюду определенные, например и даже нигде не определенная функция . 3)Операции подстановки, примитивной рекурсии и минимизации, произведенные над функциями, частично рекурсивными относительно системы , дают в результате функции, снова частично рекурсивные относительно . Чтобы получить представление о связи между примитивно рекурсивными и частично рекурсивными функциями, введем следующие понятия. Характеристической функцией какого-нибудь множества натуральных чисел называется одноместная функция, равная в точках множества и равная в точках, не принадлежащих . Частичной характеристической функцией множества называется функция, равная в точках множества и не определённая в точках, не принадлежащих . Например, характеристическая функция пустого множества есть функция, равная для всех натуральных чисел, а частичная характеристическая функция пустого множества есть нигде не определенная функция. Вообще, характеристическая и частичная характеристическая функции совпадают лишь для множества всех натуральных чисел. Множество натуральных чисел называется примитивно рекурсивным, если его характеристическая функция примитивно рекурсивна. Множество называется частично рекурсивным, если его частичная характеристическая функция частично рекурсивна. Аналогично определяются понятия примитивно рекурсивного и частично рекурсивного множества относительно системы функций . Теорема 1: Каждое (относительно) примитивно рекурсивное множество является (относительно) частично рекурсивным. Доказательство: Действительно, пусть - характеристическая функция какого-нибудь множества натуральных чисел . Тогда функция , определяемая равенством , будет частичной характеристической функцией множества , так как операция вычитания частично рекурсивна, то и функция также частично рекурсивна. Теорема 2: Пусть - произвольная примитивно рекурсивная функция и - любое примитивно рекурсивное множество натуральных чисел. Тогда частичная функция , определённая схемой: , является частично рекурсивной. Доказательство: В самом деле, по теореме 1, частичная характеристическая функция множества частично рекурсивна. Но по определению функции для всех значений имеет место равенство и, значит, функция - частично рекурсивна. Доказанная теорема позволяет строить многочисленные примеры частично рекурсивных функций. Понятие частично рекурсивной функции - одно из главных понятий теории алгоритмов. С одной стороны, каждая частично рекурсивная функция вычислима путем определённой процедуры механического характера, которая отвечает нашему интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных алгоритмов до сих пор фактически ни строились, во всех случаях неизменно оказывалось, что числовые функции, вычислимые посредством алгоритмов этих классов, были частично рекурсивными. Поэтому общепринятой является следующая естественно научная гипотеза. Тезис Чёрча. Класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций. Тезис Чёрча доказать нельзя, т.к. не существует строгого определения понятия вычислимой функции. Обобщением тезиса Чёрча является тезис Тьюринга. Тезис Тьюринга: Класс функций, алгоритмически вычислимых относительно какой-нибудь функции (или класса функций ), совпадает с классом частичных функций, частично рекурсивных относительно (соответственно относительно системы ). Из тезиса Тьюринга вытекает тезис Чёрча. Понятие общерекурсивной функции. Для каждой частично рекурсивной функции существует механический процесс, посредством которого любое натуральное число перерабатывается в значение функции . Этим процесс продолжается бесконечно, не давая окончательного результата, тогда и только тогда, когда значение функции в точке не определено. Таким образом, всюду определенная частично рекурсивная функция - это функции, для вычисления значений которой существует алгоритм, обрывающейся через конечное число шагов для любого начального числа. Алгоритмы, которые перерабатывают в определенное число любое заданное число, играют особую роль в теории алгоритмов. Вместе с ними особое положение в теории рекурсивных функций занимают всюду определённые частично рекурсивные функции. Такие функции называются общерекурсивными. Можно доказать, что многие известные арифметические функции являются примитивно рекурсивными. Среди них, например, неполное частное и остаток при делении натурального числа на число . Примитивно рекурсивной является характеристическая функция множества всех простых чисел натурального ряда. Одна из наиболее известных арифметических функций - функция - равная числу простых чисел, не превосходящих . Эта функция примитивно рекурсивная. Если значения примитивно рекурсивной, общерекурсивной или частично рекурсивной функции изменить лишь на конечном множестве точек, то новая функция будет снова примитивно рекурсивной, общерекурсивной или соответственно частично рекурсивной. Примитивно рекурсивными будут следующие множества натуральных чисел: 1) любая конечная совокупность чисел; 2) множества чисел вида ; 3) множества чисел вида и т.д. §4. Машины Тьюринга. Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми сейчас машинами Тьюринга-Поста или просто машинами Тьюринга. Машины Тьюринга копируют работу человека, вычисляющего по заданной программе. В 1936 г. Пост и Тьюринг одновременно и не зависимо друг от друга ввели в рассмотрение гипотетическую (не существующую) машину для определения алгоритма. Основная мысль их заключалась в том, что предписания всякого алгоритма может выполнить некоторая подходяще устроенная машина. Машины Поста и Тьюринга несущественно отличаются, но их возможности одинаковы и сегодня их называют машинами Тьюринга. Машина Тьюринга состоит из следующих частей: а) Конечная лента, разбитая на конечное число ячеек. В процессе работы машина к существующим ячейкам может пристраивать новые ячейки, так что ленту можно считать потенциально бесконечной в обе стороны. Каждая ячейка ленты может находиться в одном из конечного множества состояний. Эти состояния будем обозначать символами: . Множество этих символов называется внешним алфавитом машины, а сама лента часто называется внешней памятью машины. Клетки в фиксированном состоянии называются пустыми. В процессе работы машины ячейки ленты могут изменять свои состояния, но могут и не менять их. Все вновь пристраиваемые ячейки пристраиваются пустыми. Лента считается направленной и её ячейки просматриваются слева направо. Таким образом, если в какой-то момент времени лента имеет ячеек, и внешний алфавит машины состоит из символов , то состояние ленты полностью описывается словом , где - состояние первой ячейки (слева), - состояние второй ячейки и т.д. б) Внутренняя память машины - это устройство, которое в каждый рассматриваемый момент находится в некотором состоянии. Число возможных состояний внутренней памяти конечно и для каждой машины фиксированное. Состояние внутренней памяти мы будем обозначать символами , не входящими во внешний алфавит машины. Состояние внутренней памяти называют внутренними состояниями машины. Символы внутренней памяти называют внутренним алфавитом машины. Одно из внутренних состояний называется заключительным и в работе машины играет особую роль. Символ, обозначающий заключительное состояние машины будем обозначать: и называть «стоп» - символом. в) Управляющая головка. Это устройство, которое может, перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится в определённой ячейке ленты. Иногда, наоборот считают управляющую головку неподвижной, а движущейся частью считают ленту. Тогда считают, что в управляющую головку вводится то одна, то другая ячейка ленты. Если какая-нибудь ячейка находится в управляющей головке, то говорят, что машина в данный момент обозревает эту ячейку. г) Механическое устройство. Предполагается, что машина снабжена особым механизмом, который в зависимости от состояния воспринимаемой ячейки и состояния внутренней памяти может изменить состояние внутренней памяти и одновременно либо изменить состояние воспринимаемой ячейки, либо сдвинуть управляющую головку в соседнюю справа ячейку. Если управляющая головка находится в самой правой ячейке и по ходу работы машина должна сдвинуть управляющую головку в соседнюю справа отсутствующую ячейку, то предполагается, что, сдвигая головку, машина одновременно пристраивает недостающую ячейку в пустом состоянии. Аналогично работает машина и в случае, когда головка воспринимает самую левую ячейку и по ходу дела машине надо сдвинуть головку ещё левее. Наконец, если в какой-то момент времени внутренняя память машины приходит в заключительное состояние , то дальнейших изменений в машине не происходит и машина называется остановившейся. Может случиться, что в машине не будет происходить никаких изменений и при каком-то другом внутреннем состоянии . Однако в этом случае машина не считается остановившейся, считают, что в этом случае машина продолжает работать "вечно". По определению, состоянием машины Тьюринга или её конфигурацией называется совокупность, образованная последовательностью состояний всех ячеек ленты, состоянием внутренней памяти и номером к воспринимаемой ячейки . Все эти данные можно записать одним словом , которое мы будем называть машинным словом, описывающим указанное состояние машины. Таким образом, каждое машинное слово содержит лишь одно вхождение символа из внутреннего состояния. Этот символ может быть самым левым в машинном слове, но не может быть самым правым, т.к. справа от него должен помещаться символ состояния обозреваемой ячейки. С помощью такого «виртуального» устройства можно решать различные алгоритмические задачи. Машина Тьюринга – это пример того, что даже очень сложные алгоритмы могут быть реализованы на очень простых устройствах. Таким образом, машина Тьюринга - это множество, состоящее из пяти объектов (), где конечное множество А – это входной и выходной алфавит, символы этого алфавита могут быть записаны в ячейках ленты; конечное множество S – это множество внутренних состояний машины; - функции, определяемые следующим образом: 1) - это функция перехода в следующее внутреннее состояние, 2) - это функция выхода, 3) - это функция, регулирующая движение ленты, или ее остановку. Все эти функции зависят от того, в каком внутреннем состоянии в данный момент находится машина, и от считываемого с ленты символа. Машина работает дискретно, по тактам. Управляющая головка обозревает ячейку ленты, в которой записан символ . Находясь в состоянии , функция переводит машину в новое внутреннее состояние ; головка стирает символ , записанный в ячейке и записывает на ней новый символ, равный , который может совпадать с прежним, и наконец, в зависимости от значения функции (П, Л или останов.) головка сдвигается в соседнюю правую ячейку, если = П, в соседнюю слева ячейку (если =Л), или машина прекращает работу (если = останов.) Таким образом, программа работы машины состоит из тактов, каждый такт можно записать в виде: , где , , =П, Л или останов. Всякая программы работы машины – это конечная последовательность таких тактов. На машинах Поста и на машинах Тьюринга оказалось возможным осуществить все алгоритмические процессы, которые когда-либо описывались математиками. Список литературы. 1) Н. Я. Виленкин, Комбинаторика, «Наука», М., 1969. 2) М. Холл, Комбінаторика (пер. с англ.). 3) В. В. Белов, Е. М. Воробьев, В. Е. Шаталов, Теория графов, «Высшая школа», М., 1976. 4) О. Оре, Графы и их приложения, «Мир», 1965. 5) О. Оре, Теория графов (пер. с англ.), «Наука», 1968. 6) А. Гилл, Введение в теорию конечных автоматов, М., «Наука», 1966. Учебное издание курс лекций по дискретной математике 2 семестр (для студентов, специальности «Прикладная математика», «Компьютерные системы и сети») Составители: Вячеслав Викторович БАРАБАШ Елена Юрьевна ЧАЛАЯ Авторский оригинал-макет Издательство Восточноукраинского национального университета имени Владимира Даля Адрес издательства : 91034, г. Луганск, кв. Молодежный, 20а Телефон: 8 (0642) 41-34-12, факс. 8 (0642) 41-31-60 E-mail: uni@snu.edu.ua http: www.snu.edu.ua