پاورپوینت ساختارهای اطلاعاتی و صف‌بندی گراف‌های سطحی آن‌ها

توضیحات

عنوان: ساختارهای اطلاعاتی و صف‌بندی گراف‌های سطحی آن‌ها

• چکیده
• 2- مقدمه
• 3- طرح پشته
• 4- بحث مقدماتی
• 5-گراف های deque  و طرح های هندسی خطی
• 6-خلاصه مقاله

چکیده

در یک طرح پشته (گاهی نیز به عنوان جاسازی کتاب نامیده می شود)، رئوس یک گراف بر روی یک خط قرار می گیرد و یک لبه، آیتم اطلاعاتی است که بر روی پشته و در راس چپ نشانده می شود و در راس راست حذف می شود. اصل  LIFO  پشته با استفاده از مجموعه ای از لبه های تودرتو نشان داده می شود. ما در اینجا  طرح های استوانه ای خطی  را برای توصیف عملکرد اصول ساختارهای اطلاعاتی پایه شامل، پشته، صف، پشته دوگانه و صف دوطرفه معرفی می کنیم. گراف هایی که به عنوان نتیجه بدست می آیند گراف های پشته (پشته، صف، پشته دوگانه و صف دوطرفه) نامیده می شوند. ما در اینجا امکان پذیری یک توالی از الحاقیات و حذفیات را با استفاده از پلاناریته مشخصه یابی می کنیم و از کلاس های گراف برای مقایسه توان نسبی این ساختارهای اطلاعاتی استفاده می کنیم. به صورت دقیق تر ما نشان خواهیم داد که گراف های صف دوگانه، گراف هایی دو وجهی بوده و زیر گراف هایی از گراف های دو وجهی با مسیر هامیلتونین است. گراف های پشته دو گانه گراف های با یک صفحه‌بندی خطی در صفحه هستند و به عنون زیر گراف هایی از گراف های دو وجهی با چرخه هامیلتونین شناخته می شند. از این رو، توان حالت صف، صف دوگانه با هر دو مورد اختلاف بین مسیر هامیلتونین و چرخه هامیلتونین و با طرح های خطی بر استوانه و در صفحه  توصیف می شود. طرح های استوانه ای خطی توصیف دو وجهی بصری از اصل FIFO یک صف تلقی می شود. ما نشان می دهیم که یک گراف صف تکمیل شده با استفاده از یک مسیرهامیلتونین، دارای یک دوگانه از همان نوع و یک مسیر دوگانه اویلری است. در نهایت مسائل شناخته شده را مورد بررسی قرار خواهیم دارد.

مقدمه

در ” Art of Computer Programming “[31]، D. E. Knuth به بررسی ساختارهای اطلاعاتی پایه از قبیل پشته، پشته دوگانه و صف پایانی دوگانه (صف دوطرفه) پرداخته است. در اینجا، یک ساختار اطلاعاتی (D) شامل لیستی با الحاقات و حذفیات آیتم های اطلاعاتی است. یک توالی آیتم های الحاقاتی و حذفیاتی زمانی موثر است که تمام اطلاعات در پایانه های D قرار گرفته و حذف شوند. D زمانی یک پشته تلقی می شود که حذفیات و الحاقات در سر باشد و آیتم های اطلاعاتی در سر قرار گرفته و حذف شوند. خروج به ترتیب ورود (LIFO) برای پشته و خروج به ترتیب ورود (FIFO) برای صف است. اگر هر آیتمی در طرفی که قرار می گیرد حذف شود/ D یک پشته دوگانه است و D زمانی که هیچ محدودیتی اعمال نمی شود یک صف دو طرف تلقی می شود. رفتار این ساختارهای اطلاعاتی می تواند با استفاده از گراف ها مدلسازی شود، جایی که هر آیتم اطلاعاتی با استفاده از یک لبه و علامت نقاط پایانی نقاط زمانی الحاق و حذف آن توصیف می شود. در ساختار اطلاعاتی، در هر زمان یک اجرا وجود دارد که نتیجه آن گراف هایی با رئوس درجه اول است. برای گراف های کلی، اگر خط زمانی کنش‌ها در هر راس حفظ شود، کنش ها در یک راس تجمیع می شوند. اگر و تنها اگر گراف به صورت دوسطحی تحت قیدهای خاص قرار گیرد، طرح ما اصول کاری D را ارضا می کند که این توسط یک صفحه‌بندی خطی توصیف می شود. یک صفحه‌بندی خطی از گراف غیرجهت دار  یک ترتیب دهی کلی  از راس ها است که در چب به راست بر یک خط افقی مطابق  قرار می گیرید. این جهتی را بر روی هر لبه  اعمال می کند (در این بخش ما یک  e  را با حالت جهت دار آن زمانی که    u باشد، شناسایی می کنیم). دو لبه  و  بدون هیچگونه نقاط پایانی مشترک و زمانی که u سه موقعیت برای موقعیت نسبی نقطه پایان خود دارند. اگر یک صفحه‌بندی خطی برای راس ها وجود داشته باشد، یک گراف  دارای ترتیبی خواهد بود و لبه ها با استفاده از ساختار اطلاعاتی D پردازش می شوند و هر لبه  برای D در u  گرفته و از D در   در صورت برقراری  u با ترتیب خطی حذف خواهد شد. اگر توالی حذفیات و الحاقات مناسب باشد، G یک گراف D نامیده می شود.

توجه:

• برای دانلود فایل پاورپوینت لطفا اقدام به خرید فرمایید.
• پس از خرید بلافاصله لینک دانلود فایل برای شما ایمیل خواهد شد.