ماتریس تلاقی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

ماتریسهای تلاقی[ویرایش]

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

mat.image
gra.image

فرض کنید یک گراف بدون جهت است. فرض کنید یال ها و رئوس گراف G هستند.

ماتریس تلاقی نسبت به این ترتیب از e و v ماتریس ماتریس است که:

m i j =

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

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

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

منابع[ویرایش]

Kenneth H, Rosen (1998). "Graphs". Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. Check date values in: |بازبینی= (help)