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

||V{maketoc}||

^@#16:

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

ماتریس مجاورت به طورکلی در گراف {TEX()} {G} {TEX} ( چه ساده باشد چه عمومی چه چند گانه و ... ) به صورت زیر تعریف می گردد:

اگر رئوس {TEX()} {G} {TEX} را با {TEX()} {v_n,\cdots ,v_2,v_1} {TEX} نمایش دهیم ماتریس مجاورت آن ماتریسی{TEX()} {n\times n} {TEX}می باشد که درایه {TEX()} {A_{ij}} {TEX} آن برابر است با تعداد یالهایی که{TEX()} {v_i} {TEX} را به {TEX()} {v_j} {TEX} متصل می کند.

بدیهی است در گراف های غیر جهت دار{TEX()} {A_{ij}=A_{ji}} {TEX}یعنی ماتریس متقارن می باشد.

حال اگر گراف طوقه نداشته باشد

@@ {TEX()} {\forall i :A_{ii}=0} {TEX} @@

یعنی درایه های روی قطر اصلی همگی صفر می باشند.

و اگر گراف چند گانه نباشد آنگاه

@@{TEX()} {A_{ij}=1} {TEX} یا{TEX()} {\forall i,j: A_{ij}=0} {TEX}@@

زیرا بین هر دو راس {TEX()} {v_i,v_j} {TEX} حداکثر یک یال می تواند وجود داشته باشد.

لذا به راحتی دیده می شود ماتریس مجاورت یک گراف ساده ماتریس متقارن با درایه های 0 و1 می‌باشد که تمام درایه های قطر اصلی آن الزاماً‌ 0 است.

---

دو مثال از ماتریس های مجاورت:

::{picture=img/daneshnameh_up/3/36/mco0057a.jpg}::

::{picture=img/daneshnameh_up/9/97/mco0057b.jpg}::

ماتریس مجاورت نسبت به دو روش بعدی یعنی ((ماتریس وقوع ))و ((لیست مجاورت )) کاربرد بیشتری دارد زیرا قابل فهم تر، ساده تر و نسبتاً با حافظه کم می باشد.

---

!تمرین

اگر{TEX()} {A} {TEX}((ماتریس)) مجاورت گراف ساده {TEX()} {G} {TEX} باشد. درایه های{TEX()} {A^2} {TEX}معرف چه چیزی می باشند؟

__حل__

درایه های {TEX()} {A^2} {TEX} یعنی {TEX()} {A_{ij}^2} {TEX} معرف تعداد مسیرهای به طول 2 بین{TEX()} {v_i,v_j} {TEX} می باشد زیرا

@@{TEX()} {A_{ij}^2=\sum_{k=1}^n A_{ik} \times A_{kj}=\sum_{k=1}^n A_{ik}\times A_{jk}} {TEX}@@

که {TEX()} {A_{ik}\times A_{jk}} {TEX} زمانی 1 می شود که هم از{TEX()} {i} {TEX} به {TEX()} {k} {TEX} و هم از {TEX()} {k} {TEX} به {TEX()} {j} {TEX} یالی باشد. و گرنه 0 می شود پس به ازای هر مسیر به طول 2 بین {TEX()} {j,i} {TEX}، یک واحد به مجموع فوق افزوده می گردد و این یعنی مجموع فوق تعداد مسیرهای به طول 2 بین {TEX()} {v_i,v_j} {TEX} را می شمارد.

---

!تمرین

اگر {TEX()} {A} {TEX} ماتریس مجاورت گراف {TEX()} {G} {TEX} باشد ثابت کنید{TEX()} {A_{ij}^m} {TEX}برابر با تعداد مسیرهای به طول{TEX()} {m} {TEX}بین {TEX()} {v_i,v_j} {TEX} می باشد.

به استقرا روی {TEX()} {m} {TEX}ثابت می کنیم:

برای {TEX()} {m=1} {TEX} که بدیهی و برای {TEX()} {m=2} {TEX} هم در تمرین قبل ثابت کردیم.

