ماتریس مجاورت چیست؟ – به زبان ساده + انواع گراف و حل مثال

ماتریس مجاورت یا Adjacency Matrix در ریاضیات عمومی نوعی ماتریس مربعی است و با نمایش اینکه کدام راس‌ها یا گره‌ها به هم متصل هستند، به توصیف یک گراف می‌پردازد. اگر دو راس گرافی توسط یک یال به هم متصل شده باشند، موقعیت متناظر در این ماتریس عدد $$1$$ است، در غیر این صورت عدد $$0$$ را داریم. در این مطلب از مجله فرادرس توضیح می‌دهیم ماتریس مجاورت چیست، چه فرمولی دارد و چگونه می‌توان از آن در زمینه نمایش انواع گراف استفاده کرد.

ماتریس مجاورت چیست و چه فرمولی دارد؟

ماتریس مجاورت یک ماتریس مربعی است که اتصالات در یک گراف متناهی را نشان می‌دهد. در این ماتریس، هر سطر و هر ستون مربوط به یک راس یا گره است. همچنین درایه‌های این ماتریس که معمولا $$0$$ یا $$1$$ هستند، وجود یا عدم‌‌وجود یال‌ بین راس‌ها را مشخص می‌کنند. به این ترتیب برای گرافی به نام $$G$$ با $$n$$ راس که به شکل $$v_1, v_2, ..., v_n$$ نامگذاری شده‌اند، ماتریس مجاورت $$A$$ ماتریسی $$n \times n$$ است که هر درایه $$a_{ij}$$ آن به شکل زیر تعریف می‌شود:

$$a_{ij} = \begin{cases}1 & \\0 \end{cases}$$

در رابطه بالا اگر یالی از $$v_i$$ تا $$v_j$$ وجود داشته باشد، $$a_{ij} = 1$$ است و در غیر این صورت $$a_{ij} = 0$$.

برای نمونه، تصویر بالا نوعی ماتریس مجاورت را نشان می‌دهد که برای توصیف یک گراف کامل بکار می‌رود. مفهوم ماتریس مجاورت کاربردهای گسترده‌ای در نظریه گراف، ریاضیات گسسته، ساختارهای داده و بسیاری از مسائل شبکه‌ای دارد.

همچنین در سطوح پایه بکارگیری این ماتریس به دانش‌آموزان کمک می‌کند تا روابط بین اشیا را بهتر درک کنند. به علاوه ماتریس مجاورت ارتباط نزدیکی با موضوعاتی مانند ماتریس متقارن و ماتریس رخداد یا ماتریس وقوع دارد. تسلط بر ماتریس‌ مجاورت، به یادگیری الگوریتم‌ها و ساختارهای داده‌ای پیچیده‌تر در آینده کمک می‌کند.

نمایش ماتریس مجاورت

اگر بخواهیم ماتریس مجاورت متناظر با یک گراف را رسم کنیم، کافی است به ویژگی‌های آن گراف از جمله تعداد و نام راس‌ها، تعداد و نام یال‌ها و همچنین جهت‌دار یا بی‌جهت بودن یال‌های آن توجه کنیم. برای مثال، فرض کنید برای گرافی رئوسی با نام‌های $$A,B,C,D$$ و یال‌هایی به شکل $$A-B$$ و $$A-C$$ و $$B-C$$ و $$C-D$$ را داریم که همگی بدون جهت هستند.

در این صورت ماتریس مجاورت متناظر با آن به شکل زیر نمایش داده می‌شود:

هر درایه با مقدار $$1$$ در این ماتریس نشان دهنده این است که دو راس توسط یک یال به هم متصل شده‌اند. از آنجایی که در توصیف این گراف این نکته ذکر شده است که یال‌ها جهت ندارند، پس لازم است برای مثال در مورد یال $$A-B$$ درایه متناظر با جهت معکوس یعنی $$B-A$$ را نیز برابر با $$1$$ در نظر بگیریم. در حالی که اگر این گراف جهت‌دار بود، یکی از این دو درایه صفر می‌شد. در بخش‌های بعد با ویژگی‌ جهت‌دار بودن، انواع گراف و ماتریس‌های مجاورت متناظر با آن‌ها بیشتر آشنا می‌شوید.

یادگیری ماتریس و هندسه تحلیلی با فرادرس

پیش از توضیح انواع ماتریس مجاورت، ابتدا قصد داریم چند فیلم آموزشی در زمینه مباحث مطرح شده در کتاب‌ هندسه تحلیلی متوسطه دوم را معرفی کنیم. مشاهده این دوره‌ها به شما کمک می‌کند تا از طریق مشاهده تصاویر، یادگیری عمیق‌تری داشته باشید. ضمن اینکه اغلب این آموزش‌ها همراه با حل مثال‌ها و تمرین‌های متنوعی است که به درک بهتر شما از موضوعات مختلف از جمله ماتریس‌ها کمک خواهد کرد:

