“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti

 12. Distributivlik qonuni 

)

z

x

(

&

)

y

x

(

z

y

x

 va

,

x

x

x

 

,

x

x

1

 

,

A

1

1

 

,

A

A 1

 и 

(

)

A A

B

A

 teng  kuchlilik  formulalaridan  foydalanib 

KNSh  yozing  vf rele kontakt  sxemasini  chizing: 

1)

;

x

x

x

)

x~

(

f

3

2

1

3

2)

;

x

x

x

x

x

x

)

x~

(

f

3

2

3

2

2

1

3

 

31 

 

3)

;

x

x

x

x

x

)

x~

(

f

3

2

3

2

1

3

4)

;

x

x

x

x

x

)

x~

(

f

3

2

1

2

1

3

 

5)

;

x

x

x

x

x

)

x~

(

f

3

2

2

2

1

3

 

 

 

 

 

4-§. Graflar nazariyasining  elementlari 

                         4.1.Graflar  va orgraflar.Asosiy  tushunchalar. 

    Graflar 

nazariyasi 

bu 

diskret 

matematikaning 

iqtisod,sotsiologiya,texnika  programmalashtirishning  turli  sohalarida  juda 

ko’p  qo’llaniladigan  bo’limidir.  Chunki  maxsus  termin  va    belgilashlar 

tizimi  murakkab  va  nozik  jarayonlarni  modellashtirish  imkonini 

beradi.Bundan 

tashqari 

graflar 

o’rganilayotganob’ektni  geometrik 

tasvirlashga  qulay.  Masalan,to’plamlar  nazariyasida  binar  munosabatlarni 

graflar bilan ko’rsatish mumkin. 

     Graflar  nazariyasi  turli  avtorlar  tomonidan  bir  necha  bor  “kashf” 

etilgan. 

   Lekin  shuni  aytish  mumkinki,  graflar  nazariyasi    1736  yilda  mashxur 

matematik  Leonard  Eyler  tomonidan  kyoningsberg  ko’priklari  haqidagi 

masalani 

yechganidan 

boshlanadi. 

Leonard 

Eyler 

(1707-1783)-

Shveytsariyada tug’ilgan,lekin  Rossiyada yashagan  va ishlagan.  

     Ta’rif:  Bo’sh  bo’lmagan,uchlar  deb  ataluvchi  V  to’plamdan  va  qirralar 

deb  ataluvchi  V  to’plamning  ikki  elementli  qism  to’plamlaridan  iborat  E 

no’plamlar juftlgi G=G(V, E)  graf deyiladi. 

   Agar (v

i

, v

j

) E bo’lsa, V to’plamning   v

i

 va v

j

 uchlari  (v

i

, v

j

) qirra bilan 

birlashtirilgan  yoki   (v

i

, v

j

) qirraga insindent deyiladi. Agar (v

i

, v

j

) – qirra 

bo’lsa, y holda  v

i

 va v

j

  uchlar (v

i

, v

j

)  qirraning oxirlari deyiladi. Bu holda  

(v

i

,  v

j

)    qirra  v

i

  va  v

j 

  uchlarga  insindent  deyiladi.  Bitta  qirraga  insindent  

bo’lgan  uchlar  qo’shni  uchlar  deyiladi.Grafning  bitta  uchiga  insindent 

bo’lgan qirralari qo’shni qirralar deyiladi.     G grafning uchlari soni v va 

qirralari soni – e bilan belgilanadi: 

,

V

v

E

e

. 

    Ta’rif:Agar  G=G(V,  E)  grafda  E  to’plam  elementi  bo’lgan  har  bir 

juftlik  (v

i

,  v

j

)  tartiblashtirilgan  bo’lsa  u  or  graf  deyiladi.Bunda  E  to’plam 

elementlari  yoy  deyiladi.  Agar    (v

i

,  v

j

) E  bo’lsa,    v

i

    uch    (v

i

,  v

j

)  yoyning 

boshi,v

j

  esa oxirgi uchi  deyiladi. 

    Geometrik  graflar quyidagicha  beriladi: 

1)  grafning  uchlari –fazodagi  yoki tekislikdagi  nuqtalar; 

2)  grafning  qirralari – kesma; 

32 

 

3)  orgrafning  yoylari – yonaltirilgan  kesma. 

    Grafning    uchini  o’zi  bilan  bog’kovchi  qirra  yoki  yoy  sirtmoq  deyiladi. 

Agar  grafda  sirtmoq  bo’lsa  u  mul’tigraf  yoki  mul’tiorgraf  deyiladi.  Agar 

grafning qirrasi yoki yoyi belgilangan bo’lsa u belgilangan graf yoki orgraf 

deyiladi. 

Ta’rif:  Agar G=(V,E) grafda    V   V, E   E bo’lsa  G (V , E ) graf qism 

