ماتریس تلاقی

یک راه معمول برای نمایش گراف ها، استفاده از ماتریس های تلاقی است.
فرض کنید G ( V , E ) یک گراف بدون جهت است. فرض کنید e 1 , e 2 , . . , e m یال ها و v 1 , v 2 , . . , V m رئوس گراف G هستند.
ماتریس تلاقی نسبت به این ترتیب از e و v ماتریس M = n ∗ m ماتریس است که:
m i j =
اگر یال ei با vj متلاقی باشد انگاه: 1
در غیر اینصورت: 0
از ماتریس های تلاقی همچنین می توان برای نمایش یال های چندگانه و حلقه ها استفاده کرد. یال های چندگانه در ماتریس تلاقی، به صورت ستون هایی با درایه های یکسان نمایش داده می شوند، زیرا این یال ها با زوج رئوس یکسانی متلاقی هستند. حلقه ها، توسط ستونی با دقیقاً یک درایه متناظر با رأس متلاقی با این حلقه، نمایش داده می شوند.