ماتریس وقوع

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

مثال

یک گراف بی‌سو (غیرجهت‌دار)

ماتریس وقوع گراف بی‌سوی شکل سمت چپ به صورت زیر است:

$\left(\begin{array}{cccc}1& 1& 1& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 1\end{array}\right)$

جستارهای وابسته

• ماتریس مجاورت