graf  deyiladi.  Agar  G  orgraf  bo’lsa,  G (V ,  E )    qismorgraf  deyiladi.Agar  

V =V  bo’lsa ,  G  graf  asosiy qismgrafi deyiladi. 

    

Misol.Quyida graf berilganbo’lsin. 

 

 

    Ta’rif:Grafning  har  bir  uchi  qirra  bilan  tutashtirilgan  bo’lsa  u  to’la  graf 

deyiladi. Uchlari  ta bo’lgan to’la graf  K

n

 bulan belgilanadi. 

    Ta’rif:Agar  G=G(V,  E)    grafda 

, 

=   va  har  bir  qirra     

(v

i

,  v

j

)  uchun v

i

A и v

j

B bo’lsa  bu graf ikki yoqlama graf deyiladi. Agar 

ikki  yoqlama  grafda 

  va  v

i

A,  v

j

B,  (v

i

,  v

j

) E  bo’lsa  u 

to’la ikkitomonlama  graf deyiladi va  K

m, n

 bilan belgilanadi. 

v

1 

v

2 

v

3 

v

4 

v

5 

e

1 

e

2 

e

3 

e

4 

e

6 

e

5 

G(V, E) –graf 

V= v

1

, v

2

, v

3

, v

4

, v

5

 – uchlar  to’plami, 

