تاریخچه ی:
ماتریس وقوع
تفاوت با نگارش: 2
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| - | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
+ | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
| | ^@#16: | | ^@#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} قرار گرفته است یا نه. | | اگر گراف{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 اختیار می کند) | | ( اگر آری، 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} می باشد. | | جواب کاملاً بستگی به گراف ما بخصوص تعداد یالها دارد بدین معنی که در گراف تهی ماتریس وقوع از اندازه{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 می باشد. زیرا هر ستون معرف یک یال بوده و هر یال تنها دو سر دارد! | | 1.در ماتریس وقوع همواره مجموع اعداد هر ستون 2 می باشد. زیرا هر ستون معرف یک یال بوده و هر یال تنها دو سر دارد! |
| | 2.مجموع اعداد هر سطر برابر با درجه آن راس می باشد زیرا بیانگر تعداد یالهایی است که این راس یکی از دو سر آن می باشد. | | 2.مجموع اعداد هر سطر برابر با درجه آن راس می باشد زیرا بیانگر تعداد یالهایی است که این راس یکی از دو سر آن می باشد. |
| | 3.عناصر ماتریس وقوع، 0 یا 1 می باشند اگر طوقه نداشته باشد. | | 3.عناصر ماتریس وقوع، 0 یا 1 می باشند اگر طوقه نداشته باشد. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | ::{picture=img/daneshnameh_up/5/54/mco0058a.jpg}:: | | ::{picture=img/daneshnameh_up/5/54/mco0058a.jpg}:: |
| | --- | | --- |
| | !تمرین | | !تمرین |
| | اگر {TEX()} {M} {TEX} ماتریس وقوع گراف {TEX()} {G} {TEX} باشد. آیا مانند ماتریس مجاورت برای درایه های{TEX()} {M^2} {TEX}خصوصیت خاصی وجود دارد یا می توان گفت{TEX()} {M} {TEX} تقارنی یا قطر اصلی آن 0 می باشد؟ | | اگر {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()} {|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 نمی تواند باشد. | | از طرفی باز چون {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] | | [http://Olympiad.roshd.ir/computer/content/pdf/0091.pdf] |
| | --- | | --- |
| | !همچنین ببینید | | !همچنین ببینید |
| | *((ماتریس مجاورت)) | | *((ماتریس مجاورت)) |
| | *((لیست مجاورت)) | | *((لیست مجاورت)) |
| | #@^ | | #@^ |
