ماتریس وقوع

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