Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Fan: Algrotimlarni loyihalash


Download 455.21 Kb.
bet1/2
Sana02.05.2023
Hajmi455.21 Kb.
#1422371
  1   2
Bog'liq
Otabek


Muhammad Al-Xorazmiy nomidagi
Toshkent Axborot Texnologiyalari Universiteti


Fan: Algrotimlarni loyihalash
MUSTQIL ISHI




Bajardi: CAL006 guruh talabasi Sobirov Otabek

Tekshirdi: Begimov O’ktam

Toshkent 2023
Mavzu: Графларни энг арзон таянч дарахтини қуришда Крускал хасис алгоритми

Reja :
1.Graflar haqida


2.Graflar daraxtlarini qurishda algoritmlar.
3.Kruskal xasis algoritmi.

Kirish


1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Graf deb shunday  juftlikka aytiladiki, bu yerda   va –  ( ,  ) ko‘rinishdagi juftliklar korteji1 bo‘lib,  to‘plamning elementlaridan tuzilgandir.
Bundan buyon grafni belgilashda  yozuv o‘rniga  yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz.
 graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari, to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz.


 grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. Agar bo‘sh bo‘lmasa, u holda bu kortej  ( ,  ) ko‘rinishdagi juftliklardan2 tashkil topadi, bunda  bo‘lishi hamda ixtiyoriy   juftlik kortejda istalgancha marta qatnashishi mumkin.

 juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar  juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni  bo‘lsa,  juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni  bo‘lsa, u holda  juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.
kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.  graf elementlarining soni ( )ga tengdir, bu yerda grafning uchlari soni  va bilan uning qirralari (yoylari) soni belgilangan.

Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida  , yoki , yoki  ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi: masalan, yoy uchun  yoki  , qirra uchun  , yoy yoki qirra uchun (ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda.
Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni  va  yozuvlar bir-biridan farq qiluvchi yoylarni ifodalaydi. Agar yoy  ko‘rinishda ifodalangan bo‘lsa, u holda uning boshlang‘ich uchi, esa oxirgi uchi deb ataladi. Bundan tashqari, yoy  ko‘rinishda yozilsa, u haqida uchdan chiquvchi (boshlanuvchi) va uchga kiruvchi (uchda tugovchi) yoy deb aytish ham odat tusiga kirgan.
Qirra uchun uning  yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va va elementlar qirraning uchlari yoki chetlari deb ataladi. Agar grafda yo  qirra, yo  yoy, yoki  yoy topillsa, u holda va uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi.
 Kruskal algoritmi

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.

a) b)
v) g)

d) e)
j) z)
Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:

Download 455.21 Kb.

Do'stlaringiz bilan baham:
  1   2




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