تضمين جشع

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

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

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

التعريفات

في التوجيه الجشع، تنتقل الرسالة من عقدة المصدر s إلى عقدة الوجهة t عبر سلسلة من الخطوات مرورًا بعقد وسيطة، حيث تُمرر كل عقدة منها الرسالة إلى عقدة مجاورة أقرب إلى t . إذا وصلت الرسالة إلى عقدة وسيطة x لا يوجد لها جار أقرب إلى t ، فلن تتمكن من التقدم، وبالتالي تفشل عملية التوجيه الجشع. يُعرَّف التضمين الجشع بأنه تضمين للرسم البياني المعطى يتميز باستحالة حدوث فشل من هذا النوع. لذا، يمكن وصفه بأنه تضمين للرسم البياني يتميز بأنه لكل عقدتين x و t ، يوجد جار y للعقدة x بحيث يكون d ( x , t )  > d ( y , t )، حيث d تُمثل المسافة في الفضاء المُضمَّن. [ 2 ] 

الرسوم البيانية بدون تضمين جشع

K 1,6 ، رسم بياني بدون تضمين جشع في المستوى الإقليدي

لا يمكن تمثيل كل رسم بياني في المستوى الإقليدي باستخدام خوارزمية جشعة ؛ ومن الأمثلة البسيطة على ذلك النجمة K 1,6 ، وهي شجرة ذات عقدة داخلية واحدة وست أوراق. [ 2 ] عندما يتم تمثيل هذا الرسم البياني في المستوى، يجب أن تشكل اثنتان من أوراقه زاوية 60 درجة أو أقل، ومن ثمّ يترتب على ذلك أن إحدى هاتين الورقتين على الأقل لا يوجد لها جار أقرب إلى الأخرى.

في الفضاءات الإقليدية ذات الأبعاد الأعلى، قد تمتلك رسوم بيانية أكثر تمثيلاً جشعاً؛ على سبيل المثال، يمتلك الرسم البياني K 1,6 تمثيلاً جشعاً في الفضاء الإقليدي ثلاثي الأبعاد، حيث تقع العقدة الداخلية للنجمة عند نقطة الأصل، وتبعد الأوراق مسافة وحدة واحدة على طول كل محور إحداثي. مع ذلك، لكل فضاء إقليدي ذي بُعد ثابت، توجد رسوم بيانية لا يمكن تمثيلها جشعاً: فكلما كان العدد n أكبر من عدد التلامس للفضاء، لا يمتلك الرسم البياني K 1, n تمثيلاً جشعاً. [ 3 ]

التضمينات الزائدية والموجزة

على عكس حالة المستوى الإقليدي، تمتلك كل شبكة تمثيلًا جشعًا في المستوى الزائدي . تطلّب البرهان الأصلي لهذه النتيجة، الذي وضعه روبرت كلاينبرغ ، تحديد مواقع العقد بدقة عالية، [ 4 ] ولكن تبيّن لاحقًا أنه باستخدام تحليل المسار الثقيل لشجرة ممتدة للشبكة، يُمكن تمثيل كل عقدة بإيجاز، باستخدام عدد لوغاريتمي فقط من البتات لكل نقطة. [ 3 ] في المقابل، توجد رسوم بيانية لها تمثيلات جشعة في المستوى الإقليدي، ولكن أي تمثيل من هذا القبيل يتطلب عددًا متعدد الحدود من البتات للإحداثيات الديكارتية لكل نقطة. [ 5 ] [ 6 ]

فئات خاصة من الرسوم البيانية

الأشجار

تم تحديد فئة الأشجار التي تقبل تمثيلات جشعة في المستوى الإقليدي بشكل كامل، ويمكن إيجاد تمثيل جشع لشجرة في وقت خطي عندما يكون موجودًا. [ 7 ]

