رسم بياني للتقاطع

في نظرية المخططات ، يُعرف مخطط التقاطع بأنه مخطط يمثل نمط تقاطعات مجموعة من المجموعات . يمكن تمثيل أي مخطط كمخطط تقاطع، ولكن يمكن تعريف بعض الفئات الخاصة المهمة من المخططات من خلال أنواع المجموعات المستخدمة لتكوين تمثيل تقاطع لها.

بصورة رسمية، فإن الرسم البياني للتقاطع G هو رسم بياني غير موجه يتكون من مجموعة من المجموعات

${\displaystyle S_{i},\,\,\,i=0,1,2,\dots }$

عن طريق إنشاء رأس واحد v _i لكل مجموعة S _i ، وربط رأسين v _i و v _j بحافة كلما كان للمجموعتين المتناظرتين تقاطع غير فارغ ، أي

${\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}$

يمكن تمثيل أي رسم بياني غير موجه G كرسم بياني للتقاطع. لكل رأس vi _في G ، نُكوّن مجموعة Si تتكون من الحواف المتصلة بـ _vi ؛ عندئذٍ _، يكون تقاطع مجموعتين من هذا النوع غير فارغ إذا وفقط إذا كانت الرؤوس المتناظرة تشترك في حافة. ​​بالتالي، فإن G هو الرسم البياني للتقاطع للمجموعتين Si _.

قدّم إردوش وجودمان وبوسا (1966) بناءً أكثر كفاءة، إذ يتطلب عددًا إجماليًا أقل من العناصر في جميع المجموعات Sᵢ _{مجتمعة . في هذا البناء،} يكون العدد الإجمالي لعناصر المجموعة على الأكثر n² / ⁴ ، حيث n هو عدد رؤوس الرسم البياني. وينسبون ملاحظة أن جميع الرسوم البيانية هي رسوم بيانية تقاطعية إلى سزبيلراجن-مارتشيفسكي (1945) ، لكنهم يوصون أيضًا بمراجعة تشوليك (1964) . ويُعرف عدد التقاطع للرسم البياني بأنه الحد الأدنى لعدد العناصر الإجمالي في أي تمثيل تقاطعي لهذا الرسم البياني.

يمكن وصف العديد من عائلات الرسوم البيانية المهمة بأنها رسوم بيانية تقاطعية لأنواع أكثر تقييدًا من عائلات المجموعات، على سبيل المثال المجموعات المشتقة من نوع من التكوين الهندسي:

• يُعرَّف الرسم البياني للفترات بأنه الرسم البياني لتقاطع الفترات على خط الأعداد الحقيقية، أو الرسوم البيانية الفرعية المتصلة للرسم البياني للمسار .
• يمكن تعريف مخطط السواء بأنه مخطط تقاطع فترات الوحدة على خط الأعداد الحقيقية
• يُعرَّف الرسم البياني للأقواس الدائرية بأنه الرسم البياني لتقاطع الأقواس على دائرة .
• يُعرَّف الرسم البياني المضلع الدائري بأنه تقاطع المضلعات ذات الزوايا على دائرة.
• إحدى خصائص الرسم البياني الوترية هي أنه الرسم البياني للتقاطع بين الرسوم البيانية الفرعية المتصلة لشجرة .
• يُعرَّف الرسم البياني شبه المنحرف بأنه الرسم البياني لتقاطع أشباه المنحرفات المتكونة من خطين متوازيين. وهو تعميم لمفهوم الرسم البياني التبديلي ، والذي بدوره حالة خاصة من عائلة مكملات الرسوم البيانية للمقارنة، والمعروفة باسم الرسوم البيانية للمقارنة المشتركة.
• يُعرَّف الرسم البياني للقرص الواحد بأنه الرسم البياني لتقاطع الأقراص الواحدة في المستوى.
• الرسم البياني الدائري هو رسم بياني لتقاطع مجموعة من أوتار دائرة.
• تنص نظرية تعبئة الدوائر على أن الرسوم البيانية المستوية هي بالضبط رسوم بيانية تقاطعية لعائلات من الأقراص المغلقة في المستوى المحدد بدوائر غير متقاطعة.
• تنص فرضية شاينرمان (التي أصبحت الآن نظرية) على أن كل رسم بياني مستوٍ يمكن تمثيله أيضًا كرسم بياني لتقاطع قطع مستقيمة في المستوى. ومع ذلك، قد تكون رسوم تقاطع القطع المستقيمة غير مستوية أيضًا، ويُعدّ التعرف على رسوم تقاطع القطع المستقيمة أمرًا مكتملًا بالنسبة للنظرية الوجودية للأعداد الحقيقية ( شايفر 2010 ) .
• يُعرَّف الرسم البياني الخطي للرسم البياني G بأنه الرسم البياني للتقاطع لحواف G ، حيث نمثل كل حافة كمجموعة من نقطتي نهايتها.
• الرسم البياني للسلسلة هو رسم بياني لتقاطع المنحنيات على مستوى .
• يكون للرسم البياني خاصية الصندوقية k إذا كان الرسم البياني هو رسم تقاطع الصناديق متعددة الأبعاد ذات البعد k ، ولكن ليس ذات أي بعد أصغر.
• الرسم البياني للزمر هو رسم بياني لتقاطع الزمر القصوى لرسم بياني آخر
• الرسم البياني الكتلي أو شجرة الزمر هو رسم بياني للتقاطع بين مكونات ثنائية الاتصال لرسم بياني آخر

