|
Tayyorladi: 043-22 sto’ guruh talabasi miraxmedov jaxongir mirzayevich toshkent – 2023 y. Reja: Kirish
|
| bet | 8/13 | | Sana | 10.01.2024 | | Hajmi | 125,27 Kb. | | #134127 |
Bog'liq diskret| grafning uchlari qo‘shniligi m m -matritsasi deb elementlari
1,
aij
agar (i, j) U
bo'lsa,
0,
aks holda,
ko‘rinishda aniqlangan
A (aij )
( i 1,2,...,m ,
j 1,2,...,m ) matritsaga aytiladi.
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 (aij )
( i, j 1,2,...,m ) matritsa oriyentirlanmagan multigrafning
uchlari qo‘shniligi matritsasi deb ataladi.
Karrali yoylari bo‘lgan sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi
tushunchasini ham yuqoridagiga o‘xshash ta’riflash mumkin.
1.2- t a s d i q . 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.
Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qo‘shniligi matritsasi bo‘lgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bo‘yicha izlanishlar maxsus shartlarni qanoatlantiruvchi mat-ritsalarni tadqiq qilishga keltirilishi mumkinligi kelib chiqadi.
u1 , u2 ,..., un ( n 1 ) qirralarga ega yakkalangan uchlari, sirtmoq va karrali
qirralari bo‘lmagan graf uchun elementlari
1, agar ui va u j qirralar umumiyuchga ega bo'lsa,
cij
0, agar ui u j bo'lsa yokiularning umumiyuchi bo'lmasa,
quyidagicha aniqlangan
C (cij )
( i 1,2,...,n ,
j 1,2,...,n )
n n -matritsa grafning
|
| |
