Элементы Комбинаторики

1. Класс  линейных функций 
   Перекл. функция назыв............................................................ линейной, если она представима полиномом Жегалкина первой степени:   
   Число линейных функций рано  например при n=2 число линейных функций равно 8: 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
   2. Класс  функций, сохраняющих 0 
   Если перекл. функция на кортеже 00…0 равна нулю, то говорят, что функция сохрани нуль 
   Т. функция  принадлежит классу функций, сохраняющих 0, если  
   Для 2х переменных таких функций 8. 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
   3. Класс  функций, сохраняющих 1 
   Если перекл. функция на кортеже 11…1 равна 1, то говорят, что функция сохрани единицу 
   Т. функция  принадлежит классу функций, сохраняющих 1, если  
   Для 2х переменных таких функций 8 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
   4. Класс  монотонных функций 
    
   - монотонная функция 
   Таких функций 6 
    
    
    
    
    
    
    
    
    
    
    
    
    
   5. Класс   самодвойственных функций. 
   Переключательная функция называется самодвойственной, если на каждой паре противоположных кортежей значения функции противоположны. 
    
    
   На кортежах 00 и 11,01,10 противоположные значения могут иметь функции 
    
    
    
    
    
    
    
    
   Теорема Поста о функциональной полноте. Для того чтобы система булевых функций была полной необходимо и достаточно, чтобы она содержала: 
   -хотя бы одну функцию, не сохраняющую 0 
   -хотя бы одну функцию, не сохраняющую 1 
   -хотя бы одну функцию, не явл. линейной 
   -хотя бы одну функцию, не явл. монотонной 
   -хотя бы одну функцию, не явл. самодвойственной. 
   Каждый базис содержит не более 4х булевых функций.

Минимизация переключательных функций Основные понятия, Способы построения минимальных ДНФ 
Минимизация ДНФ включает следующие этапы: 

1. Получение простых импликант и сокращенной ДНФ

2. Получение тупиковой ДНФ

3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем применять один из след методов: Метод Квайна, геометрический, карты Карно 
Метод Квайна 
В его основе лежат следующие равносильности: 
1. Полного склеивания   
2. Поглощения   
3. Не полного склеивания   
 
Если в СДНФ провести все операции неполного склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ. 
Геометрический метод 
Он удобен в случаях двух и трех переменных. В более сложных случаях применение метода становится громоздким. 
Суть метода: 1) для функции n переменных отмечаются вершины куба, соответств. кортежам, на которых функция принимает значение 1. 
 
2) проводят склеивание – отмечают ребра, содерж. 2 отмеч. вершины. 
3) проводят поглощение – отмечают грани, содерж все 4 склеенные вершины. 
Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер. 
Карты Карно 
Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4 
Переменные кортежа разбиваются на 2 части. Первая часть является кодом столбца, вторах – строк. Таким образом, карты Карно неявно задают сами кортежи. 
Например:   
 

 
 
 
Процесс минимизации  СДНФ представляет собой склеивание кодов кортежей для каждого сплошного участка причем кол-во единиц на таком сплошном участке должно быть степенью числа 2. 

Понятие графа. Виды графов. Изоморфизм 
Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты удобно изображать точками системы, связи между ними – дугами со стрелками(или без них).  Такие системы образ графы. Объекты называют вершинами, дуги – ребрами графа. 
Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам , которое оно соединяет. 
Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным. 
Ребра, инцидентные одной и той же паре вершин, называют параллельными или кратными. Граф, содержащий кратные ребра, именуется мульти графом. 
Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если множество вершин пусто. 
Ребро, концевые вершины которого совпадают, называют петлей. 
Граф, без петель и кратных ребер, называется полным если каждая из его вершин соединена ребром. 
Степенью вершины в неориентир графе называется кол-во ребер, инцидентных этой вершине. 
Графы отличающиеся только нумерацией вершин и ребер, называются изоморфными.  
Изоморфные графы имеют одинаковое число вершин, ребер, степени соответствующих вершин равны. 

Способы задания графов 
В общем виде «задать граф» означает: описать множество его вершин и ребер, а также отношение инцидентности. 
Способы задания графа: 
1. Графический 
2. Перечислением вершин и ребер. 
3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа. 
Для неориентир. графа: 1 – если вершина и ребро инцидентны, 0 – если не инциндентна. 
Для ориентир - -1 если вершина является началом ребра, 1 – если концом ребра, 0 – не инциндентны, 2 – ребро – петля. 
 
Задание графа матрицей смежности 
Матрица смежности – это квадратная матрица размера n*n, которая по горизонтали и по вертикали учитывает все вершины графа. 
Матрица смежности не ориентир графа симметрична относительно главной диагонали. И кол-во ребер графа равно сумме элементов матрица, распол. выше главной диагонали. 
5. Задание графа матрицей весов. 
Матрица весов - вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n  n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v , v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи. 
17. Маршруты и циклы. Связность. 
Маршрутом называется последовательность вершин и ребер, в которой любые 2 соседних элемента инцидентны. 
Если в простом графе маршрут задан последовательностью вершин  , то вершины  и   называются концами маршрута. 
Маршрут называется замкнутым, если  . Незамкнутым - если  
Маршрут, в котором нет повторений ребер, называется цепью. Замкнутая цепь называется циклом. Цепь, все вершины различны, кроме, может быть её концов, называется простой. Замкнутая простая цепь называется простым циклом и обозначается  , где р – число вершин. 
Граф, у которого любые 2 его вершины являются смежными, называется полным графом. 
Маршрут(для ориентир графа), дуги которого различны, называется путем. 
Длинной маршрута называется число ребер графа с учетом повторений. 
Две вершины называются связными, если их соединяет хотя бы одна простая цепь. 
Отношение связности – это отношение эквивалентности. 
Граф, называют связным, если любые 2 его вершины можно соединить простой цепью. 
Ребро называют перешейком, если после его удаления граф теряет свойство связности, т.е. распадается на 2 компонента связности. 
Ориентированный граф называют сильно связным, если 2 любые его вершины, можно соединить путем, т.е.   и   
Ориентированный граф называют слабо связным, если явл. связным граф, получающийся из орграфа заменой всех его дуг на ребра. 

