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

أثبت كل من خولر، راغافاتشاري، وروزنفيلد (1996) المتباينة${\displaystyle n\leq D^{\beta }+\beta }$لأي رسم بياني ذي n رأس وقطر${\displaystyle D}$والبعد المتري${\displaystyle \beta }$. وتنتج هذه الحدود من حقيقة أن كل رأس ليس ضمن مجموعة الحل يتم تحديده بشكل فريد بواسطة متجه مسافة طوله${\displaystyle \beta }$حيث يمثل كل إدخال عددًا صحيحًا بين 1 و${\displaystyle D}$(هناك بالضبط)${\displaystyle D^{\beta }}$(مثل هذه المتجهات). ومع ذلك، لا يتم تحقيق الحد إلا لـ${\displaystyle D\leq 3}$أو${\displaystyle \beta =1}$الحد الأكثر دقة$${\displaystyle n\leq \left(\lfloor 2D/3\rfloor +1\right)^{\beta }+\beta \sum _{i=1}^{\lceil D/3\rceil }(2i-1)^{\beta -1}}$$ وقد أثبت ذلك هيرناندو وآخرون (2010) .

بالنسبة لفئات محددة من الرسوم البيانية، قد تكون الحدود الأصغر سارية. على سبيل المثال، أثبت بيودو وآخرون (2018) أن${\displaystyle n\leq (\beta D+4)(D+2)/8}$بالنسبة للأشجار (يكون الحد ضيقًا للقيم الزوجية لـ D )، وحد من الشكل${\displaystyle n=O(D^{2}\beta )}$بالنسبة للرسوم البيانية الخارجية المستوية . وقد أثبت المؤلفون أنفسهم ذلك.${\displaystyle n\leq (D\beta +1)^{t-1}}$بالنسبة للرسوم البيانية التي لا تحتوي على رسم بياني كامل من الرتبة t كرسم بياني فرعي ، فقد قدموا أيضًا حدودًا للرسوم البيانية الوترية والرسوم البيانية ذات عرض الشجرة المحدود . أثبت المؤلفون فوكو وآخرون (2017أ) حدودًا من الشكل التالي:${\displaystyle n=O(D\beta ^{2})}$بالنسبة للرسوم البيانية الفاصلية والرسوم البيانية التبديلية ، والحدود من الشكل${\displaystyle n=O(D\beta )}$بالنسبة للرسوم البيانية ذات الفترات الوحدوية ، والرسوم البيانية للتباديل الثنائية، والرسوم البيانية التكميلية .

يُعدّ تحديد ما إذا كان البُعد المتري للرسم البياني لا يتجاوز عددًا صحيحًا مُعطى مسألةً من مسائل NP-complete. ^{[ 3 ]} وتبقى هذه المسألة من مسائل NP-complete بالنسبة للرسوم البيانية المستوية ذات الدرجة المحدودة ، ^{[ 4 ]} والرسوم البيانية المنقسمة ، والرسوم البيانية ثنائية الأجزاء ومكملاتها ، والرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء، ^{[ 5 ]} ورسوم بيانية القرص الواحد ، ^{[ 6 ]} ورسوم بيانية الفترات ذات القطر 2 ورسوم بيانية التبديل ذات القطر 2، ^{[ 7 ]} والرسوم البيانية ذات عرض الشجرة المحدود . ^{[ 8 ]}

