البعد الثنائي

في مجالي نظرية المخططات والتحسين التوافقي ، يُعرف البُعد الثنائي أو عدد تغطية الثنائيات للمخطط G = ( V , E ) بأنه الحد الأدنى لعدد الثنائيات (أي المخططات الفرعية الثنائية الكاملة) اللازمة لتغطية جميع الحواف في E. تُسمى مجموعة الثنائيات التي تغطي جميع الحواف في G بغطاء حواف الثنائيات ، أو أحيانًا غطاء الثنائيات . يُرمز للبُعد الثنائي للمخطط G غالبًا بالرمز d ( G ).   

يُقدّم الرسم البياني التالي مثالاً على غطاء حافة ثنائي الزخرفة:

• 
  رسم بياني ثنائي الأجزاء...
• 
  ...وغطاء بأربعة أجزاء متداخلة
• 
  المجموعة الحمراء من الغلاف
• 
  المجموعة الزرقاء من الغلاف
• 
  المجموعة الخضراء من الغلاف
• 
  البيكليك الأسود من الغلاف

البعد الثنائي للرسم البياني الكامل ذي n رأسًا ،${\displaystyle K_{n}}$يكون${\displaystyle \lceil \log _{2}n\rceil }$.

البعد الثنائي لرسم بياني تاجي ذي 2n رأس يساوي${\displaystyle \sigma (n)}$، أين

${\displaystyle \sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}}$

هي الدالة العكسية لمعامل ذي الحدين المركزي ( دي كاين، غريغوري وبولمان 1981 ) .

البُعد الثنائي لـ${\displaystyle n\times m}$الرسم البياني الشبكي هو ${\displaystyle {\frac {nm}{2}}-1}$، لو${\displaystyle m}$زوجي و${\displaystyle n-1=k(m-1)+2\ell }$بالنسبة لبعض الأعداد الصحيحة${\displaystyle 0\leq \ell <k}$وهو${\displaystyle {\big \lfloor }{\frac {nm}{2}}{\big \rfloor }}$وإلا ( Guo, Huynh & Macchia 2019 ) .

حدد فيشبورن وهامر (1996) البعد الثنائي لبعض الرسوم البيانية الخاصة. على سبيل المثال، المسار${\displaystyle P_{n}}$ لديه${\displaystyle d(P_{n})=\lfloor n/2\rfloor }$والدورة${\displaystyle C_{n}}$لديه${\displaystyle d(C_{n})=\lceil n/2\rceil }$.

تُعدّ المهمة الحسابية لتحديد البُعد الثنائي للرسم البياني المُعطى G مسألة تحسين . ويمكن صياغة مسألة تحديد البُعد الثنائي على النحو التالي:

مثال: رسم بياني${\displaystyle G=(V,E)}$وعدد صحيح موجب${\displaystyle k}$.

السؤال: هل تقبل G غطاءً حافيًا ثنائيًا يحتوي على أكثر من${\displaystyle k}$مجموعات ثنائية؟

تظهر هذه المشكلة كمشكلة GT18 في كتاب غاري وجونسون الكلاسيكي حول اكتمال NP ، وهي إعادة صياغة مباشرة إلى حد ما لمشكلة قرار أخرى تتعلق بعائلات المجموعات المحدودة.

تظهر مسألة أساس المجموعة كمسألة SP7 في كتاب غاري وجونسون. هنا، لعائلة${\displaystyle {\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}}$من المجموعات الجزئية لمجموعة منتهية${\displaystyle {\mathcal {U}}}$، أساس محدد لـ${\displaystyle {\mathcal {S}}}$هي عائلة أخرى من المجموعات الفرعية${\displaystyle {\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}}$ل${\displaystyle {\mathcal {U}}}$بحيث تكون كل مجموعة${\displaystyle S_{i}}$يمكن وصفها بأنها اتحاد بعض العناصر الأساسية من${\displaystyle {\mathcal {B}}}$تُعطى مسألة أساس المجموعة الآن على النحو التالي:

مثال: مجموعة منتهية${\displaystyle {\mathcal {U}}}$عائلة${\displaystyle {\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}}$من مجموعات فرعية من${\displaystyle {\mathcal {U}}}$، وعدد صحيح موجب k .

السؤال: هل توجد مجموعة أساسية للحجم على الأكثر${\displaystyle k}$ل${\displaystyle {\mathcal {S}}}$؟

في صيغتها السابقة، أثبت أورلين (1977) أن المسألة من فئة NP- كاملة ، حتى بالنسبة للرسوم البيانية ثنائية الأجزاء . وقد أثبت ستوكمير (1975) سابقًا أن الصيغة كمسألة أساس مجموعة من فئة NP- كاملة . وتبقى المسألة من فئة NP- صعبة حتى لو اقتصرنا على الرسوم البيانية ثنائية الأجزاء التي يُضمن أن يكون بُعدها الثنائي على الأكثر${\displaystyle O(\log \,\!n)}$حيث يرمز n إلى حجم حالة المسألة المعطاة ( Gottlieb, Savage & Yerukhimovich 2005 ) . ومن الجوانب الإيجابية، أن المسألة قابلة للحل في وقت متعدد الحدود على الرسوم البيانية ثنائية الأجزاء الخالية من الدومينو ( Amilhastre, Janssen & Vilarem 1997 ) .

