گراف وتری

در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. ( وتر: یالی است که دو رأس از دور که در دور شرکت نکرده باشند را به هم وصل می کند ) . به عبارت دیگر، هر دور القایی در گراف می بایست حداکثر سه رأس داشته باشد. گراف های وتری زیرمجموعه ای از گراف های آرمانی می باشند که در مدت زمانی چندجمله ای شناسایی می شوند. اگر ورودی مسایلی همچون رنگ آمیزی گراف، گرافی وتری باشد در مدت زمانی چندجمله ای حل می شوند.
{ v 1 , v 2 , . . . , v n } یک ترتیب طرد آرمانی ( به انگلیسی: perfect elimination ordering ) از رئوس گراف است به طوری که به ازای هر راس v i ، زیرگراف القایی ناشی از رئوس v i وهمسایه های آن در زیرگراف القایی ناشی از v 1 , v 2 , . . . , v i گرافی کامل باشد. Rose, Lueker & Tarjan ( 1976 ) نشان دادند که یک ترتیب طرد آرمانی از گرافی وتری را می توان به طور بهینه با الگوریتمی به نام lexicographic breadth - first search پیدا کرد.
کاربرد دیگر ترتیب طرد آرمانی پیدا کردن خوشهٔ فرین در یک گراف وتری در مدت زمانی چندجمله ای است، در حالی که این مسئله در حالت کلی از مسائل NP - complete است. در حالت کلی یک گراف وتری تعدادی خطی خوشهٔ فرین دارد در حالی که این تعداد در گراف های دیگر می تواند نمایی باشد. برای بدست آوردن خوشه های فرین از گراف وتری، ابتدا یک ترتیب طرد آرمانی ( در صورت وجود ) پیدا می کنیم. سپس از ابتدای این ترتیب شروع کرده و به ازای هر رأس v i زیرگراف القایی ناشی از این رأس و رئوس قبلی آن در ترتیب را ( که تشکیل خوشه می دهند ) را در نظر می گیریم. خوشهٔ با اندازهٔ بیشینه در میان این خوشه ها، خوشهٔ فرین خواهد بود. از آنجا که گراف وتری آرمانی است، اندازهٔ خوشهٔ فرین، همان عدد رنگی گراف خواهد بود. گراف های وتری، ترتیب پذیر آرمانی هستند: با اعمال رنگ آمیزی حریصانه بر روی ترتیب معکوس طرد آرمانی می توان به طور بهینه آن را رنگ کرد.
جداساز رأسی در هر گراف، مجموعه ای از رئوس است که با حذف آن ها گراف ناهمبند می شود. جداساز مینیمال است اگر هیچ زیرمجموعهٔ محضی از آن این ویژگی را نداشته باشد. برطبق قضیهٔ Dirac ( 1961 ) در گراف های وتری، هر جداساز مینیمال یک خوشه است. Dirac با این ویژگی آرمانی بودن گراف های وتری را اثبات کرد. گراف های وتری به طور استقرایی توسط گراف هایی تعریف می شوند که رئوس آن ها به سه زیرمجموعهٔ ناتهی A , B , S افراز شوند، به طوری که A ∪ S و B ∪ S هردو تشکیل یک زیرگراف القایی وتری دهند، S خوشه باشد و هیچ یالی بین A و B نباشد.