عدد التقاطع (نظرية الرسم البياني)

في مجال نظرية المخططات الرياضية ، يُعرف عدد تقاطعات المخطط بـ${\displaystyle G=(V,E)}$هو أصغر عدد من العناصر اللازمة لتمثيل${\displaystyle G}$كرسم بياني لتقاطع المجموعات المنتهية . في هذا التمثيل، يُمثَّل كل رأس بمجموعة، ويرتبط رأسان بحافة عندما تشترك مجموعتاهما في عنصر واحد. يساوي عدد التقاطع أصغر عدد من الزمر (الرسوم البيانية الفرعية ذات الحواف بين جميع أزواج الرؤوس) اللازمة لتغطية جميع حواف الرسم البياني.${\displaystyle G}$[ ^{1 ] [ 2 ]} تمت دراسة كل من هذا الرقم والمشكلة الحسابية لإيجاده تحت العديد من الأسماء البديلة ^.

تشمل تطبيقات رقم التقاطع جدولة مستخدمي مورد مشترك أو عمليات على أجهزة الكمبيوتر ذات الكلمات التعليمية الطويلة جدًا ، وتخصيص عرض النطاق الترددي في شبكات الألياف الضوئية ، وتصور البيانات باستخدام شاشات عرض الأحرف المدمجة ، وتحليل الشبكات الغذائية في علم الأحياء، واستنتاج المركبات البروتينية من شبكات تفاعل البروتين-البروتين .

كل رسم بياني مع${\displaystyle n}$الرؤوس و${\displaystyle m}$عدد تقاطعات الحواف لا يتجاوز${\displaystyle \min(m,n^{2}/4)}$. يُعد حساب أو تقريب عدد التقاطع من المسائل الصعبة حسابيًا (NP-hard) ، ولكنه قابل للمعالجة باستخدام معلمات ثابتة .

لقد كانت الصيغتان المتكافئتان لعدد التقاطع، من حيث رسوم بيانية للتقاطع أو من حيث الزمر التي تغطي جميع الحواف، مصدراً للعديد من الأسماء لهذا المفهوم، وللمشكلة الحسابية المتمثلة في إيجاد تمثيل رسم بياني للتقاطع أو غطاء بواسطة الزمر.

تُسمى مجموعة الزمر التي تُغطي جميع حواف الرسم البياني بغطاء حواف الزمر ^{[ 3 ]} أو غطاء زمر الحواف ^{[ 4 ]} أو حتى غطاء الزمر فقط ، على الرغم من أن المصطلح الأخير غامض: إذ يمكن أن يكون غطاء الزمر أيضًا مجموعة من الزمر التي تُغطي جميع رؤوس الرسم البياني. ^{[ 5 ]} أحيانًا يُستخدم مصطلح "التغطية" بدلًا من "التغطية". ^{[ 6 ]} بالإضافة إلى تسميته برقم التقاطع، يُطلق على الحد الأدنى لعدد هذه الزمر اسم محتوى R [ ^{7 ] أو} رقم غطاء زمر الحواف ^{[ 4 ]} أو رقم غطاء الزمر . ^{[ 8 ]}

تُعرف مشكلة حساب عدد التقاطع بأسماء مختلفة، منها مشكلة عدد التقاطع ، ^{[ 9 ]} ومشكلة أساس الرسم البياني للتقاطع ، [ ^{10 ] والتغطية} بالزمر ، ^{[ 10 ]} ومشكلة تغطية زمر الحواف ، [ ^{9 ] و} (بسبب أحد تطبيقاتها المبكرة) مشكلة تعارض الكلمات المفتاحية . ^{[ 2 ]}

يمكن استخدام تمثيل الرسم البياني كرسم بياني مجرد لتقاطع المجموعات لإنشاء تمثيلات هندسية أكثر واقعية لتقاطع نفس الرسم البياني. على وجه الخصوص، إذا كان للرسم البياني عدد تقاطع${\displaystyle k}$، ويمكن تمثيلها كرسم بياني للتقاطع لـ${\displaystyle k}$الكرات الفائقة ذات الأبعاد n . يُطلق على أصغر بُعد للكرات الفائقة في هذا التمثيل اسم كروية الرسم البياني، لذا فإن الكروية أقل من أو تساوي عدد التقاطع. ^{[ 4 ]}

