From Wikipedia, the free encyclopedia
در نظریه گراف، مکمّل یا معکوس گراف G، گراف H با رئوس یکسان است به طوریکه دو رأس متمایز H مجاورند اگر و فقط اگر آن دو راس در G مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یالهای غایب مورد نیاز برای تشکیل یک گراف کامل اضافه میشوند و تمام یالهایی که قبلاً وجود داشتند حذف میگردند.[1]
فرض کنید G = (V, E) یک گراف ساده باشد و K مجموعهٔ تمام زیرمجموعههای ۲-عضوی V است. در این صورت، H = (V, K \ E) گرافِ مکمّلِ گرافِ Gست،[2] که در آن K \ E متمم نسبی E در K است. برای گرافهای جهتدار، میتوان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهتدار با مجموعه رئوس یکسان با استفاده از مجموعهٔ تمام زوج مرتبهای ۲-عضوی از V به عنوان K در عبارت مذکور.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.