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

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

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

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

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

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

• الرسوم البيانية الموجهة المتماثلة هي رسوم بيانية موجهة تظهر فيها جميع الحواف مرتين، واحدة في كل اتجاه (أي أنه لكل سهم ينتمي إلى الرسم البياني ذي الاتجاهين، ينتمي إليه أيضًا السهم المعاكس المقابل). (يُطلق على هذه الحافة أحيانًا اسم "ثنائية الاتجاه" وتُسمى هذه الرسوم البيانية أحيانًا "ثنائية الاتجاه"، ولكن هذا يتعارض مع معنى الرسوم البيانية ثنائية الاتجاه .)
• الرسوم البيانية الموجهة البسيطة هي رسوم بيانية موجهة ليس بها حلقات (أسهم تربط الرؤوس مباشرة ببعضها البعض) ولا تحتوي على أسهم متعددة بنفس عقد المصدر والهدف. وكما تم تقديمه بالفعل، في حالة الأسهم المتعددة، يتم عادةً معالجة الكيان على أنه رسم بياني متعدد موجه . يصف بعض المؤلفين الرسوم البيانية ذات الحلقات بأنها رسوم بيانية ثنائية الحلقات . ^[2]
  • الرسوم البيانية الموجهة الكاملة هي رسوم بيانية موجهة بسيطة حيث يتم ربط كل زوج من الرؤوس بزوج متماثل من الأقواس الموجهة (وهو ما يعادل رسمًا بيانيًا كاملاً غير موجه حيث يتم استبدال الحواف بأزواج من الأقواس العكسية). ويترتب على ذلك أن الرسم البياني الكامل متماثل.
  • المخططات الثنائية متعددة الأجزاء شبه الكاملة هي مخططات ثنائية بسيطة يتم فيها تقسيم مجموعة الرؤوس إلى مجموعات بحيث يكون لكل زوج من الرؤوس x و y في مجموعات مختلفة قوس بين x و y . يمكن أن يكون هناك قوس واحد بين x و y أو قوسين في اتجاهين متعاكسين. ^[3]
  • المخططات الثنائية شبه الكاملة هي مخططات ثنائية بسيطة حيث يوجد قوس بين كل زوج من الرؤوس. كل مخطط ثنائي شبه كامل هو مخطط ثنائي متعدد الأجزاء شبه كامل بطريقة تافهة، حيث يشكل كل رأس مجموعة من القسم. ^[4]
  • المضلعات شبه المتعدية هي مضلعات بسيطة حيث لكل ثلاثية x و y و z من الرؤوس المميزة ذات الأقواس من x إلى y ومن y إلى z ، يوجد قوس بين x و z . يمكن أن يكون هناك قوس واحد فقط بين x و z أو قوسين في اتجاهين متعاكسين. المضلعات شبه الكاملة هي مضلعات شبه متعدية. هناك امتدادات للمضلعات شبه المتعدية تسمى المضلعات شبه المتعدية k . ^[5]
  • الرسوم البيانية الموجهة هي رسوم بيانية موجهة ليس لها أزواج متقابلة من الحواف الموجهة (أي أن واحدًا على الأكثر من ( x ، y ) و ( y ، x ) قد يكون سهمًا للرسم البياني). ويترتب على ذلك أن الرسم البياني الموجه يكون رسمًا بيانيًا موجهًا إذا وفقط إذا لم يكن له دورتان . ^[6] ويمكن الحصول على مثل هذا الرسم البياني من خلال تطبيق التوجيه على رسم بياني غير موجه.
    • البطولات عبارة عن رسوم بيانية موجهة يتم الحصول عليها عن طريق اختيار اتجاه لكل حافة في الرسوم البيانية الكاملة غير الموجهة . البطولة عبارة عن رسم بياني ثنائي شبه كامل. ^[4]
    • الرسم البياني الموجه يكون غير دوري إذا لم يكن له دورات موجهة . الاسم المعتاد لمثل هذا الرسم البياني هو الرسم البياني غير الدوري الموجه (DAG). ^[7]
      • الأشجار المتعددة هي مجموعات بيانات متسلسلة لا تحتوي على مسارين موجهين متميزين من نفس الرأس المبدئي إلى نفس الرأس المنتهي.
      • الأشجار الموجهة أو الأشجار المتعددة هي مجموعات بيانات رقمية مترابطة تتشكل من خلال توجيه حواف الأشجار (رسوم بيانية غير موجهة متصلة وغير دورية).
        • الأشجار ذات الجذور هي أشجار موجهة حيث يتم توجيه جميع حواف الشجرة غير الموجهة الأساسية إما بعيدًا عن الجذر أو نحوه (ويطلق عليها على التوالي الأشجار الشجرية أو الأشجار الخارجية والأشجار الداخلية) .

