نشاندن گراف
 | این مقاله، نشاندن گراف، اخیراً بهواسطهٔ فرایند ایجاد مقاله ایجاد شده‌است. بازبینیکننده در حال بستن درخواست است و این برچسب احتمالاً بهزودی برداشته می‌شود.
ابزارهای بازبینی: پیشبارگیری بحث اعلان به نگارنده |
خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد. در نظریهٔ گراف مکان‌شناسی، یک نشاندن از گراف G در یک رویهٔ ∑ یک نمایش از G بر ∑ است که هر نقطه از ∑ به رئوس هم پیوند شده‌اند و قوس‌های ساده (تصاویر همسان‌ریختی از [۰٬۱]) به این طریق به لبه‌ها هم‌پیوند شده‌اند:
- نقاط پایانی از قوس که به لبهٔ e هم پیوند شده‌اند، نقاطی هستند که به قوس‌های پایانی از e هم‌پیوند شده‌اند.
- هیچ‌کدام از قوس‌ها شامل نقاطی که با رئوس دیگر هم‌پیوندند نمی‌باشند،
- دو قوس هرگز یکدیگر را دریک نقطه که درون دو قوس قرار دارند قطع نمی‌کنند.
در اینجا یک رویه، مجموعه فشرده و متصل به تعداد زیادی از لایه‌ها می‌باشد.
به‌طور غیررسمی، یک نشاندن گراف بر روی یک رویه، ترسم یک گراف بر روی رویه به این صورت که لبه‌های آن ممکن است تنها در نقاط پایانی آن متقاطع شوند می‌باشد. اینگونه به خوبی شناخته شده‌است که هر گراف متناهی می‌تواند در فضای اقلیدسی سه بعدی و گراف مسطح در فضای اقلیدسی دو بعدی هم‌پیوند شوند.
غالب اوقات، یک نشاندن به صورت یک کلاس تعادل از نمایش‌هایی از نوعی که الان توصیف شد ملاحظه می‌شود (تحت همسان‌ریختی‌هایی از ∑).
بعضی از نویسندگان یک نسخهٔ ضعیف‌تر از تعریف «نشاندن گراف» با حذف کردن وضعیت غیر متقاطع برای لبه‌ها تعریف می‌کنند. در این زمینه‌ها تعریف باریک بینانه‌تر به صورت گراف نشاندن غیر متقاطع توصیف شده‌است.
این مقاله با تعریف باریک بینانه از گراف نشاندن سر و کار دارد. تعریف ضعیف‌تر در مقاله‌های «ترسیم گراف» و «عدد عبور» مطرح شده‌است.
اصطلاحات[ویرایش]
اگر گراف G در یک فضای بستهٔ ∑ نشانده شود، مکمل اجتماع نقاط و کمان‌های متصل به رئوس و لبه‌های G جزئی از ناحیه‌ها می‌باشد. یک نشاندن دوسلولی یا نگاشت، نوعی از نشاندن به طوری است که هر نما در یک فضای باز همریخت می‌باشد. یک نشاندن دوسلولی بسته نوعی از نشاندن است که در آن بستار هر نما با فضای بسته همریخت می‌باشد.
نوع هر گراف حداقل عدد صحیحی است که گراف می‌تواند درون یک سطح نوع n نشانده شود. به‌طور خاص یک گراف مسطح داری نوع صفر می‌باشد زیرا می‌تواند بر روی یک کره بدون تقاطع کشیده شود. گراف غیر جهت‌دار از نوع حداقل عدد صحیح n می‌باشد که گراف می‌تواند در یک سطح غیر جهت‌دار نوع n نشانده شود.
گراف نوع اویلر گرافیست از حداقل عدد صحیح n به طوری که گراف می‌تواند در یک سطح جهت دار نوع n/2 یا در یک سطح غیر جهت‌دار نوع n نشانده شود. یک گراف از نوع ساده جهت‌دار می‌باشد اگر عدد اویلر آن کوچکتر از عدد غیر جهت دار آن باشد.
نوع حداکثر گراف بزرگترین عدد صحیح n است که گراف می‌تواند به صورت دو سلولی در یک سطح جهت‌دار نوع n نشانده شود.
نشاندن ترکیبی[ویرایش]
یک گراف نشانده شده به صورت یکتا ترتیب چرخه‌ای لبه‌های مجاور به رئوس مشابه را توصیف می‌کند. مجموعهٔ تمام این مرتبه‌های چرخه‌ای سیستم چرخش نامیده می‌شود. مشاندن با سیستم چرخش مشابه یکسان در نظر گرفته می‌شود و کلاس یکسان مرتبط با نشاندن‌ها، نشاندن ترکیبی نامیده می‌شود (همان‌طور که از نام نشاندن مکانی استنباط می‌شود به تعریف قبلی نقاط و منحنی‌ها اطلاق می‌شود). گاهی اوقات سیستم چرخش، نشاندن ترکیبی نامیده می‌شود.
یک گراف نشانده شده همچنین مرتبه چرخه‌ای طبیعی لبه‌ها را نیز توصیف می‌کند که مرزهای نماهای نشاندن را تشکیل می‌دهد. با این حال مدیریت این مراتب مبتنی بر نما هموار و آسان نمی‌باشد، زیرا در یعضی موارد بعضی از لبه‌ها ممکن است دو بار در راستای مرز نما عبور کنند. به‌طور مثال این موضوع برای نشاندن درخت‌ها همیشه روی می‌دهد که دارای یک نمای منفرد می‌باشد. برای چیره شدن بر این مشکل ترکیبی، یک فرد ممکن است فرض کند که هر لبه به صورت طولی در دو "نصف لبه" یا در دو "سمت" "تجزیه" بشوند. تحت این شرایط در عبور از تمام مرزهای نماها، هر نصفه لبه تنها یکبار عبور می‌کند و هر دو نصفه لبه از لبهٔ مشابه در جهت عکس عبور می‌کند.
پیچیدگی محاسباتی[ویرایش]
مسئلهٔ کشف نوع گراف نوعی از مسائل ان‌پی سخت می‌باشد (مسئله تعیین اینکه آیا یک گراف n راسی نوع g می‌باشد یا خیر از نوع ان‌پی کامل می‌باشد)
در همین زمان مسئلهٔ نوع گراف، از نوع پارامترهای ثابت رام شونده می‌باشد مثل الگوریتم‌هایی با زمان چند جمله‌ای که در چک کردن اینکه آیا یک گراف می‌تواند در یک فضا با نوع ثابت همچون کشف نشاندن شناخته‌شده می‌باشد.
اولین پیشرفت مهم مرتبط با این موضوع در سال ۱۹۷۹ در حالی روی داد که الگوریتم‌های با پیچیدگی زمانی O(nO(g)) به صورت مستقل در ACM Symposium on Theory of Computing ارائه می‌شدند. یکی از آن‌ها توسط (فیلوتی I.Filotti) و (میلر G.L.Miller) و دیگری توسط (جان ریف John Reif) ارائه شد. رویکردهای آن‌ها کاملاً با یکدیگر متفاوت بود اما بر اساس پیشنهاد کمیته برنامه‌ریزی آن‌ها یک مقالهٔ اشتراکی ارائه دادند.
در سال ۱۹۹۹ گزارش شد که مورد نوع ثابت می‌تواند در زمان خطی در فضای گراف و زمان دو برابر نمایی در نوع گراف حل شود.
نشاندن گراف در فضاهایی با ابعاد بالاتر[ویرایش]
اعتقاد بر این است که هر گراف محدود در یک فضای سه‌بعدی قابل نشاندن است.
یک روش برای انجام این موضوع این است که نقاط را در هر خط درون فضا قرار دهیم و لبه‌ها را همانند منحنی‌های هر یک از آن‌ها در یک نیم سطح مجزا ترسیم کنیم به طوری که هر نیم سطح آن خطوط را به عنوان مرز مشترک خودشان دارا هستند. چنین نشاندنی که در آن لبه‌ها در نیم سطح ترسیم می‌شوند نشاندن کتابی گراف نامیده می‌شود. این استعاره از این تصور سرچشمه می‌گیرد که هر یک از سطح‌ها که در آن یک لبه ترسیم می‌شود همانند برگی از کتاب می‌باشد. در واقعیت مشاهده شد که لبه‌های متعددی ممکن است در یک صفحهٔ مشابه ترسیم شود. ضخامت کتاب گراف حداقل تعداد نیم‌صفحه‌های مورد نیاز برای چنین ترسیمی می‌باشد.
متناوباً هر گراف محدود می‌تواند با لبه‌های مستقیم در سه بعد بدون تقاطع توسط قراردادن راس‌های آن در موقعیت معمولی ترسیم شود؛ بنابراین هر گراف چهار لبه‌ای هم سطح نمی‌باشند. به‌طور مثال این موضوع با قراردادن راس iام در نقطهٔ (I,i2,i3) منحنی لحظه‌ای بدست آید.
نشاندن گراف در فضای سه‌بعدی به طوری که هیچ ۲ چرخه‌ای از نظر مکانی متصل نباشند، نشاندن بدون اتصال نامیده می‌شوند. یک گراف نشاندن بدون اتصال دارد اگر و تنها اگر هیچ‌یک از ۷ گراف خانوادهٔ پترسن را به عنوان گراف فرعی نداشته باشد.
جستارهای وابسته[ویرایش]
منابع[ویرایش]
۱. رابرت کوهن، پیتر ایف، تاو لین، فرانک روسکی(۱۹۹۵)، «ترسیم گراف سه بعدی»، در روبرتو تاماسیا، لوانیس تولیس، ترسیم گراف: کارگاه علمی دیمکس، نیو جرسی، ایالات متحدهٔ آمریکا، اکتبر ۱۹۹۴
This article "نشاندن گراف" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:نشاندن گراف. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
