گراف تقاطع

گراف اشتراکی ( به انگلیسی: Intersection Graph ) یا گراف تقاطع گرافی ست که اشتراک خانواده ای از مجموعه ها را نشان می دهد. به عبارتی دیگر فرض کنیم مجموعه ی S و همچنین مجموعهٔ n عضوی از زیر مجموعههای S را در اختیار داریم که نام آن C است. یعنی هر عضو C، زیر مجموعه ای از S می باشد. به ازای هر عضو C یک رأس رسم می کنیم و در صورتی که دو عضو C اشتراک داشته باشند بین رئوس متناظر با آن ها یالی رسم می کنیم. شکل حاصل را گراف اشتراکی مجموعهٔ C نامیده و با I ( C ) نمایش می دهیم. [ ۱]
فرض کنید می خواهیم برنامه ریزی چراغ های راهنمای یک تقاطع را برعهده بگیریم. در مدل انتزاعی این مسئله آنچه مهم است گردش های مختلف این تقاطع و تلاقی این گردش هاست. بدیهی است که امکان حرکت گردش های متلاقی در یک بازهٔ زمانی وجود ندارد. اگر گردش از خیابان X به خیابان Y راXY بنامیم، خود گردش ها و تلاقی بین آن ها را می توان با یک گراف تقاطع نشان داد. در این گراف، هر گردش یک رأس است و بین دو گردش متلاقی یک یال قرار داده ایم.
به طور رسمی٬ یک گراف تقاطع٬ گرافی غیرجهت دار است که از خانواده مجموعه های S i , i = 0 , 1 , 2 , . . . با قرار دادن یک رأس v i برای هر مجموعه S i و وصل کردن این دو رأس توسط یک یال٬ در صورتی که دو مجموعه متناظر به آن ها اشتراک غیرصفر داشته باشند٬ به وجود می آید. یعنی:
E ( G )   =  {{vi,   vj}  |  Si  ∩  Sj  ≠  ∅}.
در مسئله مطرح شده در بالا فرض کنید چراغ راهنمایی یک تقاطع چند زمانه است و تعداد زمان های آن با توجه به جهت های حرکت ( گردش به راست، چپ، وغیره ) مشخص می شود. برای سادگی کار فرض می کنیم چراغ مورد نظر K رنگ دارد که با رنگ های ۱ تا K مشخص شده است. در مدل گراف مسئله انتساب یک یا چند رنگ به هر رأس گراف تقاطع است. به طوری که تعداد این رنگ ها همان K است و ما می خواهیم کمترین مقدار آن را بدست آوریم.
باید گراف را به گونه ای رنگ کرد که هیج دو راس دو سر یک یال رنگ یکسان نداشنه باشند. کمینه تعداد رنگ های لازم برای رنگ کردن G می نامیم وبا X ( G ) نشان می دهیم. حدود سال ۱۸۵۰، فرانسیس گاتری ( ۱۸۹۹ - ۱۸۳۱ ) بعد از نشان دادن چگونگی رنگ آمیزی استان های نقشه انگلیس تنها باچهار رنگ، به مسئله کلی علاقه مند شد. اندکی بعد از آن، مسئله چهار رنگ را به برادر کوچکش فردریک نشان داد. در آن زمان فردریک گاتری ( ۱۸۶۶ - ۱۸۳۳ ) دانشجوی اوگاستس دمورگن ( ۱۸۷۱ - ۱۸۰۶ ) بود که مسئله را در ( ۱۸۵۲ ) با ویلیام همیلتن ( ۱۸۶۵ - ۱۸۰۵ ) در میان گذاشت. این مسئله مورد توجه همیلتن قرار نگرفت. و حدود ۲۵ سال مسکوت ماند. بعداً در ۱۸۷۸، جامعه علمی از طریقه اطلاعیهٔ آرثرکلی ( ۱۸۹۵ - ۱۸۲۱ ) در گردهمایی انجمن ریاضی لندن از مسئله آگاه شد. کیلی در ۱۸۷۹ مسئله را اولین مجله گزارش انجمن سلطنتی جغرافیا بیان کرد. مدت کوتاهی بعد از آن، سرآلفردکمپ ( ۱۹۲۲ - ۱۸۴۹ ) ریاضی دان انگلیسی، برهانی پیدا کرد که بیش از یک دهه غیرقابل تردید باقی ماند. بعداً در ۱۸۹۰ پرسی جان هیوود ( ۱۹۵۵ - ۱۸۶۱ ) ، ریاضی دان دیگر انگلیسی در کار کمپ خطا یافت.