یک گراف لایه بندی شده گراف همبندی است که راس های آن به مجموعه های L۰ تا Ln تقسیم بندی شده است . هر یال وزن صحیح نا منفی دارد و فقط رأس های لایه های پی در پی را به هم متصل میکند. عرض گراف برابر ماکسیموم تعداد رأس های هر لایه هست.
در زیر الگوریتم هایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطه های وابسته در یک شبکه مناسب می باشد
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال ها
تقسیم بندی کردن رأس ها به تعدادی لایه
در هر لایه از رأس ها آن ها را به صورت خطی مرتب کنید
به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید م الگوریتم زیر از الگوریتم بالا نتیجه گرفته شده است.
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال ها
در هر لایه رأس ها را به دو گروه تقسیم می کنیم
در هر گروه در هر لایه رأس ها را به صورت خطی مرتب می کنیم
به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید این الگوریتم قدم سوم را شرح می دهد
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.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر زیر الگوریتم هایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطه های وابسته در یک شبکه مناسب می باشد
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال ها
تقسیم بندی کردن رأس ها به تعدادی لایه
در هر لایه از رأس ها آن ها را به صورت خطی مرتب کنید
به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید م الگوریتم زیر از الگوریتم بالا نتیجه گرفته شده است.
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال ها
در هر لایه رأس ها را به دو گروه تقسیم می کنیم
در هر گروه در هر لایه رأس ها را به صورت خطی مرتب می کنیم
به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید این الگوریتم قدم سوم را شرح می دهد
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.
wiki: گراف لایه بندی شده