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



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

منابع 

 http://www.websters-online-dictionary.org/la/layered+graph.html
 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.

پانویس 

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