گراف مکمل

در نظریه گراف، مکمّل یا معکوس گراف ، گراف  با رئوس یکسان است به طوری‌که دو رأس متمایز  مجاورند اگر و فقط اگر آن دو راس در  مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال‌های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می‌شوند و تمام یال‌هایی که قبلاً وجود داشتند حذف می‌گردند.

تعریف 
فرض کنید  یک گراف ساده باشد و  مجموعهٔ تمام زیرمجموعه‌های ۲-عضوی  است. در این صورت،  گرافِ مکمّلِ گرافِ ست، که در آن  متمم نسبی  در  است. برای گراف‌های جهت‌دار، می‌توان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهت‌دار با مجموعه رئوس یک‌سان با استفاده از مجموعهٔ تمام زوج مرتب‌های ۲-عضوی از V به عنوان K در عبارت مذکور.

منابع 

عملیات گراف