Дискретна математика Бележки по лекция (Описание на основните понятия и методи за решаване на дискретни задачи
За графично изпълнение на композицията и двете кореспонденции са изобразени в един чертеж, като се подравнява зоната на пристигане на първия мач с зоната на заминаване на втория мач. На графичното изображение на композицията стрелките свързват тези и само онези точки xÎ и zÎZ, които в комбинирания чертеж на оригиналните съответствия са свързани поне с един път, идващ от х в z.
За да намерим състава на съответствията с помощта на матрици, ние въвеждаме концепцията максимин продукт матрици. Максималното произведение на матриците се намира подобно на обичайното произведение на матриците, но вместо да се умножават елементите на матриците, се използва операцията за избор на минимум от два елемента и вместо сумиране на произведенията на съответните елементи, операцията на избора на максимума от минималните елементи се извършва. За да изчислите елемента sik в пресечната точка на i-тия ред и k-тата колона на получената матрица, трябва да вземете i-тия ред на първата матрица и да я умножите максимално към k-тата колона на втората матрица, използвайки формулата
където qij е елемент в пресечната точка на i-тия ред и j-тата колона на първата матрица, а pjk е елемент на пресечната точка на j-тия ред и k-тата колона на втората матрица.
Ако матриците се състоят, както в нашия случай, само от нули и единици, тогава се извиква произведението максимин булев (кръстен на известния английски математик, един от основателите на математическата логика, Джордж Бул). В този случай формулата (1.2) е опростена, тъй като ако факторите могат да бъдат само нули и единици, тогава, както е лесно да се види, минимумът от тях е равен на техния произход и формула (1.2) приема формата
От формули (1.2) и (1.3) следва, че sik = 1, ако и само ако i-тият ред на първата матрица съдържа поне една единица в този ред на същото място (j) като единицата в колона на втората матрица . Сравнението на този резултат с дефиницията на състава на съответствията показва, че ако умножените матрици описват някои съответствия, тогава техният булев продукт описва състава на тези съответствия.
Помислете за същите съвпадения, които са използвани в предишния пример, за да намерите композицията графично.
.
Елементът s11, стоящ в пресечната точка на първия ред и първата колона на матрицата M (Q ° P), се получава чрез умножаване на съответните елементи от първия ред на матрицата M (Q) и първата колона на матрица M (P), след което от получените продукти се избира максимумът: s11 = max (0 × 1, 1 × 0, 1 × 1) = 1. По същия начин се изчисляват и останалите елементи.
Сравнението на матрицата M (Q ° P) с графичното изображение на композицията Q ° P в чертежа от предишния пример показва, че както би могло да се очаква, резултатът е същият.
Нека се даде кореспонденция, където ГÍX'Y.
Тази кореспонденция се нарича картографиране задайте X, ако домейнът на тази кореспонденция съвпада с домейна на заминаване, т.е. Pr1Г = X. Ако в този случай диапазонът от стойности на съответствието съвпада с региона на неговото пристигане (Pr2Г = Y), тогава казваме, че има картографиране на множеството X На Y, ако диапазонът от стойности не съвпада с Y (Pr22ÌY), тогава преобразуването X в Y.