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

الموسوعة الحرة
مربع الرسم البياني

في نظرية المخططات ، وهي فرع من الرياضيات، يُعرف الرسم البياني غير الموجه G <sub> k</sub> ، المرفوع للقوة k، بأنه رسم بياني آخر له نفس مجموعة الرؤوس ، ولكن يكون فيه رأسان متجاورين عندما تكون المسافة بينهما في G <sub>k</sub> على الأكثر k . وتُستخدم مصطلحات مشابهة لتلك المستخدمة في رفع الأعداد إلى قوى المخططات: يُسمى G <sub>2 </sub> مربع G<sub> k </sub> ، ويُسمى G<sub> 3 </sub> مكعب G<sub> k </sub>، وهكذا. [ 1 ] 

ينبغي التمييز بين قوى الرسم البياني وضرب الرسم البياني في نفسه، والتي (على عكس القوى) تحتوي عمومًا على رؤوس أكثر بكثير من الرسم البياني الأصلي.

ملكيات

إذا كان قطر الرسم البياني d ، فإن قوته من الرتبة d تمثل الرسم البياني الكامل . [ 2 ] وإذا كانت عائلة الرسوم البيانية ذات عرض زمرة محدود ، فإن قواها من الرتبة d تكون كذلك لأي قيمة ثابتة لـ d . [ 3 ]

تلوين

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

يُقدَّر كلٌّ من العدد اللوني وانحلال القوة k للرسم البياني المستوي ذي الدرجة القصوى Δ بالقيمة O (Δ ⌊ k /2⌋ ) ، حيث يُشير حد الانحلال إلى إمكانية استخدام خوارزمية تلوين جشعة لتلوين الرسم البياني بهذا العدد من الألوان. [ 4 ] في الحالة الخاصة لمربع الرسم البياني المستوي، افترض فيجنر عام 1977 أن العدد اللوني لمربع الرسم البياني المستوي لا يتجاوز max (Δ + 5, 3Δ / 2 + 1) ، ومن المعروف أن العدد اللوني لا يتجاوز 5Δ / 3 + O (1) . [ 6 ] [ 7 ] بشكل عام، بالنسبة لأي رسم بياني ذي انحلال d ودرجة قصوى Δ ، فإن انحلال مربع الرسم البياني هو O ( d Δ) ، لذلك فإن العديد من أنواع الرسوم البيانية المتفرقة بخلاف الرسوم البيانية المستوية لها أيضًا مربعات يكون عددها اللوني متناسبًا مع Δ .

على الرغم من أن العدد اللوني لمربع الرسم البياني غير المستوي ذي الدرجة القصوى Δ قد يكون متناسبًا مع Δ² في أسوأ الحالات، إلا أنه يكون أصغر بالنسبة للرسوم البيانية ذات المحيط الكبير ، حيث يكون محدودًا بـ O (Δ² / log Δ) في هذه الحالة. [ 8 ]

يُعد تحديد الحد الأدنى لعدد الألوان اللازمة لتلوين مربع الرسم البياني مسألة صعبة من نوع NP ، حتى في الحالة المستوية. [ 9 ]

الهاميلتونية

يحتوي مكعب كل رسم بياني متصل بالضرورة على دورة هاميلتونية . [ 10 ] ليس بالضرورة أن يكون مربع الرسم البياني المتصل هاميلتونيًا، وتحديد ما إذا كان المربع هاميلتونيًا مسألة NP-كاملة . [ 11 ] مع ذلك، وبحسب نظرية فليشنر ، فإن مربع الرسم البياني المتصل برأسين يكون دائمًا هاميلتونيًا. [ 12 ]

التعقيد الحسابي

يمكن حساب القوة k لرسم بياني ذي n رأسًا و m ضلعًا في زمن O ( mn ) عن طريق إجراء بحث بالعرض أولًا بدءًا من كل رأس لتحديد المسافات إلى جميع الرؤوس الأخرى، أو بشكل أسرع قليلًا باستخدام خوارزميات أكثر تطورًا. [ 13 ] بدلاً من ذلك، إذا كانت A مصفوفة تجاور للرسم البياني، معدلة بحيث تحتوي على عناصر غير صفرية على قطرها الرئيسي، فإن العناصر غير الصفرية لـ Ak تعطي مصفوفة تجاور القوة k للرسم البياني، [ 14 ] ومن ثم يمكن استنتاج أن إنشاء القوى k يمكن إجراؤه في زمن لا يتجاوز عاملًا لوغاريتميًا لزمن ضرب المصفوفات .

