Теория графов и комбинаторика

являются упорздочанные П -ки (кортежи дашы Ю) J , где di^Ai, C.= i,i^ . Заметим, что о.тарацкя "х" не ассоциа­ тивна: СД«6)^<7 -/1 ) , Справедавц оледу»1!!па' простейшие отзойотва: (АП&) х (С{1])) х = ( A xC ) a ( 6 xD) ; (АПе , ) хС = СА>^С)Па^С);С4с^6)'<С - =M^C)u(&xC)j(y\ue>)>?({?yJ)) =(A><C)u(&><C)tJ(AyD)uC&^x>). Декартово произведет1в А^Ах-'^ А =Л'' называется И-й отопенью множеотва Л : Д"=И''*'Д. В ч'эсткооти, / 4^ - декартов каадраг мно- жao:Ja Д . Принято считать, что А -0 1 /4 = '1. Б'тначныв о.тноипния. Еквяяалгентнооть. Порядок Бинарным отношвнизм на множеотна А каанвоатся признак Рч , связывающий пары элементо!' изД ?''nirobii.R^ означает ,•что эле­ мент (L связан признаком !ч с элементом i . Воэможеп другой подход к понятии di!uapnoro 0ТЕ01квИ1!.ч. ?аоомотхл!м упорядоченные аарн эле­ ментов, oi-язaкнI^:^ привпакои Р, , Они образуй", лоджонеотво i\3 А^ , itOTQpoe таю;10 оСозкач'лм мерез Л. : = О'юпидко, маокастБО Rc/^^ однозначно опредвлявтся признаком R . Поэтог.д' под бкнаржм отношением R, на unostGCTBa А моиго ионнмагг) любое поднояестло тлкокеотаа Л^. . Таким образом, заяисъСй.;<;^6 Л экви- вaл0ETJ.a Бапкси . Расоыотрпм нбкоторио основш^е овойсгла бинарных отновюнай. Отношение R, на множеотвоД называется: - ра|)локоив!шм, 0ОЛИ У л £ А л. !ч d , т,,е. Vo-fiA (djCjeji.; - ощ«0тричным, если т . е . =^(^,<г)еЯ ; ~ г,нтЕош.штр11чным, eo,ira ) , т . е . \/a.,i6A(са.,0е(1. =?>а.=^); • - тракзнтяв1шм, еслк Угг,^,с S'Atofc^^ifA.C =ФлЯс), т . е . ~ овязным, e c n n V " , т . е . \lCL,^ € ( - антар91|и1еко'лв!"1л, еоли VCL €A 1 й.(1.й., т.a. l/a-^A (й.,Л)^11_ 1Ъедставл0нив о бинершх отношениях, как о подмножаотвах Я с Д , позволяет выложить теоратико-множэотзбнные опорацпи над ниш, т . е . определить алгейру бинарних отношашгй. , Бинарное отношение R на Д называется отнош0ш!ем экзизалант- яооти (эквивалентностью), если оно.рефлвкойзнЬ, олштвтричко и траизитивно. Эквивалентностью является, например, отношёниа ра-