|
Graflarni erkin ajratish usullari
|
| bet | 4/4 | | Sana | 22.05.2024 | | Hajmi | 25,55 Kb. | | #250452 | | Turi | Referat |
Bog'liq Referati mavzu Graf erkin uchlarini ajratish masalasi. Bajardi 5. Graflarni erkin ajratish usullari.
Grafning uchlari to'plami chekli to'plam bo'lganligidan, yuqorida bayon etilgan uchlar ketma-ketligini qurish jarayonida chekli qadamdan so'ng albatta oldin uchragan uchlardan birini tanlashga majbur bo'lamiz. Agar uch ketma-ketlikda ikki marta uchragan dastlabki uch bo'lsa, ketma-ketlikka qirralar qo'shish jarayonini to'xtatamiz, chunki tuzilgan qirralar ketma-ketligining uch ikki marta qatnashgan qismi biz izlayotgan sikldir. ?
Grafning bog'lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari va uchlardan iborat marshrut topilsa, bu va uchlar bog'langan deb, marshrutning o'zi esa va uchlarni bog'lovchi marshrut debataladi.
Tabiiyki, agar qandaydir uchlarni bog'lovchi marshrut biror uchdan bir necha marta o'tsa, u holda marshrutning siklik qismini olib tashlab (bunda siklik qismning o'rniga marshrutda faqat uch qoldiriladi) yana o'sha uchlarni bog'lovchi oddiy zanjir ko'rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog'langan uchlar doimo oddiy zanjir bilan ham bo'glangan bo'ladi degan xulosaga kelamiz.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog'langan graf bog'lamli graf deb ataladi.
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo'lsa, u holda bu ikkita uch ekvivalent (bog'langan) deyiladi. Bunday uchlar to'plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to'plami bo'yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog'lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog'lamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog'lamlilik komponentalariga bo'laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o'zining bog'lamlilik komponentalarining diz'yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog'lamlilik komponentalariga bo'laklanishi bir qiymatli aniqlanadi.
Xulosa
Ushbu ish orqali graflar nazaryasi xaqida uning ustida amallar yechish xolatlarini korib chiqdik.
Foydalanilgan adabiyotlar.
JAMOA. Kombinatorika va graflar nazariyasi. Oliy o‘quv yurtlari uchun o‘quv qo‘llanma. — Т.: «ILM ZIYO», 2009. - 256b
1. N. To’rayev, I. Azizov, S. Otaqulov. “Kombinatorika va graflar nazariyasi” Toshkent- “Ilm ziyo”-2009y 2. O.Ore. “Teoriya grafov” M….”Nauka” 1987y 3. F. Rajabov. S. Masharipov. R. Madrahimov. “Oliy matematika “Toshkent”“Turon- Iqbol” 2007 yil
|
| |
