الرسم البياني الجذري

الموسوعة الحرة

في الرياضيات ، وتحديدًا في نظرية المخططات ، يُعرف المخطط الجذري بأنه مخطط تم فيه تمييز رأس واحد باعتباره الجذر. [ 1 ] [ 2 ] وقد دُرست كل من النسخ الموجهة وغير الموجهة للمخططات الجذرية، كما توجد تعريفات بديلة تسمح بوجود جذور متعددة.

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

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

الاختلافات

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

يُلاحظ تباين في تعريف مصطلحي "الرسم البياني الموجه ذو الجذر " و "الرسم البياني الموجه ذو الجذر" . ويتمثل التعريف الأبسط في اعتبار الرسم البياني الموجه ذا جذر بتحديد عقدة معينة كجذر. [ 6 ] [ 7 ] مع ذلك، في علوم الحاسوب ، يشير هذان المصطلحان عادةً إلى مفهوم أضيق؛ وهو أن الرسم البياني الموجه ذو الجذر هو رسم بياني موجه بعقدة مميزة r ، بحيث يوجد مسار موجه من r إلى أي عقدة أخرى غير r . [ 8 ] [ 9 ] [ 10 ] [ 11 ] وقد يشير المؤلفون الذين يقدمون التعريف الأكثر عمومية إلى الرسوم البيانية التي تستوفي التعريف الأضيق باسم " الرسوم البيانية الموجهة ذات الجذر المتصلة " [ 6 ] أو "الرسوم البيانية ذات الجذر التي يمكن الوصول إليها " (انظر قسم  نظرية المجموعات ).

يُعرّف كتاب "فن برمجة الحاسوب" الرسوم البيانية الموجهة الجذرية تعريفًا أوسع قليلًا، أي أن الرسم البياني الموجه يُسمى جذريًا إذا كان يحتوي على عقدة واحدة على الأقل يمكنها الوصول إلى جميع العقد الأخرى. ويشير كنوت إلى أن المفهوم المُعرّف بهذه الطريقة هو نوع من الوسيط بين مفهومي الرسم البياني الموجه المتصل بقوة والرسم البياني الموجه المتصل . [ 12 ]

التطبيقات

مخططات التدفق

في علم الحاسوب ، تُسمى الرسوم البيانية الجذرية التي يمكن للرأس الجذري فيها الوصول إلى جميع الرؤوس الأخرى برسوم التدفق . [ 13 ] أحيانًا يُضاف قيد إضافي ينص على أن رسم التدفق يجب أن يحتوي على رأس خروج واحد ( رأس مصب ). [ 14 ]

يمكن اعتبار مخططات التدفق بمثابة تجريدات لمخططات التدفق ، مع إزالة العناصر غير الهيكلية (محتويات العقد وأنواعها). [ 15 ] [ 16 ] ولعل أشهر أنواع مخططات التدفق هي مخططات تدفق التحكم ، المستخدمة في المترجمات وتحليل البرامج . يمكن تحويل أي مخطط تدفق إلى مخطط تدفق تحكم عن طريق إجراء انكماش على كل حافة تمثل الحافة الوحيدة الخارجة من مصدرها والحافة الوحيدة الداخلة إلى هدفها. [ 17 ] وهناك نوع آخر شائع الاستخدام من مخططات التدفق وهو مخطط الاستدعاء ، حيث تتوافق العقد مع إجراءات فرعية كاملة . [ 18 ]

يُطلق على المفهوم العام لمخطط التدفق اسم مخطط البرنامج ، [ 19 ] ولكن يُستخدم المصطلح نفسه أيضًا للإشارة إلى مخططات تدفق التحكم فقط. [ 20 ] كما تُسمى مخططات التدفق بمخططات التدفق غير المُصنفة [ 21 ] ومخططات التدفق الصحيحة . [ 15 ] وتُستخدم هذه المخططات أحيانًا في اختبار البرمجيات . [ 15 ] [ 18 ]

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

نظرية المجموعات

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

نظرية الألعاب التوافقية

يمكن ربط أي لعبة توافقية برسم بياني موجه ذي جذر، حيث تمثل رؤوسه مواقع اللعبة، وحوافه الحركات، وجذره موقع البداية. يُعد هذا الرسم البياني مهمًا في دراسة تعقيد اللعبة ، حيث يُمثل تعقيد فضاء الحالة عدد رؤوس الرسم البياني.

التعداد التوافقي

عدد الرسوم البيانية غير الموجهة ذات الجذر لـ 1، 2، ... هو 1، 2، 6، 20، 90، 544، ... (التسلسل A000666 في OEIS ) .

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

يمكن دمج الرسوم البيانية الجذرية باستخدام حاصل الضرب الجذري للرسوم البيانية . [ 27 ]

انظر أيضاً

