Incidence Matrix — Grafning tugunlari va qirralari o‘rtasidagi tegishlilikni satr va ustunlar orqali ifodalovchi matritsa. Bu tushuncha algoritmlar va ma’lumotlar tuzilmalarida natijani aniq ifodalash, murakkablikni tahlil qilish hamda muqobil yechimlarni solishtirish uchun ishlatiladi.
Matematik ifoda
Yo‘naltirilmagan grafda har bir qirra ustunida uning ikki uchiga mos odatda ikkita 1 bo‘ladi. Yo‘naltirilgan graf uchun manba uch −1, qabul qiluvchi uch +1 bilan belgilanishi mumkin; ishora kelishuvi aksincha ham tanlanadi, ammo bir model ichida o‘zgarmas qoladi.
Incidence Matrixni tushunishda uning matematik ta’rifi bilan dasturiy ko‘rinishini ajratish muhim. Matematik model qaysi obyektlar va munosabatlar ruxsat etilishini belgilaydi; implementatsiya esa ularni massiv, ro‘yxat, xarita yoki boshqa tuzilma orqali saqlaydi. Bir xil model turli xotira va vaqt xususiyatlariga ega ko‘rinishlarda amalga oshirilishi mumkin. Shuning uchun “to‘g‘ri” tanlov faqat ta’rifga emas, bajariladigan so‘rovlar, kirish hajmi va yangilanish chastotasiga ham bog‘liq.
Hisoblashdagi vazifasi
Matritsa yordamida tugun darajasi, sikllar fazosi va oqimning saqlanish tenglamalari chiziqli algebra vositalari bilan o‘rganiladi. Elektr tarmoqlari, transport va optimallashtirish modellarida qirradagi miqdorlar vektori tugunlardagi balansga aynan shu matritsa orqali bog‘lanadi.
Incidence Matrixning foydasi faqat yakuniy javob bilan o‘lchanmaydi. U masalani qaysi qismlarga ajratish, qaysi invariantni saqlash va natijani qanday tekshirish mumkinligini ham ko‘rsatadi. Algoritm tanlanganda preprocessing, asosiy so‘rov, yangilash va natijani tiklash xarajatlari alohida baholanadi. Bir martalik hisoblash uchun ma’qul usul doimiy yangilanadigan xizmat uchun qimmat bo‘lishi mumkin.
Chegaralar va talqin
n tugun va m qirra uchun hajm n×m bo‘lib, siyrak grafda zich ko‘rinish ko‘p nol saqlaydi. Amaliy paketlar siyrak matritsa formatidan foydalanadi; self-loop, parallel qirra va yo‘nalish kelishuvi alohida hujjatlashtiriladi.
Incidence Matrix bilan ishlovchi dastur kirish shartlarini aniq tekshirishi kerak. Tugun yoki element identifikatorlari, yo‘nalish, vazn, tenglik va dublikat qoidalari oldindan kelishilmasa, nazariy jihatdan to‘g‘ri algoritm noto‘g‘ri model ustida ishlashi mumkin. Testlar minimal holat, bo‘sh kirish, uzilgan yoki takroriy ma’lumot, teng qiymatlar va eng yomon tartibni qamrab oladi. Katta kirishda natijaning o‘zi bilan birga xotira sarfi, bajarilish vaqti va I/O hajmi ham o‘lchanadi.
Kichik misol
Uch tugunli A—B—C yo‘lida ustunlar AB va BC ga tegishli. AB ustunida A va B satrlari, BC ustunida B va C satrlari belgilanadi; shu sabab B satridagi ikkita belgi uning ikki qirraga tutashganini ko‘rsatadi.
Amaliy hujjatda Incidence Matrix uchun kuzatiladigan kafolatlar alohida yoziladi: natijaning aniqligi, deterministikligi, murakkablik chegarasi va xato holatidagi xatti-harakat. Nazariy Big O bahosi kirish o‘sgandagi tendensiyani beradi, lekin kesh lokaliteti, disk murojaati va ma’lumot taqsimoti real tezlikka ta’sir qiladi. Shu bois kichik etalon implementatsiya bilan natijani solishtirish, so‘ng real ish yukida profil olish ishonchli tekshiruv usulidir.
+## Invariantlarni tekshirish
Matritsadan qirralarni qayta tiklab, ular asl Edge List bilan tengligi tekshiriladi. Yo‘naltirilgan holatda har oddiy qirra ustunidagi qiymatlar yig‘indisi nol, yo‘naltirilmagan holatda esa terminal belgilar soni ikki bo‘lishi kerak. Incidence Matrix implementatsiyasi uchun bu tekshiruvlar oddiy unit testdan kengroq bo‘lib, modelning asosiy matematik shartlarini nazorat qiladi. Etalon bilan farq topilsa, tasodifiy kirish minimal qarshi misolgacha kichraytiriladi; shu misol regressiya testiga qo‘shiladi.
Bog‘liq tushunchalar
incidence matrix, adjacency matrix, graph, vertex, edge, sparse matrix