گراف وتری
From Wikipedia, the free encyclopedia
در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. (وتر: یالی است که دو رأس نامتوالی از دور را به هم وصل میکند). به عبارت دیگر، هر دور القایی در گراف میبایست حداکثر سه رأس داشته باشد. گرافهای وتری زیرمجموعهای از گرافهای آرمانی میباشند که در مدت زمانی چندجملهای شناسایی میشوند. اگر ورودی مسایلی همچون رنگآمیزی گراف، گرافی وتری باشد در مدت زمانی چندجملهای حل میشوند.