لأي ثابت k ، يمكن التعرف على الرسوم البيانية ذات البعد المتري الذي لا يتجاوز k في وقت متعدد الحدود ، وذلك باختبار جميع أزواج الرؤوس الممكنة المكونة من k رأسًا، إلا أن هذه الخوارزمية غير قابلة للتطبيق في حالة المعاملات الثابتة (حيث k هو حجم الحل). وفي إجابة على سؤال طرحه لوكشتانوف (2010) ، أظهر هارتونغ ونيشترلين (2013) أن مسألة تحديد البعد المتري كاملة بالنسبة لفئة التعقيد المُعَلمة W[2]، مما يعني أن الحد الزمني من الشكل n ^{O( k )} الذي تحققه هذه الخوارزمية البسيطة هو الأمثل على الأرجح، وأنه من غير المرجح وجود خوارزمية قابلة للتطبيق في حالة المعاملات الثابتة (للمعاملة بواسطة k ). ومع ذلك، تصبح المشكلة قابلة للحل باستخدام معلمات ثابتة عند تقييدها بالرسوم البيانية الفاصلية ، ^{[ 7 ]} وبشكل أعم بالرسوم البيانية ذات طول الشجرة المحدود، ^{[ 9 ]} مثل الرسوم البيانية الوترية ، أو الرسوم البيانية التبديلية ، أو الرسوم البيانية الخالية من الثلاثيات النجمية.

يمكن تحديد ما إذا كان البُعد المتري لشجرة ما لا يتجاوز عددًا صحيحًا مُعطى في زمن خطي ^{[ 10 ].} توجد خوارزميات أخرى تعمل في زمن خطي للرسوم البيانية التكميلية ^{[ 5 ]} ، والرسوم البيانية المتسلسلة ^{[ 11 ]} ، ورسوم بيانية كتل الصبار ^{[ 12 ]} (وهي فئة تشمل كلًا من رسوم بيانية الصبار ورسوم بيانية الكتل ). يمكن حل هذه المشكلة في زمن متعدد الحدود على الرسوم البيانية الخارجية المستوية ^{[ 4 ]} . كما يمكن حلها في زمن متعدد الحدود للرسوم البيانية ذات العدد الحلقي المحدود ^{[ 5 ]،} ولكن هذه الخوارزمية غير قابلة للمعالجة بمعامل ثابت (بالنسبة للمعامل "العدد الحلقي") لأن الأس في متعدد الحدود يعتمد على العدد الحلقي. توجد خوارزميات قابلة للمعالجة بمعامل ثابت لحل مشكلة البُعد المتري للمعاملات " تغطية الرؤوس " ^{[ 13 ]} ، و"أقصى عدد للأوراق" ^{[ 14 ]} ، و"العرض المعياري". ^{[ 9 ]} تتميز الرسوم البيانية ذات العدد الحلقي المحدود، أو عدد تغطية الرؤوس، أو الحد الأقصى لعدد الأوراق، بعرض شجرة محدود ، ومع ذلك، لا تزال مسألة تحديد تعقيد مشكلة البعد المتري قائمة حتى على الرسوم البيانية ذات عرض الشجرة 2، أي الرسوم البيانية المتسلسلة المتوازية . ^{[ 9 ]}

يمكن تقريب البُعد المتري لأي رسم بياني ذي n رأس في وقت متعدد الحدود ضمن نسبة تقريب تبلغ${\displaystyle 2\log n}$من خلال التعبير عنها كمسألة تغطية مجموعة ، وهي مسألة تغطية جميع عناصر مجموعة معينة بأقل عدد ممكن من المجموعات في عائلة معينة من المجموعات . ^{[ 15 ]} في مسألة تغطية المجموعة المشتقة من مسألة البعد المتري، تكون العناصر المراد تغطيتها هي${\displaystyle {\tbinom {n}{2}}}$أزواج الرؤوس المراد تمييزها، والمجموعات التي تغطيها هي مجموعات الأزواج التي يمكن تمييزها برأس واحد مُختار. ثم يُستنتج حد التقريب بتطبيق خوارزميات التقريب القياسية لتغطية المجموعات. وتحقق خوارزمية جشعة بديلة ، تختار الرؤوس وفقًا لفرق الإنتروبيا بين فئات التكافؤ لمتجهات المسافة قبل الاختيار وبعده، نسبة تقريب أفضل.${\displaystyle \log n+\log \log _{2}n+1}$[ ^{16 ] هذه النسبة التقريبية قريبة من أفضل نسبة} ممكنة، حيث أنه في ظل افتراضات نظرية التعقيد القياسية، تكون نسبة${\displaystyle (1-\epsilon )\log n}$لا يمكن تحقيق ذلك في وقت متعدد الحدود لأي${\displaystyle \epsilon >0}$^{[ 16 ]} لا تزال صعوبة التقريب الأخيرة قائمة في الحالات المقتصرة على الرسوم البيانية شبه المكعبة، ^{[ 13 ]} وحتى على الرسوم البيانية شبه المكعبة ثنائية الأجزاء . ^{[ 17 ]}

