| 1-bobning xulosasi
BMI ning birinchi bobida asosan mavzuni bayon qilishda kerak bo’ladigan graflar nazariyasining elementlarini o’rganishga bag’ishlangan. Birinchi bob to’rtta bo’limdan iboratdir. Birinchi bo’limda graflar nazariyasidan umumiy ma’lumotlar keltirilgan, ikkinchi bolimda esa graflaming berilish usullari bayon qilingan. Uchinchi bo’lim graflar ustida amallarga, to’rtinchi bo’lim esa graflar nazariyasining tatbiq qilinish sohalariga bag’ishlangan.
II-bob
Graflar ustida matematik anailz elementlari.
2.1§ Laplas operatori
Bizga da aniqlangan funksiya berilgan bo’lsin. Malumki ,
Tenglik o’rinli bo’lib, yetarlicha kichik larda
munosabatlar o’rinlidir.
Operatorlar ayirmali operatorlar deyiladi va ularni hosilaning sonli approksimmasiyasi sifatida qarash mumkin. Ikkinchi tartibli hosilaning sonli approksimasiyasinitopamiz:
Shundayqilib, ikkinchitartiblihosilafunksiyaningqo’shnibo’lganvanuqtalaridagio’rtaqiymatidanniayirishbilananiqlarekan.
daaniqlanganfunksiyauchunikkinchitartiblixususiyhosilalarvalarshungao’xshashsonliapproksimasiyalarinitopishmumkin. Keyin esa bundan foydalanib
Laplas operatorining sonli approksimasiyasini hisoblash mumkin. Umumiy holda ta o’zgaruvchili funksiya uchun Laplas operatori
kabi aniqlanadi.
Bu operator uch o’lchamli fazoda 1784- 1785 yillarda Pierre- Simon Laplace tomonidan o’rganilgan.
(2.1) ko’rinishdagi laplas operatori ikki o’lchamli holda quyidagi approksimasiyaga ega:
Ya’ni funksiya funksiyaning ushbu
qo’shni nuqtalardagi o’rta qiymatidan ni ayirish bilan aniqlanar ekan.
Bu muloxazalar istalgan grafdagi Laplas operatorining diskret analogini aniqlashusulini beradi.
Ta’rif. Faraz qilay yakkalangan nuqtalarga ega bo’lmagan lokal finit graf bo’lib bo’lsin Har bir funksiya uchun funksiyani quyidagicha aniqlaymiz:
ga aniqlangan operator dagi Laplas operatori deyiladi.
Boshqacha aytganda funksiya barcha uchlardagi larning o’rta arfmetik qiymati va ning ayirmasiga teng ekan. Shuni ta’kidlash lozimki, funksiyaning qiymatlar soxasi bo’lgan ni bo’yicha ixtiyoriy vektor fazo bilan almashtirish mumkin, masalan bilan.
Masalan panjara grafi uchun
tenglik o’rinli, uchun
tenglik o’rinlidir.
Ta’rif.ga vaznli graf deyiladi agar V graf va μ funksiya VxV da berilgan nomanfiy funksiya bo’lib qo’yidagi shartlarni qanoatlantirsa:
1. μxy =μyx;
2. μxy> 0 faqat va faqat x va y qo’shni bo’lsa.
Laplas operatori tushunchasini vazinli graf holigaquyidaicha tushuntirish mumkin.
Ta’rif. Faraz qilaylik yakkalangan nuqtalarga ega bo’lmagan lokal finit vaznli graf bo’lsin. Istalgan funksiya uchun funksiyani
kabi aniqlaymiz. Bundaµ
dagi funksiyalarda aniqlangan operatorga dagi vazinli Laplas operatori deyiladi.
Takidlash kerakki, (2.2) dagi yig’indi bilan cheklanishi mumkin, chunki boshqa holda bo’ladi. Shu sababli, funksiya uchlardagi ning ayirmasiga tengdir. Laplas operatori vazinli Laplas operatorining xususiy holidir. Bunga ishonch hosil qilish uchun vazinni soda, ya’ni barcha larda deb olish yetarlidir.
orqaki dagi barcha haqiqiy qiymatli funksiyalar to’plamini belgilaymiz. U holda tabiiyki to’plam funksiyalarni qo’shish va songa ko’paytirish amallariga nisbatan chiziqli fazo bo’ladi. U holda ni dagi operator sifatida qarash mumkin, ya’ni . Takidlash kerakki dagi chiziqli operatordir, ya’ni
Tenglik barcha funksiyalar va soni uchun bajariladi. bu operatorning (2.2) ta’rifidan bevosita oson kelib chiqadi.
Boshqa muhim xossani keltiramiz:
Bunga o’xshash xossa differensial Laplas operatori uchun ham o’rinlidir. Haqiqatan ham, agar bo’lsa u holda
Bundan esa yuqoridagi xossa kelib chiqadi.
Mos Markov yadrosi
Ekanligini hisobga olib, ni quyidagicha
yozish mumkin. Markov yadrosini funksiyaga ta’sir qiluvchi ushbu
Operator sifatida ham qarash mumkin. Demak Laplas operatori va Markov operatori ushbu
ayniyat bilan bo’g’langan ekan, bu yerda orqali dagi birlik operator belgilangan.
Misol. dagi ni ning turli va qiymatlari uchun approksimasiya qilamiz:
Shunday qilib, mos ravishda va vaznlarga ega bo’lgan va larning vaznli o’rta qiymatini hosil qilamiz. Bu o‘rta qiymat baznli Laplas operatori sifatida quyidagiga tadbiq qilinishi mumkin. Quyidagicha aniqlangan haqiqiy sonlar kerakliligini ko'ramiz:
Masalan , va hokazo. deb olamiz va dagi uchlar to’plami ni yordamida aniqlaymiz. Endi vaznli uchlarda
kabi aniqlaymiz. U holda
tanglikka ega bo’lamiz, va dagi har bir funksiya uchun
ni hosil qilamiz.
| 