گراف لایه بندی شده گراف همبندی است که راس‌های آن به مجموعه‌های 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
منابع
for visual understanding of hierarchical system
structures’، IEEE Transaction on Systems,
Man, and Cybernetics 11(2)، 109–125.
پانویس