Эйлеровы и гамильтоновы графы 
Путь в графе называется эйлеровым, если он содержит все ребра графа. Замкнутый эйлеров путь называется эйлеровым циклом. Граф, который имеет эйлеров цикл, также называется эйлеровым. 
 
Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные. 
Эйлеровой цепью, называется маршрут, соединяющий две различные вершины u и v и содерж все ребра графа по одному разу. 
Гамильтоновым циклом называется простой цикл, проходящий через все вершины графа по одному разу. Граф, в котором сущ. гамильтонов цикл, называется гамильтоновым. Простая цепь, проходящая через все вершины графа по одному разу называется гамильтоновой цепью. 
Если в простом графе G(V,E) с p вершинами степень любой вершины v удовлетворяет неравенству p(v)≥p/2 

Планарные графы. Теорема Понтрягина-Куратовского 
Все графы, изоморфные другому, несут одну и ту же информацию, но их изображение может быть различным.  
Граф, вершины которого являются точками плоскости, а ребра – не прерывными плоскими линиями без самопересечений, причем никакие 2 ребра не имеют общих точек, кроме инцидентной им обоим вершинам, называется плоским. 
Любой граф изоморфный плоскому графу, называется планарным. 
Говорят, что граф укладывается на плоскости (имеет плоскую укладку), если его можно представить в виде плоского графа. 
Очевидно, что 1) всякий подграф планарного графа планарен. 
 
2) граф планарен, тогда и только тогда, если каждая связная компонента этого графа – планарный граф. 
Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа подразбиением(добавление вершины на ребре) ребер. 
Теорема Понтрягина-Куратовского. 
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К5 или К3.3

Формула Эйлера 
Формула Эйлера: 
n-m+p=2, где n-число вершин, m – ребер, p-граней. 
Следствие: Если в простом связном плоском графе n≥3, то m≤3n-6  
Формулой Эйлера удобно пользоваться при исследовании графа на планарность.

Раскраска графов 
Задачи раскраски вершин, рёбер, граней графа занимают важное место в теории графов. К построению раскрасок сводится ряд практических задач, например, задачи составления расписаний, проектирования технологических цепочек, распределения оборудования, раскраски географий ческой карты и т.н. 
Раскраской графа называется такое приписывание цвета его элементам (вершинам, рёбрам или граням), что никакие два смежные элемента не получают одинакового цвета. 
 
Хроматическим числом элементов (вершин, рёбер или граней) графа рыпается минимальное число цветов для раскраски элементов графа. 
В конце XIX века была сформулирована   гипотеза    четырёх   красок:    всякий    планарный    граф    4-раскрашиваем. Попытки доказать эту гипотезу привели к следующей теореме: ВСЯКИЙ ПЛАНАРНЫЙ ГРАФ 5-РАСКРАШИВАЕМ. 
На практике изображение микросхемы представляет собой граф. При изготовлении важно выяснить, можно ли схему радиоэлектронного устройства изобразить на плоскости без пересечения проводников, т.е. является ли граф планарным, возможна ли его плоская укладка. Раскраска элементов позволяет сократить затраты времени на анализ информации и корректирование процессов, изображенных в форме графа. 

Деревья. Минимальное остовное дерево 
Существует один простой и важный тип графов, которому все авторы ли одинаковое название - деревья. 
Деревом называется связный граф, не имеющий циклов. 
Лесом называется любой граф без циклов. 
Следовательно, деревья являются компонентами леса. 
Связный ориентированный граф без циклов называется ориентированным деревом. 
Если дерево имеет п вершин, то оно имеет п-1ребро 
Если какую-либо пару несмежных вершин дерева соединить ребром, то полученный граф будет содержать ровно один цикл, и следовательно, уже не будет являться деревом. 
Очевидно, что любое ребро дерева является перешейком, после его удаления граф распадается на две компоненты связности. 
Остовом или каркасом графа G называется подграф G , содержащий те же вершины, что и G, но не имеющий циклов. Вообще говоря 
С   - лес, который на любой связной компоненте графа G образует дерево. Если G - связный граф, то остов G   является деревом, которое будем называть остовным деревом графа G. 
Граф может иметь несколько остовов. 
Обратим    внимание,    что   все   остовы   одного   графа   имеют одинаковое    чило   рёбер,    но    их   вес  не    является    Величиной постоянной для данного графа,  зависит от весов выбранных ребер. 

Жадный алгоритм 
Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей. 
Один из эффективных способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма». 
 
Жадный алгоритм: 

1. Необходимо упорядочить множество весов

2. выбрать ребро наименьшего веса и инцидентные ему вершины и включит их в остовное дерево.

3. Исключить выбранное ребро из списка рёбер

4. повторяем шаг 2 и3 пока не построим все вершины

5. посчитать все полученного остовного дерева.

 
Алгоритм Прима 
Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей. 
Один из эффективных способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма». 
Алгоритм Прима или, как его ещё называют, алгоритм ближайшего соседа. 
Анализируем матрицу весов. Начинаем с произвольной вершины vi 
Шаг 1. Изучая i-ю строку матрицы весов, выбираем ребро, инцидентное vi и имеющее наименьший вес. Выбранное ребро (vi  
vj 
- первое ребро остова. Удаляем его из матрицы весов.