graflar ustida amallar

DOCX 6 sahifa 179,0 KB Bepul yuklash

6 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 179,0 KB

Fayl turi DOCX

Sahifalar 6

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 6

mavzu: graflar ustida amallar graf. uch. qirra. graflarni birlashtirish. grafdan uchni, qirrani, yoyni olib tashlash. qism graf. to‘ldiruvchi graf. grafga uchni, qirrani, yoyni qo‘shish. qirrani ikkiga bo‘lish. izomorf va gomeomorf graflar. bo‘linish grafi. graflarning birlashmasi. diz’yunkt birlashma. graflarning birikmasi. graflarning ko‘paytmasi. o‘lchovli kub. 1. graflar ustida sodda amallar. graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko‘paytirish, grafni qismlarga ajratish va hokazo. eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo‘ladi. bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta element yo‘qotishni (olib tashlashni) anglatadi. natijada uchlari soni bittaga kamaygan yangi graf hosil bo‘ladi. albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi. eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan …

2 / 6

ataladi. berilgan graf uchun to‘ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga kiritish mumkin. graf uchun to‘ldiruvchi grafni qurish amalini qo‘llash natijasida graf hosil bo‘ladi. isbotlash mumkinki, munosabat o‘rinlidir. 2- misol. 2- shaklda tasvirlangan graf 1- shaklda ifodalangan graf uchun to‘ldiruvchi grafdir.2- shakl graflar ustida shunday amallarni bajarish mumkinki, ular elementlari soni berilgan grafdagidan ko‘proq bo‘lgan boshqa graflarning hosil bo‘lishiga olib keladi. bunday amallar qatoriga uchni qo‘shish amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin. grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin. masalan, yangi uchni berilgan grafga qo‘shish shu grafning va uchlariga insident bo‘lgan qandaydir qirrasiga qo‘shish orqali quyidagicha ikki bosqichda bajarilishi mumkin: 1) qirra berilgan grafdan olib tashlanadi; 2) hosil bo‘lgan grafga ikkita yangi qirralar: va uchlarga insident qirra hamda va uchlarga insident qirra qo‘shiladi. bu jarayon grafda qirraga darajasi 2 bo‘lgan yangi uchni qo‘shish (kiritish) yoki qirrani ikkiga bo‘lish amali deb ataladi. agar …

3 / 6

4- misol. uchlari to‘plamlari kesishadigan graflarning birlashmasi amali 6- shaklda tasvirlangan. ■5- shakl 1 2 3 4 5 1 2 3 4 5 agar birlashtirilayotgan graflarning uchlari to‘plamlari kesishmasa, u holda bu graflarning birlashmasi diz’yunkt birlashma deb ataladi. masalan, 5- shaklda tasvirlangan birlashma diz’yunkt, 6- shakldagi birlashma esa – diz’yunkt emas. 3.3. graflarni biriktirish. va graflar berilgan bo‘lsin. va graflar birlashtirilishi hamda grafning har bir uchi grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo‘lgan graf va graflarning birikmasi (tutashmasi) deb ataladi va ko‘rinishda belgilanadi.6- shakl 1 2 3 4 5 1 2 3 4 5 4 3 5- misol. uchta uy va uchta quduq haqidagi boshqotirma masalaga mos graf (ushbu bobning 2- paragrafidagi 9- shaklga qarang) uchlari to‘plamlari kesishmaydigan ikkita () nolgraflarning birikmasidir. ■ 6- misol. 7- shaklda uchlari to‘plamlari kesishmaydigan va graflarning birikmasi amali tasvirlangan. ■ agar uchlari to‘plamlari kesishmasi bo‘sh bo‘lmagan graflarni biriktirish zarur bo‘lsa, …

4 / 6

