طرحبندی گراف: تبدیل طرح یک-پشته به طرح دو-صف
الموضوعات : Statistics
1 - فارغ التحصیل ارشد، دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر
2 - استادیار دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر
الکلمات المفتاحية: Graph Drawing, Graph Queue Layout, Graph Layout, Graph Stack layout,
ملخص المقالة :
طرحبندی یک گراف یافتن ترتیبی خطی به رئوس آن و بخشبندی یالهای آن به صفها یا پشتهها با توجه به ترتیب اتخاذ شده میباشد. در این مقاله هدف ما پیدا کردن یک رابطه میان طرح پشته و طرح صف یک گراف دلخواه است و یک روش برای تبدیل این دو طرح به یکدیگر ارائه خواهیم کرد. الگوریتمی ارائه میکنیم که طرح یک-پشته هر گرافی را به به طرح دو-صف آن گراف تبدیل میکند و درستی الگوریتم را اثبات میکنیم. این روش، بطور مسقیم و بدون در نظر گرفتن گراف اصلی و خواص آن، طرح پشتهی یک گراف را تبدیل به یک طرح صف میکند. به عنوان نتیجه، این روش میتواند کمک کند که اگر برای دستهای خاص از گرافها عدد پشته محدود داشته باشیم، ممکن است بدون تحلیل مستقیم طرح صف برای این دسته از گرافها به عدد صف مناسب و محدودی دست بیابیم. بنابراین الگوریتم ارائه شده در اینجا انگیزهای برای یافتن الگوریتمهای مشابه برای تبدیل طرحهای خطی به یکدیگر و یافتن پارامترهای محدود کننده بهتر و بهینهتر برای آنها خواهد بود.
