Мавзу: граф алгоритмлари 1-§. Оддий графлар. Таъриф ва мисоллар Калит сўзлар



Download 2,06 Mb.
bet1/3
Sana22.06.2022
Hajmi2,06 Mb.
#690462
  1   2   3
Bog'liq
Графлар алгор 4



МАВЗУ: ГРАФ АЛГОРИТМЛАРИ
1-§. Оддий графлар. Таъриф ва мисоллар


Калит сўзлар: Граф. Қирралар. Учлар. Йўналтирилган, йўналтирилмаган қирра. Инцидент. Оддий графлар. Графнинг тўлдирувчиси. Қисм граф. Суграф.

Графлар назарияси ҳозирги замон математикасининг асосий қисмларидан биридир. Кейинги пайтларда турли хил АСУ ва дискрет характерга эга бўлган ҳисоблаш қурилмаларни лойиҳалашда (ясашда) графларнинг роли янада ошди.


1-шакл.
Графнинг ўзи нима? Таъриф беришдан аввал қуйидаги мисолда тушунтирамиз.


1-шаклда учлари 1,2,3,4,5 рақамлар билан белгиланган доирачалардан, қирралари эса a,b,c,d,e,f,g,h,i,j,k (йўналишга эга ёки йўналишсиз) бу доирачаларни баъзи бирларини туташтирувчи чизиқлардан иборат. Қирра а йўналтирилган бўлиб 1 ва 2 учларни туташтиради (лекин 2 ва 1 учларни туташтирмайди); ёйлар деб аталувчи бу қирраларга e,f,g лар ҳам мисол бўла олади. Қирра h йўналтирилмаган бўлиб, у 1 ва 4, ҳамда 4 ва 1 учларни туташтиради; звенолар деб аталувчи бундай қирраларга i ва j лар ҳам киради. Ниҳоят b,c,d,k қирралар сиртмоқлар деб аталади ва баъзи учни унинг ўзи билан туташтиради (бу қирралар ҳам йўналишга эга эмас).
Одатда a,b,e,f,g,h қирраларни 1 учга инцидент деб атайдилар, ўз навбатида бу уч шу қирраларнинг ҳар бирига инцидентдир.Шу билан бирга a,e,f ёйлар 1 учдан 4 га қараб йўналтирилган, g эса аксинча 4 дан 1 га қарата йўналтирилгандир. Учинчи ва бешинчи учлар яккаланган дейилади (улар кўпи билан сиртмоқларга инцидент бўлиши мумкин).
Бу мисолдаги граф чеклидир: {1,2,3,4,5} учлар ва {a,b,c,d,e,f,g,h,i,j,k} қирралар тўпламларининг иккаласи ҳам чекли.
Келгусида оддий графлар муҳим ўрин тутади. Бу синфнинг графлари қуйидаги хоссаларга эга: у чекли, барча қирралари ориентирланмаган, сиртмоқлари ва каррали қирралари йўқ (исталган иккита учлар биттадан кўп звено билан туташтирилмайди).
Бундай графларга қуйидагилар мисол бўла олади.
Петерсен номи билан аталувчи ўнг томондаги граф қирраларининг доирачалар билан белгиланмаган кесишган жойлари унинг учлари эмасдир.


2-шакл.




Download 2,06 Mb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©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