E={e

1

, e

2

, e

3

, e

4

, e

5

, e

6

 – qirralar 

to’plami. 

Masalan,  e

2

=(v

2

; v

3

) qirra v

2

 va v

3

 

Uchlarga  insindent.v

2

  vav

3

  qo’shni 

uchlar. 

v

2 

v

3 

Berilgan  grafning  qism 

grafi. 

33 

 

  Misol.  K

2,4

  ikki  tomonlama  to’la  grafni  va  K

4

  to’la  grafni  chizing. 

Полный 

граф 

 

                                    4.2.  Grafkarning  bog’lamliligi. 

     Ta’rif:    Aytaylik  G=G(V,  E)  –  uchlari  v

0

,  v

1

,  v

2

, …, v

n

V  va qirralari 

e

1

,  e

2

,  …,  e

m

E  bo’lgan  graf  (orgraf).  U  holda    e

i

=(v

i-1

,  v

i

)  bolgan  

v

0

e

1

v

1

e

2

v

2

e

3

v

3

…v

k-1

e

k

v

k

  ketma  ketlik      v

0

  dan  v

k

  ga  uzunligi  k  bo’lgan 

marshrut  (yo’l) deyiladi.    

Demak,  uzunligi  k  bo’lgan  marshrutda  k  qirra  qatnashadi.    Yo’l  odatda 

v

0

v

1

v

2

…v

k

 bilan beriladi. 

     Agar  yo’lning  hamma  qirralari  har  xil  bo’lsa  u  zanjir  deyiladi.Agar  

hamma  uchlari  har  xil  bo’lsa  u  oddiy  yo’l  deyiladi.  Yopiq  zanjir  sikl 

dreyiladi.  Yopiq  oddiy  zanjir  oddiy  sikl  deyiladi.  Sikllari  bo’lmagan  graf 

asiklik graf  deyiladi. 

    Xuddi shunga  o’xshash  orgrafda ham  sikl tushunchasi  kiritiladi. 

     Misol.Graf berilgan bo’lsin. 

 

 

 

   Ta’rif:Agar    G=G(V,  E)  grafda  har  qanday  ikki  uchi  zanjir  bilan 

bog’langan  bo’lsa u bog’lamli graf deyiladi.     

   Agar     

s

G

graf      G  orgrafda  yoylarini  qirralar  bilan  almashtirib  hosi l 

qilinsa bu graflar bog’liq graflar deyiladi.  

v

1 

v

2 

v

3 

v

4 

v

5 

v

6 

x

1 

x

2 

x

3 

x

4 

Ikki  tomonlama to’la graf 

K

2,4

        A= v

1

, v

2

 

B= v

3

, v

4

, v

5

, v

6

 

To’la graf K

4

 

v

1 

v

2 

v

3 

v

4 

v

5 

e

1 

e

2 

e

3 

e

4 

e

6 

e

5 

G(V, E) – graf 

v

1

e

1

v

2

e

2

v

3

e

3

v

1

e

1

v

2

e

5

v

5

 yoki v

1

v

2

v

3

v

1

v

2

v

5

 –marshrut 

v

1

v

2

v

3

v

1

v

5

 – zanjir 

v

1

v

3

v

2

v

5

 –oddiy zanjir 

v

1

v

3

v

2

v

5

v

1

 – oddiy  sikl. 

34 

 

   Ta’rif:Agar   

,

s

s

G V E

graf  ,ga  bog’liq  bo’lib  bog’lamli  bo’lsa  , G(V, E) 

orgraf    bog’lamli  deyiladi.Agar  har  qandqay  v

i

  ,v

j

V    uchlar  uchun  ularni 

tutashtiruvchi  yo’l mavjud bo’lsa, orgraf kuchli bog’lamli deyiladi. 

 

                               4.3.Graflarning  izomorfizmi. 

    Ta’rif: Agar f: V

V

1

 va f: E

 E

1

 o’zaro bir qiymatli mosliklar bo’lsa , 

f:  G(V,  E) 

  G

1

(V

1

,  E

1

)    funksiya  izomorfizm  deyiladi  va  G G

1 

bilan 

belgilanadi.Agar  f:G

G

1

  –  izomorfizm  bo’lsa  ,  G  va  G

1

  izomorf  graflar 

deyiladi. 

Misol.Agar  G

1

(V

1

;  E

1

)  belgilangan  graf  bo’lsa,  unga  izomorf  graflarni 

quring. 

    

 

 

Yechish.

 

     

 

    Teorema .Graflarning  izomorfligi  ekvivalentlikdir.   

    Isboti.  Haqiqatan,Izomorfizm  ekvivalentlikning  barcha xossalariga ega: 

v

3 

v

4 

v

6 

v

1 

v

2 

v

5 

G

1

(V

1

; E

1

) - graf 

u

1 

u

2 

u

3 

u

4 

u

5 

u

6 

x

1 

x

2 

x

3 

x

4 

x

5 

x

6 

G

2

(V

2

; E

2

) –graf 

izomorfizm  f : G

1

G

2

 

   f (v

1

)=u

1

          f (v

4

)=u

4

       f (v

1

; 

v

2

)

(u

1

; u

2

) 

   f (v

2

)=u

2

          f (v

5

)=u

5

             и т.д. 

   f (v

3

)=u

3

          f (v

6

)=u

6

 

G

3

(V

3

; E

3

) –graf 

Izomorfizm  g : G

1

G

3

 

   g (v

1

)=x

1

          g (v

4

)=x

4

       g (v

1

; 

v

2

)

(x

1

; x

2

) 

   g (v

2

)=x

2

          g (v

5

)=x

5

           

   g (v

3

)=x

3

          g (v

6

)=x

6

 

35 

 

Refleksivlik.   G   G  bo’lsa ,izlanayotgan  biyeksiya  aynan  1 funksiyadir  ; 

Simmetriklik.     Agar  G

1

 

  G

2

    h  biyeksiya  bo’lsa  ,  G

2

    G

1

  h

  1 

biyeksiyadir;  Tranzitivlik.     Agar  G

1

    G

2

    h  biyeksiya  va  G

2

    G

3

  g 

bieksiya bo’lsa,  G

1

   G

3

  g  h  bieksiyadir. 

 

                                    4. 4. Graf uchlarining  darajasi. 

 

   Ta’rif:  Grafning  v  uchiga  insindent  bo’lgan  qirralari  soni  shu  uchining 

darajasi  deyiladi  va  d(v)  bilan  belgilanadi.Agar  graf  uchining  darajasi  0 

bo’lsa u yakkalangan,1  bo’lsa osilgan uch deyiladi.     

   Ta’rif:  Orgrafning  v  uchi  boshbo’lgan  yoylar  soni  shu  uchning  chiqish 

yarim  darajasi  deyiladi  va 

d

v

bilan  belgilanadi.  Orgrafning  v  uchida 

tugallangan    yoylar  soni  shu  uchning  kirish  yarim  darajasi  deyiladi  va 

d

v

bilan  belgilanadi.    Agar    bo’lsa 

0

d

v

,  greafning  v  uci  chashma 

deyiladi.Agar 

0

d

v

 bo’lsa ,grafning  v uchi   oqova deyiladi. 

    Teorema.(Eyler)  Grafning  uchlaruni  darajalari  yig’indisi  qirralar  sonini 

ikkilanganiga  teng  : 

2

v V

d v

e

. 

    Isboti:  Grafning  uchlaruni  darajalari  yig’indisi  hisoblanganida  har  bir 

qirra  ikki  marta  hiisobga  olinadi:qirraning    bosh  nuqtasini  va  oxirini 

darajasi hisoblanganida.   

1- natija.Toq darajali uchlarning  soni juft. 

    Isboti.Eyler  teoremasiga  ko’ra  barcha  uchlar  darajalarining  yig’indisi 

juft  son.Juft  darajali  uchlarning  darajalari  yig’indisi  ham  juft.Demak  toq 

darajali  uchlar  darajalarining  yig’indisi  juft  son  ,yani  bunday  uchlar  soni 

juft. 

    2-natija .Orgrafning  uclarini yarim darajalari yig’indisi yoylar sonini 

ikkilanganiga  teng: 

2

v V

v V

d

v

d

v

e

. 

    Isboti.Agar  orgrafning  yoylarini  yo’nalishini  hisobga  olmasak  Eyler 

teoremasidan  kelib chiqadi. 

  Misol.Berilgan grafni uchlarini  darajasini toping.  

36 

 

     Misol.Orgrafning  uchlarini  kirish  va  chiqish  yarim  darajalarini  toping. 

 

   Ta’rif:Uchlari  n  ta  bo’lgan  G  orgrafning    uchlarining  qo’shnilik 

matritsasi  deb    n  –tartibli    shunday  A= a

ij

    kvadrat  matritsani  aytiladiki, 

uning  elementlari  a

ij

    orgrafning  i-  uchidan  j-uchiga  yo’nalgan  yoylar 

soniga teng.  Agar orgrafning  yoylari bir karrali bo’lsa u 0 yoki 1 ga teng. 

    Uchlari n ta bo’lgan  G grafning   uchlarining  qo’shnilik matritsasi deb   

n  –tartibli    shunday  A= a

ij

   kvadrat matritsani aytiladiki, uning elementlari 

a

ij

    grafning  i-  uchidan  j-uchiga  yo’nalgan  qirralar  soniga  teng.  Agar 

grafning  yoylari  bir  karrali  bo’lsa  u  0  yoki  1  ga  teng.Grafning    (v

i

,  v

j

) 

qirrasi  bilan  birga  (v

j

,  v

i

)  qirrasi  mavjud  bo'lgani  uchun  uning  qo'shnilik 

matritsasi simmetrik  bo'ladi.   

Ta’rif:  Yoylari  m  ta  bo’lgan  G  orgrafning    yoylarining  qo’shnilik 

matritsasi  deb    m  –tartibli    shunday  B= b

ij

  kvadrat  matritsani  aytiladiki, 

uning  elementlari  b

ij

  orgrafning  i-  yoyi    j-yoydan  oldin  kelsa  1  ga  teng  va 

boshqa hollarda 0 ga teng. 

   Qirraqlari m ta bo’lgan G grafning  qirralarining qo’shnilik matritsasi deb  

m  –tartibli    shunday  B= b

ij

  kvadrat  matritsani  aytiladiki,  uning elementlari 

b

ij

  grafning  i-  qirrasi  va      j-qirrasi  umumiy  uchga  ega  bo’lsa  1  ga  teng  va 

boshqa hollarda 0 ga teng. 

Ta’rif:  Uchlari  n  ta  va  qirraqlari  m  ta  bo’lgan  G  grafning  insindentlik 

matrtsasi  deb 

m

n

  o’lchovli  shunday         

]