بالنسبة للرسوم البيانية الأكثر عمومية، تبدأ بعض خوارزميات التضمين الجشع، مثل خوارزمية كلاينبرغ [ 4 ]، بإيجاد شجرة ممتدة للرسم البياني المعطى، ثم تُنشئ تضمينًا جشعًا لهذه الشجرة. والنتيجة بالضرورة هي تضمين جشع للرسم البياني بأكمله. مع ذلك، توجد رسوم بيانية لها تضمين جشع في المستوى الإقليدي، ولكن لا توجد لها شجرة ممتدة لها تضمين جشع. [ 8 ]

الرسوم البيانية المستوية

مشكلة لم تُحل في الرياضيات
هل لكل رسم بياني متعدد الأوجه تمثيل جشع مستوٍ ذو وجوه محدبة؟
المزيد من المسائل غير المحلولة في الرياضيات

افترض باباديميتريو وراتاجاك (2005) أن كل رسم بياني متعدد السطوح ( رسم بياني مستوٍ متصل بثلاثة رؤوس ، أو ما يعادله، وفقًا لنظرية شتاينيتز، رسم بياني لمتعدد سطوح محدب ) له تمثيل جشع في المستوى الإقليدي. [ 2 ] وباستغلال خصائص رسوم بيانية الصبار ، أثبت لايتون ومويترا (2010) هذا الافتراض؛ [ 8 ] [ 9 ] ويمكن تعريف التمثيلات الجشعة لهذه الرسوم البيانية بإيجاز، بعدد لوغاريتمي من البتات لكل إحداثية. [ 10 ] ومع ذلك، فإن التمثيلات الجشعة التي تم إنشاؤها وفقًا لهذا البرهان ليست بالضرورة تمثيلات مستوية، إذ قد تتضمن تقاطعات بين أزواج من الحواف. بالنسبة للرسوم البيانية المستوية القصوى ، حيث يكون كل وجه مثلثًا، يمكن إيجاد تمثيل مستوٍ جشع بتطبيق مبرهنة كناستر-كوراتوفسكي-مازوركيويتش على نسخة موزونة من خوارزمية تمثيل الخط المستقيم لشنايدر. [ 11 ] [ 12 ] ولا تزال تخمينية باباديميتريو-راتاجاك القوية ، التي تنص على أن كل رسم بياني متعدد السطوح له تمثيل مستوٍ جشع تكون فيه جميع الوجوه محدبة، غير مثبتة. [ 13 ]

رسوم بيانية لوحدة القرص

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

