ماتریس وقوع

{incident matrix} [ریاضی] برای یک گراف، ماتریسی که سطرها و ستون های آن به ترتیب متناظر با رأس ها و یال های گراف اند و درایۀ (i, j ) اُم آن برابر 1 است هرگاه رأس i اُم بر یال j اُم واقع باشد و در غیر این صورت برابر صفر است

ماتریس وقوع عنوان ماتریسی است که برای توصیف توپولوژی یک گراف استفاده می شود. درایه های این ماتریس همگی صفر یا یک هستند. هر سطر این ماتریس معرف یک رأس و هر ستون آن معرف یک یال در گراف متناظر است. عدد داریهٔ i و j برابر ۱ خواهد بود اگر و تنها اگر رأس iام بر یال jام واقع شده باشد. در تعریف برخی از کتاب ها از ماتریس وقوع، جای سطرها و ستون ها عوض شده است و ماتریس حاصل ترانهادهٔ تعریف گفته شده در اینجا است. این ماتریس نخستین بار توسط گوستاو کیرشهف فیزیک دانِ آلمانی تعریف شد.
ماتریس وقوع گراف بی سوی شکل سمت چپ به صورت زیر است:

برای یک گراف، ماتریسی که سطرها و ستون‌های آن به‌ترتیب متناظر با رأس‌ها و یال‌های گراف‌اند و درایۀ (i, j) اُم آن برابر ۱ است هرگاه رأس i اُم بر یال j اُم واقع باشد و در غیر این صورت برابر صفر است.

💡 مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتمهای مناسب مانند الگوریتم دایکسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود.