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

نمونه‌ای از ماتریس مجاورت یک گراف برچسب دار. به عنوان مثال، در این گراف بین رأس ۱ و ۲ یک یال وجود دارد، بنا بر این درایه (۱،۲) ماتریس یک می‌باشد.

نمونه‌ای از ماتریس مجاورت یک گراف برچسب دار. به عنوان مثال، در این گراف در رأس ۶ یک طوقه وجود دارد بنابر این درایه (۶،۶) گراف یک می‌باشد.

در ریاضیات گسسته و علوم کامپیوتر، ماتریس مجاورت یک گراف برچسب دار (به انگلیسی: Adjacency matrix)‏ ماتریسی است که حاوی اطلاعات مربوط به تعداد یال‌هایی بین رأس‌های مختلف گراف است می‌باشد. بصورت دقیقتر ماتریس مجاورت یک گراف متناهی $G$ (جهت‌دار یا غیرجهت‌دار) با $n$ رأس، یک ماتریس $n$×$n$ می‌باشد درایهٔ $a_{ij}$ آن برابر با تعداد یال‌هایی که دو رأس $v_i$ و $v_j$ را به هم متصل می‌کند می‌باشد (درایه قطری $a_{ii}$ تعداد طوقه‌های رأس $i$ را نشان می‌دهد). پس در کل تعداد ۱های (۱‌هایی که روی قطر اصلی نیستند) ماتریس مجاورت دو برابر تعداد یال‌ها است.

برای هر گراف یک ماتریس مجاورت منحصر به فرد (یکتا) وجود دارد و هیچ ۲ ماتریسی یک ماتریس مجاورت ندارند. (در این مقاله موضوع اصلی غالباً گراف‌های غیر جهت دار اند، گراف‌های جهت نیز حالت و زیرمجموعه‌ای از گراف‌های غیرجهت دار اند و از آنها پیروی می‌کنند.)

اگر گراف مورد نظر، گرافی ساده و متناهی باشد، ماتریس مجاورت آن یک ماتریس (۰و۱) (دودویی، یعنی درایه‌های آن فقط ۰ و ۱ اند). اگر گراف غیرجهت دار هم باشد، ماتریس مجاورت آن متقارن خواهد بود و تمام درایه‌های قطر اصلی آن الزاماً صفر است.

قوانین کلی

• تمام درایه‌های ماتریس مجاورت یک گراف کامل ۱ است به جز درایه‌های روی قطر اصلی.
• تمام درایه‌های ماتریس مجاورت یک گراف خالی صفر اند.

ماتریس مجاورت گراف دو قسمتی

ماتریس مجاورت A مربوط به یک گراف دو قسمتی است که دو بخش آن r و s رأس دارند.

$A=\begin{pmatrix}
  O & B \\
  B^T & O 
\end{pmatrix}$

