منو
 کاربر Online
904 کاربر online
تاریخچه ی: ماتریس وقوع

در حال مقایسه نگارشها

نگارش واقعی نگارش:1


این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


ماتریس وقوع

ماتریس وقوع در حقیقت قرار گرفتن رئوس بر روی یالها را مستقیماً مشخص می کند و به صورت زیر تعریف می شود.
اگر گراف با مجموعه رئوس و مجموعه یالهای داشته باشیم ماتریس وقوع آن از اندازه بوده و اگر آن را با نشان دهیم آنگاه برابر است با اینکه آیا راس روی یال قرار گرفته است یا نه.
( اگر آری،‌ 1 و گرنه مقدار0 اختیار می کند)

سوال

حافظه ای که ماتریس وقوع نیاز دارد بیشتر است یا حافظه مورد نیاز ماتریس مجاورت.
جواب کاملاً بستگی به گراف ما بخصوص تعداد یالها دارد بدین معنی که در گراف تهی ماتریس وقوع از اندازه یعنی 0 می باشد ولی ماتریس مجاورت همواره از اندازه می باشد. اما در بدترین حالت حجم ماتریس مجاورت کمتر است زیرا در بدترین حالت تعداد یالها مضربی از بوده و لذا حجم ماتریس وقوع برابر با یعنی مضربی از می باشد.

خصوصیات ماتریس وقوع

1.در ماتریس وقوع همواره مجموع اعداد هر ستون 2 می باشد. زیرا هر ستون معرف یک یال بوده و هر یال تنها دو سر دارد!
2.مجموع اعداد هر سطر برابر با درجه آن راس می باشد زیرا بیانگر تعداد یالهایی است که این راس یکی از دو سر آن می باشد.
3.عناصر ماتریس وقوع، 0 یا 1 می باشند اگر طوقه نداشته باشد.

مثال

img/daneshnameh_up/5/54/mco0058a.jpg


تمرین

اگر ماتریس وقوع گراف باشد. آیا مانند ماتریس مجاورت برای درایه هایخصوصیت خاصی وجود دارد یا می توان گفت تقارنی یا قطر اصلی آن 0 می باشد؟
جواب
خیر هیچ کدام در حالت کلی بر قرار نمی باشد. اولاً چون در حالت کلی با برابر نیست پس همواره تعریف نمی شود.
از طرفی باز چون مربعی نیست نمی تواند تقارنی باشد. از طرفی راس به راحتی می تواند بر یال قرار بگیرد و درایه گردد پس قطر اصلی آن هم در حالت کلی برابر 0 نمی تواند باشد.

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

http://Olympiad.roshd.ir/computer/content/pdf/0091.pdf

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




این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


ماتریس وقوع

ماتریس وقوع در حقیقت قرار گرفتن رئوس بر روی یالها را مستقیماً مشخص می کند و به صورت زیر تعریف می شود.
اگر گراف با مجموعه رئوس و مجموعه یالهای داشته باشیم ماتریس وقوع آن از اندازه بوده و اگر آن را با نشان دهیم آنگاه برابر است با اینکه آیا راس روی یال قرار گرفته است یا نه.
( اگر آری،‌ 1 و گرنه مقدار0 اختیار می کند)

سوال

حافظه ای که ماتریس وقوع نیاز دارد بیشتر است یا حافظه مورد نیاز ماتریس مجاورت.
جواب کاملاً بستگی به گراف ما بخصوص تعداد یالها دارد بدین معنی که در گراف تهی ماتریس وقوع از اندازه یعنی 0 می باشد ولی ماتریس مجاورت همواره از اندازه می باشد. اما در بدترین حالت حجم ماتریس مجاورت کمتر است زیرا در بدترین حالت تعداد یالها مضربی از بوده و لذا حجم ماتریس وقوع برابر با یعنی مضربی از می باشد.

خصوصیات ماتریس وقوع

1.در ماتریس وقوع همواره مجموع اعداد هر ستون 2 می باشد. زیرا هر ستون معرف یک یال بوده و هر یال تنها دو سر دارد!
2.مجموع اعداد هر سطر برابر با درجه آن راس می باشد زیرا بیانگر تعداد یالهایی است که این راس یکی از دو سر آن می باشد.
3.عناصر ماتریس وقوع، 0 یا 1 می باشند اگر طوقه نداشته باشد.

مثال

img/daneshnameh_up/5/54/mco0058a.jpg


تمرین

اگر ماتریس وقوع گراف باشد. آیا مانند ماتریس مجاورت برای درایه هایخصوصیت خاصی وجود دارد یا می توان گفت تقارنی یا قطر اصلی آن 0 می باشد؟
جواب
خیر هیچ کدام در حالت کلی بر قرار نمی باشد. اولاً چون در حالت کلی با برابر نیست پس همواره تعریف نمی شود.
از طرفی باز چون مربعی نیست نمی تواند تقارنی باشد. از طرفی راس به راحتی می تواند بر یال قرار بگیرد و درایه گردد پس قطر اصلی آن هم در حالت کلی برابر 0 نمی تواند باشد.

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

http://Olympiad.roshd.ir/computer/content/pdf/0091.pdf

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



تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:34 ]   3   زینب معزی      جاری 
 دوشنبه 20 شهریور 1385 [08:37 ]   2   زینب معزی      v  c  d  s 
 دوشنبه 20 شهریور 1385 [08:37 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..