Лекции по "Дискретная математика"

39. (Теор. Шеннона 2) Любая булева функция f(x1,x2,…, xn) представима в виде разложения Шеннона: f(x1,x2,…xk,xk+1,…xn)= ( ⋁ f(,,…,xk+1,..xn)). В предельном случае когда k=n, для булевой функции f(x1,x2,…xn)≠0, получаем в виде СДНФ: f(x1,x2,…xn)=(). Аналогично для булевой функции f(x1,x2,xn) ≠1, получаем её представление в виде СКНФ: f(x1,x2,…xn)=().

40. Различают несколько способов задания ФАЛ, основными из которых являются: табличный, аналитический, координатный, графический, цифровой. При табличном способе ФАЛ задается таблицей истинности , в которой указывается, какое из двух возможных значений «0» или «1» принимает функция на каждом наборе аргументов: Аналитический способ предусматривает задание функции в виде формализированного выражения, составленного с использованием математического аппарата АЛ, например: y1=˅a; y2=(˅b)∙(b˅). Координатный способ предусматривает задание ФАЛ в виде координатных карт состояний, называемых картами Карно. При наличии n переменных карты Карно состоят из 2ⁿ полей и представляют собой прямоугольные таблицы, на пересечении строк и столбцов которых записывают значение функции при соответствующем наборе аргументов . При составлении карты необходимо, чтобы наборы аргументов в соседних полях (клетках) отличались только значением одной переменной. Графический метод предусматривает задание ФАЛ в виде единичного n–мерного куба, вершинам которого соответствуют различные наборы значений аргументов. В каждой вершине указываются значения принимаемые ФАЛ на данном наборе. При цифровом способе, ФАЛ записывается в виде совокупности наборов аргументов, на которых она принимает истинное значение.

41. Пусть G = (M,R) — неорграф, имеющий п вершин, m ребер и с компонент связности, Т — остов графа G.  T имеет v*(G) = n- с ребер u1,.., un-c, которые называются ветвями остова T. Оставшиеся m-n + с ребер v1,v2…,vm-n+c, не входящие в Т, называется хордами остова Т. Если к лесу Т добавить произвольную хорду vi, то в полученном графе найдется ровно 1 цикл, который обозначим через Сi. Цикл Ci состоит из хорды vi и некоторых ветвей остова Т, которые принадлежат единственной простой цепи, соединяющей вершины хорды vi. Цикл Ci называется фундаментальным циклом, графа G относительно хорды vi остова Т. Множество {С1,..., Cm-n+c} всех фундаментальных циклов относительно хорд остова T называется фундаментальным множеством циклов графа G относительно острова T. Мощность фундаментального множества циклов равна  цикломатическому числу v(G)= m-n+c. Обозначим через (w1,w2.wn) последовательность  (v1,v2,vm-n+c,u1,u2,un-c)  всех ребер G. Фундаментальному циклу Ci соотв. вектор  =(ai1.aim) определенный по правилу aij=

42.  Граф может быть задан  разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание  графа  с помощью  матрицы. Пусть  некоторый  граф  G имеет n вершин p1,p2…pn   и  m ребер a1,a2,..am . Построим   матрицу,   имеющую n строк и m столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец – ребру графа. В столбце aj все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги aj , ставят число +1, а в строке, соответствующей конечной вершине, - число  –1.Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра aj, ставят 1, а в остальных строках – 0. Построенные матрицы называются матрицами  инциденций  графа.

44. Формула включения-исключения — комбинаторная формула, выражающая мощность объединения конечных множеств через мощности и мощности всех их возможных пересечений. Случай для двух множеств (A,B). Для случая из двух множеств  формула включения-исключения имеет следующий вид: │AUB│=│A│+│B│-│A∩B│В силу того, что в сумме │A│+│B│ элементы пересечения  A∩B учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера—Венна для двух множеств, приведенной на рисунке справа. Для случая с большим количеством рассматриваемых множеств  n  процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного.

45. Композицией бинарных отношений G1 и G2. Заданных на множестве A, называют отношение G=G1○G2 такое, что a(aA), b(bA) :((a,b) G(c A) : (a,c) G1(c,b)G2) Если во множестве А имеется элемент с, через который осуществляется связь между элементами a и b в композиции отношений G=G1○G2, то элемент c будем называть элементом посредником, а саму связь между a и b – опосредованной связью.   Свойства: Рефлексивность x M(xRx); Антирефлексивность (xRx); Симметричность x, y M(xRyyRx); Антисимметричность x, y M (xRyyRxx=y);  Транзитивность x,y,z M(xRyyRzxRz); Асимметричность x, y M(xRy(yRx)). Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

46. Граф H=(V',U'), полученный в результате операций удаления вершин и (или) ребер графа G=(V,U), называется частью (иногда подграфом) графа G.Граф называется деревом, если он является связным и не имеет циклов.Граф, все компоненты связности которого являются деревьями, называется лесом.Пусть G — произвольный (n, m)-граф с k компонентами связности. Если G — не лес, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф G, называется остовом графа G.

48. Комбинаторика изучает количество комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества.  Правило суммы. Если некоторый объект A может быть выбран из совокупности объектов m  способами, а другой объект  B может быть n способами, то выбрать либо A , либо  B можно m+n способами Если |A|=m, |B|=n, то |A B|=m+n-|AB|, и |A B|=m+n когда AB=    . Правило произведения. Если некоторый объект A может быть выбран из совокупности объектов  m способами и после каждого такого выбора другой объект B может быть выбран n способами, то пара объектов  (A,B) в указанном порядке может быть выбрана m·n способами. Если |A|=m |B|=n, то |A×B|=m∙n