يمكن استخدام غطاء الزمر كنوع من أنظمة تصنيف التجاور للرسوم البيانية، حيث يُصنّف كل رأس بقيمة ثنائية، مما يسمح باختبار وجود حافة بين رأسين بسرعة عن طريق مقارنة قيمتيهما. تحتوي هذه التصنيفات على بت واحد لكل زمرة، يُضبط على الصفر إذا لم يكن الرأس جزءًا من الزمرة، وعلى الواحد إذا كان جزءًا منها. باستخدام نظام التصنيف هذا، يكون رأسان متجاورين إذا وفقط إذا كانت قيمة ` and` الثنائية لتصنيفاتهما غير صفرية. طول التصنيفات هو رقم تقاطع الرسم البياني. عندما يكون هذا الطول قصيرًا، يمكن لتمثيل حاسوبي للرسم البياني باستخدام هذه التصنيفات فقط أن يستهلك ذاكرة أقل من الطرق الصريحة مثل قوائم التجاور ، وأن يُجري اختبارات أسرع لتحديد ما إذا كان رأسان متجاورين. استُخدمت هذه الطريقة في تطبيق مبكر لأرقام التقاطع، لتصنيف مجموعة من الكلمات المفتاحية بحيث يمكن اكتشاف الكلمات المفتاحية المتضاربة بسرعة، وذلك بواسطة إي. كيلرمان من شركة IBM . لهذا السبب، يُعرف أيضًا بمشكلة تعارض الكلمات المفتاحية . ^{[ 13 ] [ 14 ]} وبالمثل، في الهندسة الحسابية ، تُعتبر التمثيلات القائمة على عدد التقاطع تمثيلًا مُختصرًا لرسوم بيانية الرؤية ، على الرغم من وجود مدخلات هندسية تتطلب لهذا التمثيل عددًا شبه تربيعي من الزمر. ^{[ 15 ]}

يُستمد نوع آخر من التطبيقات من مشاكل الجدولة التي تتطلب جدولة عدة مستخدمين لمورد مشترك لفترات زمنية محددة، بحيث لا تُجدول الطلبات غير المتوافقة في نفس الفترة الزمنية، بينما تُخصص فترة زمنية واحدة على الأقل لكل زوج من الطلبات المتوافقة. يُحدد عدد نقاط التقاطع في رسم بياني للتوافقات الحد الأدنى لعدد الفترات الزمنية اللازمة لمثل هذه الجدولة: فترة زمنية واحدة لكل مجموعة فرعية في غطاء المجموعة الفرعية لرسم بياني التوافق. ^{[ 2 ]} في تصميم المترجمات لأجهزة الكمبيوتر ذات الكلمات التعليمية الطويلة جدًا ، تظهر مشكلة جدولة مختلفة: إذ يمكن لهذه الأجهزة تنفيذ عمليات متعددة في تعليمة واحدة، لذا يجب على المترجم تجميع العمليات المطلوب تنفيذها في أقل عدد ممكن من التعليمات، مع التأكد من أن كل مجموعة تتكون من عمليات تسمح بنية الكمبيوتر بدمجها. يمكن استخدام غطاء مجموعة فرعية صغير لرسم بياني للعمليات غير المتوافقة لتمثيل عدم توافقها بعدد قليل من الموارد الاصطناعية (مورد واحد لكل مجموعة فرعية)، مما يسمح باستخدام تقنيات الجدولة القائمة على الموارد لتخصيص العمليات للتعليمات . ^{[ 16 ]}

لاحظ الباحثان إف بي شيبارد وإيه فيتا، من مختبرات بيل وجامعة ماكجيل ، أن عدد نقاط التقاطع في الشبكة يساوي الحد الأدنى لعدد القيود اللازمة في صياغة برمجة عددية صحيحة لمسألة حساب أكبر مجموعة مستقلة . في هذه الصياغات، يوجد متغير لكل رأس يمكن أن يأخذ إحدى القيمتين 0 أو 1، وقيد ينص على أن مجموع المتغيرات في كل زمرة من زمر الغطاء لا يتجاوز واحدًا. ويجادل الباحثان بأن أعداد نقاط التقاطع هذه صغيرة بالنسبة لرسوم بيانية تقاطع المسارات في بعض شبكات اتصالات الألياف الضوئية ، مما يفسر سهولة حل بعض مسائل التحسين في تخصيص عرض النطاق الترددي على هذه الشبكات. ^{[ 3 ]}