B ماتریس حاصلضرب r و s است (r×s) و O ماتریس تمام صفر است. واضح است که منحصراً نشان دهندهٔ ماتریس‌های دوقسمتی است و معمولاً یه آن ماتریس مجاورت دوقسمتی می‌گویند. اگر (G = (U, V, E یک ماتریس ۲ قسمتی به صورت $U={u_1,..., u_r}$ و $V={v_1,..., v_s}$ باشد . ماتریس r×s که فقط درایه‌های ۰ و ۱ دارد (ماتریس B) ماتریس مجاورت گراف دوقسمتی نامیده می‌شود درصورتی که:

$B_{i,j} = 1$

اگر و فقط اگر

$(u_i, v_j) \in E$.

اگر G یک گراف دوقسمتی چندگانه یا یک گراف وزن دار باشد، عناصر $B_{i,j}$ تعداد یال‌های بین دو رأس ($u_i,v_j$) یا وزن بین دو رأس را به ترتیب نشان می‌دهند.

ویژگی‌ها

ماتریس مجاورت یک گراف سادهٔ غیرجهت دار متقارن است و بنابراین مجموعه‌ای کامل از مقدار ویژه‌های حقیقی و یک بردار ویژهٔ متعامد دارد. (basis) مجموعهٔ مقدار ویژه‌های یک گراف، طیف آن گراف را تشکیل می‌دهند. فرض کنید ۲ گراف (جهت دار یا غیر جهت دار) $G_1$ و $G_2$ با ماتریس مجاورت‌های $A_1$ و $A_2$ داده شده‌اند. $G_1$ و $G_2$ هم ریخت (متناظر/isomorphic) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت P به طوری که :

$P A_1 P^{-1} = A_2.$

$A_1$ و $A_2$ در خصوصیات شبیه یه یکدیگرند، بنابراین، مینیمم، چندجمله‌ای، چند جمله‌ای ویژه، دترمینان و مجموع عناصر قطر داخلی آنها یکسان است. درنتیجه به عنوان گراف‌های متناظر یکدیگر در نظر گرفته می‌شوند.

با این حال ممکن است دو گراف مجموعهٔ مقدار ویژه‌های برابر داشته باشند ولی متناظر نباشند. اگر Aماتریس مجاورت گراف جهت دار یا غیر جهت دار G باشد، ماتریس $A_n$ تفسیر جالبی دارد: درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای به طول n بین دو رأس $v_i$ و $v_j$ را نشان می‌دهد. قطر اصلیِ ماتریس مجاورتِ هر گرافِ بدون طوقه‌ای، تماماً صفر است.

برای گراف (d)-منتظم (که d همچنین یک مقدار ویژهٔ A هم هست)، برای بردار $v=\left( 1,...,1 \right)$، گراف G همبند است اگر و تنها اگر تعدد d‌ها بیش از ۱ نباشد. می‌توان نشان داد که اگر G گراف همبند دوبخشی باشد،–d نیز یک مقدار ویژهٔ آن است. تمام اینها نتایج نظریهٔ پرُن-فربنیوس (Perron–Frobenius theorem) است.

این جمله غلط است که: ماتریس I-A (که I ماتریس همانی n×n است) وارون پذیر هستند اگر و فقط اگر هیچ دور مستقیمی در گراف G نباشد. در این مورد، وارون این گراف یعنی $(I-A)^{-1}$ چنین تفسیری دارد: درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای مستقیم از رأس i به رأس j را نشان می‌دهد (که اگر دور مستقیمی وجود نداشته باشد، همیشه این تعداد متناهی است.). این را می‌توان با استفاده از سری هندسی برای ماتریس‌ها فهمید  : $(I-A)^{-1} = I+A+A_2+A_3+\cdots$

که این متناظر است با اینکه تعداد مسیرها بین i و j برابر است با تعداد مسیرها به طول ۱ بعلاوهٔ تعداد مسیرها به طول ۲، بعلاوهٔ تعداد مسیرها به طول ۳ الی آخر.

ساختمان داده

در زمینهٔ ساختمان داده، اصلی‌ترین چیزی که با ماتریس مجاورت رقابت می‌کند، لیست مجاورت است. چون هر درایه در ماتریس مجاورت تنها ۱ بیت نیاز دارد، پس می‌توانند به صورت فشرده‌ای تنها با اشغال کردنn۲/۸ فضای پیوسته، نشان داده شوند (که n تعداد رأس هاست.). علاوه بر جلوگیری از هدر رفتن فضا، این فشردگی باعث بهبود و نزدیک تر شدن مکانی ارجاع‌ها می‌شود. از طرف دیگر، در گراف‌های کم یال، لیست مجاورت برنده‌است، زیرا آنها برای نشان دادن یال‌هایی که اصلا نبوده‌اند فضایی استفاده نمی‌کنند. با استفاده از یک پیاده سازی ساده با آرایه بر روی یک کامپیوتر ۳۲ بیتی، یک لیست مجاورت برای یک گراف غیر جهت دار حدود ۸e بایت حافظه نیاز دارد که e تعداد یال هاست.

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

در نمایش ماتریس مجاورت یک گراف (G=(V,E، فرض می‌کنیم رأس‌ها از ۱ تا |V| شماره گذاری شده‌اند و ماتریسی |V| × |V| به صورت (A=(a_ij اینگونه تعریف شده‌است:

اگر یال (i,j) در E باشد aij = ۱ در غیر این صورت aij = ۰.

شکل‌های ۱.b و ۲.b به ترتیب ماتریس‌های مجاورت گراف‌های بدون جهت و جهت دار ِ شکل‌های ۱.a و ۲.a هستند. ماتریس مجاورت یک گراف مستقل از تعداد یال‌ها، به(Ѳ(V۲ حافظه نیاز دارد. تقارن موجود در ماتریس شکل ۱.b را نسبت به قطر اصلی مشاهده می‌کنید. ترانهاده‌ی یک ماتریس (A=(a_ij را به صورت (A^T=(a_Tij که در آن a^Tij = aji. از آنجا که در یک گراف بدون جهت، (u,v) و (v,u) هردو یک یال را نمایش می‌دهند، ترانهادهٔ ماتریس مجاورتِ A از یک گراف بدون جهت برابر با خودش است: A=A^T. در برخی کاربردها نیاز می‌شود که فقط مقادیر روی قطر و بالای آن را ذخیره کنیم که در نتیجه میزان حافظهٔ مصرفی تقریباً نصف می‌شود.

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

منابع

در ویکی‌انبار پرونده‌هایی دربارهٔ ماتریس مجاورت موجود است.

• ریاضیات گسسته و کاربردهای آن (انگلیسی)

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (۲۰۰۱), Introduction to Algorithms, second edition. MIT Press and McGraw-Hill. ISBN ۰-۲۶۲-۰۳۲۹۳-۷. Section ۲۲٫۱: Representations of graphs, pp. ۵۲۷–۵۳۱.

• Chris Godsil and Gordon Royle (۲۰۰۱), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1