گراف لایه‌بندی شده

گراف لایه بندی شده گراف همبندی است که راس‌های آن به مجموعه‌های L۰ تا Ln تقسیم‌بندی شده است. هر یال وزن صحیح نا منفی دارد و فقط رأس‌های لایه‌های پی در پی را به هم متصل می‌کند. عرض گراف برابر ماکسیموم تعداد رأس‌های هر لایه هست.

 شیوه لایه بندی کردن گراف 
در زیر الگوریتم‌هایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطه‌های وابسته در یک شبکه مناسب می‌باشد.

 Sugiyama Method 
قدم اول:از بین بردن دورها
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال‌ها

قدم دوم:لایه بندی کردن
تقسیم‌بندی کردن رأس‌ها به تعدادی لایه

پرونده:gma2.JPG
قدم سوم:مرتب کردن راس‌ها
در هر لایه از رأس‌ها آن‌ها را به صورت خطی مرتب کنید

پرونده:gam3.jpg
قدم چهارم:نسبت دادن مختصات
به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید
پرونده:gam4.jpg

الگوریتم زیر از الگوریتم بالا نتیجه گرفته شده است.

 ۳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.

 پانویس 
رده:خانواده‌های پارامتری گراف‌ها
رده:رسم نمودار
رده:نظریه گراف