|
Guruh talabasi rejabov nodirbek adiljonovichning
|
| bet | 2/6 | | Sana | 30.09.2023 | | Hajmi | 107.7 Kb. | | #85737 |
Bog'liq Diskret tuzilmalar 1. KTE xxx, diskerit bazza 22.02.2023, Тестлар Big Data-uz, MUSTAQIL TA'LIM MAVZULARI, 713, 1-dedlayn G, 1-6 simsiztushunchalar.
G = (V,U ) graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘miga, ba’zan, tugun yoki nuqta iborasi ham qoilaniladi.
G = {V,U) grafning ta’rifiga ko‘ra, U bo‘sh kortej bo’lishi ham mumkin. Agar U bo‘sh bo'lmasa, u holda bu kortej (a,b) ( a e V , b e V) ko‘rinishdagi juftliklardan tashkil topadi, bunda a = b bo'lishi hamda ixtiyoriy (a, b) juftlik U kortejda istalgancha marta qatnashishi mumkin. (a,b) e U juftlikni tashkil etuvchi a va b uchlaming joylashish tartibiga bog‘liq holda, ya’ni yo'nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar (a,b ) juftlik uchun uni tashkil etuvchilaming joylashish tartibi ahamiyatsiz, ya’ni (a,b) = (b,a) bo‘lsa, (a,b) juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni (a,b) = (b,а) bo‘lsa, u holda {a, b) juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.
U 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. Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lurn. L. Eyler 1736- yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda bog‘lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo‘ladi? Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga) ega graf Eyler grafi deb ataladi. Agar grafda yopiq bo’lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler grafi deb ataladi. Oriyentirlangan graflarda oriyentirlangan Eyler yo'lini izlash bilan shug‘ullanish mumkin. Har bir yoydan faqat bir marta o ‘tadigan yo‘l oriyentirlangan Eyler yo‘li deb ataladi. Tarkibida oriyentirlangan Eyler yo‘li bor bo‘lgan oriyentirlangan graf oriyentirlangan Eyler grafi deb ataladi
Endi qirralari soni n ga teng bo'lgan berilgan Eyler grafida Eyler zanjirini tuzishning Flyori algoritmini keltiramiz. Bu algoritmga ko‘ra grafning qirralari Eyler siklida uchrashi tartibi bo‘yicha ldan n gacha raqamlab chiqiladi. Flyori algoritmiga ko‘ra ish yuritish Eyler grafi uchun doimo chekli jarayon ekanligi va bu jarayon doimo grafdan barcha qirralarning olib tashlanishi, ya’ni Eyler zanjirini tuzish bilan tugashi isbotlangan. Shuni ham ta’kidlash kerakki, Flyori algoritmini qo‘llash jarayonida qirralami tanlash imkoniyatlari ko‘p bo'lgani uchun, bunday vaziyatlarda, algoritmni qo'llash mavjud Eyler sikllaridan birini topish bilan cheklanadi. Tushunarliki, Flyori algoritmini takror qo'llab (bunda qirralami tanlash jaroyoni algoritmini avvalgi qo'llashlardagidek aynan takrorlanmasligi kerak) grafda mavjud bo‘lgan barcha Eyler sikllarini topish mumkin.
Berilgan grafga flyori algoritmini qo‘llab mavjud Eyler sikllaridan birini aniqlaymiz. Dastlabki uch sifatida grafdagi 1 belgili uch olingan bo‘lsin. Bu uchdan ikki yo‘nalishda: (1;2) qirra bo‘ylab yoki (1;4) qirra bo‘ylab 1-shakl harakatlanish mumkin. Masalan, (1;2) qirra bo‘ylab harakatlanib 2 belgili uchga o‘tamiz. Endi harakatni 3 yo‘nalishda: yo (2;3) qirra bo‘ylab, yo (2;4) qirra bo‘ylab, yoki (2;5) qirra bo‘ylab davom ettirish mumkin. Aytaylik, (2;3) qirra bo‘ylab harakatlanib 3 belgili uchga o‘tgan bo‘laylik. Shu usulda davom etib mumkin bo‘lgan Eyler sikllaridan birini, masalan, quyidagi siklni hosil qilamiz:
((1,2), (2,3), (3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5), (5,8), (8,7), (7,5), (5,2), (2 ,4 ), (4,1)).
|
| |
