1. To'plamlar, ularning berilish usullari va ular ustida amallar

Qo`shnilik matritsalari. Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo`shniligi matritsasi tushunchasini qarab chiqamiz.

^{G  (V ,U )} – uchlari soni m ga teng bo`lgan belgilangan, sirtmoqsiz va karrali

qirralarsiz graf bo`lsin.
Elementlari
^aij

^{1, agar}



i va
j uchlar qo'shni bo'lsa,

ko`rinishda aniqlangan

_0, aks holda.
A  (a_ij ) ( ^{i  1,2,..., m} ;

^{j  1,2,..., m} ) matritsani grafning uchlari

qo`shniligi matritsasi deb ataymiz.
Bu ta`rifdan sirtmoqsiz va karrali qirralari bo`lmagan graf uchlari qo`shniligi matritsasining bosh diagonalida faqat nollar bo`lishi, satrlaridagi birlar soni esa mos uchlarning darajalariga tengligi kelib chiqadi.
1- m i s o l . 1- shaklda tasvirlangan grafgning uchlari qo`shniligi matritsasi

ko`rinishda bo`ladi.

 ⁰


 ₁
A  ^{ 1}

_ 1
^{1 1 1}

0 0 1_



1
0 0 ^
1 1 0_

Uchlari soni m ga teng bo`lgan belgilangan oriyentirlangan ^{G  (V ,U )}

grafning uchlari qo`shniligi m  m -matritsasi deb elementlari

^aij
^{1, agar}



(i, j) U
bo'lsa,

_0, aks holda,

ko`rinishda aniqlangan
A  (a_ij ) ( ^{i  1,2,..., m} ,
j  1,2,..., m ) matritsaga aytiladi.

2. 
   m i s o l . 2- shaklda tasvirlangan orgrafning uchlari qo`shniligi matritsasi quyidagicha bo`ladi:
   

 ^{0 1 1}

_ 0 0 0


A  ^ 0 0 0


 ^{1 0 0}

0
_ 1 0
^{0 0}

0 0_


0 0^ .


^{0 1} 

0
1 _

Endi G uchlari
1,2,..., m
bo`lgan belgilangan oriyentirlanmagan multigraf

bo`lsin.
^aij
elementlari G grafning i va j uchlarini tutashtiruvchi qirralar soniga

teng bo`lgan
A  (a_ij )
( ^{i, j  1,2,..., m} ) matritsa oriyentirlanmagan multigrafning

uchlari qo`shniligi matritsasi deb ataladi.

2. 
   m i s o l . 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qo`shniligi matritsasi quyidagicha bo`ladi:
   

 0	1	2	0 
 1 A  ^	1	1	0
 2	1	0	1 
 0 	0	1 0^ 

_.

Karrali yoylari bo`lgan sirtmoqsiz orgraf uchlari qo`shniligi matritsasi

tushunchasini ham yuqoridagiga o`xshash ta`riflash mumkin.
2- t e o r e m a . Graflar faqat va faqat uchlari qo`shniligi matritsalari bir- birlaridan satrlarining o`rinlarini va ustunlarining o`rinlarini mos almashtirishlar yordamida hosil bo`lsagina izomorf bo`lishadi.

43. Yo'naltirilgan graflarda marshrut, zanjir, tsikl

1-ta’rif. Oddiy G  ( X ,U ) grafdagi

x₀ u₁ x₁ u₂
x₂u₃
^x3 ^xl 1 ^ul ^xl

kеtma-kеtlik -bu yеrda
x₀ , x₁ ,...x_l  X ; u₁u₂ ,..., u_l U ) uzunligi l tеng bo`lgan va
x₀ , x₁

uchlarni tutashtiruvchi marshrut dеyiladi.

Agar
x₀  x_l
vа l  1 bo`lsa, marshrut siklik dеyiladi.
l  0
marshrut bitta

uchdan iborat bo`ladi va u siklik hisoblanmaydi.
Marshrutda uchlar va qirralarning har xil bo`lishi talab qilinmaydi. Bitta uch yoki qirra bir nеcha marta takrorlanishi mumkin.

2. 
   ta’rif. Qirralari har xil bo`lgan marshrut zanjir dеb ataladi. Siklik zanjir esa
   

