التوجيه (نظرية الرسم البياني)

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
الرسم البياني الموجه (أو الرسم البياني الموجه) على اليمين هو اتجاه الرسم البياني غير الموجه على اليسار

في نظرية الرسم البياني ، يُعد توجيه الرسم البياني غير الموجه بمثابة تعيين اتجاه لكل حافة، مما يحول الرسم البياني الأولي إلى رسم بياني موجه .

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

يُطلق على الرسم البياني الموجه اسم الرسم البياني الموجه إذا لم يكن أي من أزواج رؤوسه مرتبطًا بحافتين متناظرتين. ومن بين الرسوم البيانية الموجهة، تُعد الرسوم البيانية الموجهة هي تلك التي لا تحتوي على دورات ثنائية (أي أن واحدًا على الأكثر من ( x , y ) و ( y , x ) قد يكون سهمًا في الرسم البياني). [ 1 ]

البطولة هي اتجاه لرسم بياني كامل . الشجرة المتعددة هي اتجاه لشجرة غير موجهة . [ 2 ] تنص تخمينات سومنر على أن كل بطولة ذات 2n - 2 رأسًا تحتوي على كل شجرة متعددة ذات n رأسًا . [ 3 ]

عدد الرسوم البيانية الموجهة غير المتماثلة ذات n رأسًا (حيث n = 1، 2، 3، ... ) هو

1، 2، 7، 42، 582، 21480، 2142288، 575016219، 415939243032، ... (التسلسل A001174 في OEIS ) .

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

التوجهات المقيدة

التوجيه القوي هو التوجيه الذي ينتج عنه رسم بياني متصل بقوة . أما التوجيهات الدورية الكاملة، وهي توجيهات وثيقة الصلة، فهي توجيهات ينتمي فيها كل ضلع إلى دورة بسيطة واحدة على الأقل. يكون توجيه الرسم البياني غير الموجه G دوريًا كاملًا إذا وفقط إذا كان توجيهًا قويًا لكل مكون متصل من G. تنص نظرية روبنز على أن الرسم البياني له توجيه قوي إذا وفقط إذا كان متصلًا بضلعين ؛ قد يكون للرسوم البيانية غير المتصلة توجيهات دورية كاملة، ولكن فقط إذا لم يكن لها جسور . [ 5 ]

التوجيه غير الدوري هو توجيه ينتج عنه رسم بياني موجه غير دوري . لكل رسم بياني توجيه غير دوري؛ ويمكن الحصول على جميع التوجيهات غير الدورية بوضع الرؤوس في تسلسل، ثم توجيه كل حافة من أقرب نقطة نهاية لها في التسلسل إلى أقرب نقطة نهاية لها. تنص نظرية غالاي-هاس-روي-فيتافر على أن الرسم البياني له توجيه غير دوري يكون فيه أطول مسار يحتوي على k رأس على الأكثر إذا وفقط إذا كان من الممكن تلوينه بـ k لون على الأكثر . [ 6 ] ترتبط التوجيهات غير الدورية والتوجيهات الدورية تمامًا ببعضها البعض من خلال الازدواجية المستوية . يُطلق على التوجيه غير الدوري الذي له مصدر واحد ومصب واحد اسم التوجيه ثنائي القطب . [ 7 ]

التوجيه المتعدي هو توجيه ينتج عنه رسم بياني موجه مغلق متعدٍ خاص به . تُسمى الرسوم البيانية ذات التوجيهات المتعدية برسوم بيانية قابلة للمقارنة ؛ ويمكن تعريفها من مجموعة مرتبة جزئيًا بجعل عنصرين متجاورين كلما كانا قابلين للمقارنة في الترتيب الجزئي. [ 8 ] يمكن إيجاد التوجيه المتعدي، إن وُجد، في زمن خطي. [ 9 ] مع ذلك، يتطلب اختبار ما إذا كان التوجيه الناتج (أو أي توجيه مُعطى) متعديًا بالفعل وقتًا أطول، لأنه يُعادل في تعقيده عملية ضرب المصفوفات .

التوجيه الأويلري للرسم البياني غير الموجه هو توجيه يكون فيه لكل رأس درجة دخول ودرجة خروج متساوية. تظهر التوجيهات الأويلرية للرسوم البيانية الشبكية في الميكانيكا الإحصائية في نظرية نماذج أنواع الجليد . [ 10 ]

A Pfaffian orientation has the property that certain even-length cycles in the graph have an odd number of edges oriented in each of the two directions around the cycle. They always exist for planar graphs, but not for certain other graphs. They are used in the FKT algorithm for counting perfect matchings.[11]

See also

References

  1. ↑Diestel, Reinhard (2005), "1.10 Other notions of graphs", Graph Theory(PDF) (3rd ed.), Springer, ISBN 978-3-540-26182-7.
  2. ↑Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228, arXiv:1304.2736.
  3. ↑Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2012-08-02.
  4. ↑Harary, Frank; Palmer, Edgar M. (1973), "Formula 5.4.13", Graphical Enumeration, New York: Academic Press, p. 133, MR 0357214.
  5. ↑Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517, JSTOR 2303897.
  6. ↑Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  7. ↑de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics, 56 (2–3): 157–179, doi:10.1016/0166-218X(94)00085-R, MR 1318743.
  8. ↑ غويلة حوري، آلان (1962)، "Caractérisation des graphes Non Orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une communication d'ordre"، Les Comptes rendus de l'Académie des Sciences ، 254 : 1370–1371 ، MR 0172275 .
  9. ↑ ماكونيل، آر إم؛ سبينراد، جيه. (1997)، "التوجيه المتعدي ذو الزمن الخطي"، الندوة الثامنة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة ، ​​الصفحات 19-25 .
  10. ↑ ميخائيل، م.؛ وينكلر، ب. (1996)، "حول عدد التوجهات الأويلرية للرسم البياني"، Algorithmica ، 16 ( 4-5 ): 402-414 ، doi : 10.1007/s004539900057 ، MR 1407581 .
  11. ↑ توماس، روبن (2006)، "دراسة استقصائية لتوجهات بفاف للرسوم البيانية" (ملف PDF) ، المؤتمر الدولي للرياضيات. المجلد الثالث ، المجلد 3، الجمعية الرياضية الأوروبية، زيورخ، الصفحات 963-984 ، doi : 10.4171/022-3/47 ، ISBN   978-3-03719-022-7MR 2275714​