تعبیه¬ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم
محورهای موضوعی :
اکرم سپهری
1
(دانشگاه آزاد اسلامی قزوین)
علیرضا باقری
2
کلید واژه: تعبیه¬ی هندسی, تعبیه¬ی درخت در مجموعه نقاط, به حداقل رساندن خم, تطبیق¬دهی گراف,
چکیده مقاله :
دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه داخل یک چند ضلعی با n رأس تعبیه کنیم این تعبیه باید به گونه¬ای باشد که تعداد خم¬های درخت حاصل حداقل شود. ایده¬ی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئله¬ی تطبیق¬دهی گراف¬ها واستفاده از الگوریتم¬های تطبیق¬دهی گراف است که منجر به بررسی مسئله¬ی فاصله¬ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه¬ی مناسب و استفاده از روش تجزیه¬ی گراف¬ها، تطبیق¬دهی گراف¬ها را با حداقل هزینه برای به حداقل رساندن تعداد خم انجام می-دهیم و الگوریتم دارای پیچیدگی محاسباتی O(N2n+N4)است.
[1] Abellanas M, Garcia-Lopez J, Hernnandez G, Noy M, P. Ramos A. Bipartite embeddings of trees in the plane. Discrete Applied Mathematics, pp: 1-10,1999.
[2] Badent M, Giacomo E.D, Liotta G. Drawing colored graphs on colored points, in Proceedings of the Tenth Workshop on Algorithms and Data Structures, pp: 129-142,2008.
[3] Bagheri A.R, Razzazi M.R. On complexity of planar embeddability of trees inside simple polygons. Information processing letters,
pp: 521-523,2010.
[4] Bose P. On embedding an outer-planar graph on a point set,computational Geometry: Theory and Applications, pp: 303–312,2002.
[5] Bose P, McAllister M, Snoeyink J. Optimal algorithms to embed trees in a point set, Journal of Graph Algorithms and Applications, pp: 1–15, 1997.
[6] Binucci C , Di Giacomo E , Didimo W , Estrella-Balderrama A, Frati F, GKobourov S, Liotta G. Upward straight-line embeddings of directed graphs into point sets, Computational Geometry, pp: 219–232, 2010.
[7] Cabello S. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard, J. Graph Algorithms Appl, pp:353–366,2006.
[8] Giacomo E.D, Didimo W, Liotta G, Meijer H, Wismath S.k. Point-set embeddings of trees with given partial drawings, Computational Geometry, pp: 664-676, 2009.
[9] Giacomo E. D, Liotta G, Trotta F. On embedding a graph on two sets of points, International Journal of Foundations of Computer Science, pp: 1071–1094, 2006.
[10] El-sonbaty Y, ismail M. A. A new algorithm for subgraph optimal Isomorphism, Pattern Recognition Society, published by Elsevier Science, pp: 205-218, 1997.
[11] Gritzmann P, Mohar B, Pach J, Pollack R. Embedding a planar triangulation with vertices at specified positions. The American Mathematical Monthly 98, pp: 165–166, 1991.
[12] Kaufmann M, Wiese R. Embedding vertices at points: Few bends suffice for planar graphs, Journal of Graph Algorithms and Applications, pp: 115–129, 2002.
[13] Pach J, Wenger R. Embedding planar graphs at fixed vertex locations, Graphs and Combinatory, pp: 717–728, 2001.
[14] Suri S. A linear time algorithm for minimum link paths inside a simple polygon, Computer Vision Graphics and Image Process, pp: 99-110, 1986.
[15] Yamada S, Hasai T. An efficient algorithm for the linear assignment problem, Elect. Comm, pp: 28-36, 1990.
فصلنامه علمي- پژوهشي فنّاوري اطلاعات و ارتباطات ایران | سال دوم، شماره‌هاي3و4، بهار و تابستان 1389 صص: 1- 7 |
|
تعبیهی هندسی درخت درنقاط داخل یک
چندضلعی با حداقل تعداد خم
اکرم سپهری▪ * علیرضا باقری **
*کارشناسی ارشد، دانشکدهی مهندسی برق، رایانه و فنآوری اطلاعات، دانشگاه آزاد اسلامی قزوین
**مربی، دانشکدهی مهندسی کامپیوتروفنآوری اطلاعات، دانشگاه صنعتی امیرکبیر
چکيده
دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه داخل یک چند ضلعی با n رأس تعبیه کنیم این تعبیه باید به گونهای باشد که تعداد خمهای درخت حاصل حداقل شود. ایدهی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئلهی تطبیقدهی گرافها واستفاده از الگوریتمهای
تطبیقدهی گراف است که منجر به بررسی مسئلهی فاصلهی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینهی مناسب و استفاده از روش تجزیهی گرافها، تطبیقدهی گرافها را با حداقل هزینه برای به حداقل رساندن تعداد خم انجام میدهیم و الگوریتم دارای پیچیدگی محاسباتی O(N2n+N4)است.
كليدواژگان: تعبیهی هندسی، تعبیهی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف.
1- مقدمه
محاسبهی تعبیهی یک ساختار بر روی مجموعهای از نقاط و همچنین مسئلهی تصمیمگیری دربارهی اینکه آیا یک ساختار میتواند در مجموعه نقاط در روی یک صفحه تعبیه شود به طوری که برخی ویژگیها ی خاص را داشته باشد موضوع
▪ نویسنده عهده‌دار مکاتبات (akram_sepehri@yahoo.com ai)
1. Graph drawing
2. Directed acyclic graph
مورد بحث دربسیاری زمینههااز جمله ترسیم گراف2 است که نتایج به دست آمده در این موارد محدود است ودر ]13،12،9،2 [لیستی از مقالات دیده می شود. در]6[ مسئله ی محاسبهی تعبیهی صعودی مستقیم الخط از یک گراف غیردوری جهت دار3 G در مجموعه نقطهی S بررسی شده است. مسئلهی تعبیهی مستقیم الخط گراف در مجموعه نقاط، هم از دیدگاه الگوریتمیک وهم از دیدگاه محاسباتی بررسی شده است. در]11[ اثبات شده است که یک تعبیهی مستقیم الخط از یک گراف درهر مجموعه از نقاط وجود دارداگر و تنها اگر آن گراف، یک گراف outer-planar باشد. از دیدگاه الگوریتمیک یک الگوریتم زمان Nlog3N)) O در
]4[ برای ساخت تعبیهی مستقیم الخط گرافهای
Outer-planarو درختها در مجموعه نقاط ارائه شده است. مسئلهی تصمیمگیری دربارهی اینکه یک تعبیهی مستقیم الخط از یک گراف مسطح در یک مجموعه نقطه وجود دارد یک مسئلهی NP کامل است]7[. ساختار مورد نظر ما درخت است، پیچیدگی مسئلهی تعبیهی یک درخت آزاد در یک چند ضلعی،NP کامل است ودر]3[ اثبات شده است. در]5[ مسئلهی تعبیهی درخت مورد بررسی قرار گرفته است یک درخت و یک مجموعه نقطه به عنوان ورودی مسئله هستند وتعبیهی مستقیم الخطی از درخت در این مجموعه نقاط در زمان (NlogN) O ارائه شده است. این الگوریتم برای تعبیهی درخت از قسمتهایی ازپوش محدب استفاده میکند. در ]1[ مسئلهی تعبیهی دو قسمتی درخت در یک مجموعه نقطه که به دو رنگ آبی و قرمز هستند بررسی شده است. دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه درون یک چند ضلعی با n رأس تعبیه کنیم این تعبیه باید به گونهای باشد که تعداد خمهای درخت حاصل حداقل شود و نیازی نیست که این تعبیه مسطح باشد. مسئله مطرح شده در این مقاله نسبتا جدید است و تحقیقات کمی روی آن انجام شده است. این مسئله با مسئلهی ترسیم گراف روی مجموعهی نقاط با داشتن قسمتی از ترسیم مرتبط میشود که در [8] بیان شده است. در چنین تعبیهای حد بالاو حد پایین برای تعداد خم دریال درخت ارائه شده است. در این مقاله یک الگوریتم جدید مبتنی بر مسئلهی تطبیقدهی گرافها برای مسئلهی تعبیهی درخت در مجموعهی نقاط داخل چند ضلعی ارائه می دهیم. در این روش با اعمال یک الگوریتم که در]14[ ارائه شده است بر روی تمام نقاط داخل چند ضلعی با پیدا کردن فاصله ی پیوندی بین نقاط ودر نتیجه تعداد خم بین نقاط، یک گراف کامل وزندار به عنوان گراف مرجع داریم که وزن نشاندهندهی تعداد خم است. سپس با به کار بردن ایدهی مطرح شده در ]10[ برای تطبیقدهی از روش تجزیهی گرافها استفاده میکنیم و تطبیقدهی بین گرافها را در سطح زیر گرافهای تجزیه شده انجام میدهیم.
در بخش2 برخی تعاریف که برای الگوریتم پیشنهادی لازم است بیان میشود. در بخش 3 به شرح الگوریتم وبیان روش تجزیه و ذکر یک مثال میپردازیم دربخش 4 آنالیز پیچیدگی محاسباتی الگوریتم بررسی می شود و در بخش 5 نتایج آزمایش ارائه شده است و در بخش 6 نتیجه گیری ارائه میشود.
2- تعاریف
حل مسئلهی مطرح شده نیازمند درک مفاهیم اولیه در مسائل مسیرهای با حداقل تعداد لینک و مسئله ی فاصلهی پیوندی و نیز مسئلهی تطبیقدهی گرافها است بنابراین به مهمترین مفاهیم در این بخش اشاره میشود.
· يك گراف G = (V,E) تركيبي از رئوس و يال‌ها است كه V مجموعه‌ي رئوس است و EÌV´V مجموعه‌ي يال‌ها در گراف است. اگر دو رأس u, vÎV با يك يال eÎE به هم متصل شده باشند مي‌گوييم U,V مجاور یا همسايه هستند. گرافی که هر دو رأس مجزای آن مجاور باشند گراف کامل نامیده میشود.
· یک مسیردر یک گراف دنبالهای از رئوس است که از هر یک ازرئوسش یک یال به رأس بعدی در دنباله وجود دارد.
· یک دور مسیری است که رأس ابتدا و انتهای آن یکی است.
· یک درخت گرافی است که هر دو رأس آن دقیقا با یک مسیر به یکدیگر متصل شده باشد. به عبارت دیگر یک درخت، گراف همبندی است که دوری ندارد.
· چندضلعی سادهP در صفحه دنباله ای ازn نقطهی v1,v2,…vn. است که رئوس نامیده می شوند و به وسیلهیn پاره خط 1v1v2,v3v4,…vn-1vn,vnvکه یال نامیده میشوند مشخص میشود وهیچ دو یال متوالی اشتراک ندارند.
· اگر G=(V,E) یک گراف مسطح با N گره و S یک مجموعه با N نقطه در یک صفحه باشد تعبیهی گراف روی مجموعه نقاط که با (Γ(G,S نشان داده میشود یک ترسیم مسطح از G روی نقاط S است که هر گره گراف G به یک نقطهی مجزای S نگاشت شود. یالها ممکن است خط مستقیم، منحنی یا چندخطی باشد.
· تطبيقدهی دو گراف Gm=(Vm,Em) و Gt=(Vt,Et) شامل ارتباط بين مجموعه‌ي رئوس Vm و Vt و مجموعه‌ي يال‌هاي Em و Et است. در تطبیقدهی گراف با ارائه‌ي دو گراف Gm=(Vm,Em) و Gt=(Vt,Et) مسأله پیدا کردن يك نگاشت F:Vt®Vm است، به طوريكه (u,v)ÎEt باشد اگر و تنها اگر (f(u),f(v))ÎEM باشد واگر این f وجود داشته باشد آنگاه ميگوئيم Gt با Gm همريخت است.
· فاصلهی پیوندی بین دو نقطهیxوy حداقل تعداد پاره خطهای مستقیم در مسیر متصل کنندهی xوy درون چندضلعی است. این فاصله را باdl(x,y) نشان میدهند. مسیر با حداقل تعداد لینک بین دو نقطهی P Î xوy دقیقاdl(x,y) یال دارد.
3-شرح الگوریتم
ایدهی اصلی الگوریتم پیشنهادی به صورت زیر است. ما فاصلهی پیوندی بین هر زوج از نقاط را با اعمال الگوریتم ارائه شده در ]14[ روی همهی زوج نقاط درون چندضلعی ساده پیدا میکنیم. سپس ما یک گراف کامل وزندار روی N نقطه میسازیم به طوریکه وزن یال (u,v) ،dl(u,v) است. الگوریتم ارائه شده در ]14[، چندضلعی را در زمانn) )O پیش پردازش می کند ودر زمان log n))O به جستجوهای فاصله پیوندی پاسخ میدهد. سپس ما حداقل وزن تطبیقدهی درخت و گراف کامل را پیدا میکنیم. بنابراین مسئلهی ما به مسئلهی تطبیقدهی گرافهای وزندار تبدیل میشود. برای تطبیقدهی ما از الگوریتم ]10[ با اعمال برخی تغییرات استفاده میکنیم. در ]10[ یک الگوریتم برای همریختی گرافها ارائه شده است که به طور خلاصه شرح میدهیم. در این الگوریتم، گراف ورودی و مرجع به زیر گرافهای کوچکتر تقسیمبندی میشود. گرافهای پایه گرافهایی به شکل ستاره هستند یعنی زیرگرافها و همسایه هایش یک گراف پایه را میسازند. سپس یک ماتریس فاصله ی D بین گرافهای پایهی ورودی ساخته میشود که Dij نشاندهندهی فاصلهی بین i– امین گراف پایهی گراف ورودی و j– امین گراف پایه در گراف مرجع است و به صورت زیر محاسبه میشود.
Distance (U,V) = Wns*dist(ni, vj) + min(wbi, wbd)*abs (k - p)
+ min(wni, wnd)*abs(k - p)
+ dist (b's,e's) .
که dist(ni, vj) فاصلهی بین برچسب های گره ni و vj است.p وk تعدادیالهای متصل شده به گره ریشهی هر گراف پایه است که تطبیق می