• فیلم آموزش هندسه پایه دوازدهم رشته ریاضی و فیزیک فرادرس
• فیلم آموزش ریاضی پایه دوازدهم علوم تجربی فرادرس

انواع ماتریس مجاورت

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

• گراف‌های بی‌جهت: در یک گراف بی‌جهت اگر راس $$i$$ به راس $$j$$ متصل باشد، درایه $$(i,j)$$ و $$(j,i)$$ هر دو مساوی $$1$$ خواهند شد. در نتیجه ماتریس متقارن است.
• گراف‌های جهت‌دار: در یک گراف جهت‌دار درایه $$(i,j)$$ در صورتی برابر با $$1$$ است که یک یال از راس $$i$$ به راس $$j$$ وجود داشته باشد. در این حالت ممکن است ماتریس نامتقارن باشد.
• گراف‌های وزن‌دار: برای گراف‌هایی که یال‌ها دارای وزن (مانند مسافت) هستند، درایه $$(i,j)$$ می‌تواند به جای مقدار $$1$$ وزن یال را نشان دهد.

عملکرد و ویژگی‌ های ماتریس مجاورت

به‌طور خلاصه عملکرد ماتریس مجاورت توسط دو مورد زیر تعریف می‌شود:

• راس‌ها به عنوان سطر و ستون: برای گرافی با $$n$$ راس، ماتریس مجاورت یک ماتریس $$n \times n$$ خواهد شد.
• درایه‌ها نشان‌دهنده اتصالات: درایه $$1$$ در موقعیت $$(i,j)$$ نشان می‌دهد که یک یال بین راس $$i$$ و راس $$j$$ وجود دارد، در حالی که درایه $$0$$ نشان‌دهنده عدم‌وجود یالی مستقیم بین آن دو راس است.

فیلم آموزش ماتریس مجاورت گراف + ۲ نوع با مثال‌ (رایگان) در فرادرس

کلیک کنید

همچنین ویژگی‌های زیر را می‌توانیم از جمله مهم‌ترین ویژگی‌های یک ماتریس مجاورت در نظر بگیریم:

• اگر گراف بی‌جهت باشد، ماتریس مجاورت متقارن است، یعنی داریم: $$a_{ij}= a_{ji}$$.
• درایه‌های روی قطر اصلی حلقه‌های خودی یا Self Loops را نشان می‌دهند، به این معنا که اگر در آن راس حلقه وجود داشته باشد، درایه برابر با $$1$$ می‌شود و در غیر این صورت آن درایه $$0$$ است.
• جمع درایه‌های یک سطر یا ستون درجه یا Degree راس را نشان می‌دهد.
• ضرب ماتریس در خودش (به توان رساندن) اطلاعاتی درباره مسیرهایی با طول بیشتر را به ما نشان می‌دهد.
• در مورد گراف‌های وزن‌دار، مقدار $$1$$ با وزن یال جایگزین می‌شود.

نظریه گراف و ارتباط آن با ماتریس مجاورت

در این بخش مروری داریم بر نظریه گراف تا بهتر متوجه شوید مبنای ارتباط گراف‌‌ها و ماتریس مجاورت چیست. یک گراف عموما توسط نموداری مانند شکل سمت چپ در تصویر زیر نمایش داده می‌شود. همچنین این گراف را می‌توان در قالب ماتریسی به نام ماتریس مجاورت (شکل سمت راست) نمایش داد:

ماتریس مجاورت اطلاعات نمودار گراف را به شکل دیگری اما به‌طور دقیق بیان می‌کند. اصولا رسم نمودار گراف برای تجسم ساده‌تر است، اما شکل ماتریسی گراف نیز مفید است، چون امکان تحلیل و انجام محاسبات ریاضیاتی را برای ما فراهم می‌کند. همچنین با توجه به اینکه ماتریس در واقع جدولی از اعداد است، پس می‌توانیم آن را به‌راحتی توسط یک برنامه کامپیوتری پردازش کنیم. در ادامه با انواع گراف و ماتریس مجاورت هر کدام بیشتر آشنا خواهیم شد.

گراف ساده

گرافی که در ابتدای این بخش رسم شد، یک گراف ساده یا Simple Graph با چهار راس است که بین آن‌ها یال‌های ساده‌ای وجود دارد. در ماتریس مجاورت این گراف ساده، مقدار $$1$$ را داریم که نشان می‌دهد دو راس به هم متصل هستند و مقدار $$0$$ را برای حالتی داریم که راس‌ها به هم متصل نیستند. برای مثال، درایه متناظر با سطر $$A$$ و ستون $$B$$ برابر با $$1$$ است، چون بین این دو راس یک یال وجود دارد. اما درایه متناظر با سطر $$B$$ و ستون $$D$$ برابر با $$0$$ است، چون بین این دو راس هیچ یالی وجود ندارد.

نکته جالب توجه در نمایش ماتریسی این گراف این است که تمام درایه‌های روی قطر اصلی (با زمینه رنگ زرد) صفر هستند، چون هیچ راسی به خودش متصل نیست. برای نمونه، درایه متناظر با سطر $$A$$ و ستون $$A$$ صفر است، چرا که راس $$A$$ به خودش متصل نیست. همچنین توجه کنید که این ماتریس نسبت به قطر اصلی متقارن است، به این معنا که ناحیه‌ آبی رنگ انعکاسی از ناحیه سبز رنگ است. تقارن به این دلیل است که در یک گراف ساده، هر یال در هر دو جهت عمل می‌کند. برای مثال، اگر $$A$$ به $$B$$ متصل باشد، این به معنی آن است که $$B$$ هم به $$A$$ توسط همان یال متصل است.

گراف ساده با حلقه

این نوع گراف همان گراف ساده است، با این تفاوت که حداقل روی یک راس آن یک حلقه وجود دارد‌. برای مثال مطابق تصویر زیر، حلقه‌ای روی راس $$C$$ داریم، به این معنا که راس $$C$$ به خودش متصل است. به این ترتیب درایه متناظر با سطر و ستون $$C$$ برابر است با مقدار $$1$$ که نشان می‌دهد در گراف متناظر با این ماتریس مجاورت یک حلقه وجود دارد:

گراف جهت‌ دار

تصویر زیر نمودار یک گراف جهت‌دار را نمایش می‌دهد. در گراف جهت‌دار، هر یال فقط در یک جهت عمل می‌کند. برای مثال در گراف زیر یک یال از $$W$$ به $$X$$ وجود دارد، اما یالی از $$X$$ به $$W$$ وجود ندارد. دقت کنید یک گراف جهت‌دار لزوما نسبت به قطر اصلی متقارن نیست، چون وجود یک یال در یک جهت لزوما به معنای وجود یال در جهت مخالف آن نیست.

اگر اتصال دو راس دو طرفه باشد، این موضوع با دو یال نشان داده می‌شود. برای مثال یال بین دو راس $$W$$ و $$X$$ دو طرفه است. در این حالت در هر دو جایگاه ماتریس مقدار $$1$$ قرار می‌گیرد. همچنین یک حلقه نیز نشان داده شده است که طبق آن راس $$W$$ به خودش متصل است. این موضوع نیز با عدد $$1$$ مشخص می‌شود. باید دقت داشته باشید که حتی در یک ماتریس جهت‌دار، حلقه جهت ندارد. در حقیقت حلقه $$W$$ را به $$W$$ متصل می‌کند، بنابراین هیچ جهتی برای آن در نظر گرفته نمی‌شود.

گراف چندگانه

در یک گراف چندگانه یا Multigraph می‌توانیم بین دو راس، بیش از یک یال داشته باشیم. این گراف می‌تواند جهت‌دار یا بدون جهت باشد. در تصویر زیر نمونه‌ای از یک گراف چندگانه بدون جهت را ملاحظه می‌کنید. در این حالت، بین راس‌های $$C$$ و $$D$$ دو یال وجود دارد. همچنین ماتریس مجاورت در مورد این گراف کمی با ماتریس مجاورت گراف ساده متفاوت است، زیرا در اینجا هر درایه تعداد یال‌ها را نشان می‌دهد. چون تعداد یال‌های بین دو راس $$C$$ و $$D$$ برابر است با $$2$$، پس درایه متناظر نیز $$2$$ است.

همچنین اگر بین دو راس هیچ یالی وجود نداشته باشد، مقدار آن $$0$$ است (مشابه گراف ساده). به‌ عنوان مثال، درایه متناظر با یالی که بین دو راس $$A$$ و $$C$$ وجود دارد، برابر با $$0$$ است زیرا $$A$$ و $$C$$ به هم متصل نیستند. نکته دیگر این است که ماتریس بالا متقارن است، چون یک گراف بدون جهت را نمایش می‌دهد. اگر گراف جهت‌دار بود، ماتریس می‌توانست نامتقارن باشد. قطر اصلی این ماتریس نیز کاملا شامل مقادیر $$0$$ است، مگر اینکه گراف دارای حلقه باشد. این ویژگی نیز مشابه گراف ساده است.

گراف وزن‌ دار

در یک گراف وزن‌دار یا Weighted Graph هر یال دارای مقداری است که به آن وزن گفته می‌شود. گراف‌های وزن‌دار نیز می‌توانند جهت‌دار یا بدون جهت باشند، اما در اینجا فقط حالت بدون جهت را بررسی می‌کنیم. ماتریس مجاورت در گراف وزن‌دار، وزن یال‌ها را نشان می‌دهد. برای مثال، درایه‌های متناظر برای دو راس $$A$$ و $$C$$ و همچنین رئوس $$C$$ و $$A$$ هر دو برابر با $$3$$ است، زیرا یال بین $$A$$ و $$C$$ وزنی برابر با $$3$$ دارد.

برای حالتی که هیچ یالی وجود ندارد، باید از یک مقدار ویژه استفاده کنیم. در این مثال، از مقدار $$0$$ برای نشان دادن عدم وجود یال استفاده می‌کنیم، با این فرض که اگر یالی وجود داشته باشد، وزن آن نمی‌تواند صفر باشد. برای مثال، اگر گرافی نمایانگر یک شبکه جاده‌ای باشد و وزن‌ها نشان‌دهنده فاصله‌ها باشند، منطقی است که بگوییم هیچ جاده‌ای طول صفر ندارد، بنابراین می‌توانیم از $$0$$ برای نشان دادن عدم وجود جاده استفاده کنیم.

البته در برخی سیستم‌ها ممکن است داشتن یالی با وزن صفر معتبر باشد. در این صورت لازم است از مقدار دیگری برای نشان دادن عدم وجود یال استفاده شود (برای مثال $$-1$$ اگر وزن‌های منفی معتبر نباشند). گراف‌های چندگانه وزن‌دار را نمی‌توان به‌راحتی با ماتریس مجاورت نمایش داد، زیرا یک جفت راس می‌تواند چند مقدار (چند یال با وزن‌های متفاوت) داشته باشد.

گراف کامل

گراف کامل یا Complete Graph گرافی است که در آن هر راس به تمام راس‌های دیگر متصل است. در این نوع گراف، به جز درایه‌‌های روی قطر اصلی سایر درایه‌ها مخالف صفر هستند. این به این معنا است که بین هر جفت راس غیرمشابه یک یال وجود دارد. تصویر زیر این نوع گراف و ماتریس مجاورت آن را به‌خوبی نشان می‌دهد:

گراف‌ ایزومورف و ماتریس‌ جابجایی

به دو گراف در تصویر زیر ایزومورف یا یک‌ریخت گفته می‌شود، چنانچه گراف‌هایی معادل باشند که تنها تفاوت‌ آن‌ها در نامگذاری راس‌ها و / یا نحوه نمایش آن‌هاست. در حقیقت اگر به ماتریس‌های مجاورت دو گراف ایزومورف نگاه کنیم، آن‌ها یکسان هستند، به جز اینکه ممکن است ترتیب سطرها و ستون‌های آن‌ها متفاوت باشد.

در این بخش توضیح می‌دهیم یکی از کاربردهای مهم ماتریس مجاورت چیست. به کمک ماتریس مجاورت می‌توانیم ویژگی‌های مختلف یک راس را تعیین کنیم. توضیحات این بخش مربوط به گراف‌های ساده است، اما می‌توان این روش‌ها را برای گراف‌های جهت‌دار، وزن‌دار یا گراف‌های چندگانه نیز بکار برد.

فیلم آموزش ریاضیات گسسته پایه دوازدهم – مرور و حل مساله در فرادرس

کلیک کنید

به ماتریس مجاورت گراف ساده حلقه‌دار در تصویر زیر توجه کنید. همان‌طور که قبلا اشاره کردیم، قطر اصلی ماتریس مجاورت نشان می‌دهد که آیا گراف ما دارای حلقه است یا خیر. در این مثال، درایه‌‌های روی قطر اصلی صفر نیستند، بنابراین راس $$A$$ دارای یک حلقه است. همچنین می‌توانیم به‌راحتی درجه‌ یک راس، یعنی تعداد یال‌هایی که به آن متصل هستند را با توجه به ماتریس مجاورت بررسی کنیم. برای رسیدن به این هدف، کافی است تعداد یک‌ها را در سطر مربوط به آن راس جمع کنیم (در تصویر بالا می‌توانیم از ستون نیز استفاده کنیم، چون ماتریس داده شده متقارن است).

برای مثال راس $$D$$ درجه‌ $$3$$ دارد، زیرا سه عدد $$1$$ را در سطر $$D$$ داریم که در شکل با رنگ آبی مشخص شده‌‌اند. همچنین درجه راس $$B$$ نیز $$0$$  است، چون هیچ عدد برابر با یکی در سطر $$B$$ وجود ندارد (در شکل با رنگ صورتی مشخص شده است). این جمله به این معنا است که راس $$B$$ جدا افتاده است. با نگاه کردن به شکل گراف نیز این موضوع را مشاهده خواهید کرد.

از طرفی راس $$A$$ را داریم که یک حالت خاص است، چون حلقه دارد. حلقه به‌ عنوان دو اتصال شمرده می‌شود، چون دو بار به همان راس وصل می‌شود. بنابراین هنگام جمع‌ زدن تعداد یک‌های موجود در سطر، اگر درایه‌ قطر اصلی مقداری مخالف صفر داشته باشد، باید آن را به‌جای $$1$$ عدد $$2$$ در نظر بگیریم. پس در این مثال، راس $$A$$ درجه‌‌ای برابر با مقدار $$4$$ دارد. پس تا حدی یاد گرفتیم که چگونه می‌توان از ماتریس مجاورت برای تعیین ویژگی‌های یک گراف استفاده کرد. در همین راستا، اینکه آیا گراف ما درخت است یا خیر، متصل است یا خیر، دو بخشی است یا خیر و ... نیز با استفاده از الگوریتم‌های ساده‌ و قابل‌اجرا روی ماتریس مجاورت مشخص می‌شوند.

توان‌ های ماتریس مجاورت

در این بخش توضیح می‌دهیم منظور از توان‌های ماتریس مجاورت چیست. می‌دانیم ماتریس مجاورت یک گراف ساده را می‌توان به این صورت تفسیر کرد که مقدار درایه متناظر برای هر دو راس نوعی برابر با یک است، اگر بین آن دو راس یک یال وجود داشته باشد. بر این اساس، مجذور ماتریس مجاورت یعنی ماتریسی که در خودش ضرب شده است، ویژگی جالب دیگری ارائه می‌دهد. اگر مقدار عددی درایه متناظر برای دو راس نوعی $$i$$ و $$j$$ را با $$M[i,j]$$ نشان دهیم، در این صورت $$M^2[i,j]$$ برابر است با تعداد مسیرهای ممکن بین راس $$i$$ و $$j$$ که طول آن‌ها دقیقا برابر با $$2$$ است.

به همین شکل، توان سوم ماتریس مجاورت نیز الگوی مشابهی دارد. پس مقدار $$M^3[i,j]$$ برابر است با تعداد مسیرهای ممکن بین راس $$i$$ و راس $$j$$ که طول آن‌ها دقیقا برابر با $$3$$ است. برای توان‌های بالاتر نیز روند به همین صورت است. البته توجه داشته باشید که این ویژگی به عبورها یا Walks مربوط می‌شود، نه به مسیر‌ها یا Paths. گذر یا عبور مسیری بین دو راس است که اجازه دارد از یک راس بیشتر از یک بار عبور کند. برای مثال اگر بین دو راس $$A$$ و $$B$$ یک یال وجود داشته باشد، یک گذر با طول $$1$$ از $$A$$ به $$B$$ وجود دارد. اما ممکن است در کنار آن، یک گذر با طول $$3$$ هم وجود دارشته باشد که از $$A$$ به $$B$$ می‌رود، سپس به $$A$$ برمی‌گردد و دوباره به $$B$$ می‌رود.

حل مثال از ماتریس مجاورت

در بخش‌های قبل آموختیم مارتیس مجاورت چیست و چه ویژگی‌هایی دارد. در این بخش با بکارگیری نکات بیان شده، به حل چند نمونه مثال می‌پردازیم.

مثال ۱

ابتدا یک گراف بدون جهت با $$4$$ راس و $$3$$ یال رسم کنید:

• سپس ماتریس مجاورت آن را بنویسید.
• در این ماتریس مجاورت عدد $$1$$ به چه معنا است؟
• این ماتریس مجاورت را به یک لیست مجاورت تبدیل کنید:

پاسخ

دقت کنید برای رسم چنین گرافی می‌توان حالت‌های دلخواه متفاوتی را در نظر گرفت. اما مهم این است که ماتریس مجاورت آن به درستی نمایش داده شود. ما گراف زیر را در نظر گرفته‌ایم که دارای چهار راس با شمار‌ه‌های $$1$$ و $$2$$ و $$3$$ و $$4$$ است و سه یال $$2-1$$ و $$3-2$$ و $$4-1$$ در آن دیده می‌شود:

سپس ماتریس مجاورت متناظر با چنین گرافی را به شکل زیر خواهیم داشت، تعداد سطرها و ستون‌ها چهار است و با توجه به اینکه گراف بدون جهت است، ماتریس مجاورت متقارن خواهد بود:

می‌دانیم در این نمایش مقدار $$1$$ به معنای وجود یال و مقدار $$0$$ به معنای عدم‌وجود یال بین دو راس است. پس $$1$$ یعنی در گراف بدون جهت ما یک یال بین هر دو راس موردنظر وجود دارد یا به بیانی دیگر، آن دو راس مجاور هم هستند. در مورد سوال سوم، لیست مجاورت برای هر راس عبارت است از لیست راس‌هایی که به آن راس متصل‌اند. این لیست به شکل زیر است:

• $$1$$: راس $$2$$ و $$4$$
• $$2$$: راس $$1$$ و $$3$$
• $$3$$: راس $$2$$
• $$4$$: راس $$1$$

مثال ۲

اگر گراف چندگانه‌ای با مشخصات زیر داشته باشیم، ماتریس مجاورت آن به چه صورت است؟ در ادامه ویژگی‌های رئوس آن را بررسی کنید:

راس‌ها: $$A,B,C,D$$

یال‌ها: $$A-C , A-A, C-D, D-D, D-A$$

پاسخ

در این گراف چهار راس داریم، پس ماتریس مجاورت ما که یک ماتریس مربعی است، ماتریس چهار در چهاری خواهد بود که با توجه به یال‌های داده شده مقادیر عددی درایه‌های متناظر با این یال‌ها برابر با $$1$$ هستند. همچنین پیش از شروع دقت کنید، یال‌هایی به شکل $$D-D$$ و $$A-A$$ متناظر‌اند با حلقه روی راس‌های $$D$$ و $$A$$. با توجه به اینکه در صورت سوال به جهت‌دار بودن گراف اشاره‌ای نشده است، بنابراین یال‌ها جهت‌دار نیستند و لازم است اگر درایه متناظر با $$A-C$$ را برابر با $$1$$ در نظر می‌گیریم، درایه متناظر با $$C-A$$ را نیز $$1$$ فرض کنیم. به این ترتیب ماتریس مجاورت برای این گراف به شکل زیر خواهد شد:

حالا ویژگی‌های رئوس را به ترتیب بررسی می‌کنیم:

• راس $$A$$: درایه‌‌‌ قطر اصلی متناظر با این راس برابر است با $$1$$. پس روی راس $$A$$ یک حلقه داریم. همچنین مجموع درایه‌های سطر $$A$$ برابر است با $$1+1+1 = 3$$، اما چون روی این راس یک حلقه داریم، پس اولین $$1$$ دو مرتبه شمرده می‌شود و درجه راس $$A$$ برابر است با $$2+1+1 = 4$$.
• راس $$B$$: تمام مقادیر روی سطر $$B$$ برابر با صفر هستند. بنابراین درجه این راس نیز برابر است با صفر. به عبارت دیگر، می‌توانیم بگوییم راس $$B$$ یک راس جدا افتاده است.
• راس $$C$$: مجموع درایه‌های سطر $$C$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.
• راس $$D$$: درایه‌‌‌ قطر اصلی متناظر با این راس برابر است با $$1$$. پس روی راس $$D$$ یک حلقه داریم. همچنین مجموع درایه‌های سطر $$D$$ برابر است با $$1+1+1 = 3$$، اما چون روی این راس یک حلقه داریم، پس اولین $$1$$ دو مرتبه شمرده می‌شود و درجه راس $$D$$ برابر است با $$2+1+1 = 4$$.

مثال ۳

فرض کنید گرافی با مشخصات زیر داریم:

راس‌ها: $$A,B,C,D, E$$

یال‌ها: $$A-B , A-C, B-D, C-E, D-E$$

ماتریس مجاورت این گراف به همراه ویژگی‌های هر راس آن چگونه است؟

پاسخ

در این گراف پنج راس داریم، پس ماتریس مجاورت ما یک ماتریس مربعی پنج در پنج خواهد بود:

حالا ویژگی‌های رئوس را به ترتیب بررسی می‌کنیم:

• راس $$A$$: مجموع درایه‌های سطر $$A$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.
• راس $$B$$: مجموع درایه‌های سطر $$B$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.
• راس $$C$$: مجموع درایه‌های سطر $$C$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.
• راس $$D$$: مجموع درایه‌های سطر $$D$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.
• راس $$E$$: مجموع درایه‌های سطر $$E$$ برابر است با $$1+1 = 2$$ و حلقه‌ای نداریم. پس درجه این راس برابر است با $$2$$.

مقایسه ماتریس مجاورت با سایر روش‌ های نمایش گراف

جدول زیر سه روش اصلی برای نمایش گراف‌ها در علوم کامپیوتر و ریاضیات را مقایسه می‌کند که عبارت‌اند از ماتریس مجاورت، لیست مجاورت و ماتریس وقوع یا Incidence Matrix. هر کدام از این روش‌ها مزایا و معایب خاص خود را دارند و همین مسئله موجب شده است که آن‌ها را برای انواع مختلفی از گراف‌ها و الگوریتم‌ها مناسب بدانیم.

نمایش گراف توسط ماتریس مجاورت

در بخش‌های قبل گفتیم که ماتریس مجاورت یک آرایه دو بعدی مربعی به شکل $$V \times V$$ است که در آن $$V$$ تعداد رئوس گراف است. هر درایه $$(i,j)$$ در این ماتریس نشان‌دهنده وجود یا عدم‌وجود یک یال بین راس $$i$$ و راس $$j$$ است. فضای موردنیاز برای کار با این ماتریس فضای $$O(V^2)$$ است، به این معنا که فضای ذخیره‌سازی مورد‌نیاز به‌ شکل مجذور تعداد رئوس رشد می‌کند.

این روش برای گراف‌هایی با تعداد رئوس زیاد اما یال‌های کم بسیار ناکارآمد است، زیرا بخش زیادی از ماتریس با صفر پر می‌شود. در همین زمینه اگر تمایل دارید اطلاعات بیشتری به‌دست آورید، می‌توانید فیلم آموزش ریاضیات گسسته – پایه دوازدهم فرادرس را مشاهده کنید که لینک آن نیز برای دسترسی شما در ادامه قرار داده شده است:

فیلم آموزش ریاضیات گسسته – پایه دوازدهم در فرادرس

کلیک کنید

همچنین سرعت یافتن یال در مورد ماتریس مجاورت ثابت است، یعنی داریم $$O(1)$$ و این یکی از بزرگ‌ترین مزایای ماتریس مجاورت است. برای بررسی اینکه آیا یالی بین دو راس $$i$$ و $$j$$ وجود دارد یا خیر، کافی است به درایه $$a_{ij}$$ مراجعه کنیم و این کار در زمان ثابتی انجام می‌شود. بنابراین این ویژگی برای الگوریتم‌هایی که نیاز دارند مکررا وجود یال را بررسی کنند، بسیار بهینه است. بیشترین کاربرد برای ماتریس مجاورت در مورد گراف‌های چگال است. گراف چگال گرافی است که تعداد یال‌های آن به تعداد حداکثر یال‌های ممکن نزدیک است. در چنین گراف‌هایی ماتریس مجاورت فضای ذخیره‌سازی را به‌خوبی توجیه می‌کند و سرعت بالای جستجوی یال، آن را به گزینه‌ای عالی تبدیل می‌کند.

نمایش گراف توسط لیست مجاورت

لیست مجاورت یا Adjacency List آرایه‌ای از لیست‌ها است که در آن هر خانه آرایه (با اندیس $$i$$) یک لیست پیوندی دارد که شامل تمام رئوس مجاور با راس $$i$$ است. این روش به جای یک ماتریس بزرگ، از ساختارهای داده پویا استفاده می‌کند. فضای موردنیاز برای لیست مجاورت به شکل $$O(V+E)$$ است، به این مفهوم که این روش به مجموع تعداد رئوس و یال‌ها بستگی دارد. این مسئله باعث می‌شود که لیست مجاورت برای گراف‌هایی با تعداد یال‌های کم بسیار مناسب باشد، زیرا فقط یال‌های موجود ذخیره می‌شوند.

سرعت یافتن یال در مورد لیست مجاورت به شکل خطی، $$O(E)$$ یا $$O(deg(V))$$ است. برای بررسی وجود یال بین دو راس $$i$$ و $$j$$، باید لیست مربوط به راس $$i$$ را به‌طور کامل جستجو کنیم. در بدترین حالت، این زمان به تعداد یال‌های متصل به راس $$i$$ (درجه آن) وابسته است که در نهایت می‌تواند به $$O(V)$$ یا $$O(E)$$ برسد. به این ترتیب کاربرد لیست مجاورت در مورد گراف‌هایی با تعداد یال‌های کم است. از آنجایی که لیست مجاورت از فضای ذخیره‌سازی بهینه‌تری استفاده می‌کند و الگوریتم‌های پیمایشی مانند BFS و DFS به‌طور طبیعی با آن سازگار هستند، این روش انتخاب اول برای اکثر مسائل گراف است.

نمایش گراف توسط ماتریس وقوع

در نهایت ماتریس وقوع یا Incidence Matrix را داریم که یک ماتریس $$V \times E$$ است و در آن $$V$$ تعداد رئوس و $$E$$ تعداد یال‌ها است. یک درایه $$(i,j)$$ در این ماتریس نشان می‌دهد که آیا راس $$i$$ با یال $$j$$ در ارتباط است یا خیر. همچنین فضای موردنیاز در این نوع ماتریس $$O(V \times E)$$ است. بنابراین این روش می‌تواند به فضای زیادی نیاز داشته باشد، به‌ویژه در مورد گراف‌های بزرگ. سرعت یافتن یال برای ماتریس وقوع خطی یا $$O( E)$$ است. برای یافتن یال بین دو راس، باید کل ماتریس را جستجو کنیم که زمان زیادی می‌برد. بنابراین این روش برای اجرای عملیات‌ روزمره روی گراف ناکارآمد است.

در عین حال کاربرد ماتریس وقوع بیشتر در زمینه تحلیل‌های نظری و اثبات‌های ریاضی در نظریه گراف است و کاربرد عملی آن در الگوریتم‌ها کمتر است. پس انتخاب بین این سه روش به نوع گرافی که با آن سر و کار داریم، بستگی دارد. اگر گراف چگال است (یال‌های زیادی دارد)، ماتریس مجاورت به دلیل سرعت بالای جستجوی یال انتخاب بهتری است. اگر گراف تنک است یا یال‌های کمی دارد، لیست مجاورت به دلیل کارآمدی در فضای ذخیره‌سازی انتخاب برتر است و در عمل، در اکثر مسائل گراف از همین روش استفاده می‌شود. ماتریس وقوع نیز بیشتر جنبه نظری دارد و کاربردهای عملی آن محدود است.

همچنین پس از اینکه یاد گرفتیم تفاوت‌های دو روش دیگر نمایش گراف با ماتریس مجاورت چیست، بهتر است به نکات زیر حتما توجه کنیم:

• فراموش کردن وارد کردن هر دو خانه برای گراف‌های بدون جهت.
• فرض اینکه برای گراف‌هایی با تعداد راس‌ بالا ولی یال‌های کم باید از ماتریس مجاورت استفاده شود، در حالی که برای گراف‌های تنک بهتر است از لیست مجاورت استفاده کنید.
• اشتباه برچسب‌گذاری یا Labeling راس‌ها هنگام ساختن ماتریس، به این مفهوم که سعی کنید همیشه از یک ترتیب مشخص و واضح برای شماره‌گذاری استفاده کنید.

یادگیری گراف‌ ها و ریاضیات گسسته با فرادرس

یکی از مهم‌ترین مباحث درس ریاضی مقطع متوسطه دوم و به‌ویژه برای دانش‌آموزان رشته ریاضی، درس ریاضیات گسسته است. ریاضیات گسسته یا Discrete Mathematics بخشی از علم ریاضی است که به مطالعه ساختارها و عناصر گسسته می‌پردازد. مباحث مهمی که در ریاضیات گسسته مطرح می‌شوند عبارت‌اند از نظریه مجموعه‌ها، ترکیبیات و نظریه گراف که ماتریس مجاروت بخشی از این نظریه محسوب می‌شود. به همین علت در این بخش می‌خواهیم چند فیلم آموزشی از مجموعه فرادرس را به شما معرفی کنیم که در تمام آن‌ها بخشی از این مباحث توضیح داده شده است:

• فیلم آموزش رایگان گراف در ریاضیات گسسته
• فیلم آموزش ریاضیات گسسته پایه دوازدهم
• فیلم آموزش ریاضیات گسسته پایه دوازدهم – مرور و حل مساله

ماتریس مجاورت و برنامه‌ نویسی

در این بخش نشان می‌دهیم در محیط‌های برنامه‌نویسی از جمله پایتون یا ++C، روش استفاده از ماتریس مجاورت چیست. الگوریتم‌هایی مانند BFS و DFS می‌توانند از ماتریس مجاورت برای پیمایش گراف در مسائل کدنویسی استفاده کنند.

مثال ماتریس مجاورت در پایتون

در محیط پایتون می‌توانید از کد زیر برای استفاده از ماتریس مجاورت استفاده کنید:

# n = number of nodes adj_matrix = [[0 for _ in range(n)] for _ in range(n)] # Add an edge from node i to node j adj_matrix[i][j] = 1

مثال ماتریس مجاورت در ++C

همچنین در سی پلاس پلاس نیز کد زیر در زمینه محاسبه ماتریس مجاورت به شما کمک خواهد کرد:

// n = number of nodes vector<vector> adj_matrix(n, vector(n, 0)); // Add an edge from node i to node j adj_matrix[i][j] = 1;

سایر کاربردهای ماتریس مجاورت

در انتهای این مطلب از مجله فرادرس، کاربردهای ماتریس مجاورت را با هم مرور می‌کنیم. به‌طور کلی بخش عمده‌ای از کاربرد این نوع ماتریس در نظریه گراف و علوم کامپیوتر است. برای مثال محاسبات مربوط به تحلیل اتصال‌پذیری، درجه رئوس (تعداد یال‌های متصل به یک راس که با جمع زدن یک سطر یا ستون به دست می‌آید) و یافتن مسیر در نظریه گراف را می‌توان با استفاده از ماتریس مجاورت انجام داد.

همچنین در حوزه‌هایی از علوم کامپیوتر مانند نمایش شبکه‌، پیاده‌سازی الگوریتم‌های گراف و تحلیل روابط در ساختارهای داده می‌توان مفاهیم و محاسبات ماتریس مجاورت را بکار برد. بنابراین ماتریس‌ مجاورت فقط در ریاضیات کاربرد ندارد، بلکه نقش‌ مهمی در علم فیزیک (تحلیل شبکه)، علوم کامپیوتر (الگوریتم‌های گراف مانند BFS و DFS) و حتی استدلال منطقی در زندگی روزمره ایفا می‌کند.