گراف بازهای
ظاهر
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Interval_graph.svg/300px-Interval_graph.svg.png)
در نظریه گرافها گراف بازهای (به انگلیسی: Interval Graph) گرافی اشتراکی از خانوادهای از بازههایی روی خط اعداد حقیقی است. به ازای هر بازه یک رأس رسم میگردد و بازههایی که دارای اشتراک هستند (اشتراکشان تهی نیست) بین رئوس متناظرشان یال رسم میگردد.[۱]
شروط لازم[ویرایش]
![](http://upload.wikimedia.org/wikipedia/fa/4/4f/%DA%AF%D8%B1%D8%A7%D9%81_%D8%BA%DB%8C%D8%B1_%D8%A8%D8%A7%D8%B2%D9%87%E2%80%8C%D8%A7%DB%8C.jpg)
در اینجا شرطی لازم برای بازهای بودن گراف ارائه میکنیم که یک گراف اگر دارای حفره (حفره را دوری با اندازهٔ بزرگ تر از ۳ گویند که هیچ یالی بین رئوس غیر متوالی در آن دور نباشد.) باشد حتماً بازهای نمیباشد. برای مثال گراف abcde در زیر، بازهای نمیباشد به خاطر وجود دور abde. [نیازمند منبع]
منابع[ویرایش]
- ↑ ویکیپدیای انگلیسی