في مجال الإحصاء وتصوير البيانات ، تُستخدم أغطية مجموعات الحواف في الرسم البياني الذي يُمثل أزواجًا من المتغيرات غير القابلة للتمييز إحصائيًا، لإنتاج عروض حرفية مُختصرة تُساعد في تصور المقارنات الثنائية المتعددة. تتشكل هذه العروض باختيار حرف أو علامة بصرية أخرى لكل مجموعة، ثم تسمية كل متغير بالأحرف الخاصة بالمجموعات التي ينتمي إليها. تُوفر هذه الطريقة تمثيلًا بيانيًا للمتغيرات غير القابلة للتمييز: فهي غير قابلة للتمييز إذا كانت تشترك في حرف واحد على الأقل في تسمياتها. ^{[ 17 ] [ 18 ]}

في تحليل الشبكات الغذائية التي تصف علاقات المفترس والفريسة بين أنواع الحيوانات، يُعدّ مخطط التنافس أو مخطط تداخل المتخصصة مخططًا غير موجه، حيث تمثل الرؤوس الأنواع، وتمثل الحواف أزواجًا من الأنواع التي تتنافس على نفس الفريسة. ويمكن اشتقاق هذه المخططات من مخطط موجه غير دوري يمثل علاقات المفترس والفريسة عن طريق رسم حافة.${\displaystyle uv}$في الرسم البياني للمنافسة كلما وُجد نوع من الفرائس${\displaystyle w}$بحيث يحتوي الرسم البياني لعلاقة المفترس بالفريسة على حواف${\displaystyle u\to w}$و${\displaystyle v\to w}$يجب أن يحتوي كل رسم بياني للمنافسة على رأس معزول واحد على الأقل ، ويمثل عدد المنافسة لأي رسم بياني أصغر عدد من الرؤوس المعزولة التي يمكن إضافتها لتحويله إلى رسم بياني للمنافسة. بيولوجيًا، إذا تمت ملاحظة جزء من رسم بياني للمنافسة، فإن عدد المنافسة يمثل أصغر عدد ممكن من أنواع الفرائس غير الملاحظة اللازمة لتفسيره. عدد المنافسة يساوي على الأكثر عدد التقاطع: يمكن تحويل رسم بياني غير موجه إلى رسم بياني للمنافسة بإضافة نوع من الفرائس لكل زمرة في غطاء زمر الحواف. ومع ذلك، فإن هذه العلاقة ليست دقيقة تمامًا، لأنه من الممكن أيضًا أن يكون نوع المفترس فريسة لأنواع أخرى. في رسم بياني مع${\displaystyle n}$الرؤوس، على الأكثر${\displaystyle n-2}$يمكن أن يكون أحدها فريسة لأكثر من نوع آخر، لذا فإن عدد المنافسة لا يقل عن عدد التقاطع مطروحًا منه${\displaystyle n-2}$[ ^{19 ]​}

استُخدمت أغطية الزمر الحافية أيضًا لاستنتاج وجود معقدات بروتينية ، وهي أنظمة من البروتينات المتفاعلة فيما بينها، من شبكات تفاعل البروتين-بروتين التي تصف فقط التفاعلات الثنائية بين البروتينات. ^{[ 20 ]} وبشكل أعم، جادل غيوم ولاتابي بأنه بالنسبة للشبكات المعقدة من جميع الأنواع، فإن استبدال الشبكة برسم بياني ثنائي الأجزاء يربط رؤوسها بالزمر في غطاء الزمر يُبرز البنية في الشبكة. ^{[ 21 ]}

كل رسم بياني مع${\displaystyle m}$عدد تقاطعات الحواف لا يتجاوز${\displaystyle m}$وينتج هذا عن ملاحظة أن كل حافة هي في حد ذاتها زمرة ثنائية الرؤوس.${\displaystyle m}$من هذه الزمر، وهي تغطي معًا جميع الحواف، لذا فهي تشكل غطاءً زمرًا حافيًا بحجم${\displaystyle m}$[ ^{22 ]​}