• بودو، لوران؛ دانكلمان، بيتر؛ فوكو، فلورنت؛ هينينغ، مايكل أ.؛ ماري، أرنو؛ بارو، ألين (2018)، "تحديد رتبة الرسم البياني باستخدام قطره وبُعده المتري: دراسة من خلال تفكيكات الشجرة وبُعد VC"، مجلة SIAM للرياضيات المتقطعة ، 32 (2): 902-918 ، arXiv : 1610.01475 ، doi : 10.1137/16M1097833 ، S2CID 51882750 
• بيلمونتي، ر.؛ فومين، ف. ف.؛ غولوفاتش، ب. أ.؛ رامانوجان، م. س. (2015)، "البعد المتري للرسوم البيانية ذات العرض المحدود"، في: Italiano، جي. إف.؛ بيغيزيني، ج.؛ سانيلا، د. ت. (محررون)، الأسس الرياضية لعلوم الحاسوب 2015 - MFCS 2015: الندوة الدولية الأربعون، ميلانو، إيطاليا، 24-28 أغسطس 2015، وقائع ، سلسلة محاضرات في علوم الحاسوب ، المجلد  9235، سبرينغر، الصفحات 115-126 ، doi : 10.1007/978-3-662-48054-0_10 ، ISBN  978-3-662-48053-3.
• بلومنتال، إل إم (1953)، نظرية وتطبيقات هندسة المسافة ، كلارندون، أكسفورد.
• بونيه، إي.؛ بوروهيت، ن. (2019)، "البعد المتري المُعَلم بعرض الشجرة"، في جانسن، بي إم بي؛ تيل، جيه إيه (محرران)، الحساب المُعَلم والدقيق 2019 - IPEC 2019: وقائع الندوة الدولية الرابعة عشرة، وقائع لايبنيز الدولية في المعلوماتية (LIPIcs)، المجلد  148، شلوس داغشتول - مركز لايبنيز للمعلوماتية، الصفحات  5:1-5:15، arXiv : 1907.08093 ، doi : 10.4230/LIPIcs.IPEC.2019.5 ، ISBN 978-3-95977-129-0.
• بوكزكوفسكي، ب. تشارتراند، ج . بواسون، C .؛ Zhang، P. (2003)، “على الرسوم البيانية ذات الأبعاد k وقواعدها”، الدورية Mathematica Hungarica ، 46 (1): 9–15 ، دوى : 10.1023 / A:1025745406160 ، MR 1975342 ، S2CID 33390310  .
• شارتراند، جي .؛ إيروه، إل.؛ جونسون، إم. إيه.؛ أويلرمان، أو. آر. (2000)، "قابلية الحل في الرسوم البيانية والبعد المتري للرسم البياني"، الرياضيات التطبيقية المنفصلة ، ​​105 ( 1-3 ): 99-113 ، doi : 10.1016/S0166-218X(00)00198-0 ، hdl : 10338.dmlcz/127843 ، MR 1780464 .
• دياز، ج.؛ بوتونين، أ.؛ سيرنا، م. ج .؛ فان ليوين، إ. ج. (2012)، "حول تعقيد البُعد المتري" (ملف PDF) ، في إبستين، ليا؛ فيراجينا، باولو (محرران)، الخوارزميات - ESA 2012: الندوة الأوروبية السنوية العشرون، ليوبليانا، سلوفينيا، 10-12 سبتمبر 2012، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد  7501، سبرينغر، الصفحات 419-430 ، arXiv : 1107.2256 ، doi : 10.1007/978-3-642-33090-2_37 ، ISBN  978-3-642-33089-6.
• إبستين، ديفيد (2015)، "البعد المتري المُعَلم بأقصى عدد للأوراق"، مجلة خوارزميات وتطبيقات الرسوم البيانية ، 19 (1): 313-323 ، arXiv : 1506.01749 ، doi : 10.7155/jgaa.00360 ، S2CID 1318601 .
• إبستين، ليا؛ ليفين، آساف؛ ووجينجر، جيرهارد ج. (2012)، "البُعد المتري (الموزون) للرسوم البيانية: حالات صعبة وسهلة"، في جولومبيك، مارتن تشارلز ؛ ستيرن، ميخال؛ ليفي، أفيفيت؛ وآخرون  (محررون)، مفاهيم نظرية الرسوم البيانية في علوم الحاسوب: ورشة العمل الدولية الثامنة والثلاثون، WG 2012، القدس، إسرائيل، 26-28 يونيو 2012، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد  7551، الصفحات 114-125 ، doi : 10.1007/978-3-642-34611-8_14 ، ISBN  978-3-642-34610-1.
• فينغ، مين؛ شو، مين؛ وانغ، كايشون (2013)، "حول البُعد المتري للرسوم البيانية الخطية"، الرياضيات التطبيقية المنفصلة ، ​​161 (6): 802-805 ، arXiv : 1107.4140 ، doi : 10.1016/j.dam.2012.10.018 ، S2CID 36010185 .
• فيرناو، هينينغ؛ هيغيرنيس، بينار ؛ فان هوف، بيم؛ مايستر، دانيال؛ ساعي، رضا (2015)، "حساب البعد المتري للرسوم البيانية المتسلسلة"، رسائل معالجة المعلومات ، 115 (9): 671-676 ، doi : 10.1016/j.ipl.2015.04.006.
• فوكو، فلورنت؛ ميرتزيوس، جورج ب.؛ ناصر عسر، رضا؛ بارو، ألين؛ فاليكوف، بيترو (2017أ)، "التحديد، والسيطرة على الموقع، والبعد المتري على الرسوم البيانية الفاصلية والتباديلية. الجزء الأول: الحدود"، علوم الحاسوب النظرية ، 68 : 43-58 ، arXiv : 1507.08164 ، doi : 10.1016/j.tcs.2017.01.006 ، S2CID 25244200 
• فوكو، فلورنت؛ ميرتزيوس، جورج ب.؛ ناصر عسر، رضا؛ بارو، ألين؛ فاليكوف، بيترو (2017ب)، "التحديد، والسيطرة على الموقع، والبعد المتري على الرسوم البيانية الفاصلية والتباديلية. الجزء الثاني: الخوارزميات والتعقيد"، Algorithmica ، 78 (3): 914-944 ، arXiv : 1405.2424 ، doi : 10.1007/s00453-016-0184-1 ، S2CID 1520161 .
• غاري، إم آر ؛ جونسون، دي إس (1979)، الحواسيب والاستعصاء: دليل لنظرية الاكتمال غير القطعي ، دبليو إتش فريمان، رقم ISBN 0-7167-1045-5A1.5: GT61، ص  204.
• هاراري، ف .؛ ميلتر، ر. أ. (1976)، "حول البعد المتري للرسم البياني"، آرس كومبيناتوريا ، 2 : 191-195 ، MR 0457289 .
• هارتونج ، سيب (2014) ، استكشاف مساحات المعلمات في التعامل مع الاستعصاء الحسابي، أطروحة دكتوراه ، الجامعة التقنية في برلين ، استرجاعها 2015/09/15.
• هارتونغ، سيب؛ نيشتيرلين، أندريه (2013)، "حول صعوبة التقريب والمعاملة للبعد المتري"، مؤتمر IEEE لعام 2013 حول التعقيد الحسابي (CCC)، ستانفورد، كاليفورنيا، الولايات المتحدة الأمريكية، 5-7 يونيو 2013، وقائع المؤتمر ، IEEE، الصفحات 266-276 ، arXiv : 1211.1636 ، doi : 10.1109/CCC.2013.36 ، ISBN  978-0-7695-4997-2، S2CID 684505 .
• هاوبتمان، ماتياس. شميد، ريتشارد. Viehmann، Claus (2012)، “تعقيد التقريب لمشكلة البعد المتري”، مجلة الخوارزميات المنفصلة ، ​​14 : 214–222 ، دوى : 10.1016/j.jda.2011.12.010 ، MR 2922072 .
• هيرناندو، كارمن. مورا، ميرسي؛ بيلايو، اجناسيو م.؛ سيرا، كارلوس؛ Wood، David R. (2010)، “نظرية الرسم البياني المتطرف للبعد المتري والقطر” ، المجلة الإلكترونية للتوافقيات ، 17 R30: #R30، دوى : 10.37236/302 ، HDL : 2117/8261.
• هوفمان، ستيفان؛ إلترمان، ألينا؛ وانكي، إيغون (2016)، "خوارزمية زمنية خطية للبعد المتري لرسوم بيانية كتل الصبار"، علوم الحاسوب النظرية ، 630 : 43-62 ، doi : 10.1016/j.tcs.2016.03.024
• هوفمان، ستيفان؛ وانكي، إيغون (2013)، "البُعد المتري لرسوم بيانية قرص غابرييل الوحدوي هو مسألة NP-كاملة"، في بار-نوي، أموتز؛ هالدورسون، ماغنوس م. (محرران)، خوارزميات لأنظمة الاستشعار: الندوة الدولية الثامنة حول خوارزميات أنظمة الاستشعار، وشبكات Ad Hoc اللاسلكية، والكيانات المتنقلة المستقلة، ALGOSENSORS 2012، ليوبليانا، سلوفينيا، 13-14 سبتمبر 2012، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد  7718، سبرينغر، الصفحات 90-92 ، arXiv : 1306.2187 ، doi : 10.1007/978-3-642-36092-3_10 ، ISBN  978-3-642-36091-6، S2CID 9740623 .
• خولر، س .؛ راغافاتشاري، ب.؛ روزنفيلد، أ. (1996)، "المعالم في الرسوم البيانية"، الرياضيات التطبيقية المنفصلة ، ​​70 (3): 217-229 ، doi : 10.1016/0166-218x(95)00106-2 ، hdl : 10338.dmlcz/140702.
• لي شاوهوا. Pilipczuk، Marcin (يوليو 2022)، “صلابة البعد المتري في الرسوم البيانية لعرض الشجرة الثابتة”، الخوارزمية ، 84 (11): 3110–3155 ، أرخايف : 2102.09791 ، دوى : 10.1007 / s00453-022-01005-y ، S2CID 231979414 
• لوكشتانوف، دانيال (2010)، “المشكلات المفتوحة – تعقيد المعلمات وخوارزميات التقريب: البعد المتري”، في ديمين، إريك د . حاجياغي، محمد تاغي؛ ماركس ، دانييل (محرران)، خوارزميات التعقيد والتقريب ، Dagstuhl Seminar Proceedings، المجلد.  9511، داغستوهل، ألمانيا: Schloss Dagstuhl – Leibniz-Zentrum für Informatik ، الصفحات من 1 إلى 10، doi : 10.4230/DagSemProc.09511.3 .
• سلاتر، بي جيه (1975)، "أوراق الأشجار"، وقائع المؤتمر السادس لجنوب شرق الولايات المتحدة حول التوافقية ونظرية الرسم البياني والحوسبة (جامعة فلوريدا أتلانتيك، بوكا راتون، فلوريدا، 1975) ، كونغرسوس نوميرانتيوم، المجلد  14، وينيبيغ: يوتيليتاس ماث، الصفحات 549-559 ، MR 0422062  .
• سلاتر، بي جيه (1988)، "المجموعات المهيمنة والمرجعية في الرسم البياني"، مجلة العلوم الرياضية والفيزيائية ، 22 (4): 445-455 ، MR 0966610 .