گراف لایهبندی شده
گراف لایه بندی شده گراف همبندی است که راسهای آن به مجموعههای 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.