گراف تقاطع

گراف اشتراکی (به انگلیسی: 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) = {{v_i, v_j} | S_i ∩ S_j ≠ ∅}.

رابطه بین گراف تقاطع و مسئله رنگ آمیزی یک گراف

در مسئله مطرح شده در بالا فرض کنید چراغ راهنمایی یک تقاطع چند زمانه است و تعداد زمان‌های آن با توجه به جهت‌های حرکت (گردش به راست، چپ، وغیره) مشخص می‌شود. برای سادگی کار فرض می‌کنیم چراغ مورد نظر K رنگ دارد که با رنگ‌های ۱ تا K مشخص شده‌است. در مدل گراف مسئله انتساب یک یا چند رنگ به هر رأس گراف تقاطع است. به‌طوری‌که تعداد این رنگ‌ها همان K است و ما می‌خواهیم کمترین مقدار آن را بدست آوریم.

رنگ آمیزی گراف تقاطع

باید گراف را به گونه‌ای رنگ کرد که هیج دو راس دو سر یک یال رنگ یکسان نداشنه باشند. کمینه تعداد رنگ‌های لازم برای رنگ کردن G می‌نامیم وبا X(G) نشان می‌دهیم. حدود سال ۱۸۵۰، فرانسیس گاتری (۱۸۹۹-۱۸۳۱) بعد از نشان دادن چگونگی رنگ آمیزی استان‌های نقشه انگلیس تنها باچهار رنگ، به مسئله کلی علاقه‌مند شد. اندکی بعد از آن، مسئله چهار رنگ را به برادر کوچکش فردریک نشان داد. در آن زمان فردریک گاتری (۱۸۶۶-۱۸۳۳) دانشجوی اوگاستس دمورگن (۱۸۷۱-۱۸۰۶) بود که مسئله را در (۱۸۵۲) با ویلیام همیلتن (۱۸۶۵-۱۸۰۵) در میان گذاشت. این مسئله مورد توجه همیلتن قرار نگرفت. و حدود ۲۵ سال مسکوت ماند. بعداً در ۱۸۷۸، جامعه علمی از طریقه اطلاعیهٔ آرثرکلی (۱۸۹۵-۱۸۲۱) در گردهمایی انجمن ریاضی لندن از مسئله آگاه شد.کیلی در ۱۸۷۹ مسئله را اولین مجله گزارش انجمن سلطنتی جغرافیا بیان کرد. مدت کوتاهی بعد از آن، سرآلفردکمپ(۱۹۲۲-۱۸۴۹) ریاضی‌دان انگلیسی، برهانی پیدا کرد که بیش از یک دهه غیرقابل تردید باقی ماند. بعداً در ۱۸۹۰ پرسی جان هیوود (۱۹۵۵-۱۸۶۱)، ریاضی‌دان دیگر انگلیسی در کار کمپ خطا یافت.

مسئله تا سال ۱۹۷۶ حل نشده ماند، تا اینکه سرانجام کنت آپل و ولفگانک هیکن را حل کردند. در برهان تحلیل کامپیوتری بسیار پیچیده‌ای از پیکربندهای (کاهش پذیر) ۱۹۳۶ به کار رفته‌است.

گرچه تنها چهار رنگ برای رنگ آمیزی خاص ناحیه‌های یک نقشه هامنی مورد نیاز است، ولی برای رنگ آمیزی خاص راسهای گرافهای غیرهامنی، بیش از چهار رنگ لازم است.

منابع

• ریاضیات گسسته وترکیبیاتی از دیدگاه کاربردی مولف رالف گریمالدی
• داده ساختارها ومبانی الگوریتم‌ها مولف دکتر محمد قدسی

Kenneth H, Rosen (1998). "Graphs". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007. {{cite book}}: Check date values in: |بازبینی= (help)