عرّف شاينرمان (1985) فئات تقاطع الرسوم البيانية ، وهي عائلات من الرسوم البيانية المحدودة التي يمكن وصفها بأنها رسوم بيانية لتقاطع مجموعات مُستمدة من عائلة معينة من المجموعات. ومن الضروري والكافي أن تتمتع هذه العائلة بالخصائص التالية:

• يجب أن يكون كل رسم بياني فرعي مستحث من رسم بياني في العائلة موجودًا أيضًا في العائلة.
• كل رسم بياني يتكون من رسم بياني في العائلة عن طريق استبدال رأس بزمرة يجب أن ينتمي أيضًا إلى العائلة.
• يوجد تسلسل لانهائي من الرسوم البيانية في العائلة، كل منها عبارة عن رسم بياني فرعي مستحث للرسم البياني التالي في التسلسل، مع خاصية أن كل رسم بياني في العائلة هو رسم بياني فرعي مستحث لرسم بياني في التسلسل.

إذا كانت تمثيلات الرسم البياني للتقاطع تتطلب شرطًا إضافيًا يتمثل في ضرورة تمثيل الرؤوس المختلفة بمجموعات مختلفة، فيمكن حذف خاصية توسيع الزمرة.

تُعدّ ترتيبات التضمين نظيراً نظرياً لرسوم التقاطع . فكما أن تمثيل التقاطع لرسم بياني يُصنّف كل رأس بمجموعة بحيث تكون الرؤوس متجاورة إذا وفقط إذا كانت مجموعاتها تتقاطع بشكل غير فارغ، فإن تمثيل التضمين f لمجموعة مرتبة جزئياً يُصنّف كل عنصر بمجموعة بحيث يكون x ≤ y لأي x و y في المجموعة المرتبة جزئياً إذا وفقط إذا كان f ( x ) ⊆ f ( y ).    

• مخطط الاتصال

• تشوليك، ك. (1964)، "تطبيقات نظرية الرسم البياني على المنطق الرياضي واللغويات"، نظرية الرسوم البيانية وتطبيقاتها (وقائع ندوة سمولينيتسه، 1963) ، براغ: دار نشر الأكاديمية التشيكوسلوفاكية للعلوم، ص 13-20 ، MR 0176940  .
• إيردوس، بول ؛ غودمان، أ. و؛ بوسا، لويس (1966)، "تمثيل الرسم البياني بواسطة تقاطعات المجموعات" (ملف PDF) ، المجلة الكندية للرياضيات ، 18 (1): 106-112 ، doi : 10.4153/CJM-1966-014-3 ، MR 0186575 ، S2CID 646660  .
• غولومبيك، مارتن تشارلز (1980)، نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية ، دار النشر الأكاديمية، رقم ISBN 0-12-289260-7.
• ماكي، تيري أ.؛ ماكموريس، إف آر (1999)، موضوعات في نظرية الرسم البياني للتقاطع ، سلسلة دراسات سيام في الرياضيات المتقطعة وتطبيقاتها، المجلد  2، فيلادلفيا: جمعية الرياضيات الصناعية والتطبيقية، ISBN 0-89871-430-3MR 1672910​ .
• Szpilrajn-Marczewski, E. (1945)، “Sur deux propriétés des class d’ensembles”، الصندوق. الرياضيات. , 33 : 303–307 , دوى : 10.4064/fm-33-1-303-307 , السيد 0015448 .
• شيفر، ماركوس (2010)، "تعقيد بعض المسائل الهندسية والطوبولوجية" (ملف PDF) ، رسم المخططات، الندوة الدولية السابعة عشرة، GS 2009، شيكاغو، إلينوي، الولايات المتحدة الأمريكية، سبتمبر 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد  5849، سبرينغر-فيرلاغ، الصفحات 334-344 ، doi : 10.1007/978-3-642-11805-0_32 ، ISBN  978-3-642-11804-3.
• شاينرمان، إدوارد ر. (1985)، "توصيف فئات تقاطع الرسوم البيانية"، الرياضيات المتقطعة ، 55 (2): 185-193 ، doi : 10.1016/0012-365X(85)90047-0 ، MR 0798535 .

• للحصول على نظرة عامة على كل من نظرية الرسوم البيانية المتقاطعة والفئات الخاصة المهمة من الرسوم البيانية المتقاطعة، انظر McKee & McMorris (1999) .

• جان كراتوشفيل، محاضرة فيديو حول الرسوم البيانية للتقاطع (يونيو 2007)
• إي. بريسنر، رحلة عبر مقاطعة إنترسيكشن غراف