ماتریس مجاورت (Adjacency Matrix)، در ریاضیات (Mathematics)
ماتریس مجاورت (Adjacency Matrix) برای نمایش گراف ها (Graph) به کار می رود. یعنی وقتی در ریاضیات با گراف ها (Graph) کار می کنیم، اگر بخواهیم آنها را به صورت ماتریس در بیاوریم و محاسباتمان را بر اساس ماتریس انجام دهیم، یکی از روش های تعریف گراف ها به صورت ماتریس، استفاده از ماتریس مجاورت (Adjacency Matrix) می باشد.
ماتریس مجاورت (Adjacency Matrix) برای گراف بدون جهت (Undirected Graph) :
اگر یک گراف بدون جهت (Undirected Graph) دارای n گره (رأس - Node) باشد :
\[ V = \{v_1, v_2, ..., v_n\} \]آنگاه ماتریس مجاورت (Adjacency Matrix) آن دارای اندازه $ n \times n $ خواهد بود :
\[ A = [a_{ij}]_{n \times n} \]هر عنصر (درایه) از ماتریس نشان می دهد که آیا بین دو گره مربوط به آن عنصر (درایه)، یال (Edge) وجود دارد یا خیر. اگر یال (Edge) وجود داشته باشد، مقدار عنصر برابر 1 و اگر یال وجود نداشته باشد، مقدار عنصر برابر 0 خواهد بود :
\[ {a_{ij}} = \left\{ {\matrix{ 1 \hfill & {{\rm{if }}({v_i},{v_j}) \in E} \hfill \cr 0 \hfill & {{\rm{otherwise}}} \hfill \cr } } \right. \]یعنی اگر بین گره های i و j یال وجود داشته باشد، مقدار عنصر $ $${a_{ij}}$$ $ برابر 1 خواهد بود و اگر یال وجود نداشته باشد، مقدار عنصر برابر 0 خواهد بود.
ماتریس مجاورت (Adjacency Matrix) برای گراف جهت دار (Directed Graph - Digraph) :
اگر یک گراف جهت دار (Directed Graph - Digraph) دارای n گره (رأس - Node) باشد :
\[ V = \{v_1, v_2, ..., v_n\} \]آنگاه ماتریس مجاورت (Adjacency Matrix) آن دارای اندازه $ n \times n $ خواهد بود :
\[ A = [a_{ij}]_{n \times n} \]در گراف جهت دار (Directed Graph - Digraph)، یال ها دارای جهت می باشند. بنابراین اگر یک یال از گره i به گره j وجود داشته باشد آنگاه مقدار عنصر $ a_{ij} $ برابر 1 خواهد بود :
\[ a_{ij} = 1 \]ماتریس مجاورت (Adjacency Matrix) برای گراف وزن دار (Weighted Graph) :
اگر یک گراف وزن دار (Weighted Graph) دارای n گره (رأس - Node) باشد :
\[ V = \{v_1, v_2, ..., v_n\} \]آنگاه ماتریس مجاورت (Adjacency Matrix) آن دارای اندازه $ n \times n $ خواهد بود :
\[ A = [a_{ij}]_{n \times n} \]در گراف وزن دار (Weighted Graph)، هر یال دارای یک مقدار وزن (Weight) می باشد. اگر یال بین گره های i و j وجود داشته باشد، وزن (Weight) مربوط به آن یال را برای عنصر $ $${a_{ij}}$$ $ قرار می دهیم و اگر یال وجود نداشته باشد، مقدار 0 یا بینهایت ( $ $$\infty $$ $ ) برای آن عنصر قرار داده می شود :
\[ a_{ij} = \begin{cases} w_{ij} & \text{if } (v_i, v_j) \in E \\ 0 \text{ یا } \infty & \text{otherwise} \end{cases} \]