| 1.4§- Graflar hazariyasining qo’llanish sohalari.
Sport musobaqalari: faraz qilaylik, harflar bilan belilangan oltita tomonda orasida qandaydir musobaqa o’tkazilayotgan bo’lsin . Musobaqalashuvchi komandalarorasida o’yinlarning bir nechtasi o’tkazilgan, qaysi komandalar o’zaro o’ynaganlarini graf orqali ifodalash mumkin.
Masalan:
komanda komandalar bilan, komanda komandalar bilan, komanda komandalar bilan, komanda komandalar bilan, komanda komandalar bilan o’zaro o’ynaganliklarini graf orqali tasvirlash uchun har bir komandani tekislikda olingan qandaydir nuqtalar bilan belgilaymiz va o’zaro o’ynagan komandalarga mos keluvchi nuqtalarni tutashtiramiz.
U holda
chizmadagi tasvirlangan graf hosil bo’ladi. Bu graf oltita uchga va sakkizta qirraga ega. Agar grafning qandaydir ikkita uchi qirra bilan tutashtirilgan bo’lsa, ularni qo’shni uchlar deb atagan edik. Masalan yuqoridagi chizmadagi grafda va lar qo’shni uchlar bo’lib, va lar qo’shni bo’lmagan uchlardir.
Graflar nazariyasida uchlari va qirralari cheksiz ko’p bo’lgan graflar ham o’rganiladi. Odatda bunday grafni umumiy holda ko’rinishda belgilanadi: bunda – grafning uchlari
ko’rinishda esa grafning qirralari belgilanadi.
Chekli sondagi elementlarga ega bo’lgan to’plam elementlariga mos qo’yilgan nuqtalarni ma’lum bir qonuniyat bilan tutashtirishdan hosil bo’ladigan graflar matematikaning turli sohalarida va ayniqsa amaliy matematikada keng tadbiqga ega.
XVII asr o’rtalarida paydo bo’lgan bu nazariyani faqatgina, matematik o’yinlar va boshqotirmalarga qo’llash mumkin deb o’ylab kelingan. Bu jixatdan graflar nazariyasiga bo’lgan munosabat o’z davrida ehtimollar nazariyasiga bo’lgam munosabatga o’xshab ketadi. Ehtimollar nazariyasi ham boshqa azart o’yinlargagina (karta , damino va hokazo) tadbiq etilishi mumkin bo’lgan soxa deb qaralgan. XX asr boshlarida esa bu soxaga, ya’ni graflar nazariyasiga topologiya fani bilan shug’ullanuvchi olimlar qiziqa boshlaganlar.
Keyinchalik esa graflar soxasida erishilgan natijalarni elektr texnika, informatika, transport masalalari, avtomatika, chiziqli va kvadratik programmalashtirish kabi soxalarining masalalariga qo’llash mumkinligi aniqlandi. Graflar va ularning xossalari grafning qanday tekislikda (Evkilid, Lobachevskiy, Rimon, Proektiv ) qaralayotganligiga bog’liq. Bajarilgan ishda odatdagi Evklid tekisliga va sfera sirtida berilgan graflarning ba’zi xossalari o’rinlidir.
Endi grafning stiklometrik soni tushunchasini o’rganamiz.faraz qilaylik sirtmoqsiz va karrali, qirralari bo’lmagan qandaydir bog’lamli graf bo’lsin. Bu grafdan uning biron sikliga tegishli bironta qirrasini olib tashlash natijasida hosil bo’lgan graf bog’lamli graf bo’lishi ravshandir. Grafdan uning biron sikliga tegishli bitta qirrasini olib tashlash amalini hosil bo’lgan graflarga imkoni boricha ketma-ket qo’llash natijasida grafning barcha uchlarini bog’lovchi graf daraxtni hosil qilish mumkin. Bunday daraxt grafning sinch daraxti (sinchi, karkasi, qovurg’asi) deyiladi. Tabiiyki, bitta grafning bir necha sinch daraxtlari mavjud bo’lishi mumkin. Endi graf sirtmoqsiz va karrali qirralari bo’lmagan ta uch,ta qirra va ta bog’lamli komponentlardan tashkil topgan graf bo’lsin. Agar yuqorida tasvirlangan usul yordamida grafdan qirralarni ketma- ket olib tashlash amalini qo’llash natijasida uning har bir komponentasi bog’lamliligi buzilmasa, u holda berilgan grafning sinch o’rmoni deb ataluvchi grafni hosil qilish mumkin. Berilgan grafdan uning sinch o’rmonini hosil qilish maqsadida olib tashlanishi kerak bo’lgan qirralar soni bu qirralarni olib tashlash tartibiga bog’liq emasliga va bo’lishi ravshandir. Qaralayotgan graf uchun tengsizlik o’rinli bo’lgandagina bo’ladi. soniga grafning siklometrik soni (siklik rangi) deyiladi. Grafning siklometrik soni tushunchasi, qandaydir ma’noda grafning bog’lamlilik darajasini aniqlovchi vositadir.
|
