منو
 صفحه های تصادفی
بانک مرکزی جمهوری اسلامی ایران
نظام الدین عبدالعلی بن محمد حسین بیرجندی حنفی
دیوپتر
رشته باغبانی
valley fever
اطلاعات بیشتر پیرامون تجارت الکترونیکی
غیبت امام زمان - هشدار پیامبر اکرم
آینه های دی الکتریک
محمد خان بلوچ
سلسله مراتب شهرها
 کاربر Online
645 کاربر online
تاریخچه ی: لیست مجاورت

تفاوت با نگارش: 1

Lines: 1-34Lines: 1-34
 ||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:
 !لیست مجاورت !لیست مجاورت
 همانطور که ملاحظه فرمودید ((ماتریس مجاورت )) و ((ماتریس وقوع )) هر دو علی رغم کارائی خود، خانه های خالی بسیاری در ماتریس خود دارند و این علاوه بر اتلاف حافظه، موجب اتلاف زمان نیز خواهد گردید. به عنوان مثال یک گراف تهی 100 راسی ماتریس مجاورت {TEX()} {100\times 100} {TEX} می خواهد که تمام خانه های آن خالی هستند. همانطور که ملاحظه فرمودید ((ماتریس مجاورت )) و ((ماتریس وقوع )) هر دو علی رغم کارائی خود، خانه های خالی بسیاری در ماتریس خود دارند و این علاوه بر اتلاف حافظه، موجب اتلاف زمان نیز خواهد گردید. به عنوان مثال یک گراف تهی 100 راسی ماتریس مجاورت {TEX()} {100\times 100} {TEX} می خواهد که تمام خانه های آن خالی هستند.
 براساس ماتریس مجاورت، گراف را به روش دیگری که آن را لیست مجاورت می نامند و نیز نگه داری می کنند و آن عبارت از این است که لیستی از رئوس{TEX()} {v_1} {TEX} تا {TEX()} {v_n} {TEX} داریم و در هر خانه این لیست اشاره گری به اولین همسایه آن خانه موجود می باشد. و از آنجا هم اشاره گری به دومین همسایه آن و الی آخر. براساس ماتریس مجاورت، گراف را به روش دیگری که آن را لیست مجاورت می نامند و نیز نگه داری می کنند و آن عبارت از این است که لیستی از رئوس{TEX()} {v_1} {TEX} تا {TEX()} {v_n} {TEX} داریم و در هر خانه این لیست اشاره گری به اولین همسایه آن خانه موجود می باشد. و از آنجا هم اشاره گری به دومین همسایه آن و الی آخر.
 به عبارتی، به هر خانه لیست رئوس {TEX()} {v_1} {TEX} تا{TEX()} {v_n} {TEX}، همسایه های آن در یک لیست پیوندی نسبت داده می شوند. به عبارتی، به هر خانه لیست رئوس {TEX()} {v_1} {TEX} تا{TEX()} {v_n} {TEX}، همسایه های آن در یک لیست پیوندی نسبت داده می شوند.
 --- ---
 !!مثال !!مثال
 ::{picture=img/daneshnameh_up/a/a9/mco0059a.jpg} ::  ::{picture=img/daneshnameh_up/a/a9/mco0059a.jpg} ::
 به جزئیات ساخت لیست پیوندی و تعریف دقیق‌آن در مباحث مربوطه خواهیم پرداخت ولی فعلاً نیاز به آشنایی مقدماتی می باشد. به جزئیات ساخت لیست پیوندی و تعریف دقیق‌آن در مباحث مربوطه خواهیم پرداخت ولی فعلاً نیاز به آشنایی مقدماتی می باشد.
 --- ---
 !!سوال !!سوال
  میزان حافظه مورد نیاز لیست وقوع را بدست آورید.  میزان حافظه مورد نیاز لیست وقوع را بدست آورید.
 هر راس {TEX()} {v_i} {TEX} در لیست های پیوندی به تعداد درجه خود ظاهر می شود زیرا زمانی در لیست می آید که همسایه راس دیگری باشد. هر راس {TEX()} {v_i} {TEX} در لیست های پیوندی به تعداد درجه خود ظاهر می شود زیرا زمانی در لیست می آید که همسایه راس دیگری باشد.
 پس مجموع تعداد ظهور تمام رئوس برابر با مجموع کل درجات و این یعنی دو برابر تعداد یالها می باشد. پس مجموع تعداد ظهور تمام رئوس برابر با مجموع کل درجات و این یعنی دو برابر تعداد یالها می باشد.
 که بجز این تعداد به تعداد رئوس خانه هم برای نگه داری خانه های سر لیست های پیوندی لازم بوده پس جمعاً {TEX()} {|V|+2|E|} {TEX} خانه در حافظه مورد نیاز می باشد. که بجز این تعداد به تعداد رئوس خانه هم برای نگه داری خانه های سر لیست های پیوندی لازم بوده پس جمعاً {TEX()} {|V|+2|E|} {TEX} خانه در حافظه مورد نیاز می باشد.
 --- ---
 !تمرین !تمرین
  ماتریس مجاورت، ماتریس وقوع و لیست مجاورت گراف زیر را بدست آورید.  ماتریس مجاورت، ماتریس وقوع و لیست مجاورت گراف زیر را بدست آورید.
 ::{picture=img/daneshnameh_up/a/aa/mco0059b.jpg}:: ::{picture=img/daneshnameh_up/a/aa/mco0059b.jpg}::
 ::{picture=img/daneshnameh_up/5/5b/mco0059c.jpg}:: ::{picture=img/daneshnameh_up/5/5b/mco0059c.jpg}::
 --- ---
 ! پیوند های خارجی ! پیوند های خارجی
 [http://Olympiad.roshd.ir/computer/content/pdf/0092.pdf] [http://Olympiad.roshd.ir/computer/content/pdf/0092.pdf]
 --- ---
 !همچنین ببینید !همچنین ببینید
 *((ماتریس مجاورت )) *((ماتریس مجاورت ))
 *((ماتریس وقوع )) *((ماتریس وقوع ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [12:33 ]   2   زینب معزی      جاری 
 دوشنبه 20 شهریور 1385 [09:46 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..