Jild. 3, No 4, 2015 issn 2309-0405

Shakl 6. Interferentsiya grafigi
Yuqoridagi 5-rasmda oddiy kompyuter tarmog'i va mos keladigan minimal cho'qqi qopqog'i {2, 4,
5} ko'rsatilgan.
Ushbu bo'limda biz tarmoqni grafik ko'rinishida modellashtirish va uni grafik rang berish
metodologiyasi yordamida hal qilish orqali simsiz LANda kanallarni taqsimlash masalasiga e'tibor
qaratamiz. Grafik modeli qurilgan va interferentsiya grafigi deb ataladi, chunki kirish nuqtalari bir
xil mintaqadagi boshqa kirish nuqtalariga xalaqit beradi. Grafik kirish nuqtalari tomonidan
tugunlar sifatida tuzilgan interferentsiya grafigi deb ataladi. Agar bitta kanaldan foydalanganda
tugunlar bir-biriga xalaqit bersa, bu tugunlarni yo'naltirilmagan chekka bog'laydi. Endi kanallarni
ajratish muammosi grafik rang berish muammosiga aylantirildi. ya'ni vertex rang berish
muammosi. F :v(G)ÿC cho'qqilarni bo'yash funktsiyasi, bu erda C - kirish nuqtalaridagi kanallarga
mos keladigan ranglar to'plami. Ushbu kanallar, afzalroq, bir-birining ustiga chiqmaydigan
qirralardir. Rang berish algoritmi mualliflar tomonidan rang berish uchun DSATUR (To'yinganlik
darajasi) deb nomlangan. Algoritm evristik qidiruvdir. Ya'ni, turli rangdagi qo'shnilarning eng ko'p
sonini topadi. Agar bu kichik to'plamda faqat bitta cho'qqi bo'lsa, u rang berish uchun tanlanadi.
Agar kichik to'plamda bir nechta cho'qqilar bo'lsa, rang berish rangsiz qo'shnilar sonini kamaytirish
tartibi asosida amalga oshiriladi. Agar bir nechta nomzod cho'qqilari mavjud bo'lsa, yakuniy
tanlov cho'qqini tanlash uchun deterministik tanlash funktsiyasi bilan almashtiriladi. Protokol
operatsiyasi kirish nuqtalari tomonidan yaratilgan xabarlarni tinglash orqali qo'shnilarni aniqlash
orqali amalga oshiriladi. Xabar kirish nuqtalari tomonidan qayta uzatilganda protokol operatsiyasi
tugaydi. Buni tugatgandan so'ng, interferentsiya grafigi tuziladi va rang berish algoritmi
qo'llaniladi. Kanallar va grafik o'rtasidagi yozishma shundaki, kanallar xabarlarni muntazam
ravishda tinglaganidek, rang berish algoritmi muntazam ravishda ishlayotgan bo'lishi kerak.
Zamin rejasi va tegishli interferentsiya grafigi quyida keltirilgan.