hmaydigan va graflarning ko‘paytmasi amali tasvirlangan. ■1 2 8- shakl i bobning 4- paragrafida ta’kidlanganidek, dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan amallar boshqalaridan o‘ziga xosligi bilan ajralib turadi. bu o‘ziga xoslik graflarni ko‘paytirish amalida namoyon bo‘ladi. aniqrog‘i, graflar ko‘patmasida qatnashgan birorta grafning qirralari korteji bo‘sh bo‘lsada, ko‘paytirish amalini qo‘llash natijasida hosil bo‘lgan grafning qirralari korteji bo‘sh bo‘lmasligi ham mumkin. haqiqatdan ham, yuqorida keltirilgan graflarning ko‘paytmasi ta’rifidan kelib chiqadiki, agar graf va graflarning ko‘paytmasi, ya’ni, bo‘lsa, u holda bo‘ladi va kortej elementlari bilan birlashma elementlari orasida o‘zaro bir qiymatli moslik mavjud. shuning uchun, agar, masalan, , bo‘lsa, u holda bo‘ladi, chunki grafning tarifiga ko‘ra . demak, , ya’ni bo‘sh graf bo‘lsada, bo‘sh bo‘lmagan grafdir.9- shakl graflarni ko‘paytirish amalini takror qo‘llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi o‘lchovli kublarni aniqlash mumkin. o‘lchovli kub () uchlari soni ikkiga teng bo‘lgan to‘la graf yordamida quyidagi rekurrent formula bilan aniqlanadi: , . …

5 / 6

lari kesishadigan va kesishmaydigan hollarni alohida qarang). 7. graflarni ko‘paytirish amalini qo‘llab, , , va graflarni toping. 8. va graflarning geometrik ifodalanishidan foydalanib ular ustida birlashma, birikma va ko‘paytma amallarini bajaring (bunda graflar uchlari to‘plamlari kesishadigan va kesishmaydigan hollarni alohida qarang). mustaqil ishlash uchun savollar 1. grafdan uchni olib tashlash amali qanday bajariladi? 2. grafdan qirrani (yoyni) olib tashlash amali qanday bajariladi? 3. qism graf deganda nima tushuniladi? 4. to‘ldiruvchi graf deb qanday grafga aytiladi? 5. grafga yangi uchni qo‘shish amalini bajarishning qanday usullarini bilasiz? 6. berilgan grafning bo‘linish grafi qanday tuziladi? 7. qanday graflar gomeomorf graflar deb ataladi? 8. berilgan graflarning birlashmasi (uyushmasi) qanday hosil qilinadi? 9. berilgan graflarning diz’yunkt birlashmasi natijasida hosil bo‘lgan graf uchlarining soni haqida nima deyish mumkin? 10. graflarning birlashmasi (uyushmasi) amali bilan ularning birikmasi (tutashmasi) amali orasida qanday o‘xshashlik va farqlar bor? 11. berilgan ikkita graflarning ko‘paytmasi qanday hosil qilinadi? 12. berilgan graf bilan …

Ko'proq o'qimoqchimisiz?

Barcha 6 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflar ustida amallar" haqida

mavzu: graflar ustida amallar graf. uch. qirra. graflarni birlashtirish. grafdan uchni, qirrani, yoyni olib tashlash. qism graf. to‘ldiruvchi graf. grafga uchni, qirrani, yoyni qo‘shish. qirrani ikkiga bo‘lish. izomorf va gomeomorf graflar. bo‘linish grafi. graflarning birlashmasi. diz’yunkt birlashma. graflarning birikmasi. graflarning ko‘paytmasi. o‘lchovli kub. 1. graflar ustida sodda amallar. graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko‘paytirish, grafni qismlarga ajratish va hokazo. eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo‘ladi. bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta element yo‘qotishni (olib tashlashni) anglatadi. natijada uchlari soni bittaga kamaygan yangi graf hos...

Bu fayl DOCX formatida 6 sahifadan iborat (179,0 KB). "graflar ustida amallar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflar ustida amallar DOCX 6 sahifa Bepul yuklash Telegram