صحيح أيضاً أن كل رسم بياني مع${\displaystyle n}$عدد تقاطعات الرؤوس لا يتجاوز${\displaystyle \lfloor n^{2}/4\rfloor }$وبقوة أكبر، حواف كل${\displaystyle n}$يمكن تغطية الرسم البياني ذي الرؤوس المتعددة بحد أقصى${\displaystyle \lfloor n^{2}/4\rfloor }$الزمر، وكلها إما حواف مفردة أو مثلثات. يمكن لخوارزمية جشعة إيجاد هذا الغطاء بإزالة رأسين متجاورين وتغطية الرسم البياني المتبقي استقرائيًا . بعد إعادة الرأسين المُزالين، تُضمّن الخوارزمية في الغطاء كل مثلث ينتمي إليه كلاهما، مما يُغطي أي حواف تربطهما بجيران مشتركين. أي حواف متبقية تربط أحد الرأسين المُزالين بجار، دون تشكيل مثلث، تُغطى بزمر ثنائية الرؤوس. إذا لم تكن هناك مثلثات تشمل الرأسين المُزالين، فإن الحافة بينهما تُغطى أيضًا بزمرة ثنائية الرؤوس. وفقًا لفرضية الاستقراء، فإن غطاء الرسم البياني بعد إزالة الرأسين يحتوي على أكثر من${\displaystyle \lfloor (n-2)^{2}/4\rfloor }$الزمر. يساهم الرأسان المُزالان على الأكثر برأس آخر${\displaystyle n-1}$تكون الزمر في أقصى حالاتها عندما تكون جميع الرؤوس الأخرى جيرانًا غير مشتركين ويجب استخدام الحافة بين الرأسين كزمرة. جمع هاتين الكميتين يعطي${\displaystyle \lfloor n^{2}/4\rfloor }$عدد المجموعات الكاملة. ^{[ 2 ] [ 12 ]} وهذا يُعمم نظرية مانتل التي تنص على أن الرسم البياني الخالي من المثلثات يحتوي على أكثر من${\displaystyle \lfloor n^{2}/4\rfloor }$الحواف، لأنه في الرسم البياني الخالي من المثلثات، فإن غطاء الحافة الأمثل الوحيد للزمرة يحتوي على زمرة واحدة لكل حافة، وبالتالي فإن عدد التقاطعات يساوي عدد الحواف. ^{[ 2 ]}

يمكن الحصول على حد أكثر دقة عندما يكون عدد الحواف أكبر من ذلك بكثير.${\displaystyle {\tfrac {n^{2}}{4}}}$. يترك${\displaystyle p}$ليكن عدد أزواج الرؤوس غير المتصلة بحافة في الرسم البياني المعطى${\displaystyle G}$ودع${\displaystyle t}$ليكن العدد الصحيح الوحيد الذي${\displaystyle (t-1)t\leq p<t(t+1)}$ثم رقم التقاطع لـ${\displaystyle G}$هو على الأكثر${\displaystyle p+t}$[ ^{2 ] [ 23 ]} تتميز الرسوم البيانية التي تُكمل الرسم البياني المتفرق ^بأعداد تقاطع صغيرة: عدد تقاطع أي${\displaystyle n}$الرسم البياني ذو الرؤوس${\displaystyle G}$هو على الأكثر${\displaystyle 2e^{2}(d+1)^{2}\ln n}$، أين${\displaystyle e}$هو أساس اللوغاريتم الطبيعي و${\displaystyle d}$هي أعلى درجة للرسم البياني المكمل لـ${\displaystyle G}$[ ^{6 ]​}

