گراف لایهبندی شده
گراف لایه بندی شده گراف همبندی است که راسهای آن به مجموعههای L۰ تا Ln تقسیمبندی شده است. هر یال وزن صحیح نا منفی دارد و فقط رأسهای لایههای پی در پی را به هم متصل میکند. عرض گراف برابر ماکسیموم تعداد رأسهای هر لایه هست.
شیوه لایه بندی کردن گراف[ویرایش]
در زیر الگوریتمهایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطههای وابسته در یک شبکه مناسب میباشد.
Sugiyama Method[ویرایش]
- قدم اول:از بین بردن دورها
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یالها
- قدم دوم:لایه بندی کردن
تقسیمبندی کردن رأسها به تعدادی لایه
- قدم سوم:مرتب کردن راسها
در هر لایه از رأسها آنها را به صورت خطی مرتب کنید
- قدم چهارم:نسبت دادن مختصات
- به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید
الگوریتم زیر از الگوریتم بالا نتیجه گرفته شده است.
۳D Layered Digraph[ویرایش]
- قدم اول:از بین بردن دورها
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یالها
- قدم دوم:لایه بندی کردن
تقسیمبندی کردن رأسها به تعدادی لایه
- قدم سوم:تقسیمبندی راسها
در هر لایه رأسها را به دو گروه تقسیم میکنیم
- قدم جهارم:مرتب کردن راسها
در هر گروه در هر لایه رأسها را به صورت خطی مرتب میکنیم
- قدم پنجم:نسبت دادن مختصات به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید
این الگوریتم قدم سوم را شرح میدهد
الگوریتم تقسیمبندی رأسها[ویرایش]
Ai ← φ Bi ← φ for all v ∈ Li do if |N+(v) ∩ Ai−1|> |N+(v) ∩ Bi−1| then Ai ← Ai ∪ {v} else Bi ← Bi ∪ {v} end if end for if |Ai|> |Bi| then X is a synonym of A and x is a synonym of B else X is a synonym of B and x is a synonym of A end if while (|Li| is even and |Xi|> |xi|) or (|Li| is odd and |Xi|> |xi| + 1) do move vertex v ∈ Xi with the minimum |N+(v)∩ Xi−1| − |N+(v) ∩ xi−1| to xi end while
منابع[ویرایش]
- https://ics.uci.edu/~eppstein/junkyard/thickness/
- www.cs.usyd.edu.au/~visual/comp4048/slides03.ppt
- Sugiyama, K.، Tagawa, S. & Toda, M. (1981)، ‘Methods
for visual understanding of hierarchical system structures’، IEEE Transaction on Systems, Man, and Cybernetics 11(2)، 109–125.