يمكن التعرف على القوى k للأشجار في وقت خطي يتناسب مع حجم الرسم البياني المدخل. [ 15 ]

بالنظر إلى رسم بياني، فإن تحديد ما إذا كان مربعًا لرسم بياني آخر يُعد مسألة NP-كاملة . [ 16 ] علاوة على ذلك، فإن تحديد ما إذا كان رسم بياني ما يمثل القوة k لرسم بياني آخر، لعدد معين k ≥ 2 ، أو ما إذا كان يمثل القوة k لرسم بياني ثنائي الأجزاء ، لـ k > 2 ، يُعد مسألة NP-كاملة. [ 17 ]

في الرسوم البيانية الموجهة

مربع الرسم البياني المزدوج

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

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

الرسوم البيانية الفرعية المستحثة

K 4 باعتباره نصف مربع من رسم بياني مكعب

المربع النصفي للرسم البياني الثنائي G هو الرسم البياني الجزئي لـ G² الناتج عن أحد جانبي التقسيم الثنائي لـ G. الرسوم البيانية الخرائطية هي المربعات النصفية للرسوم البيانية المستوية ، [ 19 ] والرسوم البيانية المكعبة المقسمة إلى نصفين هي المربعات النصفية للرسوم البيانية المكعبة الفائقة . [ 20 ]

القوى الورقية هي الرسوم البيانية الفرعية لقوى الأشجار الناتجة عن أوراق الشجرة. القوة الورقية من الرتبة k هي قوة ورقية يكون أسها k . [ 21 ]