يستنتج من نتائج بنية الرسوم البيانية الخالية من المخالب أنه عندما يكون الرسم البياني متصلاً${\displaystyle n}$يحتوي الرسم البياني الخالي من المخالب ذو الرؤوس على ثلاثة رؤوس مستقلة على الأقل، ويكون عدد تقاطعاته على الأكثر${\displaystyle n}$لا تزال مسألة ما إذا كان هذا ينطبق على جميع الرسوم البيانية الخالية من المخالب دون اشتراط امتلاكها مجموعات مستقلة كبيرة، مسألةً لم تُحل بعد. ^{[ 8 ]} ومن الفئات الفرعية المهمة للرسوم البيانية الخالية من المخالب ، الرسوم البيانية الخطية ، وهي رسوم بيانية تمثل حوافًا وأزواجًا متلامسة من حواف رسم بياني آخر.${\displaystyle G}$. غطاء الزمرة الأمثل للرسم البياني الخطي${\displaystyle L(G)}$يمكن تشكيلها باستخدام زمرة واحدة لكل مثلث في${\displaystyle G}$يحتوي المثلث على رأسين أو ثلاثة رؤوس من الدرجة الثانية، وزمرة واحدة لكل رأس من الدرجة الثانية على الأقل وليس رأسًا من الدرجة الثانية في أحد هذه المثلثات. عدد التقاطع هو عدد الزمر من هذين النوعين. ^{[ 7 ]}

في نموذج Erdős-Rényi-Gilbert للرسوم البيانية العشوائية ، حيث تكون جميع الرسوم البيانية على${\displaystyle n}$تكون احتمالية وجود الرؤوس المصنفة متساوية (أو ما يعادلها، وجود كل حافة أو غيابها، بشكل مستقل عن الحواف الأخرى، باحتمالية معينة).${\displaystyle {\tfrac {1}{2}}}$)، رقم التقاطع لـ${\displaystyle n}$الرسم البياني العشوائي ذو الرؤوس المتعددة يكون باحتمالية عالية ضمن عامل ثابت من$${\displaystyle {\frac {n^{2}}{\log ^{2}n}},}$$أصغر بمعامل${\displaystyle \log ^{2}n}$أكثر من عدد الحواف. في هذه الرسوم البيانية، تحتوي أكبر الزمر (باحتمالية عالية) على عدد لوغاريتمي من الرؤوس فقط، مما يعني أن هذا العدد منها يكفي لتغطية جميع الحواف. أما الاتجاه الآخر للحد فيتضمن إثبات إمكانية إيجاد عدد كافٍ من الزمر ذات الحجم اللوغاريتمي لتغطية معظم الحواف، مما يسمح بتغطية الحواف المتبقية بواسطة زمر ذات رأسين. ^{[ 24 ] [ 25 ]}

انصبّ جزء كبير من الأبحاث المبكرة حول أرقام التقاطع على حساب هذه الأرقام على رسوم بيانية محددة مختلفة، مثل الرسوم البيانية التي تم تشكيلها عن طريق إزالة رسم بياني فرعي كامل أو مطابقة مثالية من رسم بياني كامل أكبر. ^{[ 26 ]}

اختبار ما إذا كان الرسم البياني المعطى${\displaystyle G}$يحتوي على رقم تقاطع على الأكثر رقم معين${\displaystyle k}$هي مسألة NP-كاملة . ^{[ 10 ] [ 7 ] [ 14 ]} لذلك، فإن حساب عدد التقاطعات في رسم بياني مُعطى هو أيضًا مسألة NP-صعبة. وبدورها، استُخدمت صعوبة حساب عدد التقاطعات لإثبات أن التعرف على مربعات الرسوم البيانية المنقسمة هو مسألة NP-كاملة . ^{[ 27 ]}

ومع ذلك، فإن مشكلة حساب عدد التقاطعات قابلة للحل باستخدام معلمات ثابتة : أي أنه يمكن حلها في فترة زمنية محدودة بكثير حدود في${\displaystyle n}$مضروبًا في دالة أكبر ولكن قابلة للحساب لرقم التقاطع${\displaystyle k}$[ ^{5 ] [ 28 ]} ويمكن إثبات ذلك بملاحظة أن هناك على ^الأكثر${\displaystyle 2^{k}}$تُعرَّف الجوارات المغلقة المتميزة في الرسم البياني بأنها رؤوس تنتمي إلى نفس مجموعة الزمر ولها نفس الجوار ، وأن الرسم البياني المُشكَّل باختيار رأس واحد من كل جوار مغلق له نفس عدد التقاطعات في الرسم البياني الأصلي. ^{[ 5 ] [ 29 ]} لذلك، في وقت متعدد الحدود، يمكن اختزال المدخلات إلى نواة أصغر بحد أقصى${\textstyle 2^{k}}$الرؤوس. تطبيق بحث شامل على الأكثر${\displaystyle 2^{k}!}$إن تخصيص مجموعات متميزة من الزمر للرؤوس المتبقية يعطي زمنًا ذا أس مزدوج في${\displaystyle k}$[ ^{5 ] [ 28 ]} الاعتماد الأسي المزدوج ^على${\displaystyle k}$لا يمكن اختزالها إلى دالة أسية واحدة باستخدام نواة ذات حجم متعدد الحدود، إلا إذا انهار التسلسل الهرمي متعدد الحدود ، ^{[ 30 ]} وإذا كانت فرضية الزمن الأسي صحيحة، فإن الاعتماد الأسي المزدوج ضروري بغض النظر عن استخدام النواة. ^{[ 28 ]} في الرسوم البيانية ذات عرض الشجرة المحدود ، يمكن للبرمجة الديناميكية على تحليل شجري للرسم البياني إيجاد عدد التقاطعات في زمن خطي، ^{[ 31 ] [ 20 ]} لكن الخوارزميات الأبسط القائمة على مجموعات محدودة من قواعد الاختزال لا تعمل. ^{[ 31 ]}

