O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KAMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
Kampyuter injiniring FAKULTETI
Algaritmlash va matematik modellashtirish kafedrasi
“Diskret tuzilmalar” fani
MUSTAQIL ISH Ν° 1
Mavzu: Qo’shnilik va insidentik matrisalari . Graflarning izomorfigi
Topshirdi: 030-20 guruh talabasi
To’rayev. SH.
Qabul qildi: A.Mirzayev
Toshkent - 2022 y
Qo’shnilik va insidentik matritsalari. Graflarning izomoforlidgi
Reja:
1. Kirish
2. Graflarning izomoforligi haqida
3.Qo’shnichilik matrisalari
4.Insedentlik matrisalari
5.Orgraf uchlari
6.Foydali adabiyotlar
Qo`shnilik va intsedentlik matritsalari.Graflarning izomorfligi.
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.
Do'stlaringiz bilan baham: |
