Графтар теориясының элементтері
А/Е фактор –жиыны А болып табылады. Керісінше, егер
жүктеу/скачать 1,03 Mb. Pdf көрінісі
|
vm 14
| .
А/Е фактор –жиыны А болып табылады. Керісінше, егер А ={ A i } А жиынының қандай да бір бөлікшесі болса, онда оған қандай да бір Е эквиваленттілік қатынасы сәйкес келеді : xEy x,y A i қандай да бір i үшін. Сонымен, А жиынының барлық бөлікшелер жиыны мен А жиынының барлық эквиваленттілік қатынасы жиыны арасында өзара бірмәнді сәйкестік табылады. Мысалы 1.3.2 - А ={1,2,3,4}. А={{1},{2,3,4}}={ A 1 ,A 2 } – А бөлікшесі. E ={( x;y )| x,y A i ,i=1,2}={(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,2),(4,3),(4,4)} - берілген бөлікшеге сәйкес эквиваленттілік қатынасы. Мысалы 1.3.3 - A ={1,2,3,4,5,6}, P A 2 , P ={(1;1); (2;2);(3;3);(4;4); (5;5); (6;6); (1;2); (1;4);(2;1);(2;4);(3;5);(5;3);(4;1);(4;2)}. Берілген қатынастың эквиваленттілік қатынас болатындығын көрсетеміз. 13 Оның матрицасы бойынша [ P ]= 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 P рефлексивті, симметриялы, транзитивті екндігін анықтаймыз, олай болса Р – А жиынындағы эквиваленттілік қатынасы. Эквиваленттілік классы және фактор – жиынды құрамыз: [1] P ={x|(x;1) P}={1,2,4}; [2] P ={x|(x;2) P}={1,2,4}; [3] P ={x|(x;3) P}={3,5}; [4] P ={x|(x;4) P}={1,2,4}; [5] P ={x|(x;5) P}={3,5}; [6] P ={x|(x;6) P}={6}. Сонымен, тек үш эквиваленттілік классы бар [1]=[2]=[4]={1,2,4}, [3]=[5]={3,5}, [6]={6}. Фактор – жиын A/Р = {[1],[3],[6]}={{1,2,4},{3,5},{6}} – берілген эквиваленттілік қатынасына сәйкес А жиынының бөлікшесі болады. Реттік қатынасы. Анықтама . Егер Р қатынасы А жиынында антисимметриялы және транзитивті болса, онда ол реттік қатынасы деп аталады. Жиі белгіленуі . Егер сонымен қатар ол 1) рефлексивті болса, онда ол дербес немесе қатаң емес реттік қатынас делінеді (≤); 2) антирефлексивті болса, онда ол қатаң емес реттік қатынасделінеді (<). Анықтама . А жиынында реттік қатынасы берілген болсын. Егер осы жиынның кез келген a және b элементтері үшін a b немесе b a орындалса, онда элементтер салыстырмалы деп аталынады, қарсы жағдайда – салыстырмалы емес. Анықтама . Егер А жиынының кез келген екі элементі салыстырмалы болса, онда осы жиындағы дербес реттелген қатынас сызықты немесе шынжыр деп аталады. Дербес (сызықты) қатынасы анықталған А жиыны дербес реттелген жиын (д.р.ж) делінеді (сызықты реттелген жиын (с.р.ж)). Белгіленуі ( А , ). Мысалы, сызықты реттелген жиындар: N, Z, Q, R, мұнда кәдімгі рет анықталған. Анықтама . Егер А жиынында x ( x>a ) қанағаттандыратын x болмаса, онда осы жиындағы a элементі ең кіші (ең үлкен) делінеді. Егер жиынның кез келген бос емес ішкі жиынының ең кіші элементі бар болса, онда с.р.ж. әбден реттелген жиын (ә.р.ж), Мысалы 1.3.4 - ( N ; ≤) – ә.р.ж. ([0;1]; ≤) – ә.р.ж. емес, себебі мысалы, (0;1] [0;1], бірақ (0;1]-де ең кіші элементі жоқ. |