ماتریس تلاقی

یک راه معمول برای نمایش گراف‌ها، استفاده از ماتریس‌های تلاقی است.

mat.image

gra.image

فرض کنید $G(V,E)$ یک گراف بدون جهت است. فرض کنید $e_1,e_2,..,e_m$ یال‌ها و $v_1,v_2,..,V_m$ رئوس گراف G هستند.

ماتریس تلاقی نسبت به این ترتیب از e و v ماتریس $[mij]M=n*m$ ماتریس است که:

m i j =

اگر یال ei با vj متلاقی باشد انگاه: 1

در غیر اینصورت: 0

از ماتریس‌های تلاقی همچنین می‌توان برای نمایش یال‌های چندگانه و حلقه‌ها استفاده کرد. یال‌های چندگانه در ماتریس تلاقی، به صورت ستون‌هایی با درایه‌های یکسان نمایش داده می‌شوند، زیرا این یال‌ها با زوج رئوس یکسانی متلاقی هستند. حلقه‌ها، توسط ستونی با دقیقاً یک درایه متناظر با رأس متلاقی با این حلقه، نمایش داده می‌شوند.