sikl dеyiladi. Agar zanjirda -siklda) x₀ vа x₁ lardan tashqari barcha uchlari har xil
bo`lsa, u holda sodda zanjir -sikl) dеyiladi.

1-shakl.
Yuqoridagi grafda (1-shakl) 3v2u1w3p4t5t4t5 vа 3w1u2v3p4t5t4t5marshrutlar bir xil elеmеntlardan tuzilgan bo`lsada, lеkin xar xildir. Ular siklik emas va zanjir xam emasdir. 3w1u2v3p4 mar0okshrut zanjir, lеkin sodda emas va siklni tashkil etmaydi.3w1u2v3p4s6r7g3 vа 3v2u1w3p4s6r7g3 xar xil sodda bo`lmagan sikllar. 3g7r6s4p3 -marshrut sodda sikldir. 1u3v2 kеtma-kеtlik umuman marshrut emas.

2. 
   ta’rif. Agar G grafning ^x vа y uchlari orasida hеch bo`lmaganda bitta zanjir mavjud bo`lsa, u holda ular tutashtirilgan dеyiladi.
   

Ravshanki, grafning uchlari to`plamida bеrilgan “tutashtirilganlik” munosabati rеflеksivlik, simmеtriklik, tranzitivlik xossalariga ega. Dеmak, bu

