turg‘unlik to‘plami haqida tushuncha

DOCX 12 стр. 312,3 КБ Бесплатная загрузка

12 стр.

FaylHub.uz

Скачать через Telegram

Размер 312,3 КБ

Тип файла DOCX

Страницы 12

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 12

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi zahiriddin muhammad bobur nomidagi andijon davlat universiteti it injiniringi fakulteti kompyuter injinirigi at-servis yo‘nalishi 3-bosqich 303-guruh talabasi olimjonov ahrorbekning diskret tuzilmalar fanidan fanidan mustaqil ishi mavzu: graflarda turg’unlik to’plami. grafning ichki va tashqi turg’unliklari soni. andijon-2025 mavzu : graflarda turg’unlik to’plami. grafning ichki va tashqi turg’unliklari soni. reja: 1. turg‘unlik to‘plami haqida tushuncha. 2. turg‘unlik to‘plamining asosiy turlari. 3. ichki turg‘unlik nima? 4. tashqi turg‘unlik nima? 5. ichki turg‘unliklar sonini aniqlash. 6. tashqi turg‘unliklar sonini aniqlash. 7. xulosa. turg‘unlik to‘plami haqida tushuncha turg‘unlik to‘plami — bu graflar nazariyasidagi muhim tushunchalardan biri bo‘lib, grafikda o‘zaro bog‘lanmagan (ya’ni ular orasida qirra yo‘q) tugunlar to‘plamidir. graf nazariyasida turg‘unlik to‘plami (yoki mustaqil to‘plam) — bu shunday tugunlar (vertexlar) to‘plamiki, ularning hech biri o‘zaro bog‘lanmagan bo‘ladi. boshqacha aytganda, bu to‘plamdagi har qanday ikki tugun orasida grafda qirra (bog‘lovchi chiziq) mavjud emas. oddiy misol: agar a, b, c, …

2 / 12

