گراف های مکعبی (Hypercube Graphs)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های مکعبی (Hypercube Graphs) :
گراف های مکعبی یا ابرمکعب ها (Hypercube Graphs) خانواده مهمی از گراف ها هستند که برای ابعاد مختلف تعریف می شوند. گراف
\[ d \]-مکعبی (که معمولا
\[ Q_d \]نامیده می شود) گرافی است که رئوس آن تمام رشته های دودویی (Binary Strings) به طول
\[ d \]هستند و دو رأس به هم متصل می شوند اگر و تنها اگر رشته های متناظرشان دقیقا در یک بیت (بیت) با هم تفاوت داشته باشند .
همه گراف های مکعبی دو بخشی هستند . یک بخش شامل تمام رشته هایی است که تعداد بیت های 1 در آنها زوج (Even) است و بخش دیگر شامل رشته هایی با تعداد فرد (Odd) بیت 1 است. از آنجا که حرکت در طول یک یال، دقیقا یک بیت را تغییر می دهد، تعداد بیت های 1 همیشه بین زوج و فرد جابه جا می شود و هیچ یالی دو رأس با یک نوع زوجیت را به هم وصل نمی کند. این گراف ها در معماری کامپیوتر (برای طراحی ابررایانه ها)، نظریه کدگذاری و توپولوژی شبکه های ارتباطی کاربرد گسترده ای دارند.