مراجع

  1. ↑ زويلينجر، دانيال (2011)، جداول وصيغ الرياضيات القياسية من سي آر سي، الطبعة الثانية والثلاثون ، مطبعة سي آر سي، ص  150، رقم ISBN 978-1-4398-3550-0
  2. ↑ هاراري، فرانك (1955)، "عدد الرسوم البيانية الخطية والموجهة والجذرية والمتصلة"، معاملات الجمعية الرياضية الأمريكية ، 78 (2): 445-463 ، doi : 10.1090/S0002-9947-1955-0068198-2 ، MR 0068198 انظر الصفحة  454.
  3. ↑ غروس، جوناثان ل.؛ يلين، جاي؛ تشانغ، بينغ (2013)، دليل نظرية الرسم البياني (الطبعة الثانية )، مطبعة سي آر سي، الصفحات 764-765 ، رقم ISBN   978-1-4398-8018-0
  4. ↑ سبنسر، جويل (2001)، المنطق الغريب للرسوم البيانية العشوائية ، سبرينغر ساينس آند بيزنس ميديا، الفصل 4، رقم ISBN 978-3-540-41654-8
  5. ↑ هاراري (1955 ، ص 455) . 
  6. 1 2 بيورنر، أندرس ؛ زيغلر، غونتر م. (1992)، "8. مقدمة إلى الغريدويدات" (ملف PDF) ، في وايت، نيل (محرر)، تطبيقات الماترويد ، موسوعة الرياضيات وتطبيقاتها، المجلد 40، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 284-357 ، doi : 10.1017/CBO9780511662041.009 ، ISBN   0-521-38165-7، MR 1165537 ، Zbl 0772.05026 ، في هذا السياق ، يُطلق على الرسم البياني الموجه الجذري Δ = ( V ، E ، r ) اسم متصل (أو متصل من الدرجة 1 ) إذا كان هناك مسار موجه من الجذر إلى كل رأس.  انظر على وجه الخصوص الصفحة  307.
  7. ١ ٢ غوردون، غاري؛ ماكماهون، إليزابيث (فبراير ١٩٨٩)، "متعدد حدود جشع يميز التفرعات الجذرية" (ملف PDF) ، وقائع الجمعية الرياضية الأمريكية ، ١٠٧ (٢): ٢٨٧، CiteSeerX ١٠.١.١.٣٠٨.٢٥٢٦ ، doi : ١٠.١٠٩٠/s٠٠٠٢-٩٩٣٩-١٩٨٩-٠٩٦٧٤٨٦-٠ ، يُسمى الرسم البياني الفرعي الجذري F تفرعًا جذريًا إذا كان رأس الجذر ∗ موجودًا في F ، ولكل رأس v في F ، يوجد مسار موجه فريد في F من ∗ إلى v . وبالتالي، فإن التفرعات الجذرية في الرسوم البيانية الموجهة تُقابل الأشجار الجذرية في الرسوم البيانية غير الموجهة. 
  8. ↑ راماشاندران، فيجايا (1988)، "خوارزميات متوازية سريعة لرسوم بيانية التدفق القابلة للاختزال"، الحوسبة المتزامنة ، ص 117-138 ، doi : 10.1007/978-1-4684-5511-3_8 ، ISBN  978-1-4684-5513-7، الرسم البياني الموجه ذو الجذر أو الرسم البياني للتدفق G = ( V , A , r ) هو رسم بياني موجه برأس مميز r بحيث يوجد مسار موجه في G من r إلى كل رأس v في V − r .انظر على وجه الخصوص الصفحة  122.
  9. ↑ أوكاموتو، يوشيو؛ ناكامورا، ماساتاكا (2003)، "التوصيف الجزئي المحظور للمصفوفات المضادة للبحث الخطي للرسوم البيانية الموجهة الجذرية" (PDF) ، الرياضيات التطبيقية المنفصلة ، ​​131 (2): 523-533 ، doi : 10.1016/S0166-218X(02)00471-7 ، الرسم البياني الموجه الجذري هو ثلاثية G = ( V , E , r ) حيث ( V ∪ { r }, E ) هو رسم بياني موجه و r هو رأس محدد يسمى الجذر بحيث يوجد مسار من r إلى كل رأس من رؤوس V.انظر على وجه الخصوص الصفحة  524.
  10. ↑ جاين، أبهيناندان (2010)، ديناميكيات الروبوتات والأجسام المتعددة: التحليل والخوارزميات ، سبرينغر ساينس آند بيزنس ميديا، ص 136، ISBN  978-1-4419-7267-5، الرسم البياني الموجه ذو الجذر هو رسم بياني موجه متصل بعقدة جذرية واحدة تمثل سلف كل عقدة أخرى في الرسم البياني الموجه.
  11. ↑ تشين، شوجين؛ زانغ، وينان (2006)، "خوارزمية فعالة لإيجاد أقصى عدد من دورات التعبئة في مخططات التدفق القابلة للاختزال"، Algorithmica ، 44 (3): 195-211 ، doi : 10.1007/s00453-005-1174-x ، hdl : 10722/48600 ، MR 2199991 ، S2CID 5235131  
  12. ↑ كنوت، دونالد (1997)، "2.3.4.2. الأشجار الموجهة"، فن برمجة الحاسوب ، المجلد 1 ( الطبعة الثالثة)، بيرسون للتعليم، ص 372، ISBN    0-201-89683-4يقال إنها متجذرة إذا كان هناك جذر واحد على الأقل، أي رأس واحد على الأقل R بحيث يكون هناك مسار موجه من V إلى R لجميع V ≠ R.
  13. ↑ غروس، يلين وتشانغ (2013 ، ص 1372) . 
  14. ↑ فينتون، نورمان إليوت؛ هيل، جيليان أ. (1993)، بناء وتحليل الأنظمة: إطار رياضي ومنطقي ، ماكجرو هيل، ص 319، ISBN  978-0-07-707431-9.
  15. 1 2 3 زوسي، هورست (1998)، إطار قياس البرمجيات ، والتر دي جرويتر، الصفحات من 32 إلى 33، ISBN  978-3-11-080730-1
  16. ↑ سامارو، أنجلينا؛ طومسون، جيف؛ ويليامز، بيتر (2010)، اختبار البرمجيات: دليل مؤسسة ISTQB-ISEB ، BCS، المعهد المعتمد، ص 108، ISBN  978-1-906124-76-2
  17. ↑ تار، بيري ل.؛ وولف، ألكسندر ل. (2011)، هندسة البرمجيات: المساهمات المستمرة لليون ج. أوسترويل ، سبرينغر ساينس آند بيزنس ميديا، ص 58، ISBN  978-3-642-19823-6
  18. 1 2 جالوت، بانكاج (1997)، منهج متكامل لهندسة البرمجيات ، سبرينغر ساينس آند بيزنس ميديا، ص 372 ، ISBN  978-0-387-94899-7
  19. ↑ ثولاسيرامان، ك.؛ سوامي، م.ن.س. (1992)، الرسوم البيانية: النظرية والخوارزميات ، جون وايلي وأولاده، ص 361، ISBN  978-0-471-51356-8
  20. ↑ سيتشيتش، أليخاندرا؛ بياتيني، ماريو؛ فاليشيلو، أنطونيو (2003)، جودة البرمجيات القائمة على المكونات: الأساليب والتقنيات ، سبرينغر ساينس آند بيزنس ميديا، ص 105، ISBN  978-3-540-40503-0
  21. ↑ بينيك، لويل دبليو .؛ ويلسون، روبن جيه. (1997)، روابط الرسوم البيانية: العلاقات بين نظرية الرسوم البيانية ومجالات أخرى من الرياضيات ، مطبعة كلارندون، ص 237 ، ISBN  978-0-19-851497-8
  22. ↑ فينتون وهيل (1993 ، ص 323) . 
  23. ↑ فينتون وهيل (1993 ، ص 339) . 
  24. ↑ كوبر، سي. (2008)، "التعداد التقاربي لمخططات تدفق وصلات المسند"، التوافقية والاحتمالات والحوسبة ، 5 (3): 215-226 ، doi : 10.1017/S0963548300001991 ، S2CID 10313545 
  25. ↑ أكسل، بيتر (1988)، المجموعات غير المؤسسة جيدًا (ملف PDF) ، سلسلة محاضرات CSLI، المجلد 14، ستانفورد، كاليفورنيا: جامعة ستانفورد، مركز دراسة اللغة والمعلومات، ISBN  0-937073-22-9، LCCN 87-17857 ، MR 0940014 ، مؤرشف من الأصل (PDF) بتاريخ 26-03-2015  
  26. ↑ دريشر، ماثيو؛ فيتا، أدريان (2010)، "خوارزمية تقريبية لمسألة امتداد الأوراق القصوى في الأشجار" ، معاملات ACM للخوارزميات ، 6 (3): 46:1–46:18، doi : 10.1145/1798596.1798599 ، S2CID 13987985 .
  27. ↑ جودسيل، سي دي ؛ مكاي، بي دي (1978)، "ناتج رسم بياني جديد وطيفه" (ملف PDF) ، نشرة الجمعية الأسترالية للرياضيات ، 18 (1): 21-28 ، doi : 10.1017/S0004972700007760 ، MR 0494910 

للمزيد من القراءة

  • مكماهون، إليزابيث و. (1993)، "حول متعددة الحدود الجشعة للرسوم البيانية الجذرية والرسوم البيانية الموجهة الجذرية"، مجلة نظرية الرسم البياني ، 17 (3): 433-442 ، doi : 10.1002/jgt.3190170316
  • غوردون، غاري (2001)، "متعددة حدود مميزة للرسوم البيانية الجذرية والرسوم البيانية الموجهة الجذرية"، الرياضيات المتقطعة ، 232 ( 1-3 ): 19-33 ، doi : 10.1016/S0012-365X(00)00186-2