a boshqa hech qanday tugunni qo‘shib bo‘lmaydi, chunki bu holda bog‘lanish paydo bo‘ladi. oddiy tilda: boshqa tugun qo‘shilsa, u mavjud to‘plamdagi tugun bilan bog‘lanib qoladi. masalan: {a, c} maksimal bo‘lishi mumkin, agar b va d har ikkisi ham a yoki c bilan bog‘langan bo‘lsa. 3. eng katta turg‘unlik to‘plami (maximum independent set) bu — barcha mumkin bo‘lgan turg‘unlik to‘plamlari orasida eng ko‘p tugunni o‘z ichiga olgan to‘plam. farqi: har bir eng katta to‘plam maksimal bo‘ladi, lekin har bir maksimal to‘plam eng katta bo‘lavermaydi. masalan: agar maksimal to‘plamlar {a, c}, {b, d} bo‘lsa, va {a, c, d} — eng katta turg‘unlik to‘plami bo‘lishi mumkin (bog‘lanish holatiga qarab). ichki turg‘unlik nima? ichki turg‘unlik — bu grafdagi turg‘unlik to‘plamining asosiy xususiyatini bildiradi, ya’ni to‘plam ichidagi tugunlar o‘zaro bog‘lanmagan bo‘lishi kerak. oddiy misol: tasavvur qilaylik, grafda quyidagi tugunlar va qirralar bor: tugunlar: a, b, c, d qirralar: (a-b), (b-c) shunda : to‘plam {a, c, …

3 / 12

c — b va d bilan bog‘langan e — d bilan bog‘langan demak: har bir tashqaridagi tugun ichkaridagilardan biri bilan bog‘langan → tashqi turg‘unlik mavjud. tashqi turg‘unlikning ahamiyati: bu tushuncha grafdagi nazorat yoki qamrov darajasini ifodalaydi. dominant to‘plamlar bilan yaqin aloqada, ya’ni biror to‘plam butun grafikni qamrab oladimi — shuni bildiradi. ichki turg‘unliklar sonini aniqlash grafdagi ichki turg‘unliklar soni — bu grafda nechta turg‘un (ya'ni mustaqil) tugunlar to‘plami mavjudligini bildiradi. ya’ni, nechta turli-tuman tugunlar to‘plami bor-ki, ularning ichida birorta ham bog‘lanish (qirra) yo‘q. qanday aniqlanadi? ichki turg‘unliklar sonini topish uchun quyidagilar bajariladi: 1. barcha tugunlar to‘plamlarini ko‘rib chiqish (har xil kombinatsiyalar). 2. har bir to‘plamda ichki bog‘lanish (ya'ni qirralar) mavjud yoki yo‘qligi tekshiriladi. 3. qirralar mavjud bo‘lmasa — bu ichki turg‘unlik to‘plami hisoblanadi. 4. shunday to‘plamlar soni hisoblanadi. oddiy misol: faraz qilaylik, quyidagi oddiy graf bor: tugunlar: a, b, c qirralar: (a-b), (b-c) to‘liq tugunlar to‘plamlari: {}, {a}, {b}, {c} …

4 / 12

turg‘unlik to‘plamlarini aniqlang. 2. ularning har biri uchun quyidagini tekshiring: to‘plamdan tashqarida qolgan har bir tugun (ya'ni ) turg‘unlik to‘plamidagi hech bo‘lmasa bitta tugun bilan bog‘langanmi? 3. shunday shartni qanoatlantiradigan turg‘unlik to‘plamlari — tashqi turg‘unlik to‘plamlari hisoblanadi. 4. shu to‘plamlarning soni hisoblanadi. oddiy misol orqali tushuntirish: faraz qilaylik, quyidagi graf bor: tug’unlar: a, b, c, d qirralar: (a-b), (b-c), (c-d) barcha ichki turg‘unlik to‘plamlari: {}, {a}, {b}, {c}, {d}, {a, c}, {a, d}, {b, d} endi tekshiramiz (faqat tashqi turg‘unlikka ega bo‘lganlar): masalan: {b, d}: tashqarida a va c bor a — b bilan bog‘langan c — b va d bilan bog‘langan → tashqi turg‘unlik bor {a, c}: tashqarida b va d b — a va c bilan bog‘langan d — faqat c bilan bog‘langan → tashqi turg‘unlik bor shu kabi har bir to‘plam tekshiriladi va tashqi turg‘unlikka ega bo‘lganlari sanaladi. eslatma:tashqi turg‘unliklar sonini topish — bu ham murakkab masala …

5 / 12

kning murakkabligi, boshqaruv darajasi va samaradorligini baholash mumkin bo‘ladi. bu esa amaliy sohalarda — kompyuter tarmoqlari, transport tizimlari, ijtimoiy tarmoqlar va boshqa ko‘plab sohalarda grafik modellardan foydalanishni yanada samarali qiladi. image1.png image2.png

Хотите читать дальше?

Скачайте все 12 страниц бесплатно через Telegram.

Скачать полный файл

О "turg‘unlik to‘plami haqida tushuncha"

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi zahiriddin muhammad bobur nomidagi andijon davlat universiteti it injiniringi fakulteti kompyuter injinirigi at-servis yo‘nalishi 3-bosqich 303-guruh talabasi olimjonov ahrorbekning diskret tuzilmalar fanidan fanidan mustaqil ishi mavzu: graflarda turg’unlik to’plami. grafning ichki va tashqi turg’unliklari soni. andijon-2025 mavzu : graflarda turg’unlik to’plami. grafning ichki va tashqi turg’unliklari soni. reja: 1. turg‘unlik to‘plami haqida tushuncha. 2. turg‘unlik to‘plamining asosiy turlari. 3. ichki turg‘unlik nima? 4. tashqi turg‘unlik nima? 5. ichki turg‘unliklar sonini aniqlash. 6. tashqi turg‘unliklar sonini aniqlash. 7. xulosa. turg‘unlik to‘plami haqida tushuncha turg‘unlik to‘plami — bu graflar nazariyasida...

Этот файл содержит 12 стр. в формате DOCX (312,3 КБ). Чтобы скачать "turg‘unlik to‘plami haqida tushuncha", нажмите кнопку Telegram слева.

Теги: turg‘unlik to‘plami haqida tush… DOCX 12 стр. Бесплатная загрузка Telegram