|
Mavzu graf qo’shnilik, insidentlik matritsalarini tuzish. Matritsalariga ko’ra grafni tiklash Grafning maxsus turdagi ko‘phad yordamida berilishi
|
bet | 1/2 | Sana | 11.02.2024 | Hajmi | 308.83 Kb. | | #154770 |
Bog'liq diskret web dizayn 1-maruzaaaa, 1-Mustaqil ish Bajardi Sirojiddinov z-fayllar.org, 8-labaratoreya
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITET
Mustaqil ish
Bajardi Subhonov Lazizbek
Tekshirdi Turg’unov Abror
MAVZU
Graf qo’shnilik, insidentlik matritsalarini tuzish. Matritsalariga ko’ra grafni tiklash
Grafning maxsus turdagi ko‘phad yordamida berilishi. Grafni maxsus turdagi ko‘phad yordamida ham berish mumkinligini ta’kidlaymiz. Uchlari to‘plami bo‘lgan graf berilgan bo‘lsin. grafning yakkalangan uchlari yo‘q deb faraz qilamiz,. Bu grafni ta o‘zgaruvchilarga bog‘liq
ko‘rinishdagi ko‘phad yordamida tasvirlash mumkin, bu yerda ko‘paytma shartni qanoatlantiruvchi barcha juftlar bo‘yicha amalga oshiriladi, o‘zgaruvchi uchga mos keladi, – va uchlarni tutashtiruvchi qirralar soni, – uchdagi sirtmoqlar soni.
ko‘phad grafga izomorflik aniqligida mos kelishini isbotlash mumkin.
Misol. 11- shaklda tasvirlangan grafga mos ko‘phadni aniqlaymiz. Berilgan oriyentirlanmagan grafda yettita uch va sakkizta qirra bor. Uning har bir uchiga bitta ( ) o‘zgaruvchini mos q1ilib qo‘yamiz. grafda karrali qirralari yo‘q, uning uchta qirrasi sirtmoq-lardan iborat bo‘lib, ulardan ikkitasi 3 uchga, biri esa 5 uchga insidentdir. Shuning uchun , , ; , qolgan barcha bo‘ladi. Berilgan grafga mos ko‘phad
ko‘rinishga ega bo‘ladi.
Misol. ko‘phadga mos keluvchi grafning geometrik tasvirini topamiz. Bu ko‘phadning tarkibiga ko‘ra unga mos keluvchi oriyentirlanmagan grafda 4ta uch va 6ta qirra bo‘lib, bu qirralardan ikkitasi karrali ( ) va bittasi sirtmoq ( ) ekanligini ta’kidlaymiz.
Qo‘shnilik matritsalari. Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo‘shniligi matritsasi tushunchasini qarab chiqamiz.
– uchlari soni ga teng bo‘lgan belgilangan, sirtmoqsiz va karrali qirralarsiz graf bo‘lsin.
Elementlari
ko‘rinishda aniqlangan ( ; ) 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.
Uchlari soni ga teng bo‘lgan belgilangan oriyentirlangan grafning uchlari qo‘shniligi -matritsasi deb elementlari
ko‘rinishda aniqlangan ( , ) matritsaga aytiladi.
Endi uchlari bo‘lgan belgilangan oriyentirlanmagan multigraf bo‘lsin.elementlari grafning va uchlarini tutashtiruvchi qirralar soniga teng bo‘lgan ( )matritsa oriyentirlanmaganmultigrafning uchlari qo‘shniligi matritsasi deb ataladi.
Misol. 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qo‘shniligi matritsasi quyidagicha bo‘ladi:
.
Karrali yoylari bo‘lgan sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi tushunchasini ham yuqoridagiga o‘xshash ta’riflash mumkin.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Mavzu graf qo’shnilik, insidentlik matritsalarini tuzish. Matritsalariga ko’ra grafni tiklash Grafning maxsus turdagi ko‘phad yordamida berilishi
|