Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
26, 27. КЛАСС M. ЛЕММА О НЕМОНОТОННОЙ ФУНКЦИИ Определение монотонной функции из дискретной математики очень похоже на определение из математического анализа. Нам понадобится понятие предшествования наборов. Пусть набор 𝛼 = (𝜎1, 𝜎2, … , 𝜎𝑛) и 𝛽 = (𝛿1, 𝛿2, … , 𝛿𝑛). Тогда набор 𝛼 предшествует набору 𝛽 (𝛼 ≼ 𝛽), если ∀𝑖 = 1, 𝑛 (𝜎𝑖 ≤ 𝛿𝑖). Например, наборы (010010) и (011011) находятся в отношении предшествования (первый предшествует второму), а (110010) и (101011) несравнимы в отношении предшествования. Теперь определение. Функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) ∈ 𝑃2 𝑛 - монотонная, если ∀𝛼, 𝛽 (𝛼 ≼ 𝛽 → 𝑓(𝛼) ≤ 𝑓(𝛽)). То есть если 𝑓(𝛼) = 0, то 𝑓(𝛽) может быть равно 0 или 1. А если 𝑓(𝛼) = 1, то 𝑓(𝛽) может равняться только 1. Докажем замкнутость класса M. ТЕОРЕМА. [M] = M. То есть какую бы формулу из произвольного числа монотонных функций не составить, эта формула всегда реализует монотонную функцию. ДОКАЗАТЕЛЬСТВО. Утверждения будут совершенно аналогичны тем, что были в доказательстве замкнутости класса Т0. Будем также доказывать по методу математической индукции и заменять формулы на реализуемые ими функции. Базис индукции: d (U) = 1. Пусть есть формула глубины 1, которая имеет вид: U = «𝑓(𝑥1, … , 𝑥𝑛)» (является записью функции, принадлежащей классу M). Рассмотрим функцию, реализуемую этой формулой 𝑓𝑈(𝑥1, … , 𝑥𝑛 ). Возьмём два любых двоичных набора такие, что один предшествует другому (пусть это наборы 𝛼 и 𝛽 и 𝛼 ≼ 𝛽). Тогда 𝑓𝑈(𝛼) = 𝑓(𝛼) (так как U = «𝑓(𝑥1, … , 𝑥𝑛)»). Но, зная, что 𝛼 ≼ 𝛽 и 𝑓(𝑥1, … , 𝑥𝑛) – монотонная функция, мы можем сказать, что 𝑓(𝛼) ≤ 𝑓(𝛽). А 𝑓(𝛽) = 𝑓𝑈(𝛽). В итоге 𝑓𝑈(𝛼) ≤ 𝑓𝑈(𝛽). То есть любая формула над М глубины 1 реализует монотонную функцию. Базис доказан. Индуктивное предположение и переход. Пусть функция, реализуемая формулой глубины d (U) ≤ k, принадлежит классу M. Докажем, что формула над M глубины k+1 реализует монотонную функцию. Рассмотрим такую формулу: 𝑈 = 𝑓(𝐴1, … , 𝐴𝑛 ). Проведём все те же операции, что и в доказательстве замкнутости Т0: заменим 𝐴1, … ,𝐴𝑛 на функции, которые они реализуют: 𝑈 = 𝑓(𝐴1, … , 𝐴𝑛 ) = 𝑓(𝑓𝐴1 (𝑥11 , … , 𝑥1𝑚1 ) , 𝑓𝐴2 (𝑥21 , … , 𝑥2𝑚2 ) , … , 𝑓𝐴𝑛 (𝑥𝑛1 , … , 𝑥1𝑚𝑛 ) ). Здесь у нас 𝑓, 𝑓𝐴1 ,…, 𝑓𝐴𝑛 - это всё монотонные функции. Рассмотрим теперь снова наши 2 набора 𝛼 и 𝛽, которые предшествуют друг другу. Поскольку 𝑓𝐴1 ,…, 𝑓𝐴𝑛 - монотонные функции и 𝛼 ≼ 𝛽, то мы можем сказать, что для всех них верно: 𝑓𝐴𝑖 (𝛼) ≤ 𝑓𝐴𝑖 (𝛽) (𝑖 = 1, 𝑛). Но запись 𝑓𝐴𝑖 (𝛼) ≤ 𝑓𝐴𝑖 (𝛽), оказывается, немного некорректна, потому что наборы 𝛼 и 𝛽 брались именно для функции 𝑓, а не 𝑓𝐴1 , … , 𝑓𝐴𝑛 , а функция 𝑓 и функция 𝑓𝐴𝑖 (𝑖 = 1, 𝑛) могут иметь разное количество аргументов, так же, как и функции 𝑓𝐴1 , … , 𝑓𝐴𝑛 могут иметь между собой разное количество переменных-аргументов. Например, 𝑓 имеет 4 аргумента, а 𝑓𝐴1 - 3 аргумента. Поэтому для подстановки в эти функции наборов 𝛼 и 𝛽 мы будем использовать только их части, которые как раз совпадают с количеством аргументов в 𝑓𝐴𝑖 (𝑖 = 1, 𝑛). То есть, возвращаясь к примеру выше, если 𝛼 = 0110, то в 𝑓𝐴1 мы подставим не 0110, а только 011, так как переменных у неё не 4, а 3. И такой набор мы назовём 𝑎1. И так поступим со всеми остальными функциями 𝑓𝐴2 , … , 𝑓𝐴𝑛 . Тоже самое и с 𝛽. Так как набор 𝛼 предшествует набору 𝛽, то и их части тоже находятся в отношении предшествования (то есть 𝑎𝑖 ≼ 𝛽𝑖 ). Итак, мы имеем 𝑓𝐴𝑖 (𝑎𝑖 ) ≤ 𝑓𝐴𝑖 (𝛽𝑖 ), поскольку 𝑎𝑖 ≼ 𝛽𝑖 и 𝑓𝐴𝑖 - монотонная функция. Но 𝑓𝐴𝑖 (𝑎𝑖 ) и 𝑓𝐴𝑖 (𝛽𝑖 ) - это просто какие-то значения (либо 0, либо 1). А значит, (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ),…, 𝑓𝐴𝑛 (𝑎𝑛 )) и (𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ),…, 𝑓𝐴𝑛 (𝛽𝑛 )) – это какието двоичные наборы, так как они просто составлены из нулей и единиц, которые являются значениями функций в этих наборах. Причём мы знаем, что 𝑓𝐴𝑖 (𝑎𝑖 ) ≤ 𝑓𝐴𝑖 (𝛽𝑖 ) для 𝑖 = 1, 𝑛. А значит, эти два набора (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ),…, 𝑓𝐴𝑛 (𝑎𝑛 )) и (𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ),…, 𝑓𝐴𝑛 (𝛽𝑛 )) подходят под определение предшествующих наборов, так как каждая из цифр набора (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ),…, 𝑓𝐴𝑛 (𝑎𝑛 )) меньше либо равна соответствующей ей цифре набора (𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ),…, 𝑓𝐴𝑛 (𝛽𝑛 )) (напомню ещё раз, это следует из условия 𝑓𝐴𝑖 (𝑎𝑖 ) ≤ 𝑓𝐴𝑖 (𝛽𝑖 )). То есть мы получили, что это два предшествующих набора, причём (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ),…, 𝑓𝐴𝑛 (𝑎𝑛 )) ≼ (𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ),…, 𝑓𝐴𝑛 (𝛽𝑛 )). Осталось ещё немного. Вспомним, что у нас формула над М глубины k+1: 𝑈 = 𝑓(𝐴1, … ,𝐴𝑛 ), причём 𝑓 - монотонная функция. А так как 𝑓 - монотонная функция и наши 2 длинных набора предшествуют друг другу, то мы можем записать следующее: 𝑓𝑈 (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ), … , 𝑓𝐴𝑛 (𝑎𝑛 )) = 𝑓 (𝑓𝐴1 (𝑎1 ), 𝑓𝐴2 (𝑎2 ), … , 𝑓𝐴𝑛 (𝑎𝑛 )) ≤ 𝑓 (𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ), … , 𝑓𝐴𝑛 (𝛽𝑛 )) = 𝑓𝑈(𝑓𝐴1 (𝛽1 ), 𝑓𝐴2 (𝛽2 ), … , 𝑓𝐴𝑛 (𝛽𝑛 )) То есть в итоге функция 𝑓𝑈, реализуемая формулой над М глубины k+1, также является монотонной. Теорема доказана. Лемма о немонотонной функции. Если функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) немонотонная, то подстановкой вместо переменных этой функции функций констант (0 и 1) можно получить функцию 𝑥. ДОКАЗАТЕЛЬСТВО. Здесь опять же нужно получить функцию от одной переменной, так как функция отрицания – функция одной переменной. Напишем отрицание части определения монотонной функции: ∃𝛼, 𝛽 (𝛼 ≼ 𝛽 & 𝑓(𝛼) > 𝑓(𝛽)). То, что набор 𝛼 предшествует набору 𝛽 говорит о том, что, если рассмотреть те позиции в этих наборах, где эти наборы различаются между собой, то в 𝛼 на этих позициях обязательно будет 0, а в 𝛽 на тех же позициях – 1. Количество позиций, в которых 𝛼 и 𝛽 могут быть различными, может быть разным. Пусть наборы 𝛼 и 𝛽 различаются ровно в 𝑟 позициях. Рассмотрим последовательность 𝛼0, 𝛼1, …, 𝛼𝑟 (𝛼0 = 𝛼, 𝛼𝑟 = 𝛽). Лучше всего можно понять на примере. Пусть 𝛼0 = 00010110100000, 𝛼𝑟 = 11010111101010 (я подчеркнул те позиции, в которых 𝛼 и 𝛽 различаются). А теперь будем поочерёдно заменять нули в подчёркнутых позициях в 𝛼 на единицы, чтобы в конце получить 𝛽. То есть получаем, что 𝛼0 = 00010110100000 = 𝛼, 𝛼1 = 10010110100000, 𝛼2 = 11010110100000, 𝛼3 = 11010111100000, 𝛼4 = 11010111101000, 𝛼5 = 11010111101010 = 𝛽. То есть каков индекс у 𝛼, столько подчёркнутых нулей в наборе 𝛼 мы заменили на единицы (слева направо и последовательно). Здесь любые два набора находятся в отношении предшествования. А теперь рассмотрим значения функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) на всех этих наборах (то есть рассмотрим значения 𝑓(𝛼0 ), 𝑓(𝛼1 ), …, 𝑓(𝛼𝑟 )). Вспомним начало доказательства: мы писали, что 𝛼 ≼ 𝛽 & 𝑓(𝛼) > 𝑓(𝛽). Но значений функции может быть всего 2: 0 и 1, поэтому мы спокойно сможем найти ту самую границу, где заканчиваются значения, равные 1, и начинаются значения, равные 0. Поэтому, мы сможем найти два соседних набора 𝛼𝑖 и 𝛼𝑖+1, на которых 𝑓(𝛼𝑖 ) = 1, а 𝑓(𝛼𝑖+1 ) = 0. Но эти два набора различаются только в одной позиции (у 𝛼𝑖 на ней стоит 0, а у 𝛼𝑖+1 стоит 1). Поэтому эти наборы имеют вид: 𝛼𝑖 = (𝜎1 … 𝜎𝑗−1 0 𝜎𝑗+1 … 𝜎𝑛), 𝛼𝑖+1 = (𝜎1 … 𝜎𝑗−1 1 𝜎𝑗+1 … 𝜎𝑛) (здесь индекс j, поскольку мы не можем сказать, где этот 0 находится, он может находиться где угодно. На i-той позиции в наборе он не находится, но относительно тех позиций, в которых различаются 𝛼 и 𝛽, он на i-том месте. Также здесь мы вводим набор из сигм, потому что мы ничего не знаем про наборы 𝛼𝑖 и 𝛼𝑖+1). Тогда можем составить такую функцию ℎ(𝑥), получаемую из 𝑓 подстановкой этого набора вместо переменных: ℎ(𝑥) = 𝑓(𝜎1 … 𝜎𝑗−1 𝑥 𝜎𝑗+1 … 𝜎𝑛), в которой будет лишь одна переменная, а остальные аргументы – какие-то фиксированные значения. Тогда ℎ(0) = 𝑓(𝜎1 … 𝜎𝑗−1 0 𝜎𝑗+1 … 𝜎𝑛) = 1 и ℎ(1) = 𝑓(𝜎1 … 𝜎𝑗−1 1 𝜎𝑗+1 … 𝜎𝑛) = 0, так как функция немонотонная. Мы получили отрицание, поскольку ℎ(0) = 1 и ℎ(1) = 0, а это и есть табличное задание функции отрицания (при x = 0 значение функции равно 1, при x = 1 значение функции равно 0). Доказательство завершено. 28. КЛАСС L. ЛЕММА О НЕЛИНЕЙНОЙ ФУНКЦИИ Линейной функцией называется функция вида 𝛼1𝑥1 +…+ 𝛼𝑛𝑥𝑛 + 𝛼𝑛+1, где 𝛼1,…, 𝛼𝑛+1 - коэффициенты, которые равны 0 или 1 при переменных и свободном члене. Здесь «+» - сумма по модулю 2. То есть она представляется в виде полинома Жегалкина. Причём заметим, что в каждом из слагаемых только по одной переменной, двух и больше здесь нет (при свободном члене нет переменной, здесь всё нормально). Лемма о нелинейной функции. Если 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) – нелинейная функция, то подстановкой вместо переменных функций 0, 1, 𝑥, 𝑥 и (возможно) отрицания 𝑓 можно получить конъюнкцию 𝑥1&𝑥2. ДОКАЗАТЕЛЬСТВО. Здесь мы уже должны получить функцию от двух переменных, а не от одной. Поскольку функция является нелинейной, то в её представлении в виде полинома Жегалкина найдётся слагаемое, в котором минимум 2 переменные (пусть это будут переменные x1 и x2; в противном случае можно переименовать переменные). После всех преобразований, которые ведут от функции к полиному Жегалкина, у нас будет: 𝑓(𝑥1, 𝑥2, 𝜎3, … , 𝜎𝑛 ) = 𝑥1&𝑥2&𝑃1(𝑥3, … , 𝑥𝑛) + 𝑥1&𝑃2(𝑥3, … , 𝑥𝑛) + 𝑥2&𝑃3(𝑥3, … , 𝑥𝑛) + 𝑃4(𝑥3, … , 𝑥𝑛). Здесь 𝑃1(𝑥3, … , 𝑥𝑛),…, 𝑃4(𝑥3, … , 𝑥𝑛) – полиномы Жегалкина от переменных 𝑥3, … , 𝑥𝑛. 𝑃1(𝑥3, … , 𝑥𝑛) содержит хотя бы одно ненулевое слагаемое (иначе не было бы слагаемого 𝑥1&𝑥2 и функция была бы линейной). Значит, существует набор 𝜎3,…, 𝜎𝑛, на котором 𝑃1(𝜎3,…, 𝜎𝑛) = 1. Подставим этот набор в 𝑃2, 𝑃3, 𝑃4. Значения могут быть как 0, так и 1, поэтому мы получаем выражение 𝑥1&𝑥2 + 𝛼𝑥1 + 𝛽𝑥2 + 𝛾. Для дальнейшего доказательства мы будем производить замену переменных. Пусть у нас 𝛼 и 𝛽 не равны 0 (если кто-то или все равны нулю, то замену переменной в соответствующем слагаемом проводить не будем). Если они не равны нулю, то они равны единице. Поэтому, мы можем сделать замену 𝑥1 на 𝑥1 + 𝛼. А это равно 𝑥1 + 1 = 𝑥1. А это равносильно подстановке в функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) функции отрицания. То же самое для 𝑥2, заменим на 𝑥2 + 𝛽. Теперь мы можем преобразовать полученное выражение: 𝑓(𝑥1, 𝑥2, 𝜎3, … , 𝜎𝑛 ) = (𝑥1 + 𝛼)&(𝑥2 + 𝛽) + 𝛼(𝑥1 + 𝛼) + 𝛽(𝑥2 + 𝛽) + 𝛾. После всех преобразований (раскрытие скобок, использование соотношений эквивалентности) мы получаем выражение 𝑥1&𝑥2 + 𝛼 𝛽 + 𝛾. Если в итоге 𝛼 𝛽 + 𝛾 = 0, то конъюнкция получена. Если 𝛼 𝛽 + 𝛾 = 1, то мы можем навесить на 𝑓 отрицание, и мы получим конъюнкцию. Почему? Потому что у нас выходит в таком случае 𝑥1&𝑥2 + 1, а это равно 𝑥1&𝑥2 (по свойству суммы по модулю 2; это свойство можно проверить просто подстановкой значений). При навешивании отрицания на 𝑓 получим конъюнкцию. Доказательство завершено. Подстановка констант осуществлялась, когда мы подставляли набор 𝜎3,…, 𝜎𝑛 в функцию, а подстановка тождественной функции 𝑥 была равносильна замене 𝑥 на 𝑥 + 𝛼 (где 𝛼 = 0). Но так как 𝛼 = 0, то можно сказать, что эта подстановка нам не сильно понадобилась, так как слагаемое всё равно уходило. 29. КРИТЕРИЙ ПОЛНОТЫ В P2 Теперь рассмотрим важное условие, при выполнении которого мы гарантированно сможем сказать, что некоторая система функций В является полной. Для изучения этой темы нужно понять 3 леммы и определения классов (всё расписано выше). КРИТЕРИЙ. Система B ⊆ P2 полна тогда и только тогда, когда система В не содержится ни в одном из классов T0, T1, S, M, L. ДОКАЗАТЕЛЬСТВО. Этот критерий нужно доказывать в обе стороны (об этом нам говорит словосочетание «тогда и только тогда, когда»). Здесь нужно приготовиться к тому, что нужно будет рассматривать немало случаев, которые могут быть. В одну сторону доказывается очень просто. Пусть система В полна. Нам нужно доказать, что она не содержится ни в одном из 5 классов. Доказываем от противного. Мы предполагаем, что вторая часть критерия не выполняется, то есть рассматриваемая нами система функций полностью содержится в каком-то из классов Т0, Т1, S, M, L. Пусть, к примеру, она содержится в Т0. Это означает, что все функции, принадлежащие В, принадлежат и Т0. Тогда можем записать, что В ⊆ Т0. Но с другой стороны мы имеем условие (которым можем пользоваться), что В - полная система, то есть [B] = P2. Но [Т0] = Т0 ≠ P2. Получаем, что В содержится в P2, а Т0 там не содержится. А P2 - это множество всех функций алгебры логики. Поэтому получаем противоречие. В обратную сторону доказательство будет подлиннее. Условие о том, что система В не содержится в каком-то из 5 классов (например, в Т0) равносильно тому, что есть хотя бы одна функция из множества функций В, которая не принадлежит классу Т0 (иначе все бы функции из В принадлежали Т0 и В полностью содержалась бы в Т0). То есть мы имеем условие, что в классе В есть функции, не принадлежащие всем 5 классам (Это не значит, что не принадлежат всем 5 одновременно. Это значит (ЭТО ЧИСТО ПРИМЕР), что например есть функция f1, которая не принадлежит, например, классу Т0, есть функция f2, которая не принадлежит S, L, есть функция f3, которая не принадлежит классам Т1, M, S, L и тд). Нам необходимо предоставить алгоритм, по которому, имея эти функции, мы можем доказать, что с этими функциями система В действительно является полной. Самый простой пример полной системы - система из двух функций: конъюнкция и отрицание. Её мы сейчас и будем получать. Мы прошли 3 леммы, а также знаем определения классов. Этим мы и будем пользоваться. Нам нужно получить отрицание и конъюнкцию. Но для их получения нам также понадобятся функции-константы (это требуют некоторые из лемм). Сначала получим отрицание. Как можно получить отрицание? Мы можем вспомнить, что отрицание получается с помощью немонотонной функции (мы знаем лемму о ней). Но для этого нам нужно получить константы, чтобы их подставить для получения отрицания (по лемме о немонотонной функции). 1. Получение константы Как можно получить функции-константы? Есть два варианта: 1) рассмотрение классов Т0 и Т1 2) лемма о несамодвойственной функции (но этот вариант отпадает, потому что здесь мы должны подставлять отрицание для получения констант, которого у нас пока нет). Рассмотрим функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), которая не принадлежит классу Т0. Рассмотрим функцию ℎ(𝑥) = 𝑓(𝑥, … , 𝑥). Тогда мы можем сказать, что ℎ(0) = 𝑓(0, … ,0) = 1 (если 0, то принадлежит классу Т0, а это нам не нужно). Теперь рассмотрим ℎ(1). Чему это может быть равно? 1) Если ℎ(1) = 0, то ℎ(𝑥) − функция отрицания. В этом случае мы уже получили отрицание. Нам необходимо получить константы (это требует лемма о немонотонной и нелинейной функции). Именно в этом случае (в пункте 1) мы можем воспользоваться леммой о несамодвойственной функции. По ней мы получаем одну из констант подстановкой отрицания и тождественной функции (если ℎ(𝑥) – функция отрицания, то тождественную функцию 𝑔(𝑥) можно получить путём навешивания отрицания на ℎ(𝑥), то есть 𝑔(𝑥) = ℎ(𝑥)). Другую константу получаем отрицанием первой. Но может оказаться так, что ℎ(1) = 1 и это уже другой случай. 2) Если ℎ(1) = 1, то ℎ(0) = ℎ(1) и в данном случае ℎ(𝑥) - константа, равная 1. Одна из констант получена. Константа 0 получается тем же путём, только проделав такие рассуждения с функцией, не принадлежащей Т1. 2. Получение отрицания Константы получены, теперь переходим к получению отрицания. Для этого применяем лемму к функции, не принадлежащей классу M (то есть к немонотонной) 3. Получение конъюнкции У нас есть на данном этапе константы, отрицание и тождественная функция. Мы можем воспользоваться леммой о нелинейной функции и конъюнкция будет получена. Мы получили то, что хотели, и значит, предъявили алгоритм, по которому, имея систему функций, не принадлежащую T0, T1, S, M, L, доказали, что эта система – полная. Доказательство завершено. 40. ТЕОРЕМА ЭЙЛЕРА (ДОСТАТОЧНОСТЬ) Нам понадобиться определение компоненты связности и связности графа. Компоненты связности – максимально связные подграфы графа. Пример. Здесь компонентами связности являются G1 и G2. Смысл в том, что, например, компонентой связности не являются части подграфов G1 и G2. Компоненты связности должны иметь максимально возможное количество рёбер так, чтобы подграф оставался связным. Надеюсь, понятно. Доказательство достаточности теоремы Эйлера состоит из двух этапов: 1) В качестве вспомогательного утверждения доказывается, что в чётном графе всегда есть элементарный цикл длины не меньше трёх 2) Доказывается утверждение теоремы с помощью вспомогательного утверждения методом математической индукции 1. С этим всё более менее просто. Берём одну какую-то вершину графа v0 и начинаем движение по рёбрам графа. Достигли вершины v1. Поскольку граф – чётный, то из вершины v1 должно выходить по крайней мере ещё одно ребро (в противном случае степень вершины v1 будет равна 1, то есть будет нечётной, что противоречит определению чётного графа). Дальше идём по ребру от вершины v1 до вершины v2. Потом аналогично от вершины v2 идёт ребро в вершину v3, а затем из v3 ребро идёт в v1, либо дальше, скажем, в вершину v4. В первом случае элементарный цикл длины не меньше трёх получен (его длина 3), во втором случае просто продолжаем алгоритм, и за конечное число шагов мы всё-таки дойдём снова до вершины v1 (так как вершин графа конечное число) и получим элементарный цикл длины не меньше 3. То есть элементарный цикл длины не меньше трёх в ЧЁТНОМ графе всегда существует. Это нам поможет во втором пункте. 2. Начинаем доказывать утверждение теоремы индукцией по числу m рёбер графа. Базис: m = 0. То есть это одновершинный граф без рёбер. Ну и какойникакой, цикл Эйлера, можно сказать, тут присутствует. Индуктивное предположение и переход: пусть для чётного графа с m ≤ k рёбрами выполнено условие теоремы и для таких графов существует цикл Эйлера (про знак ≤ говорилось в теме про классы Т0 и Т1). Докажем, что для чётного графа с m = k + 1 ребром существует цикл Эйлера. Мы доказали вспомогательное утверждение. То есть в любом чётном графе существует элементарный цикл длины не меньше трёх. Здесь нужно вспомнить, какими свойствами обладает граф, который мы сейчас рассматриваем. Он чётный, связный, неориентированный, без петель. Для дальнейших рассуждений нужно понять, как могут вообще выглядеть чётные графы. В этом графе можно выделить очень-очень много элементарных циклов, но для примера возьмём цикл С (который идёт по красным точкам). Теперь произведём следующее действие: удалим все рёбра этого цикла из графа. Удаляем их не навсегда, а лишь затем, чтобы понять, какими свойствами обладает наш получившийся граф (он состоит из всех вершин исходного графа, так как мы вершины не удаляли, и из рёбер, которые остались после удаления ребёр цикла С). Самое важное – это то, что граф остался чётным, степени вершин графа либо не изменились (это те вершины, которые циклу С не принадлежали), либо уменьшились на 2 (это вершины, принадлежащие циклу С), но операция вычитания числа 2 чётность степени вершин не меняет. То есть мы уяснили для себя, что граф даже при удалении элементарного цикла остался чётным. После удаления цикла С у графа образовалось несколько компонент связности. Обозначим за 𝐺1, … ,𝐺𝑟 все компоненты связности графа 𝐺. В нашем примере 4 компоненты связности после удаления цикла С 𝐺1, 𝐺2, 𝐺3, 𝐺4. Возьмём из них произвольную компоненту связности 𝐺𝑖 (в примере пусть это будет С1). Нам нужно будет доказать на вид простое утверждение: что компонента связности 𝐺𝑖 и цикл С имеют общую вершину. Для этого обозначим за 𝑣𝑖 вершину, принадлежащую 𝐺𝑖 (она необязательно принадлежит циклу С). Обозначим за 𝑣0 произвольную вершину, лежащую на цикле С. Граф 𝐺 является связным, поэтому существует путь из 𝑣0 в 𝑣𝑖 . Обозначим вершину, которая является последней на цикле в пути из 𝑣0 в 𝑣𝑖 , за 𝑣𝑠 . На рисунке сиреневым цветом обозначен путь из 𝑣0 в 𝑣𝑖 . Мы должны доказать, что 𝑣𝑠 принадлежит компоненте 𝐺𝑖 . Это доказывается одним предложением: все рёбра нашего пути, проходимые через 𝑣𝑠 , не были удалены из графа 𝐺 при удалении рёбер цикла С (так как 𝑣𝑠 является последней вершиной пути, и которая лежит на цикле С), а это и означает, что вершина 𝑣𝑠 принадлежит компоненте 𝐺𝑖 , поскольку рёбра, идущие после вершины 𝑣𝑠 , принадлежат лишь компоненте 𝐺𝑖 и не принадлежат циклу С. Поэтому помимо того, что 𝑣𝑠 принадлежит циклу С, она ещё принадлежит 𝐺𝑖 . Такие утверждения мы можем проделать для всех компонент связности графа, поэтому все компоненты связности имеют хотя бы одну общую вершину с циклом С. Как было сказано ранее, компоненты связности являются чётными графами, а значит, по индуктивному предположению (у них же не k+1 ребро, а меньше, поэтому можем пользоваться этим) у этих компонент существуют циклы Эйлера. Обозначим их за 𝐶1,…, 𝐶𝑟 (их, естественно, столько же, сколько и компонент). Эти циклы в компонентах можно начинать с любой вершины, поэтому для удобства будем считать, что каждый из них начинается с вершины, лежащей на цикле С. Осталось совсем чуть-чуть. Дальше идёт простой алгоритм: начинаем движение с начальной вершины 𝑣0 и будем идти по рёбрам, проходя все циклы Эйлера в компонентах (полный алгоритм нужно выучить из лекции, он очень простой) до тех пор, пока не пройдём все компоненты и не вернёмся в вершину 𝑣0. Этот алгоритм и есть наш цикл Эйлера для чётного графа с k+1 ребром. Всё доказано. То есть ключевая идея в построении цикла Эйлера в любом чётном графе состоит в том, что мы ищем какой-нибудь элементарный цикл в графе, для нас он будет как опорный. А потом двигаемся по этому опорному циклу, по пути проходя «второстепенные» части графа (компоненты связности). |