graflar nazariyasi elementlari va o'tish algoritmlari

DOCX 18 стр. 885,9 КБ Бесплатная загрузка

18 стр.

FaylHub.uz

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

Размер 885,9 КБ

Тип файла DOCX

Страницы 18

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

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

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

1 / 18

1-ma’ruza. graflar nazariyasi elementlari va o'tish algoritmlari. grafni aniqlanishi. orientirlangan va orientirlanmagan graflar. lokal daraja. yo`l va sikl. grafni mashina xotirasida ifodalash usullari: tomonlar ketma-ketligi, uchlar qo`shniligi massivi orqali, uchlar qo`shniligi ro`yhat orqali, qo`shnilik matrisalar orqali. grafda o`tish muammolari. umumlashtirilgan o'tish algoritmi. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. grafda o`tish bo`yi bo`yicha qidiruv- dfs algoritmi. topologik saralash. graf, uch, qirra, yoy, yo‘nalish, orgraf, qo‘shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf, nolgraf, to‘la, belgilangan va izomorf graflar, grafning geometrik ifodalanishi, uchlar, qirralar va yoylar insidentligi. 1.1. graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda l. eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg[footnoteref:1] ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. [1: kyonigsberg (königsberg) – bu shahar 1255 yilda asoslangan bo‘lib, sharqiy prussiyadagi pregel daryosi qirg‘oqlarida joylashgan. 1946 yildan boshlab kaliningrad, hozir rossiya federatsiyasi tarkibida.] kyonigsberg shahridagi pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi …

2 / 18

. eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. xix asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar g. kirxgof[footnoteref:2] va a. keli[footnoteref:3] ishlarida paydo bo‘ldi. [2: kirxgof (kirchhoff gustav robert, 1824-1887) – olmon faylasufi, fizigi.] [3: keli yoki keyli (cayley artur, 1821-1895) – ingliz matematigi.] 1- shakl “graf” iborasi d. kyonig[footnoteref:4] tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda[footnoteref:5] uchraydi. [4: kyonig (dénes könig, 1884-1944) – venger matematigi.] [5: bu darslik olmon tilida yozilgan.] graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. 1.2. grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin. uning va elementlaridan tuzilgan …

3 / 18

si 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 juftliklardan[footnoteref:7] tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. [7: bu yerda ham juftlikning (kortejning) odatdagi yozuvi o‘rniga yozuvdan foydalanamiz.] 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 …

4 / 18

uvchi (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. grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga (yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi. grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar (yoylar) deyiladi. shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi. ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar (yoylar) soni ga qarab belgilanadi va bu holda grafni -graf deb ataydilar. agar grafda kortej …

5 / 18

adi. umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji cheksiz ko‘p elementli bo‘lishi mumkin. bundan keyin to‘plam va kortej faqat chekli bo‘lgan graflarni qaraymiz. bunday graflar chekli graflar deb ataladi. hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan, xolis, yalong‘och) uch deb ataladi. faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. uchlari soni ga teng bo‘lgan bo‘sh grafni yoki kabi belgilash qabul qilingan. istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf to‘la graf deb ataladi. uchlari soni ga teng bo‘lgan to‘la graf bilan belgilanadi. ravshanki, grafning qirralar soni bo‘ladi. agar orgrafning istalgan ikkita uchini har bir yo‘nalishda tutashtiruvchi faqat bittadan yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi. ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. shuning uchun, to‘la orgrafdagi …

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

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

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

О "graflar nazariyasi elementlari va o'tish algoritmlari"

1-ma’ruza. graflar nazariyasi elementlari va o'tish algoritmlari. grafni aniqlanishi. orientirlangan va orientirlanmagan graflar. lokal daraja. yo`l va sikl. grafni mashina xotirasida ifodalash usullari: tomonlar ketma-ketligi, uchlar qo`shniligi massivi orqali, uchlar qo`shniligi ro`yhat orqali, qo`shnilik matrisalar orqali. grafda o`tish muammolari. umumlashtirilgan o'tish algoritmi. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. grafda o`tish bo`yi bo`yicha qidiruv- dfs algoritmi. topologik saralash. graf, uch, qirra, yoy, yo‘nalish, orgraf, qo‘shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf, nolgraf, to‘la, belgilangan va izomorf graflar, grafning geometrik ifodalanishi, uchlar, qirralar va yoylar insidentligi. 1.1. graflar nazariyasi haqida umumiy ma’lumotlar...

Этот файл содержит 18 стр. в формате DOCX (885,9 КБ). Чтобы скачать "graflar nazariyasi elementlari va o'tish algoritmlari", нажмите кнопку Telegram слева.

Теги: graflar nazariyasi elementlari … DOCX 18 стр. Бесплатная загрузка Telegram