Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

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

^1,

^aij ^{ }
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.

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.
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.


u₁ , u₂ ,..., u_n ( 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 u_i  u _j bo'lsa yokiularning umumiyuchi bo'lmasa,

quyidagicha aniqlangan

C  (c_ij )
( i  1,2,...,n ,


j  1,2,...,n )

n  n -matritsa grafning