مراجع

  1. ↑ راو، أنانث؛ راتناسيمي، سيلفيا؛ باباديميتريو، كريستوس هـ .؛ شينكر، سكوت ؛ ستويكا، أيون (2003)، "التوجيه الجغرافي بدون معلومات الموقع"، وقائع المؤتمر التاسع للحوسبة المتنقلة والشبكات التابع لجمعية آلات الحوسبة (MobiCom) ، الصفحات 96-108 ، doi : 10.1145/938985.938996 ، ISBN  1-58113-753-2، S2CID 8374920 .
  2. 1 2 3 باباديميتريو، كريستوس هـ .؛ راتاتشاك، ديفيد (2005)، "حول تخمين متعلق بالتوجيه الهندسي"، علوم الحاسوب النظرية ، 344 (1): 3-14 ، doi : 10.1016/j.tcs.2005.06.022 ، MR 2178923 .
  3. 1 2 إيبستين، د .؛ جودريتش، إم تي (2011)، "التوجيه الهندسي الجشع الموجز باستخدام الهندسة الزائدية"، معاملات IEEE للحواسيب ، 60 (11): 1571-1580 ، Bibcode : 2011ITCmp..60.1571E ، doi : 10.1109/TC.2010.257 ، S2CID 40368995 .
  4. 1 2 كلاينبرغ، ر. (2007)، "التوجيه الجغرافي باستخدام الفضاء الزائدي"، وقائع المؤتمر الدولي السادس والعشرين لـ IEEE حول اتصالات الحاسوب (INFOCOM 2007) ، الصفحات 1902-1909 ، doi : 10.1109/INFCOM.2007.221 ، ISBN  978-1-4244-1047-7، S2CID 11845175 .
  5. ↑ كاو، لي؛ ستريلزوف، أ.؛ صن، جيه زد (2009)، "حول إيجاز التوجيه الجشع الهندسي في المستوى الإقليدي"، الندوة الدولية العاشرة حول الأنظمة والخوارزميات والشبكات المنتشرة (ISPAN 2009) ، ص 326-331 ، doi : 10.1109/I-SPAN.2009.20 ، ISBN  978-1-4244-5403-7، S2CID 6513298 .
  6. ↑ أنجيليني، باتريزيو؛ دي باتيستا، جوزيبي؛ فراتي، فابريزيو (2010)، "الرسومات الجشعة الموجزة ليست موجودة دائمًا"، رسم المخططات: الندوة الدولية السابعة عشرة، GD 2009، شيكاغو، إلينوي، الولايات المتحدة الأمريكية، 22-25 سبتمبر 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5849، الصفحات 171-182 ، doi : 10.1007/978-3-642-11805-0_17 ، ISBN   978-3-642-11804-3.
  7. ↑ نولنبورغ، مارتن؛ بروتكين، رومان (2013)، "رسومات إقليدية جشعة للأشجار"، وقائع الندوة الأوروبية الحادية والعشرين حول الخوارزميات (ESA 2013) ، arXiv : 1306.5224 ، Bibcode : 2013arXiv1306.5224N.
  8. 1 2 لايتون، توم ؛ مويترا، أنكور (2010)، "بعض النتائج حول التضمينات الجشعة في الفضاءات المترية"، الهندسة المنفصلة والحسابية ، 44 (3): 686-705 ، doi : 10.1007/s00454-009-9227-6 ، hdl : 1721.1/80843 ، MR 2679063 .
  9. ↑ أنجيليني، باتريزيو؛ فراتي، فابريزيو؛ غريللي، لوكا (2010)، "خوارزمية لإنشاء رسومات جشعة للتثليثات"، مجلة خوارزميات وتطبيقات الرسوم البيانية ، 14 (1): 19-51 ، doi : 10.7155/jgaa.00197 ، MR 2595019 .
  10. ↑ غودريتش، مايكل ت .؛ ستراش، دارين (2009)، "التوجيه الهندسي الجشع الموجز في المستوى الإقليدي"، الخوارزميات والحوسبة: الندوة الدولية العشرون، ISAAC 2009، هونولولو، هاواي، الولايات المتحدة الأمريكية، 16-18 ديسمبر 2009، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 5878، برلين: سبرينغر، الصفحات 781-791 ، arXiv : 0812.3893 ، doi : 10.1007/978-3-642-10631-6_79 ، ISBN   978-3-642-10630-9، MR 2792775 ، S2CID 15026956  .
  11. ↑ شنايدر، والتر (1990)، "تضمين الرسوم البيانية المستوية على الشبكة"، وقائع الندوة الأولى لجمعية آلات الحوسبة/جمعية الرياضيات التطبيقية والصناعية حول الخوارزميات المنفصلة (SODA) ، الصفحات 138-148 .
  12. ↑ دانداباني، راغافان (2010)، "الرسومات الجشعة للتثليثات"، الهندسة المنفصلة والحسابية ، 43 (2): 375-392 ، doi : 10.1007/s00454-009-9235-6 ، MR 2579703 ، S2CID 11617189  انظر أيضًا
  13. ↑ نولنبورغ، مارتن؛ بروتكين، رومان؛ روتر، إغناز (2016)، "حول الرسومات ذاتية التقارب ورسومات الأوتار المتزايدة للرسوم البيانية المستوية ثلاثية الاتصال"، مجلة الهندسة الحسابية ، 7 (1): 47-69 ، arXiv : 1409.0315 ، doi : 10.20382/jocg.v7i1a3 ، MR 3463906 ، S2CID 1500695  .
  14. ↑ فلوري، ر.؛ بيماراجو، إس. في.؛ واتنهوفر، ر. (2009)، "التوجيه الجشع مع امتداد محدود"، IEEE Infocom 2009 ، ص 1737-1745 ، doi : 10.1109/INFCOM.2009.5062093 ، ISBN  978-1-4244-3512-8، S2CID 1881560 .