گراف بازه‌ای
(تغییرمسیر از گراف بازه‌ها)
در نظریه گراف‌ها گراف بازه‌ای (به انگلیسی: Interval Graph) گرافی اشتراکی از خانواده‌ای از بازه‌هایی روی خط اعداد حقیقی است. به ازای هر بازه یک رأس رسم می‌گردد و بازه‌هایی که دارای اشتراک هستند (اشتراکشان تهی نیست) بین رئوس متناظرشان یال رسم می‌گردد.[۱]
شروط لازم
[ویرایش]
در اینجا شرطی لازم برای بازه‌ای بودن گراف ارائه می‌کنیم که یک گراف اگر دارای حفره (حفره را دوری با اندازهٔ بزرگ تر از ۳ گویند که هیچ یالی بین رئوس غیر متوالی در آن دور نباشد.) باشد حتماً بازه‌ای نمی‌باشد. برای مثال گراف abcde در زیر، بازه‌ای نمی‌باشد به خاطر وجود دور abde. [نیازمند منبع]
منابع
[ویرایش]- ↑ ویکی‌پدیای انگلیسی
 | این یک مقالهٔ خرد ریاضیات است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید. |