munosabat ekvivalеntlikdir va grafning X uchlari to`plamini
X₁ , X ₂ ,..., X _k
sinflarga

ajratadi. Har bir sinfga tеgishli bo`lgan uchlar o`zaro tutashtirilgandir -turli sinflarga tеgishli bo`lgan uchlar orasida zanjirlar yo`q).
Marshrutning uzunligi deb undagi qirralar soniga aytiladi.
Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi. Agar zanjirning chetlaridan tashqari barcha uchlari turlicha bo„lsa, u holda uni oddiy zanjir deb ataydilar.

Berilgan
(v₁,v₂ ,..., v_s )
zanjir yoki oddiy zanjir uchun
v₁  v_s
bo„lsa, u yopiq

zanjir deb ataladi. Hech bo„lmaganda bitta qirraga ega yopiq oddiy zanjir sikl deb ataladi.
Misol. Bu shaklda (1,2,5,1) va (2,3,4,5,2) siklni tashkil qiladi.

44. Qidiruv algoritmlar.

45. Eng qisqa yo'lni topish.
2- m i s o l . 2- shaklda tasvirlangan orgrafda oltita uch (V  {1, 2, 3, 4, 5, 6} ) va o‘n bitta yoy bo‘lib, har bir yoy uzunligi uning yoniga yozilgan. Ko‘rinib turibdiki,

berilgan grafda manfiy uzunlikka ega
(5,3)
yoy ham bor. Isbotlash mumkinki, bu

grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas.
Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni topish bilan shug‘ullanamiz.

Dastlabki qadam. Manbaga (1 belgili uchga) ₁  0
qiymatni mos qo‘yamiz

va R  {1} to‘plamga ega bo‘lamiz. Shuning uchun,
R  V \ R  {2, 3, 4, 5, 6}
bo‘ladi.

Umumiy qadam. 1- iteratsiya.

R  {1} va
R  {2,3,4,5,6}
bo‘lgani uchun

boshlang‘ich uchi R to‘plamga tegishli, oxirgi uchi esa R to‘plam elementi

bo‘lgan barcha yoylar to‘plami
(R, R )  {(1, 2),(1, 3),(1, 4)} ga ega bo‘lamiz.

(R, R )

to‘plamga tegishli bo‘lgan har bir yoy uchun
h_ij ^{ning qiymatlarini topamiz:}

(1, 2)

(1, 3)

(1, 4)
yoy uchun yoy uchun yoy uchun
h₁₂  ₁  c₁₂  0  2  2 ; h₁₃  ₁  c₁₃  0 10  10 ; h₁₄  ₁  c₁₄  0 13  13.

Bu h₁₂ ,
h₁₃ va
^h14
miqdorlar orasida eng kichigi
^h12
bo‘lgani uchun
(1, 2)
yoyni

ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va 2 belgili uchga
₂  2 qiymatni mos qo‘yamiz. Algoritmga ko‘ra 2 uchni R to‘plamdan chiqarib,

R to‘plamga kiritamiz. Natijada ⁶
bo‘lamiz.
R  {1, 2} va
R  {3, 4, 5, 6}
to‘plamlarga ega

Ikkala uchi ham R to‘plamga tegishli bo‘lgan bitta
(1, 2)
yoy bo‘lgani uchun

faqat bitta
₁  c₁₂  ₂
tengsizlikning bajarilishini tekshirish kifoya. Bu tengsizlik

0  2  2 ^{ko‘rinishdagi to‘g‘ri munosabatdan iborat bo‘lgani uchun 2- iteratsiyaga} o‘tamiz.

2. iteratsiya.

(R,R )  {(1, 3),(1, 4),(2, 3),(2, 5)} bo‘lgani sababli
h₁₃  10 ,
h₁₄  13 ,

h₂₃  7 va
h₂₅  11 qiymatlarni va
min{h₁₃ , h₁₄ , h₂₃ , h₂₅}  h₂₃  7
ekanligini aniqlaymiz.

Bu yerda eng kichik qiymat
(2, 3)
yoyga mos keladi. Shuning uchun,
(2, 3)
yoyni

ajratamiz va
₃  7
^qiymatni 3 ^{belgili uchga mos qo‘yamiz.} 3 ^{belgili uchni R}

to‘plamdan chiqarib, R to‘plamga kiritgandan so‘ng to‘plamlar hosil bo‘ladi.
R  {1, 2, 3} va
R  {4, 5, 6}

Ikkala uchi ham R to‘plamga tegishli bo‘lgan uchta
(1, 2) ,
(1, 3)
va (2, 3)

yoylardan birinchisi uchun
₁  c₁₂  ₂
tengsizlikning bajarilishi 1- iteratsiyada

tekshirilganligi va ₁ , ₂
qiymatlarning o‘zgarmaganligi sababli faqat ikkinchi va

uchinchi yoylarga mos
₁  c₁₃  ₃
va  ₂  c₂₃  ₃
munosabatlarni tekshirish kifoya.

Bu munosabatlar
0 10  7 ^va
2  5  7
ko‘rinishda bajariladi. Shuning uchun 3-

iteratsiyaga o‘tamiz.

2. 
   iteratsiya. Boshlang‘ich uchi
   

R  {1, 2, 3}

to‘plamga tegishli, oxiri esa

R  {4, 5, 6} to‘plamga tegishli bo‘lgan yoylar to‘rtta:
^{(1, 4)} ,
^{(2, 5)} ,
(3, 4)
va ^{(3, 5)} .

Shu yoylarga mos
h_ij ^{ning qiymatlari}
h₁₄  13 ,
h₂₅  11,
h₃₄  15 ,
h₃₅  13
va, shuning

uchun,
min{h₁₄ , h₂₅ , h₃₄ , h₃₅}  h₂₅  11
bo‘ladi. Demak, bu iteratsiyada
(2, 5)
yoyni

ajratamiz va ₅  11 deb olamiz. Endi, algoritmga ko‘ra, to‘plamlarni hosil qilamiz.
R  {1, 2, 3, 5} va
R  {4, 6}

Ikkala uchi ham R to‘plamga tegishli bo‘lgan yoylar oltita:
(1, 2) ,
(2, 3) ,

(1, 3) ,
(2, 5) ,
(3, 5)
^{va (5, 3) . Bu yoylarning har biri uchun} _i  c_ij   _j
tengsizlikning

bajarilishini tekshirishimiz kerak. Lekin, 1- va 2- iteratsiyalarda
(1, 2) ,
(2, 3) va

(1, 3)
^{yoylar uchun bu ish bajarilganligi sababli tekshirishni tarkibida} 5 ^{belgili uch}

⁶ Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun R va R
belgilar qoldiriladi.

qatnashgan
(2, 5) ,
(3, 5)
va (5, 3)
yoylar uchun amalga oshirib, quyidagilarga ega

bo‘lamiz:
(2, 5)
yoy uchun
 ₂  c₂₅  ₅
^{munosabat to‘g‘ri (} 2  9 11 ^),
(3, 5)
yoy

uchun
₃  c₃₅  ₅
^{munosabat to‘g‘ri (} 7  6 11^{), lekin}
(5, 3)
yoy uchun ₅  c₅₃  ₃

munosabat noto‘g‘ri (11 (6)  5  7 ). Oxirgi munosabatni hisobga olib, algoritmga

ko‘ra
₃  7
o‘rniga
₃  5
deb olamiz va
(5, 3)
yoyni ajratilgan deb, ilgari

ajratilgan
(2, 3)
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
₃  7

yozuvning va
(2, 3)
yoyning qalin chiziq’i ustiga ajratilganlikni inkor qiluvchi 

belgisi qo‘yilgan).