[

ij

c

C

          matritsani  aytiladiki, 

v

1 

v

2 

v

3 

v

4 

v

5 

e

1 

e

2 

e

3 

e

4 

e

5 

e

5 

G(V, E) – graf 

d(v

1

)=4          d(v

4

)=1 

d(v

2

)=3          d(v

5

)=2 

d(v

3

)=2 

 

 v

4

 – osilib qolgan uchi 

v

1

 

v

2

 

v

3

 

v

4

 

v

5

 

d  (v

1

)=1        d  (v

3

)=1         d  (v

5

)=0 

d 

+

(v

1

)=1        d 

+

(v

3

)=2         d 

+

(v

5

)=2 

 

d  (v

2

)=2        d  (v

4

)=2 

d 

+

(v

2

)=1        d 

+

(v

4

)=0 

 v

4

 – chashma, v

5

 –oqova 

37 

 

uning 

ij

c

elementi 

i

v

uch   

j

e

  qirraga  insindent  bo’lsa  1  ga  teng  va  qolgan 

hollarda 0 ga teng.    

     Uchlari  n  ta  va  yoylari  m  ta  bo’lgan  G  orgrafning  insindentlik matrtsasi 

deb 

m

n

  o’lchovli  shunday         

]

[

ij

c

C

          matritsani  aytiladiki,  uning 

ij

c

elementi 

i

v

uch   

j

e

  yoyning  boshi  bo’lsa  1  ga  teng, 

i

v

uch   

j

e

  yoyning 

oxiri bo’lsa -1 ga teng va qolgan hollarda 0 ga teng.   

    Agar  grafning  har  bir  qirrasiga  biror  son  bog’langan  bo’lsa  u  son 

qirraning  vazni  deyiladi,graf  esa  vaznlashtirilgan  deyiladi. Vaznlashtirilgan 

graf  o’zining  vaznlari  matritsasi   

ij

  bilan  berilishi  mumkin,  bunda 

ij

                (v

i

  ,v

j

  )  qirraning  vazni.    Mavjud  bo’lmagan  qirralarning  vazni 

masalaning  qo’yilishiga qarab 0 yoki cheksizlik hisoblanadi.