ماتریس تلاقی

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

فرض کنید $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

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

منابع ویرایش

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