3. Понятие алгебры логики. Морфизмы. Конгруэнции. Фактор-алгебры 4

генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер. В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.
Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?
Обозначим белый шар символом ○, чёрный — ●, Tn — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев: Если n=1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T2 = 2. Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●. Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●. В итоге количество шаров удвоилось, то есть T3 = 2T2. Аналогично T4 = 2T3, то есть, обобщая для всех n, получаем рекуррентное уравнение Tn = 2Tn-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — Tn = 2n (так как 2⋅2n-1 = 2n). А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции? «Просуммируем» все возможные комбинации расположений шаров: G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +… Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.
Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G получим уравнение G = Ø + ○G +●G. Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,
Учитывая формулу суммы геометрической прогрессии 
имеем
В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: 
где
— число сочетаний из n по k. Тогда с учетом этого имеем:
Коэффициент при ○k ●n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно 
Эту формулу можно было получить непосредственно из 
заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим 
то есть коэффициент при zn равен 2n.
Обсуждение метода
Так что же позволяет данному методу быть работоспособным при решении различных задач? Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g0 + g1z + g2z2 +… + gnzn +… причем коэффициенты gk (не заданные в явном виде) — являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z — является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов. G(z) = g0 + g1z + g2z2 +… + gnzn +… — называется производящей функцией для последовательности . Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z0, за исключением z = 0, так как G(0) = g0. Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов gk. Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x2 + x3 + ..., а в замкнутом 
Пути и циклы. Планарные граф
Графом называется геометрическая фигура состоящая из точек и соединяющих их линий. Точки называются вершинами. Стороны - ребрами
два ребра называются смежными, если они имеют общую вершину; ребра называется петлей если его концы совпадают; два ребра называют кратными если они соединяют одну и ту же пару вершин; Определения A B C D E m p s t r q Пример: Смежные ребра: D С и CA, CD и DB, DB и BA, BA и AC Изолированная вершина: E Кратные ребра: m и p Петля: q вершина называется изолированной, если она не является концом ни для одного ребра
степенью вершины A называют количество ребер, для которых она является концевой (петли считать дважды) Обозначение: deg ( A ). G H E C D F A B A B C D E u p s t r q deg(E) = 0 deg(C) = 2 E – изолированная вершина deg(G) = 1 deg(H) = 1 deg(E) = 1 deg(B) = 1 deg(A) = 1 deg(C) = 4 deg (D) = 2 G, H, E, B, A - висячие вершины Определения Пример:
В любом графе сумма степеней всех вершин равна удвоенному числу ребер Доказательство: Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней всех вершин мы учтем это ребро дважды; Если ребро является петлей, то при подсчете суммы степеней всех вершин мы также учтем это ребро дважды; В любом графе число вершин нечетной степени четно Следствие степенью вершины называют количество ребер, для которых она является концевой (петли считать дважды) |=> (по определению степени вершины) ч.т.д
В любом графе число вершин нечетной степени четно Следствие Доказательство: Т.к. каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа каждое ребро вносит двойку. Таким образом, мы приходим к утверждению, которое установлено Эйлером и является исторически первой теоремой теории графов.
Может ли в государстве, в котором из каждого города выходит 3 дороги быть ровно 100 дорог Ответ: не может Решение : Города – вершины графа ( k, k є N ). Степень кратности каждой вершины 3 => Дороги – ребра графа ( p = 100 ) По Лемме 3 k = 2p. Если р = 100, то k = Но k є N => p ≠ 100
Граф, состоящий из «изолированных» вершин, называется нулевым графом Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром. Граф, в которых не построены все возможные ребра, называют неполным графом. M A D B C A B C D E L U B O V