يوجد ثابت${\displaystyle c>0}$بحيث لا يمكن تقريب المشكلة في وقت متعدد الحدود بنسبة تقريب أفضل من${\displaystyle n^{c}}$[ ^{32 ]} إن أفضل نسبة تقريب تم التوصل إليها أفضل من النسبة التافهة ^.${\displaystyle O(n^{2})}$بمعامل لوغاريتمي متعدد فقط . ^{[ 5 ]} كما بحث الباحثون في هذا المجال الكفاءة الحسابية للأساليب الاستدلالية ، دون ضمانات على جودة الحلول التي تنتجها، وسلوكها على الشبكات الواقعية. ^{[ 5 ] [ 33 ]}

توجد خوارزميات أكثر كفاءة لأنواع خاصة معينة من الرسوم البيانية. يساوي عدد التقاطع في الرسم البياني الفاصل دائمًا عدد الزمر القصوى ، والذي يمكن حسابه في وقت متعدد الحدود. ^{[ 34 ] [ 35 ]} بشكل عام، في الرسوم البيانية الوترية ، يمكن حساب عدد التقاطع بواسطة خوارزمية تأخذ في الاعتبار الرؤوس في ترتيب حذف للرسم البياني (ترتيب يشكل فيه كل رأس وجيرانه اللاحقون زمرة)، وذلك لكل رأس${\displaystyle v}$يشكل زمرة لـ${\displaystyle v}$وجيرانها اللاحقين كلما كان أحد الحواف على الأقل متصلاً بـ${\displaystyle v}$لا يغطيها أي زمرة سابقة. ^{[ 35 ]} من الممكن أيضًا إيجاد عدد التقاطع في وقت خطي في الرسوم البيانية ذات الأقواس الدائرية . ^{[ 36 ]} ومع ذلك، على الرغم من أن هذه الرسوم البيانية لا تحتوي إلا على عدد كثير الحدود من الزمر للاختيار من بينها للتغطية، فإن وجود عدد قليل من الزمر وحده لا يكفي لجعل المشكلة سهلة: توجد عائلات من الرسوم البيانية ذات عدد كثير الحدود من الزمر التي يظل عدد التقاطع فيها صعبًا من نوع NP. ^{[ 9 ]} يمكن أيضًا إيجاد عدد التقاطع في وقت كثير الحدود للرسوم البيانية التي تبلغ درجتها القصوى خمسة، ولكنه صعب من نوع NP للرسوم البيانية التي تبلغ درجتها القصوى ستة. ^{[ 37 ] [ 38 ]} في الرسوم البيانية المستوية ، يظل حساب عدد التقاطع بدقة صعبًا من نوع NP، ولكنه يحتوي على مخطط تقريبي كثير الحدود يعتمد على تقنية بيكر . ^{[ 20 ]}

• البُعد الثنائي ، وهو أصغر عدد من المجموعات الثنائية اللازمة لتغطية جميع حواف الرسم البياني
• الرسم البياني المقيد ، وهو نوع من الرسوم البيانية يتميز بأغطية حواف الزمر ذات شكل خاص

• وايسشتاين، إريك دبليو ، "عدد التقاطع" ، عالم الرياضيات{{cite web}}: CS1 maint: overridden setting ( link )