graf uchlari va qirralarini bo’yash. graf siklomatik soni va sinfini aniqlash

PDF 11 стр. 1,1 МБ Бесплатная загрузка

11 стр.

FaylHub.uz

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

Размер 1,1 МБ

Тип файла PDF

Страницы 11

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

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

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

1 / 11

1 o‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti fan: diskret mutaqil ish №1 mavzu : graf uchlari va qirralarini bo’yash. graf siklomatik soni va sinfini aniqlash bajardi: turdiyev samandar tekshirdi: oybek begimov toshkent-2024 2 reja kirish 1. graflar nazariyasiga oid asosiy tushunchalar. 2. mustaqil bajarish uchun masala va topshiriqlar 3. graflar ustida amallar xulosa foydalanilgan adabiyotlar 3 kirish: grafning uchlari (vertex) va qirralarini (edge) bo'yash, graf nazariyasida muhim mavzular hisoblanadi. grafni bo'yash jarayoni grafning uchlarini yoki qirralarini ma'lum bir ranglar bilan shunday bo'yashdan iboratki, qo'yilgan qoidalar buzilmaydi. grafning uchlarini bo'yash (vertex coloring) grafning uchlarini bo'yashda har bir uchi ranglanadi va qo'shni uchlar (bir qirra bilan bog'langan uchlar) bir xil rangda bo'lishi mumkin emas. grafning uchlarini bo'yash uchun zarur bo'lgan minimal ranglar soni grafning xromatik soni (chromatic number) deyiladi va bu odatda χ(g) bilan belgilanadi. grafning qirralarini bo'yash (edge coloring) grafning qirralarini bo'yashda …

2 / 11

di. 4 1. graflar nazariyasiga oid asosiy tushunchalar. berilgang grafdan uning sincho’rmonini hosil qilish maqsadida olib tashlanishi kerak bo’lgan qirralar soni bu qirralarni olib tashlash tartibiga bog’liq emasligi vak bo’lishi ravshandir. tengsizliko’rinli bo’lganligidan qaralayotgang grafuchunn tasdiq 1.grafning siklomatik soni tushunchasi, qandaydir ma’noda,grafningbog’lamlilikdarajasinianiqlovchivositadir. ravshanki, daraxt uchun 0  bo’ladi. tasdiq 2.grafningo’rmon bo’lishi uchun uning siklomatik soni nolga teng bo’lishi zarur va yetarlidir. tasdiq 3.grafning yagona siklga ega bo’lishi uchun uning siklomatik soni 1 ga teng bo’lishi zarur va yetarlidir. qirralari soni uchlari sonidan kichik bo’lmagan graf siklga egadir. misol.yuqoridagi misoldatasvirlangan graf) 9,6(-graf bo’lib, uning bog’lamlilik komponentalari soni birga teng. bu grafning siklomatik sonini aniqlasak, bo’ladi. olib tashlangan qirralarshaklda ingichka chiziqlar bilan ifodalangan 2. mustaqil bajarish uchun masala va topshiriqlar 15.1- ta’rif. qirraning boshi yoki oxirini ifodalovchi uchga bu qirraga intsident uchdeyiladi. 15.2- ta’rif. graf uchining darajasi deb bu uchga intsident qirralarsoniga aytiladi. xiuchning darajasini p(xi ) bilan belgilanadi. boshqacha aytganda uchdan …

3 / 11

graf bo`lishi zarur va yetarlidir. 15.2- teorema.oriyentirlanmagan graf a va v uchlarni birlashtiruvchi eyler zanjiriga ega bo`ladi, faqat va faqat shu holdaki, agar graf bog`liq bo`lsa hamda faqatgina ava vuchlar toq darajalarga, qolgan uchlar juft darajalarga ega bo`lsa. 15.5- ta’rif. grafni tekislikka yotqizish mumkin bo`lsa, bunday graf planar grafdeyiladi. tekislikka yotqizilgan graf tekis grafdeyiladi. mashrutning uzunligideb, shu marshrutda mavjud qo`shni (ei-1, ei ) qirralar soniga aytiladi. grafning ixtiyoriy ava ixtiyoriy vuchlari orasidagi masofa deb, shu uchlarni bog`lovchi eng kichik uzunlikka ega bo`lgan zanjirga aytiladi. 15.1- misol. yig`indi grafikkita qo`shiluvchi graflardan hech bo`lmaganda bittasida uchraydigan uch va qirralarni o`z ichiga oladi. ko`paytma graf ko`paytirilayotgan graflarning umumiy uchlari va qirralaridan iborat. 6 3. graflar ustida amallar planar graflarni bo’yash masalasi graflar nazariyasining eng mashhur muammolaridan biri hisoblanadi. o’tgan asrningo’rtalarida paydo bo’lgan masala hamon mutaxassis va qiziquvchilar diqqatida. dastlab savol quyidagichaqo’yilgan: geografik xaritani bo’yash uchun ixtiyoriy 2 taqo’shni davlatni rangi har xil bo’lishini …

4 / 11

ylik: teorema 1.grafikki bo’lakli bo’lishi uchun uning tarkibida uzunligi toq son bilan ifodalanuvchisiklbo’lmasligizarurva yetarlidir. 99berilgan) ,(uvggrafning ikki bo’lakliligini aniqlashning sodda usuli bor. bu usulko’ndalangiga izlashdeyiladi. ko’ndalangiga izlash usuliga ko’ra grafning uchlari ,... 3,2,1,0raqamlar bilan quyidagi qoida bo’yicha belgilanadi. dastlab grafning ixtiyoriy uchi 0 raqami bilan belgilab olinadi. shu 0 belgili uchga qo’shni barcha uchlarga 1 belgisiqo’yiladi. endi 1 belgili har bir uchga qo’shni uchlarni aniqlab, ular orasidagi belgisi yo’quchlarga 2 belgisini qo’yamiz. keyin 2 belgisiga ega barcha uchlarni aniqlab, ular uchun ham yuqoridagigao’xshash ish yuritamiz. bu jarayonni mumkin bo’lgan qadar davom ettiramiz. tushunarliki, agarg graf bog’lamli bo’lsa, u holda ko’ndalangiga izlash usuli grafning barcha uchlarini raqamlab chiqish imkonini beradi. bog’lamli graf uchlarini belgilash jarayoni tugagandan so’ng, uning uchlari to’plamivni 7 ikkitajvvaq v to’plamga quyidagicha ajratamiz: juft raqamli uchlarnijvto’plamga, qolgan uchlarni esa q v to’plamga kiritamiz (0 raqamli uchj v to’plamga kiritiladi).g grafning ikkala uchi hamjvto’plamga tegishli barcha qirralari kortejinij u …

5 / 11

a kod yozish va masalalarni yechish mumkin. 8 masalan, python dasturida networkx kutubxonasidan foydalanish 9 10 xulosa graf nazariyasi va uning bo'yash masalalari zamonaviy matematikada va kompyuter ilmida muhim o'rin tutadi. ushbu tushunchalarni tushunish va qo'llash, ko'plab real dunyo muammolarini hal qilishda samarali usullarni taqdim etadi. graf bo'yash algoritmlari va siklomatik son kabi ko'rsatkichlar, tarmoqlarni rejalashtirish, optimallashtirish va tahlil qilishda keng qo'llaniladi. bu bilimlar dasturiy ta'minot muhandisligi, operatsion izlanishlar, logistika va boshqa ko'plab sohalarda foydali bo'lishi mumkin. graf nazariyasida uchlarni va qirralarni bo'yash muhim mavzulardan biri bo'lib, uning amaliyotda ko'plab qo'llanilish joylari mavjud. grafning uchlarini bo'yashda qo'shni uchlar bir xil rangda bo'lmasligi kerak, bu esa grafning xromatik soni orqali o'lchanadi. bu parametr grafni bo'yash uchun zarur minimal ranglar sonini aniqlaydi va χ(g) bilan belgilanadi. grafning qirralarini bo'yashda esa qo'shni qirralar bir xil rangda bo'lmasligi kerak, bu grafning qirra xromatik soni bilan o'lchanadi va χ'(g) bilan belgilanadi. har ikkala bo'yash jarayoni …

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

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

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

О "graf uchlari va qirralarini bo’yash. graf siklomatik soni va sinfini aniqlash"

1 o‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti fan: diskret mutaqil ish №1 mavzu : graf uchlari va qirralarini bo’yash. graf siklomatik soni va sinfini aniqlash bajardi: turdiyev samandar tekshirdi: oybek begimov toshkent-2024 2 reja kirish 1. graflar nazariyasiga oid asosiy tushunchalar. 2. mustaqil bajarish uchun masala va topshiriqlar 3. graflar ustida amallar xulosa foydalanilgan adabiyotlar 3 kirish: grafning uchlari (vertex) va qirralarini (edge) bo'yash, graf nazariyasida muhim mavzular hisoblanadi. grafni bo'yash jarayoni grafning uchlarini yoki qirralarini ma'lum bir ranglar bilan shunday bo'yashdan iboratki, qo'yilgan qoidalar buzilmaydi. grafning uchla...

Этот файл содержит 11 стр. в формате PDF (1,1 МБ). Чтобы скачать "graf uchlari va qirralarini bo’yash. graf siklomatik soni va sinfini aniqlash", нажмите кнопку Telegram слева.

Теги: graf uchlari va qirralarini bo’… PDF 11 стр. Бесплатная загрузка Telegram