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