Graflar nazariyasi haqida umumiy ma’lumotlar

Graflar nazariyasi haqida umumiy ma’lumotlar

“Amaliy matematika” fakulteti

“Axborot tizimlari va texnologiyalari” yo’nalishi 120-20 guruh talabasi Boltaboyev Sardorning Algoritmlar va berilganlar strukturasi fanidan tayyorlagan
Mustaqil ishi
Mavzu: Grafni sikl borligiga tekshirish. Sikllarni topish algoritmlari.
Graflar nazariyasi haqida umumiy ma’lumotlar.
1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta A,B,C va D qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi.
Agar (a,b)juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni(a,b)=(b,a) bo‘lsa, (a,b)juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni (a,b)(b,a)bo‘lsa, u holda (a,b) juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.
U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.
Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar (yoylar) deyiladi
Graflarning berilish usullari
1-shakl
1- shaklda tasvirlangan grafni G  (V,U) deb belgilaymiz. Berilgan G graf belgilangan graf bo‘lib, 4ta uch va 6ta qirraga ega. Demak, u (4,6)-grafdir. Bu graf uchun: V {1,2,3,4}, U  u1,u2,u3,u4,u5,u6 , u1  (1, 2) , u2  u3  (1, 3) , u4  (2, 3) , u5  (3, 4), u6  (2,2). G grafning barcha ui (i 1,6) qirralari oriyentirlanmagan (chunki uchlarini tutashtiruvchi chiziklarda yo‘nalish ko‘rsatilmagan) bo‘lgani uchun G oriyentirlanmagan grafdir. Grafning qirralaridan biri, aniqrog‘i, u6 sirtmoqdir, u2 va u3 esa karrali qirralardir. Bu grafda, masalan, 1 va 2 uchlar qo‘shni, 1 va 4 uchlar esa qo‘shni emas. Undagi 2 va 3 uchlar u4 qirraga insident va, aksincha, u4 qirra 2 va 3 uchlarga insidentdir. Bu yerda u4 va u5 qirralar qo‘shni qirralardir, chunki ular umumiy uchga (3 uch) ega, u1 va u5 qirralar esa qo‘shni emas.
Geometrik ifodalanishi 2- shakldagi ko‘rinishda bo‘lgan oriyentirlangan grafni qaraymiz. Bu grafda o‘n bitta element bor: 5ta uch va 6ta yoy, ya’ni shaklda (5,6)-orgraf berilgan. Bu grafni G  (V,U) bilan belgilaymiz, bu yerda V {1,2,3,4,5}, U  (1,2),(1,3),(5,2),(4,1),(4,5),(5,4)  yoki U  u1,u2,u3,u4,u5,u6 . Berilgan G orgrafda sirtmoq ham, karrali yoylar ham yo‘q. Bu grafning (1,3) yoyi uchun 1 boshlang‘ich, 3 uch esa oxirgi uchdir.
Sikl - bu boshlang'ich va oxirgi uchlari bir-biriga to'g'ri keladigan yo'l. Siklning uzunligi - bu sikldagi qirralarning soni.
Agar bir cho'qqidan bir necha marta o'tmasa, sikl oddiy deyiladi.
Ushbu grafik quyidagi sikllarni o'z ichiga oladi:
1) x 1 , x 5 , x 4 , x 1 3 uzunlikdagi sikl;
2) x 1 , x 2 , x 3 , x 1 3 uzunlikdagi sikl;
3) x 1 , x 2 , x 4 , x 5 , x 3 , x 1 5 uzunlikdagi sikl;
4) x 1 , x 2 , x 4 , x 5 , x 2 , x 3 , x 1 6 uzunlikdagi sikl;
va hokazo.
E’tiboringiz uchun rahmat
http://azkurs.org