گراف بازه‌ای

یک گراف اشتراکی از مجموعه‌ای از بازه‌ها
(تغییرمسیر از گراف بازه‌ها)
گراف متناظر با هفت بازه بر روی خط حقیقی

در نظریه گراف‌ها گراف بازه‌ای (به انگلیسی: Interval Graph) گرافی اشتراکی از خانواده‌ای از بازه‌هایی روی خط اعداد حقیقی است. به ازای هر بازه یک رأس رسم می‌گردد و بازه‌هایی که دارای اشتراک هستند (اشتراکشان تهی نیست) بین رئوس متناظرشان یال رسم می‌گردد.[۱]

شروط لازمویرایش

در اینجا شرطی لازم برای بازه‌ای بودن گراف ارائه می‌کنیم که یک گراف اگر دارای حفره (حفره را دوری با اندازهٔ بزرگ تر از ۳ گویند که هیچ یالی بین رئوس غیر متوالی در آن دور نباشد.) باشد حتماً بازه‌ای نمی‌باشد. برای مثال گراف abcde در زیر، بازه‌ای نمی‌باشد به خاطر وجود دور abde. [نیازمند منبع]

منابعویرایش

  1. ویکی‌پدیای انگلیسی