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

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

بصورة رسمية، فإن الرسم البياني الموجه هو زوج مرتب G = ( V , A ) حيث ^{[ 1 ]}

• V هي مجموعة تسمى عناصرها رؤوسًا أو عقدًا أو نقاطًا ؛​
• A هي مجموعة من الأزواج المرتبة من الرؤوس، تسمى الأقواس ، والحواف الموجهة (أحيانًا ببساطة الحواف مع المجموعة المقابلة المسماة E بدلاً من A )، والأسهم ، أو الخطوط الموجهة .

وهو يختلف عن الرسم البياني العادي أو غير الموجه ، حيث يتم تعريف الأخير من حيث أزواج غير مرتبة من الرؤوس، والتي تسمى عادة الحواف أو الروابط أو الخطوط .

لا يسمح التعريف المذكور آنفًا بوجود أسهم متعددة في الرسم البياني الموجه، تشترك في نفس عقدة المصدر والهدف، لكن بعض الباحثين يتبنون تعريفًا أوسع يسمح بوجود هذه الأقواس المتعددة (أي أن مجموعة الأقواس تُعتبر مجموعة متعددة ). تُسمى هذه الكيانات أحيانًا بالرسوم البيانية الموجهة المتعددة (أو الرسوم البيانية الموجهة المتعددة ). من جهة أخرى، يسمح التعريف المذكور آنفًا بوجود حلقات في الرسم البياني الموجه (أي أقواس تربط العقد ببعضها مباشرةً)، لكن بعض الباحثين يتبنون تعريفًا أضيق لا يسمح بوجود حلقات في الرسوم البيانية الموجهة. ^{[ 2 ]} تُسمى الرسوم البيانية الموجهة بدون حلقات بالرسوم البيانية الموجهة البسيطة ، بينما تُسمى الرسوم البيانية الموجهة التي تحتوي على حلقات بالرسوم البيانية الموجهة الحلقية (انظر قسم أنواع الرسوم البيانية الموجهة ).

يُعتبر القوس ( س ، ص ) موجهًا من س إلى ص ؛ يُسمى ص رأس القوس ، ويُسمى س ذيله ؛ ويُقال إن ص هو التالي المباشر لـ س ، ويُقال إن س هو السابق المباشر لـ ص . إذا كان هناك مسار يؤدي من س إلى ص ، فإن ص يُقال إنه التالي لـ س ويمكن الوصول إليه من س ، ويُقال إن س هو السابق لـ ص . يُسمى القوس ( ص ، س ) القوس المعكوس لـ ( س ، ص ) .

مصفوفة التجاور للرسم البياني متعدد الاتجاهات ذي الحلقات هي مصفوفة ذات قيم صحيحة، صفوفها وأعمدتها تُقابل الرؤوس، حيث يُمثل العنصر غير القطري a _{_ij} عدد الأقواس من الرأس i إلى الرأس j ، بينما يُمثل العنصر القطري a_{_ii} عدد الحلقات عند الرأس i . أما مصفوفة التجاور للرسم البياني الموجه فهي مصفوفة منطقية ، وتكون فريدة حتى تبديل الصفوف والأعمدة.

هناك تمثيل مصفوفي آخر للرسم البياني الموجه وهو مصفوفة وقوعه .

راجع التعليمات لمزيد من التعريفات.

بالنسبة للرأس، يُطلق على عدد النهايات الرأسية المجاورة للرأس اسم درجة الدخول للرأس، ويُطلق على عدد النهايات الذيلية المجاورة للرأس اسم درجة الخروج (وتسمى عامل التفرع في الأشجار).

ليكن G = ( V , E ) و v ∈ V . يُرمز إلى درجة الدخول لـ v بـ deg ⁻ ( v ) ويُرمز إلى درجة الخروج بـ deg ⁺ ( v ).

يُطلق على الرأس الذي تكون فيه الدرجة ⁻ ( v ) = 0 اسم المصدر ، لأنه نقطة انطلاق كل قوس من أقواسه الخارجة. وبالمثل، يُطلق على الرأس الذي تكون فيه الدرجة ⁺ ( v ) = 0 اسم المصب ، لأنه نقطة نهاية كل قوس من أقواسه الداخلة.

تنص صيغة مجموع الدرجات على أنه بالنسبة للرسم البياني الموجه،

${\displaystyle \sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.}$

إذا كان لكل رأس v ∈ V ، فإن deg ⁺ ( v ) = deg ⁻ ( v ) ، فإن الرسم البياني يسمى رسمًا بيانيًا موجهًا متوازنًا . ^{[ 8 ]}

تُعرَّف متتالية الدرجات في الرسم البياني الموجه بأنها قائمة أزواج درجات الدخول والخروج؛ ففي المثال السابق، لدينا متتالية الدرجات ((2, 0), (2, 2), (0, 2), (1, 1)). تُعدّ متتالية الدرجات خاصية ثابتة في الرسم البياني الموجه، لذا فإن الرسوم البيانية الموجهة المتماثلة لها نفس متتالية الدرجات. مع ذلك، لا تُحدِّد متتالية الدرجات، بشكل عام، الرسم البياني الموجه بشكل فريد؛ ففي بعض الحالات، قد يكون للرسوم البيانية الموجهة غير المتماثلة نفس متتالية الدرجات.

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

يكون الرسم البياني الموجه متصلاً بشكل ضعيف (أو متصلاً فقط ^{[ 9 ]} ) إذا كان الرسم البياني الأساسي غير الموجه الذي تم الحصول عليه عن طريق استبدال جميع الحواف الموجهة للرسم البياني بحواف غير موجهة هو رسم بياني متصل .

يكون الرسم البياني الموجه متصلاً بقوة أو قوياً إذا كان يحتوي على مسار موجه من x إلى y (ومن y إلى x ) لكل زوج من الرؤوس ( x ، y ) . المكونات القوية هي الرسوم البيانية الفرعية المتصلة بقوة القصوى.

الرسم البياني المتصل ذو الجذر (أو الرسم البياني للتدفق ) هو الرسم البياني الذي يوجد فيه مسار موجه إلى كل رأس من رأس جذر مميز .

• بانج جنسن، يورغن؛ جوتين ، جريجوري (2000)، Digraphs: النظرية والخوارزميات والتطبيقات ، سبرينغر ، ISBN 1-85233-268-9(الطبعة الأولى المصححة لعام 2007 متاحة الآن مجانًا على موقع المؤلفين؛ صدرت الطبعة الثانية في عام 2009 ISBN) 1-84800-997-6).
• بانج جنسن، يورغن؛ غوتين، غريغوري (2018)، فئات الرسوم البيانية الموجهة ، سبرينغر ، ISBN 978-3319718408.
• بوندي، جون أدريان ؛ مورتي، يو إس آر (1976)، نظرية الرسم البياني مع التطبيقات ، نورث هولاند، رقم ISBN 0-444-19451-7.
• ديستل، راينهارد (2005)، نظرية الرسم البياني (  الطبعة الثالثة)، سبرينغر ، رقم ISBN 3-540-26182-6(النسخة الإلكترونية الثالثة متاحة مجاناً على موقع المؤلف).
• هاراري، فرانك ؛ نورمان، روبرت ز.؛ كارترايت، دوروين (1965)، النماذج الهيكلية: مقدمة لنظرية الرسوم البيانية الموجهة ، نيويورك: وايلي.
• عدد الرسوم البيانية الموجهة (أو الرسوم البيانية الموجهة) التي تحتوي على n عقدة من الموسوعة الإلكترونية لتسلسلات الأعداد الصحيحة