فرض کنیم برای {TEX()} {m=k-1} {TEX}، {TEX()} {A_{ij}^{k-1}} {TEX} تعداد مسیرهای به طول {TEX()} {k-1} {TEX} مابین {TEX()} {v_j,v_i} {TEX} باشد.

برای{TEX()} {m=k} {TEX} داریم:

{TEX()} {A_{ij}^k=A\times A^{k-1}=\sum_{L=1}^n A_{iL}\times A_{Lj}^Pk-1}} {TEX}

که {TEX()} {A_{iL}\times A_{Lj}^{k-1}} {TEX} وقتی صفر می شودکه {TEX()} {A_{iL}=0} {TEX} یعنی یالی بین {TEX()} {v_L,v_i} {TEX} نباشد. یا{TEX()} {A_{Lj}^{k-1}=0} {TEX} یعنی بنا بر فرض استقرا تعداد مسیرهای به طول {TEX()} {k-1} {TEX} بین {TEX()} {v_L,v_i} {TEX}، 0 نباشد. که واضح است که در هر دو صورت مسیری به طول {TEX()} {k} {TEX} بین {TEX()} {v_L,v_i} {TEX} وجود نخواهد داشت.

و {TEX()} {A_{iL}\times A_{Lj}^{k-1}} {TEX} اگر{TEX()} {A_{iL}=1} {TEX}و{TEX()} {A_{Lj}^{k-1}\neq 0} {TEX}باشد برابر با{TEX()} {A_{ij}^{k-1}} {TEX} می شود یعنی در این صورت چون یالی بین {TEX()} {v_L,v_i} {TEX} وجود دارد پس می توان با یک گام از{TEX()} {v_i} {TEX} به{TEX()} {v_L} {TEX} آمد و پس از آن برای رفتن به {TEX()} {v_j} {TEX} با {TEX()} {k-1} {TEX}گام بنابر فرض استقرا {TEX()} {A_{Lj}^{k-1}} {TEX} طریق موجود می باشد.

لذا {TEX()} {A_{iL}\times A_{Lj}^{k-1}} {TEX} تعداد مسیرهای به طول{TEX()} {k} {TEX} را می شمرد که در گام اول از {TEX()} {v_i} {TEX} به {TEX()} {v_L} {TEX} برویم.

و از آنجا که در گام اول از {TEX()} {v_i} {TEX} به هر کدام از رئوس همسایه آن می توانیم برویم کل تعداد مسیرهای به طول بین{TEX()} {v_j,v_i} {TEX} برابر با مجموع فوق می گردد.

لذا {TEX()} {A_{ij}^k=\sum_{L=1}^n A_{iL}\times A_{Lj}^{k-1}} {TEX}

برابر است با تعداد مسیرهای به طول {TEX()} {k} {TEX} بین {TEX()} {v_j,v_i} {TEX}

---

!تمرین

از روی ماتریس مجاورت گراف {TEX()} {G} {TEX}ماتریس بسازید مانند {TEX()} {O} {TEX} که {TEX()} {O_{ij}^m} {TEX} برابر باشد با تعداد مسیرهای حداکثر به طول {TEX()} {k} {TEX} بین{TEX()} {v_j,v_i} {TEX}.

__حل__

کافی است {TEX()} {O=A+I} {TEX}

یعنی درایه های قطر اصلی را یک کنیم زیرا

اگر درایه های قطر اصلی را یک کنیم یعنی برای هر راس یک طوقه در نظر گرفته ایم و واضح است که تعداد مسیرهای دقیقاً به طول{TEX()} {m} {TEX} در این گراف جدید برابر است با تعداد مسیرهای به طول حداکثر {TEX()} {m} {TEX} در گراف قبلی زیرا به ازای هر مسیر با طول کمتر از{TEX()} {m} {TEX} در گراف قبل با تعداد کافی دور زدن در یکی از طوقه ها می توان طول آن را به{TEX()} {m} {TEX} رساند.که می دانیم تعداد مسیرهای به طول دقیقاً {TEX()} {m} {TEX} در گراف جدید{TEX()} {O_{ij}^m} {TEX} می‌باشد.

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0090.pdf]

---

!همچنین ببینید

*((ماتریس وقوع ))

*((لیست مجاورت))

#@^