Graflar ustida amallar

Graflar ustida amallar REJA: Graflar nazariyasi Qo'shmalik matritsasi. 3. Qo'shnilik matritsasi. 4. Eyler grafi. 5 Gamilton grafi 1. Graflar nazariyasi fani - chiziqlar va nuqtalardan tuzilgan bazi bir geometrik konfiguratsiyalar to'g'risidagi masalalarni yechishda ishlatiladi. Bunday masalalarni yechishda, geometrik konfiguratsiyalarda nuqtalar bir -biri bilan to'g'ri chiziq yoki yoy bilan birlashtirilganmi, bularning uzunligi qancha kabi faktorlar etiborga olinmaydi. Eng muhimi shundaki, har bir chiziq qandaydir berilgan ikkita nuqtani birlashtirayapti. Shunday qilib, grafning ta'rifini quyidagicha berishi mumkin. ta'rif. To'plam V=a1,a2,…,an va V to'plamdan olingan juftliklar E=(ai1, aj1),…,(aik, ajk) naboriga Graf deyiladi. V to'plamdagi a1,…,an lar qandaydir obyektlar bo'lib G grafning uchlari deyiladi. Ye to'plamdagi har bir (ai1, aj1),…,(aik, ajk) juftlik Grafning qirralari deyiladi. Agar (ai, aj) qirra berilgan bo'lsa, u holda ai, va aj uchlar birlashtirilgan deyiladi. Misol. Agar V=a1, a2, a3, a4, a5, a6, a7,va E=(a1,a2)(a2,a2)(a2,a3)(a3,a4)(a4,a5)(a5,a6)(a6,a5) bo'lsin, u holda V va Ye to'plam G grafni hosil qiladi. Grafning uchlarini tugunlar, 2 ta uchini birlashtiruvchi chiziqni qirralar deb ataymiz. Grafning ikkita tuguni umumiy qirra bilan o'zaro bog'langan bœlsa, ular qo'shni tugunlar deyiladi. Agar G ning 2 ta qirrasi umumiy tugunga ega bo'lsa, ular qo'shma qirralar deyiladi. Misol. (a1 a2) qirra ( a2 a3) qirraga qo'shma, chunki a2 umumiy tugunga ega. Birorta tugunni o'zini - o'ziga bog'laydigan qirraga sirtmoq deyiladi. Barcha tugunlari yolg'iz tugundan iborat graf nol (bo'sh) graf deyiladi. Agar G grafning barcha tugunlari o'zaro bog'langan bo'lsa, bunday graf to'liq graf deyiladi. Agar G grafning barcha qirralarida yo'nalish ko'rsatilgan bo'lsa, bunday graf yo'naltirigan graf deyiladi. Agar G grafning qirralarida yo'naltirish ko'rsatilmagan bo'lsa, u ќolda graf yo'naltirilmagan graf deyiladi. G| graf G grafning qismi deyiladi, agar G| ning tugunlari to'plami G ga tegishli bo'lsa, yani V|V bo'lsa, hamda G| ning barcha qirralari G ning ham qirralar bo'lsa, yani Ye| E V=a, v, c, d, V|=a|, b|, c|, d|, V| V . G Graf G grafning to'ldiruvchisi diyiladi, agarda uning barcha tugunlari G grafga tegishli bo'lib, birorta ham qirrasi G ga tegishli bo'lmasa. 2 Qo'shmalik matritsasi. Bizga G yo'naltirilmagan graf berilgan bo'lib, u chekli bo'lsin. Aytaylik (a1,…,an), G grafning qirralari bo'lsin. U holda qo'shmalik matritsasi Aij, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo'ladi, Aij matritsaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo'yamiz. U holda Aij= šoidadan foydadanib šœshmalik matritsasini ќosil šilamiz. Misol. Agar G yo'naltirilgan graf bo'lsa, u holda Aij= šoidadan foydadanib šœshmalik matritsasini ќosil šilamiz. Misol. 3 Qo'shnilik matritsasi. Faraz qilaylik G graf yo'naltirilmagan bo'lsin. Grafning ...