مراجع

  1. ↑ بوندي، أدريان؛ مورتي، يو إس آر (2008)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد  244، سبرينغر، ص  82، ISBN 9781846289699.
  2. ↑ وايسشتاين، إريك دبليو ، "قوة الرسم البياني" ، عالم الرياضيات
  3. ↑ تودينكا، إيوان (2003)، "قوى تلوين الرسوم البيانية ذات عرض الزمرة المحدود"، مفاهيم نظرية الرسوم البيانية في علوم الحاسوب ، سلسلة محاضرات في علوم الحاسوب، المجلد 2880، سبرينغر، برلين، الصفحات 370-382 ، doi : 10.1007/978-3-540-39890-5_32 ، ISBN   978-3-540-20452-7MR 2080095​ .
  4. 1 2 أجنارسون، جير؛ Halldórsson، Magnús M. (2000)، “Coloring Powers Planar graphs”، وقائع الندوة السنوية الحادية عشرة ACM-SIAM حول الخوارزميات المنفصلة (SODA '00) ، سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية، الصفحات من 654 إلى 662 {{citation}}: CS1 maint: موقع الناشر مفقود ( رابط ) .
  5. ↑ فورمان، م.؛ هاجيروب، ت.؛ هارالامبيدس، ج.؛ كوفمان، م.؛ لايتون، ف . ت.؛ سيمفونيس، أ.؛ ويلزل، إ .؛ ووجينجر، ج. (1993)، "رسم الرسوم البيانية في المستوى بدقة عالية"، مجلة SIAM للحوسبة ، 22 (5): 1035-1052 ، doi : 10.1137/0222063 ، MR 1237161 .
  6. ↑ كرامر، فلوريكا؛ كرامر، هورست (2008)، "دراسة استقصائية حول تلوين الرسوم البيانية بناءً على المسافة"، الرياضيات المتقطعة ، 308 ( 2-3 ): 422-426 ، doi : 10.1016/j.disc.2006.11.059 ، MR 2378044 .
  7. ↑ مولوي، مايكل؛ صلواتيبور، محمد ر. (2005)، "حدٌّ على العدد اللوني لمربع الرسم البياني المستوي"، مجلة نظرية التوافيق ، السلسلة ب، 94 (2): 189-213 ، doi : 10.1016/j.jctb.2004.12.005 ، hdl : 1807/9473 ، MR 2145512 .
  8. ↑ ألون، نوغا ؛ موهار، بوجان (2002)، "العدد اللوني لقوى الرسم البياني"، التوافقية، الاحتمالات والحوسبة ، 11 (1): 1-10 ، doi : 10.1017/S0963548301004965 ، MR 1888178 ، S2CID 2706926  .
  9. ↑ أجنارسون وهالدورسون (2000) يسرد المنشورات التي تثبت صعوبة NP للرسوم البيانية العامة بواسطة ماكورميك (1983) ولين وسكيينا (1995)، وللرسوم البيانية المستوية بواسطة راماناثان ولويد (1992، 1993).
  10. ↑ بوندي ومورتي (2008) ، ص 105.
  11. ↑ أندرجراوند، بولي (1978)، "حول الرسوم البيانية ذات المربعات الهاميلتونية"، الرياضيات المتقطعة ، 21 (3): 323، doi : 10.1016/0012-365X(78)90164-4 ، MR 0522906 .
  12. ↑ ديستل، راينهارد (2012)، "10. دورات هاميلتونية"، نظرية الرسم البياني (PDF) (الطبعة الإلكترونية الرابعة المصححة ). .
  13. ↑ تشان، تيموثي م. (2012)، "أقصر المسارات بين جميع الأزواج للرسوم البيانية غير الموجهة غير الموزونة فيo(من){\displaystyle o(mn)}"الوقت"، معاملات ACM في الخوارزميات ، 8 (4): A34:1–A34:17، doi : 10.1145/2344422.2344424 ، MR 2981912 ، S2CID 1212001  
  14. ↑ هاماك، ريتشارد؛ إمريش، ويلفريد؛ كلافزار، ساندي (2011)، دليل رسوم بيانية للمنتجات ، الرياضيات المتقطعة وتطبيقاتها ( الطبعة الثانية)، مطبعة سي آر سي، ص 94، رقم ISBN   9781439813058.
  15. ↑ تشانغ، ماو-شانغ؛ كو، مينغ-تات؛ لو، هسوه-آي (2015)، "خوارزميات زمنية خطية لمسائل جذر الشجرة"، Algorithmica ، 71 (2): 471-495 ، doi : 10.1007/s00453-013-9815-y ، S2CID 253971732 .
  16. ↑ موتاني، ر.؛ سودان، م. (1994)، "حساب جذور الرسوم البيانية أمر صعب"، الرياضيات التطبيقية المنفصلة ، ​​54 : 81-88 ، doi : 10.1016/0166-218x(94)00023-9.
  17. ↑ لي، فان بانغ؛ نغوين، نغوك توي (2010)، "نتائج الصعوبة والخوارزميات الفعالة لقوى الرسوم البيانية"، مفاهيم نظرية الرسوم البيانية في علوم الحاسوب: ورشة العمل الدولية الخامسة والثلاثون، WG 2009، مونبلييه، فرنسا، 24-26 يونيو 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5911، برلين: سبرينغر، الصفحات 238-249 ، doi : 10.1007/978-3-642-11409-0_21 ، ISBN   978-3-642-11408-3MR 2587715​ .
  18. ↑ دين، ناثانيال؛ لاتكا، بريندا جيه. (1995)، "تربيع البطولة - مشكلة مفتوحة"، وقائع المؤتمر الدولي السادس والعشرين لجنوب شرق الولايات المتحدة حول التوافقية ونظرية الرسم البياني والحوسبة (بوكا راتون، فلوريدا، 1995)، Congressus Numerantium ، 109 : 73-80 ، MR 1369296 
  19. ^ تشين ، تشي تشونغ. غريني، مايكل أنجلو؛ Papadimitriou، Christos H. (2002)، “Map graphs”، مجلة ACM ، 49 (2): 127–138 ، أرخايف : cs/9910013 ، دوى : 10.1145/506147.506148 ، السيد 2147819 ، S2CID 2657838  .
  20. ↑ شبكتوروف، إس. في. (1993)، "حول تضمينات المقياس للرسوم البيانية في المكعبات الفائقة"، المجلة الأوروبية للتوافقية ، 14 (2): 117-130 ، doi : 10.1006/eujc.1993.1016 ، MR 1206617 .
  21. ↑ نيشيمورا، ن.؛ راغدي، ب.؛ ثيليكوس، د.م. (2002)، "حول قوى الرسم البياني للأشجار المصنفة حسب الأوراق"، مجلة الخوارزميات ، 42 : 69-108 ، doi : 10.1006/jagm.2001.1195.