فيما يتعلق بوجود خوارزميات تقريبية ، أثبت سيمون (1990) أنه لا يمكن تقريب المشكلة بشكل جيد (بافتراض أن P ≠ NP ). في الواقع، تبين أن البعد الثنائي يمثل مسألة صعبة التقريب من نوع NP.${\displaystyle |V|^{1/3-\epsilon }}$لكل ثابت${\displaystyle \epsilon >0}$بواسطة غروبر وهولزر (2007) و NP - يصعب تقريبها ضمن${\displaystyle |V|^{1-\epsilon }}$بواسطة تشاليرمسوك وآخرون (2014) ، حتى على الرسوم البيانية ثنائية الأجزاء.

في المقابل، يُعدّ إثبات إمكانية حلّ المشكلة باستخدام معلمات ثابتة تمرينًا في تصميم خوارزميات التكوين ، وهو ما ورد في كتاب داوني وفيلوز (1999) . كما قدّم فليشنر وآخرون (2009) حدًا ملموسًا لحجم النواة الناتجة، والذي حسّنه نور وآخرون (2010) . في الواقع، بالنسبة لرسم بياني ثنائي الأجزاء مُعطى على n رأسًا، يمكن حسم الأمر في وقت${\displaystyle O(f(k))+n^{3}}$مع${\displaystyle f(k)=2^{k2^{k-1}+3k}}$ما إذا كان بُعدها الثنائي على الأكثر k ( نور وآخرون 2010 ) .

تظهر مشكلة تحديد البُعد الثنائي للرسم البياني في سياقات حاسوبية متنوعة. فعلى سبيل المثال، في أنظمة الحاسوب، يُمكن السماح لمستخدمين مختلفين بالوصول إلى موارد مُحددة أو منعهم من ذلك. في نظام التحكم بالوصول القائم على الأدوار ، يُوفر كل دور حقوق الوصول إلى مجموعة من الموارد. يُمكن للمستخدم امتلاك أدوار متعددة، ويملك إذن الوصول إلى جميع الموارد الممنوحة له من خلال بعض أدواره. كما يُمكن أن يمتلك دور واحد أكثر من مستخدم. تكمن مشكلة استخراج الأدوار في إيجاد الحد الأدنى من الأدوار، بحيث تُتيح أدوار كل مستخدم مجتمعةً الوصول إلى جميع الموارد المُحددة. تُؤدي مجموعة المستخدمين مع مجموعة الموارد في النظام بشكل طبيعي إلى رسم بياني ثنائي، حيث تُمثل حوافه الأذونات. كل مجموعة ثنائية في هذا الرسم البياني تُمثل دورًا مُحتملًا، والحلول المُثلى لمشكلة استخراج الأدوار هي تحديدًا الحد الأدنى من تغطية حواف المجموعات الثنائية ( إيني وآخرون، 2008 ) .

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

يوجد تطبيق مختلف في علم الأحياء، حيث يتم استخدام أغطية حواف ثنائية الحد الأدنى في النماذج الرياضية لعلم مصل مستضد الكريات البيضاء البشرية (HLA) ( Nau et al. 1978 ) .

• قائمة مسائل NP-كاملة
• عدد التقاطع (نظرية الرسم البياني) ، وهو الحد الأدنى لعدد المجموعات الفرعية اللازمة لتغطية حواف الرسم البياني

