Oriyentirlangan grafning uchlari qorinishda aniqlangan (, ) matritsaga aytiladi. Endi uchlari bolsin elementlari grafning va uchlarini tutashtiruvchi qirralar soniga teng boshniligi matritsasi

xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
16-mavzu graflarning berilish usullari. Qo`shnilik va intsedentlik matritsalari. Graflarning izomorfligi. Grafning maxsus turdagi kophad yordamida berilishi. Grafni maxsus turdagi kokidlaymiz. Uchlari tolgan graf berilgan boq deb faraz qilamiz,. Bu grafni ta oliq

kophad yordamida tasvirlash mumkin, bu yerda koyicha amalga oshiriladi, o va uchlarni tutashtiruvchi qirralar soni, phad grafga izomorflik aniqligida mos kelishini isbotlash mumkin.
Misol. 11- shaklda tasvirlangan grafga mos kozgaruvchini mos q1ilib qoq, uning uchta qirrasi sirtmoq-lardan iborat boladi. Berilgan grafga mos korinishga ega bophadga mos keluvchi grafning geometrik tasvirini topamiz. Bu kora unga mos keluvchi oriyentirlanmagan grafda 4ta uch va 6ta qirra bokidlaymiz.
Qoshniligi matritsasi tushunchasini qarab chiqamiz.
lgan belgilangan, sirtmoqsiz va karrali qirralarsiz graf borinishda aniqlangan (; ) matritsani grafning uchlari qorifdan sirtmoqsiz va karrali qirralari boshniligi matritsasining bosh diagonalida faqat nollar bolgan belgilangan oriyentirlangan grafning uchlari qorinishda aniqlangan (, ) matritsaga aytiladi.

Endi uchlari bolsin.elementlari grafning va uchlarini tutashtiruvchi qirralar soniga teng boshniligi matritsasi deb ataladi.

Misol. 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qoladi:
.
Karrali yoylari boshniligi matritsasi tushunchasini ham yuqoridagiga oriflash mumkin.


Teorema.Graflar faqat va faqat uchlari qorinlarini va ustunlarining olsagina izomorf boliq ravishda, turlicha qolgan ixtiyoriy ikkita belgilangan, oyilgan belgilar turlicha va ulardan biri boshqasidan uchlarning qollab hosil qilingan boni grafdagi va uchlar faqat va faqat grafning va uchlari qolsagina qolsin. grafning uchlari qoshniligi matritsasini esa () bilan belgilasak, oladi.
Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qolgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bolmagan graf uchun elementlari

quyidagicha aniqlangan (, )-matritsagrafning qirralari qolib, uning qirralari qorinishga egadir.

Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qolgan belgilangan graf berilgan borinishda aniqlangan (, ) matritsagrafning insidentlik matritsasi deb ataladi.

koladi:
.
Teorema.Graflar (orgraflar) faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining orinlarini mos almashtirishlar yordamida hosil bolishadi.
http://fayllar.org