گراف های دوبخشی منتظم (Regular Bipartite Graphs)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های دوبخشی منتظم (Regular Bipartite Graphs) :
یک گراف دوبخشی منتظم (Regular Bipartite Graph) گرافی دو بخشی است که در آن همه رئوس دارای درجه (Degree) یکسانی هستند. اگر درجه هر رأس برابر با
\[ k \]باشد، گراف را
\[ k \]-منتظم (
\[ k \]-Regular) می نامند .
در یک گراف دوبخشی
\[ k \]-منتظم با افراز
\[ U \]و
\[ V \]، همیشه تعداد یال هایی که از
\[ U \]خارج می شوند برابر با
\[ k|U| \]و تعداد یال هایی که به
\[ V \]وارد می شوند برابر با
\[ k|V| \]است. از آنجا که این دو تعداد برابر هستند، نتیجه می شود که در یک گراف دوبخشی
\[ k \]-منتظم، اندازه دو بخش باید با هم برابر باشد (
\[ |U| = |V| \])، مگر آنکه
\[ k=0 \]. این گراف ها در طراحی آزمایش های آماری، نظریه رمزنگاری و ساختارهای ترکیبیاتی کاربرد دارند. مکعب ها (Cubes) نمونه هایی از گراف های دوبخشی منتظم هستند.
نویسنده علیرضا گلمکانی
شماره کلید 5495
گزینه ها 
نظرات 0 0 0