Графтар теориясының элементтері

10 
в) I – 
А
жиынындағы тепе-теңдік қатынас (белгіленуі id
A
).
 I
={(
a,a
)|
a

A
}, 
I

A
2
(
A
2
–дегі диагональ деп те атайды, себебі оның матрицасы бірлік матрица 
болады); 
г) 
U
– универсалды қатынас 

U
={(
a,b
)|
a

A
и 
b

A
}, яғни 
U=A
2
. 
Анықтама
.
 
P
1
 

A×B
және 
P
2
 

B×C
бинарлы қатынастардың 
композициясы (көбейтіндісі) (белгіленуі 
P
1

P
2
) деп 
Р=P
1

P
2
= {(
a,c)|a

A
, 
c

C
және 

b

B
: (
a,b)

 P
1
және (
b,c) 

 P
2
} қатынасы айтылады. 
1.2.2 сурет 
Мысалы 1.2.2
-
A
={1,2,3}, 
B
={
x,y
}; 
C
={ 
a, b, c, d
}. 
P
1
={(1,
x
),(1,
y
),(3,
x
)}, 
P
2
={(
x,a
),(
x,b
),(
y,c
),(
y,d
)} болсын, онда 
P
1

P
2
={(1,
a
),(1,
b
),(1
,c
),(1,
d
),(3,
a
),(3,
b
)}.
Мысалы 1.2.3
- 
P
1
={(
x,x
+2)|
x

Z
+
}, 
P
2
={(
x,x
2
)|
x

Z
+
}, онда
P
1

P
2
={(
x,(x
+2)
2
)| 
x

Z
+
},
P
2

P
1
={(
x,x
2
+2)| 
x

Z
+
}. 
Теорема. 
P, Q, R
бинарлы қатынастары үшін келесі қасиеттер орынды: 
а) (
P
-1
)
-1
=P
; 
б) (
P

Q
)
-1
=
Q
-1

P
-1
; 
в) (
P

Q
) 

R
=
P

(
Q

R
). 
 
Бинарлы қатынастардың матрицаларының негізгі қасиеттері.
1.
P,Q 

A×B
, [
P
]=(
p
i
,j
), [
Q
]=(
q
i,j
) болсын. 
[
P

Q
]=(
p
ij
+q
ij
)=[
P
]+[
Q
], мұндағы матрицаның элементтері қосылады: 0+0=0, 
1+0=0+1=1+1=1;
[
P

Q
]=(
p
ij*
q
ij
)=[
P
]*[
Q
], мұндағы матрицаның элементтері келесі жолмен 
көбейтіледі: 0*0=0*1=0*1=0, 1*1=1. 
2.
 
Егер 
P

A×B
, 
Q

B×C
, онда [
P

Q
]=
   
Q
P

- кәдімгі матрицаларды 
көбейту, бірақ [
P
] және [
Q
] матрицаларының элементтері 1 қасиеттегі ереже 
бойынша қосылып, көбейтіледі). 
3. Егер 
P
-1
–
P
-ға кері, то [
P
-1
]=[
P
]
T
. 
4.

P

Q
және [
P
]=(
p
ij
), [
Q
]=(
q
ij
), онда 
p
ij
≤q
ij
. 
 
5.

I
–тепе-теңдік қатынас, онда 
 
E
I

- бірлік матрица. 
6. 
P
- 
Р-
ның толықтауышы, онда [
P
] - 
Р 
қатынасының матрицасына тең, 
тек нолдер бірлермен, бірлер нолдермен айырбасталған. 
Мысалы 1.2.4
–
P
және 
Q
қатынастарының матрицалары мына түрде 
болсын
 

11 
 







1
0
0
1
P
, 
 







1
0
1
0
Q
, ондаа 

    
























1
0
1
1
1
0
1
0
1
0
0
1
Q
P
Q
P
;

    
























1
0
0
0
1
0
1
0
1
0
0
1
Q
P
Q
P
; 

    























1
0
1
0
1
0
1
0
1
0
0
1
Q
P
Q
P

. 
Қатынас қасиеттері. 
P

A
2
болсын. 
Р
қатынасы 
а) рефлексивті 


a

A
, (
a,a
)

P
; 
б) симметриялы 

(
a,b
)

P
,

(
b,a
)

P
; 
в) антисимметриялы 

(
a,b
)

P
и (
b,a
)

P

a=b
; 
г) транзитивті

(
a,b
)

P
и (
b,с
)

P

(
a,c
)

P 
деп аталады. 
Айта кетелік, егер 
а) 
P
-рефлексивті 

I

P
, [
P
]= 





















1
1
1




; 
б) 
P
– симметриялы 

P
=
P
-1
, [
P
]=[
P
]
T
; 
в) 
Р
-антисимметриялы 

Р

Р
-1 

I
, [
P

P
-1
]=[
P
]*[
P
-1
], соңғы матрицаның 
бас диагоналінен өзге жердегі элементтері нолге тең; 
г) 
P
- транзитивті 

P

P

P
, яғни егер [
P

P
]=(
a
ij
), [
P
]=(
p
ij
), онда 
a
ij
≤p
ij
. 
Мысалы 1.2.5
-
А
= {1,2,3}, 
P 
= {(1,2),(2,3),(3,2)}, [
P
]=










0
1
0
1
0
0
0
1
0
: 
а) 
P
рефлексивті емес, себебі бас диагоналінде бірлер жоқ;
б) 
P
симметриялы емес, себебі 1; 2)

P
→(2;1)

P
немесе [
P
]≠[
P
]
T
;
в) 
P
антисимметриялы емес, себебі (2;3)

P
, (3;2)

P
→2≠3 немесе
   
























0
1
0
1
0
1
0
0
0
0
1
0
1
0
0
0
1
0
T
P
P










0
1
0
1
0
0
0
0
0
матрицасының бас диагоналінен 
өзге жердегі элементтерінің бәрі нолге тең емес; 
г) 
P
транзитивті емес, себебі мысалы, (1,2)

P,
(2,3)

P
, бірақ (1,3)

P
немесе
[
P

Р
]=
   
P
P

= 










0
1
0
1
0
0
0
1
0











0
1
0
1
0
0
0
1
0
=










1
0
0
0
1
0
1
0
0
, [
P

P
]=(
a
ij
), [
P
]=(
p
ij
), барлық 
элементтерге 
a
ij
≤p
ij
орындалмайды, мысалы,
13
13
p
a

(
1
13

a
, 
0
13

p
). 

жүктеу/скачать 1,03 Mb.

Достарыңызбен бөлісу: