معنی گراف مکمل

فرهنگستان زبان و ادب

{complement graph, complement of a graph} [ریاضی] برای گراف G، گرافی که رأس های آن همان رأس های G است و دو رأس متمایز آن مجاورند، هرگاه در G مجاور نباشند

دانشنامه عمومی

در نظریه گراف، مکمّل یا معکوس گراف G، گراف H با رئوس یکسان است به طوری که دو رأس متمایز H مجاورند اگر و فقط اگر آن دو راس در G مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می شوند و تمام یال هایی که قبلاً وجود داشتند حذف می گردند.
فرض کنید G = ( V, E ) یک گراف ساده باشد و K مجموعهٔ تمام زیرمجموعه های ۲ - عضوی V است. در این صورت، H = ( V, K \ E ) گرافِ مکمّلِ گرافِ Gست، که در آن K \ E متمم نسبی E در K است. برای گراف های جهت دار، می توان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهت دار با مجموعه رئوس یک سان با استفاده از مجموعهٔ تمام زوج مرتب های ۲ - عضوی از V به عنوان K در عبارت مذکور.