ماتریس تلاقی

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

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

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

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)