گراف بازه‌ای
در نظریه گراف‌ها گراف بازه‌ای (به انگلیسی: Interval Graph) گرافی اشتراکی از خانواده‌ای از بازه‌هایی روی خط اعداد حقیقی است. به ازای هر بازه یک رأس رسم می‌گردد و بازه‌هایی که دارای اشتراک هستند (اشتراکشان تهی نیست) بین رئوس متناظرشان یال رسم می‌گردد.[1]
گراف متناظر با هفت بازه بر روی خط حقیقی
شروط لازم
در اینجا شرطی لازم برای بازه‌ای بودن گراف ارائه می‌کنیم که یک گراف اگر دارای حفره (حفره را دوری با اندازهٔ بزرگ تر از ۳ گویند که هیچ یالی بین رئوس غیر متوالی در آن دور نباشد.) باشد حتماً بازه‌ای نمی‌باشد. برای مثال گراف abcde در زیر، بازه‌ای نمی‌باشد به خاطر وجود دور abde.
منابع
- ویکی‌پدیای انگلیسی
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.