تاریخچه ی:
ماتریس وقوع
||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__||
^@#16:
!ماتریس وقوع
ماتریس وقوع در حقیقت قرار گرفتن رئوس بر روی یالها را مستقیماً مشخص می کند و به صورت زیر تعریف می شود.
اگر گراف{TEX()} {G} {TEX} با مجموعه رئوس{TEX()} {V(G)} {TEX} و مجموعه یالهای {TEX()} {E(G)} {TEX} داشته باشیم ماتریس وقوع آن از اندازه {TEX()} {|V|\times |E|} {TEX} بوده و اگر آن را با {TEX()} {M} {TEX} نشان دهیم آنگاه {TEX()} {M_{ij}} {TEX} برابر است با اینکه آیا راس {TEX()} {v_i} {TEX} روی یال {TEX()} {e_j} {TEX} قرار گرفته است یا نه.
( اگر آری، 1 و گرنه مقدار0 اختیار می کند)
---
!!سوال
حافظه ای که ماتریس وقوع نیاز دارد بیشتر است یا حافظه مورد نیاز ماتریس مجاورت.
جواب کاملاً بستگی به گراف ما بخصوص تعداد یالها دارد بدین معنی که در گراف تهی ماتریس وقوع از اندازه{TEX()} {|V|\times O} {TEX} یعنی 0 می باشد ولی ماتریس مجاورت همواره از اندازه {TEX()} {|V|\times |V|} {TEX}می باشد. اما در بدترین حالت حجم ماتریس مجاورت کمتر است زیرا در بدترین حالت تعداد یالها مضربی از {TEX()} {|V|\times |V|} {TEX} بوده و لذا حجم ماتریس وقوع برابر با {TEX()} {|V|\times |E|} {TEX} یعنی مضربی از {TEX()} {|V|^3} {TEX} می باشد.
---
!خصوصیات ماتریس وقوع
1.در ماتریس وقوع همواره مجموع اعداد هر ستون 2 می باشد. زیرا هر ستون معرف یک یال بوده و هر یال تنها دو سر دارد!
2.مجموع اعداد هر سطر برابر با درجه آن راس می باشد زیرا بیانگر تعداد یالهایی است که این راس یکی از دو سر آن می باشد.
3.عناصر ماتریس وقوع، 0 یا 1 می باشند اگر طوقه نداشته باشد.
---
!!مثال
::{picture=img/daneshnameh_up/5/54/mco0058a.jpg}::
---
!تمرین
اگر {TEX()} {M} {TEX} ماتریس وقوع گراف {TEX()} {G} {TEX} باشد. آیا مانند ماتریس مجاورت برای درایه های{TEX()} {M^2} {TEX}خصوصیت خاصی وجود دارد یا می توان گفت{TEX()} {M} {TEX} تقارنی یا قطر اصلی آن 0 می باشد؟
__جواب__
خیر هیچ کدام در حالت کلی بر قرار نمی باشد. اولاً چون در حالت کلی {TEX()} {|V|} {TEX} با {TEX()} {|E|} {TEX} برابر نیست پس همواره{TEX()} {M^2} {TEX} تعریف نمی شود.
از طرفی باز چون {TEX()} {M} {TEX} مربعی نیست{TEX()} {M} {TEX} نمی تواند تقارنی باشد. از طرفی راس {TEX()} {v_i} {TEX} به راحتی می تواند بر یال {TEX()} {e_j} {TEX} قرار بگیرد و درایه {TEX()} {M_ii}=1} {TEX} گردد پس قطر اصلی آن هم در حالت کلی برابر 0 نمی تواند باشد.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0091.pdf]
---
!همچنین ببینید
*((ماتریس مجاورت))
*((لیست مجاورت))
#@^