باز کردن منو اصلی

گراف بازه‌ای

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

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

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

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

منابعویرایش

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