• أميلهستر، جيروم؛ جانسن، فيليب؛ فيلاريم، ماري-كاثرين (1997)، "حساب غطاء ثنائي الزمر الأدنى متعدد الحدود للرسوم البيانية ثنائية الأجزاء الخالية من الدومينو" ، وقائع الندوة السنوية الثامنة لجمعية ACM-SIAM حول الخوارزميات المنفصلة، ​​5-7 يناير 1997، نيو أورليانز، لويزيانا ، ACM/SIAM، الصفحات 36-42 ، ISBN  9780898713909
• تشاليرمسوك، بارينيا؛ هيدريش، ساندي؛ هولم، يوجينيا؛ كارينباور، أندرياس (2014)، "نتائج التقريب شبه المحكم لتغطية وتقسيم ثنائيات الزمر الدنيا" ، الندوة الأوروبية حول الخوارزميات
• دي كاين، دومينيك؛ غريغوري، ديفيد أ.؛ بولمان، نورمان ج. (1981)، "الرتبة البولية للمصفوفات الصفرية-الواحدية"، في كادوجان، تشارلز سي. (محرر)، المؤتمر الكاريبي الثالث حول التوافقية والحوسبة ، قسم الرياضيات، جامعة جزر الهند الغربية، ص 169-173 ، MR 0657202  .
• داوني، رود ؛ فيلوز، مايكل ر. (1999)، التعقيد المُعَلم ، سبرينغر، ISBN 0-387-94883-X.
• إيني، ألينا؛ هورن، ويليام ج.؛ ميلوسافليفيتش، نيكولا؛ راو، براساد؛ شرايبر، روبرت؛ تارجان، روبرت إندري (2008)، "طرق سريعة ودقيقة واستدلالية لمشاكل تقليل الأدوار"، في راي، إندراكشي؛ لي، نينغوي (محرران)، الندوة الثالثة عشرة لجمعية الحوسبة الآلية حول نماذج وتقنيات التحكم في الوصول (SACMAT 2008) ، جمعية الحوسبة الآلية، الصفحات 1-10 .
• فيشبورن، بيتر سي .؛ هامر، بيتر لاديسلاو (1996)، "الأبعاد الثنائية ودرجات الرسوم البيانية الثنائية"، الرياضيات المتقطعة ، 160 ( 1-3 ): 127-148 ، doi : 10.1016/0012-365X(95)00154-O.
• فليشنر، هربرت؛ موجوني، إيغبرت؛ باولوسما، دانيال؛ سزيدر، ستيفان (2009)، "تغطية الرسوم البيانية بعدد قليل من الرسوم البيانية الفرعية الثنائية الكاملة"، علوم الحاسوب النظرية ، 410 ( 21-23 ): 2045-2053 ، doi : 10.1016/j.tcs.2008.12.059.
• غاري، مايكل ر.؛ جونسون ، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 0-7167-1045-5.
• غوتليب، لي-آد جيه؛ سافاج، جون إي ؛ يروخيموفيتش، أركادي (2005)، "تخزين البيانات بكفاءة في المصفوفات النانوية الكبيرة"، نظرية أنظمة الحوسبة ، 38 (4): 503-536 ، doi : 10.1007/s00224-004-1196-9 ، S2CID 5844939 .
• غروبر، هيرمان؛ هولزر، ماركوس (2007)، "عدم إمكانية تقريب تعقيد الحالة والانتقال غير الحتمي بافتراض P <> NP."، في هارجو، تيرجو؛ كارهوماكي، جوهاني؛ ليبيستو، أرتو (محررون)، المؤتمر الدولي الحادي عشر حول التطورات في نظرية اللغة (DLT 2007) ، سلسلة محاضرات في علوم الحاسوب، المجلد  4588، توركو، فنلندا: سبرينغر، الصفحات 205-216 ، doi : 10.1007/978-3-540-73208-2_21 ، ISBN  978-3-540-73207-5.
• غو، كريستال؛ هوينه، توني؛ ماكيا، ماركو (2019)، "عدد تغطية الثنائيات للشبكات"، المجلة الإلكترونية للتوافقية ، 26 (4)، arXiv : 1811.03396 ، doi : 10.37236/8316.
• مونسون، سيلفيا د.؛ بولمان، نورمان ج.؛ ريس، رولف (1995)، "دراسة استقصائية لأغطية الزمر والزمر الثنائية وتحليلات المصفوفات (0،1)"، نشرة ICA ، 14 : 17-86 ، MR 1330781 .
• ناو، دي إس؛ ماركوفسكي، جي؛ وودبري، إم إيه؛ آموس، دي بي (1978)، "تحليل رياضي لمصلية مستضدات الكريات البيضاء البشرية" (ملف PDF) ، العلوم البيولوجية الرياضية ، 40 ( 3-4 ): 243-270 ، doi : 10.1016/0025-5564(78)90088-3.
• نور، إيغور؛ هيرملين، داني؛ شارلات، سيلفان؛ إنجلستادتر، يان؛ رويتر، ماكس؛ دورون، أوليفييه؛ ساغوت، ماري فرانس (2010)، "استدلال البخل المعدل/الاستقصائي"، مطابقة الأنماط التوافقية ، سلسلة محاضرات في علوم الحاسوب، المجلد  6129، الصفحات 202-213 ، arXiv : 1002.1292 ، doi : 10.1007/978-3-642-13509-5_19 ، ISBN  978-3-642-13508-8، S2CID 6675399 
• أورلين، جيمس (1977)، "الرضا في نظرية المخططات: تغطية المخططات بالزمر"، Indagationes Mathematicae ، 80 (5): 406-424 ، doi : 10.1016/1385-7258(77)90055-5.
• شو، غوكيانغ؛ لي، ديفيد؛ ياناكاكيس، ميهاليس (2006)، "ملاحظة حول إدارة مفاتيح تشفير البث مع تطبيقات لأنظمة الإنذار في حالات الطوارئ واسعة النطاق."، المؤتمر الدولي العشرون للمعالجة المتوازية والموزعة (IPDPS 2006) ، معهد مهندسي الكهرباء والإلكترونيات.
• سايمون، هانز-أولريش (1990)، "حول الحلول التقريبية لمسائل التحسين التوافقي"، مجلة SIAM للرياضيات المتقطعة ، 3 (2): 294-310 ، doi : 10.1137/0403025.
• ستوكمير، لاري جيه. (1975)، مسألة أساس المجموعة هي مسألة NP-كاملة ، تقرير فني RC-5431، شركة IBM.

• مقال مدونة حول البعد الثنائي بقلم ديفيد إبستين