1. Oddiy graflar Ta’rif va misollar Grafning uchlari va qirralari



Download 310,47 Kb.
Pdf ko'rish
Sana28.04.2023
Hajmi310,47 Kb.
#932833
Bog'liq
graflar nazariyasi



Asosiy tushunchalar. Graflar ustida 
amallar. Graflarning izomorfligi
Ma’ruzachi : Mamatov A
Toshkent 2011


Reja:
1.Oddiy graflar Ta’rif va misollar
2.Grafning uchlari va qirralari.
3.Insidentlik tushunchasi.Qism graf.
4.To‘ldiruvchi graf. Graflarning izomorfligi.


Graflar nazariyasi xozirgi zamon matematika
-
sining asosiy qismlaridan biridir. Keyingi 
paytlarda turli xil ABT va diskret xususiyat
-
larga ega bo‘lgan xisoblash qurilmalarini 
loyixalashda (yasashda) graflarning axamiyati 
yanada oshdi. Grafni ta’riflashdan avval uni 
misolda tushuntiramiz.


1, 2, 3, 4, 5 –grafning uchlari; a, b, c, d, e, f, g, h, i, j -grafning qirralari
:
a, b, e, f, g qirralilar yo‘naltirilgan.b, c, d, k qirralar sirtmoqlar deb 
ataladi. a, b, e, f, g qirralarni 1 uchga insident deb ataydilar, o‘z 
navbatida bu uch shu qirralarning xar biriga insidentdir. 3 va 5 
uchlar yakkalangan, deyiladi, ular ko‘pi bilan sirtmoqlarga ega 
bo‘lishi mumkin. Kelgusida oddiy graflar muxim o‘rin tutadi
j
i
а
1
2
4
3
5
e
f
g
h
d
K
c
b


Ta

rif. Bo‘sh bo‘lmagan X uchlar to‘plami va qirralar 
to‘plamidan tuzilgan tartiblangan G=(X,U) juftlik oddiy graf 
deb ataladi. 
Petersen 
nomi bilan 
atalgan graf.
Bu sinfning graflari quyidagi xossalarga ega u chekli (qirralari 
va uchlari soni chekli), barcha qirralari yo‘naltirilmagan, 
sirtmoqlari va karrali qirrali yo‘q. Bunday graflarga quyidagilar 
misol bo‘la oladi:


Agar uchlar uchun bo‘lsa, uchlar qo‘shni, bo‘lsa, bu uchlar 
qo‘shnimas deyiladi. Oddiy graflarning ikki xolini ko‘ramiz: 
E
n
-n uchli bo‘sh graf,
U(E
n
)=Ø
F
n
-n uchli to‘liq graf, 
U(F
n
)=X
|2|
SHaklda E
5
va 
F

graflar keltirilgan. 



Ta

rif. Agar G=(X,U) va G=(X
|
,U
|
) graflar uchun bo‘lsa, u 
xolda G
|
graf G grafning bo‘lagi deyiladi. Ma
s
alan 5 shakldagi 
graflar 4 shakldagi birinchi grafning bo‘lagidir
1
2
1
2
5
4
5
1
4
2
3
3
Ta

rif. Agar G=(X,U) grafning bo‘lagi G
|
=(X
|
,U
|
) uchun bo‘lsa, 
u xolda u sugraf deb ataladi. Sugraflarni xosil qilish uchun 
faqat qirralarni murojat qilamiz. Quyidagi graflar uning 
sugraflaridir.



Document Outline

  • Asosiy tushunchalar. Graflar ustida amallar. Graflarning izomorfligi
  • Reja:
  • Слайд номер 3
  • Слайд номер 4
  • Слайд номер 5
  • Слайд номер 6
  • Слайд номер 7
  • Слайд номер 8
  • Слайд номер 9
  • Слайд номер 10

Download 310,47 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish