المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:گراف:ماتریس ها و نمایش گراف

برای سادگی محاسبات می توان گراف ها را به صورت ماتریسی نشان داد.

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

تصور کنید $G(V, E)$ یک گراف ساده است که تعداد رئوس آن برابر با $n$ می باشد. تصور کنید که رئوس $G$ به صورت دلخواه همانند $v_1,v_2,...,v_n$ لیست شده اند. ماتریس مجاورت $A$ با توجه به لیست رئوس، یک ماتریس $n\times n$ صفر و یک است که در صورتی $(i, j)$ برابر ۱ است که $v_i$ و $v_j$ با یکدیگر مجاور باشند و نیز در صورتی برابر صفر است که آن ها با یکدیگر مجاور نباشند.
ماتریس مجاورت یک گراف ساده متقارن است.
ماتریس مجاورت همچنین می تواند برای نمایش گراف های بی جهت با حلقه ها و یال های چندگانه نیز استفاده شود. با این وجود دیگر به دلیل وجود یال ها و حلقه های چندگانه ماتریس مجاورت یک ماتریس صفر و یک نیست.
تمامی گراف های بی جهت از جمله گراف های چندگانه و شبه گراف ها دارای ماتریس مجاورت متقارن می باشند.
مثال: با استفاده از ماتریس مجاورت شبه گراف شکل زیر را نشان دهید. $$\left[\begin{array} 00 & 3 & 0 & 2\\ 3 & 0 & 1 & 1\\ 0 & 1 & 1 & 2\\ 2 & 1 & 2 & 0 \end{array}\right]$$ ما برای نمایش گراف های جهت دار نیز می توانیم از ماتریس صفر و یک استفاده کنیم.
در ماتریس مجاورت برای گراف جهت دار $G(V, E)$ هنگامی $(i, j)$ برابر ۱ می شود که $v_i$ به $v_j$ وجود داشته باشد در صورتی که رئوس گراف جهت دار $G$ به صورت دلخواه همانند $v_1,v_2,...,v_n$ لیست شده باشند.
ماتریس مجاورت برای گراف های جهت دار متقارن نیستند زیرا در آن ها لزومی ندارد که اگر یال از $v_i$ به $v_j$ وجود داشته باشد، از $v_j$ به $v_i$ نیز موجود باشد.
ماتریس های مجاورت همچنین می تواند برای گراف های جهت دار چندگانه نیز استفاده شود که در آن صورت از شکل ماتریس صفر و یک در می آید.

ماتریس وقوع

راه رایج دیگر برای نشان دادن گراف ها استفاده از ماتریس وقوع می باشد.
تصور کنید $G(V, E)$ یک گراف بی جهت است و $v_1,v_2,...,v_n$ رئوس آن و $e_1,e_2,...,e_m$ یال های آن می باشند.
ماتریس وقوع با توجه به ترتیب $V$ و $E$ یک ماتریس $n \times m$ می باشد به صورتی که $m_{ij}$ هنگامی برابر ۱ است که $e_j$ با $v_i$ برخورد داشته باشند و در غیر این صورت ۰ می باشد.
ماتریس وقوع همچنین می تواند برای نمایش یال ها و حلقه های چندگانه مورد استفاده قرار گیرد.
مثال: شبه گراف زیر را با استفاده از ماتریس وقوع نمایش دهید.
$$\begin{array} 1 & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 & e_8\\ v_1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ v_2 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0\\ v_3 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ v_4 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ v_5 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array}$$


ابزار صفحه