• الرسوم البيانية الموجهة المرجحة (المعروفة أيضًا باسم الشبكات الموجهة ) هي رسوم بيانية موجهة (بسيطة) مع أوزان مخصصة لأسهمها، على غرار الرسوم البيانية المرجحة (والتي تُعرف أيضًا باسم الشبكات غير الموجهة أو الشبكات المرجحة ). ^[2]
  • شبكات التدفق هي عبارة عن رسوم بيانية موجهة مرجحة حيث يتم التمييز بين عقدتين، مصدر ومصرف.
• الرسوم البيانية الموجهة ذات الجذور (المعروفة أيضًا باسم الرسوم البيانية التدفقية ) هي رسوم بيانية ثنائية يتم فيها تمييز الرأس باعتباره الجذر.
  • الرسوم البيانية للتحكم في التدفق هي عبارة عن رسوم بيانية متجذرة تستخدم في علوم الكمبيوتر كتمثيل للمسارات التي قد يتم عبورها عبر برنامج أثناء تنفيذه.
• الرسوم البيانية لتدفق الإشارة هي رسوم بيانية موجهة تمثل فيها العقد متغيرات النظام وتمثل الفروع (الحواف أو الأقواس أو الأسهم) اتصالات وظيفية بين أزواج العقد.
• المخططات التدفقية هي مخططات ثنائية مرتبطة بمجموعة من المعادلات الجبرية أو التفاضلية الخطية.
• المخططات الحالة هي عبارة عن رسوم بيانية متعددة موجهة تمثل آلات الحالة المحدودة .
• المخططات التبديلية هي مخططات ثنائية تستخدم في نظرية الفئات ، حيث تمثل الرؤوس الكائنات (الرياضية) وتمثل الأسهم التشكلات، مع الخاصية التي مفادها أن جميع المسارات الموجهة بنفس نقاط البداية والنهاية تؤدي إلى نفس النتيجة من خلال التركيب.
• في نظرية مجموعات لاي ، فإن الجعبة Q هي رسم بياني موجه يعمل كمجال، وبالتالي يميز شكل، تمثيل V الذي يتم تعريفه كمتجه ، وتحديدًا كائن من فئة المتجه FinVct _K ^{F ( Q )} حيث F ( Q ) هي الفئة الحرة على Q المكونة من مسارات في Q و FinVct _K هي فئة مساحات المتجهات ذات الأبعاد المحدودة على حقل K. تحدد تمثيلات الجعبة رؤوسها بمساحات متجهة وحوافها (وبالتالي مساراتها) بشكل متوافق مع التحويلات الخطية بينها، وتتحول عبر التحويلات الطبيعية .

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

مصفوفة الجوار لرسم بياني متعدد الخطوط مع حلقات هي مصفوفة ذات قيمة عددية صحيحة مع صفوف وأعمدة تتوافق مع الرؤوس، حيث يكون المدخل غير القطري 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 عقدة من الموسوعة الإلكترونية لتسلسلات الأعداد الصحيحة