گراف مکمل

در نظریه گراف، مکمّل یا معکوس گراف $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.

[bm-1] Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 6, ISBN 0-444-19451-7.

[2] Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.