گراف تقاطع

گراف اشتراکی (به انگلیسی: Intersection Graph) یا گراف تقاطع گرافی ست که اشتراک خانواده ای از مجموعه ها را نشان می دهد.به عبارتی دیگر فرض کنیم مجموعه ی S و همچنین مجموعهٔ n عضوی از زیر مجموعه های S را در اختیار داریم که نام آن C است. یعنی هر عضو C، زیر مجموعه ای از S می باشد. به ازای هر عضو C یک رأس رسم می کنیم و در صورتی که دو عضو C اشتراک داشته باشند بین رئوس متناظر با آن ها یالی رسم می کنیم. شکل حاصل را گراف اشتراکی مجموعهٔ C نامیده و با I(C) نمایش می دهیم.
ریاضیات گسسته وترکیبیاتی از دیدگاه کاربردی مولف رالف گریمالدی
داده ساختارها ومبانی الگوریتم ها مولف دکتر محمد قدسی
فرض کنید می خواهیم برنامه ریزی چراغ های راهنمای یک تقاطع را برعهده بگیریم. در مدل انتزاعی این مسئله آنچه مهم است گردش های مختلف این تقاطع و تلاقی این گردش هاست. بدیهی است که امکان حرکت گردش های متلاقی در یک بازهٔ زمانی وجود ندارد. اگر گردش از خیابان X به خیابان Y راXY بنامیم، خود گردش ها و تلاقی بین آن ها را می توان با یک گراف تقاطع نشان داد. در این گراف، هر گردش یک رأس است و بین دو گردش متلاقی یک یال قرار داده ایم.
به طور رسمی٬ یک گراف تقاطع٬ گرافی غیرجهت دار است که از خانواده مجموعه های S i , i = 0 , 1 , 2 , . . . {\displaystyle S_{i},i=0,1,2,...}   با قرار دادن یک رأس v i {\displaystyle v_{i}}   برای هر مجموعه S i {\displaystyle S_{i}}   و وصل کردن این دو رأس توسط یک یال٬ در صورتی که دو مجموعه متناظر به آن ها اشتراک غیرصفر داشته باشند٬ به وجود می آید.یعنی:
E(G) = {{vi, vj} | Si ∩ Sj ≠ ∅}.