گراف کامل From Wikipedia, the free encyclopedia
در نظریه گراف، گراف تام (به انگلیسی: Perfect Graph)، گرافی است که عدد رنگی آن برای هر زیرگراف القایی اش برابر با مرتبه بزرگترین کلیک آن زیرگراف (عدد کلیکی) باشد. بهطور معادل میتوان تعریف اخیر را برحسب نمادها بیان نماد: گراف دلخواهی چون تام است اگر و تنها اگر برای تمام داشته باشیم .
گرافهای تام شامل خانوادههای مهم بسیاری از گرافها بوده و موجب اتحاد و یکی شدن نتایج رنگآمیزیها و کلیکهای مرتبط در آن خانوادهها میگردد. به عنوان مثال، در تمام گرافهای تام، مسئله رنگآمیزی گراف، مسئله کلیک ماکسیمم و مسئله مجموعه مستقل ماکسیمم را میتوان به صورت زمان-چندجملهای حل نمود. به علاوه، قضایای متعدد و مهم ترکیبیاتی از نوع مین-مکس، همچون قضیه دیلورث را میتوان برحسب تام سازی گرافهای خاصی بیان نمود.
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.