گراف مکمل
در نظریه گراف، مکمّل یا معکوس گراف G، گراف H با رئوس یکسان است به طوری‌که دو رأس متمایز H مجاورند اگر و فقط اگر آن دو راس در G مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال‌های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می‌شوند و تمام یال‌هایی که قبلاً وجود داشتند حذف می‌گردند.[۱]
تعریف
[ویرایش]فرض کنید G = (V, E) یک گراف ساده باشد و K مجموعهٔ تمام زیرمجموعه‌های ۲-عضوی V است. در این صورت، H = (V, K \ E) گرافِ مکمّلِ گرافِ Gست،[۲] که در آن K \ E متمم نسبی E در K است. برای گراف‌های جهت‌دار، می‌توان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهت‌دار با مجموعه رئوس یکسان با استفاده از مجموعهٔ تمام زوج مرتب‌های ۲-عضوی از V به عنوان K در عبارت مذکور.
منابع
[ویرایش]- ↑ Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 6, ISBN 0-444-19451-7.
- ↑ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.