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



Pdf көрінісі
бет4/13
Дата08.02.2022
өлшемі1,03 Mb.
#98807
1   2   3   4   5   6   7   8   9   ...   13
Байланысты:
vm 14

 
Анықтама.
 
Р
қатынасының анықталу облысы деп (белгіленуі 
D
P

D
P
={x| 
(
x,y
)

P
қандай да бір y үшін} жиыны айтылады; мәндерінің жиыны деп 
(белгіленуі 
E
P

E
P
={
y
| (
x,y
)

P
қандай да бір x үшін} жиыны айтылады (яғни 
D
P

бұл 
Р
жұбының бірінші координаталар жиыны
, E
P
– екінші).
Қатынасты элементтерін тізу арқылы, сипаттаушы қасиеттері арқылы, 
графиктік түрде, матрица көмегімен беруге болады. 
Ақырлы жиындарда бинарлы, матрицамен, графиктік түрде береді.
Анықтама.
 
A
={
a
1
,a
2
,…,a
m
}, 
B
={
b
1
,b
2
,…,b
n
} және 
P

A×B
болсын. Егер 
1
0
i
j
ij
i
j
,егер(a ,b )
P
p
,егер(a ,b )
P


 


,
i
=1,2,…
m
; =1,2,…
n
болса, 
онда 
m×n
өлшемді [
P
] =(
p
ij
) матрицасы 
Р 
қатынасының матрицасы деп аталады.
 
Мысалы 1.2.1

A
1
={
a;b
}, 
A
2
={3;4;5}. Қатынасты жұптарының тізімімен 
берілуі:
P
1
={(
a,a
),(
а,b
)}

2
1
A
, P
2
={(
a
,3),(
a
,4),(
b
;3),(
a
,5)}

A
1
×A
2
; матрицамен 
берілуі:
 







0
0
1
1
1
P

 







0
0
1
1
1
1
2
P
; графиктік түрде берілуі: 
1.2.1 сурет 
Анықтама. 
P

A×B, P
={(
a,b
)|
a

A, b

B
} болсын. 
а) 
P
-
1

Р
–ға кері 

P
-1
= {(
b,a
)|(
a,b
)

P
}, 
P
-1

 B×A

б) 
P
– 
P
-ның толықтауышы 

P
={(
a,b
)|(
a,b
)

P
}, 
P

A×B



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
-рефлексивті 

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}, 

= {(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   2   3   4   5   6   7   8   9   ...   13




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет