أنواع الرسوم البيانية في بنية البيانات مع الأمثلة
فريق التحرير
⚡ ملخص ذكي
الرسوم البيانية في بنية البيانات هي مجموعات غير خطية من الرؤوس والحواف مصنفة إلى عائلات مثل الرسوم البيانية الموجهة وغير الموجهة والموزونة والدورية وغير الدورية والكاملة والمتصلة والثنائية الأجزاء ورسوم أويلر وهاملتون بناءً على البنية.
الرسم البياني هو بنية بيانات غير خطية تتكون من رؤوس وحواف. تحتوي الرؤوس على المعلومات أو البيانات، وتعمل الحواف كرابط بين زوج من الرؤوس.
يمكن أن تكون الرسوم البيانية من أنواع متعددة، وذلك بحسب موقع العقد والحواف. فيما يلي بعض الأنواع المهمة للرسوم البيانية:
مخطط موجه
تحتوي حواف الرسم البياني الموجه على أسهم تُشير إلى الاتجاه. يُحدد السهم وجهة الحافة أو نهايتها. إليك مثال على الرسم البياني الموجه.
مخطط موجه
- يمكننا الانتقال من العقدة A إلى D.
- ومع ذلك، لا يمكننا الانتقال من العقدة D إلى العقدة A، لأن الحافة تشير من A إلى D.
- نظرًا لأن الرسم البياني لا يحتوي على أوزان، فإن السفر من الرأس A إلى D سيكلف نفس تكلفة السفر من D إلى F.
رسم بياني غير موجه
يحتوي الرسم البياني غير الموجه على حواف بدون مؤشرات. وهذا يعني أنه يمكننا التنقل بين رأسين بالعكس. إليك مثال بسيط على الرسم البياني غير الموجه.
رسم بياني غير موجه
في الرسم البياني أعلاه،
- يمكننا الانتقال من النقطة أ إلى النقطة ب.
- يمكننا أيضاً الانتقال من النقطة ب إلى النقطة أ.
- الحواف لا تحتوي على اتجاهات.
إنه مثال على رسم بياني غير موجه يحتوي على عدد محدود من الرؤوس والحواف بدون أوزان.
الرسم البياني المرجح
يُطلق على الرسم البياني الذي يحتوي على أوزان أو تكاليف على حوافه اسم الرسم البياني الموزون. تمثل القيمة العددية عادةً تكلفة الانتقال من رأس إلى آخر. يمكن أن تحتوي كل من الرسوم البيانية الموجهة وغير الموجهة على أوزان على حوافها. إليك مثال على رسم بياني موزون (موجه).
الرسم البياني الموجه مع الوزن
- من النقطة أ إلى النقطة ب، هناك حافة، والوزن هو 5، مما يعني أن الانتقال من النقطة أ إلى النقطة ب سيكلفنا 5.
- يشير A إلى B، ولكن في هذا الرسم البياني، لا يوجد لـ B حافة مباشرة على A. لذلك لا يمكننا الانتقال من B إلى A.
- لكن إذا أردنا الانتقال من النقطة أ إلى النقطة و، فهناك مسارات متعددة. هذه المسارات هي أ د ف و أ ب ف. سيكلف الانتقال من أ د ف (10 + 11) أو 21.
- هنا، سيكلف المسار ABF (5+15) أو 20. هنا نقوم بإضافة وزن كل حافة في المسار.
فيما يلي مثال على رسم بياني غير موجه مع أوزان:
الرسم البياني غير الموجه مع الوزن
هنا، الحافة لها وزن ولكن ليس لها اتجاه. وهذا يعني أن السفر من الرأس A إلى D سيكلف 10 والعكس صحيح.
الرسم البياني ثنائي الاتجاه
تشترك الرسوم البيانية ثنائية الاتجاه وغير الموجهة في خاصية مشتركة، وهي:
- بشكل عام، يمكن أن يحتوي الرسم البياني غير الموجه على حافة واحدة بين رأسين.
فمثلا:
- هنا، الانتقال من A إلى D أو D إلى A سيكلف 10.
- في الرسم البياني ثنائي الاتجاه، يمكن أن يكون لدينا حافتان بين رأسين.
هنا مثال:
الرسم البياني ثنائي الاتجاه
سيكلفنا السفر من النقطة أ إلى النقطة د 17، بينما سيكلفنا السفر من النقطة د إلى النقطة أ 12. لذلك، لا يمكننا تحديد وزنين مختلفين إذا كان الرسم البياني غير موجه.
رسم لانهائي
سيحتوي الرسم البياني على عدد لا نهائي من الحواف والعقد. إذا كان الرسم البياني لانهائيًا ومتصلًا، فسيحتوي أيضًا على عدد لا نهائي من الحواف. هنا، تعني الحواف الممتدة إمكانية ربط المزيد من الحواف بهذه العقد عبر حواف أخرى. إليك مثال على الرسم البياني اللانهائي:
رسم لانهائي
رسم بياني فارغ
الرسم البياني الفارغ يحتوي على العقد أو الرؤوس فقط، دون أي حواف. إذا كان لدينا الرسم البياني G = (V, E)، حيث V هي الرؤوس وE هي الحواف، فسيكون الرسم البياني فارغًا إذا كان عدد الحواف E يساوي صفرًا. إليك مثال على الرسم البياني الفارغ:
رسم بياني فارغ
الرسم البياني تافهة
يُعتبر الرسم البياني تافهاً إذا احتوى على رأس واحد فقط دون أي حواف. إليك مثال على رسم بياني تافه:
رسم بياني متعدد
يُطلق على الرسم البياني اسم "الرسم البياني المتعدد" عندما توجد عدة حواف بين رأسين، أو عندما يحتوي الرأس على حلقة. يُشير مصطلح "الحلقة" في بنية بيانات الرسم البياني إلى حافة تُشير إلى نفس العقدة أو الرأس. يمكن أن يكون الرسم البياني المتعدد موجهًا أو غير موجه. إليك مثال على رسم بياني متعدد:
يوجد ضلعان من النقطة B إلى النقطة A. بالإضافة إلى ذلك، تحتوي النقطة E على حلقة ذاتية. الرسم البياني أعلاه هو رسم بياني موجه بدون أوزان على الأضلاع.
الرسم البياني الكامل
يُعتبر الرسم البياني كاملاً إذا كان لكل رأس فيه حواف موجهة أو غير موجهة مع جميع الرؤوس الأخرى. لنفترض أن لدينا V رأسًا، ولكل رأس V-1 حافة بالضبط. عندئذٍ، يُسمى هذا الرسم البياني رسمًا بيانيًا كاملاً. في هذا النوع من الرسوم البيانية، يرتبط كل رأس بجميع الرؤوس الأخرى عبر الحواف. إليك مثال على رسم بياني كامل بخمسة رؤوس:
يمكنك أن ترى في الصورة أن العدد الإجمالي للعقد هو خمسة، وأن جميع العقد لها أربعة حواف بالضبط.
الرسم البياني المتصل
يُطلق على الرسم البياني اسم الرسم البياني المتصل إذا بدأنا من عقدة أو رأس، وتمكّنا من الانتقال إلى جميع العقد انطلاقًا من تلك العقدة. ولتحقيق ذلك، يجب أن يكون هناك ضلع واحد على الأقل بين كل زوج من العقد أو الرؤوس. إليك مثال على رسم بياني متصل:
إليكم بعض التوضيحات حول الرسم البياني المتصل أعلاه:
- بافتراض عدم وجود حافة بين C و F، لا يمكننا الانتقال من A إلى G. ومع ذلك، فإن الحافة من C إلى F تمكننا من الانتقال إلى أي عقدة من عقدة معينة.
- الرسم البياني الكامل هو رسم بياني متصل لأنه يمكننا الانتقال من عقدة إلى أي عقدة أخرى في الرسم البياني المحدد.
الرسم البياني الدوري
يُقال إن الرسم البياني دوري إذا احتوى على دورة واحدة أو أكثر. إليك مثال على رسم بياني دوري:
هنا، تشكل الرؤوس A وB وC دورة. يمكن أن يحتوي الرسم البياني على دورات متعددة بداخله.
رسم بياني دوري موجه (DAG)
يُطلق على الرسم البياني اسم الرسم البياني الموجه غير الدوري (DAG) إذا لم تكن هناك دورات داخله. يُعدّ الرسم البياني الموجه غير الدوري (DAG) مهمًا عند القيام بـ الفرز الطوبولوجي أو لتحديد ترتيب التنفيذ. يُعدّ الرسم البياني الموجّه غير الدوري (DAG) مهمًا أيضًا لإنشاء أنظمة جدولة أو فحص تبعية الموارد، وما إلى ذلك. مع ذلك، لا يحتوي الرسم البياني أعلاه على أي دورة داخلية. إليك مثال بسيط على الرسم البياني الموجّه غير الدوري (DAG):
الرسم البياني للدورة
الرسم البياني الدوري ليس هو نفسه الرسم البياني الدائري. في الرسم البياني الدوري، يرتبط كل عقدة بحافتين فقط، أي أن لكل عقدة درجتين فقط. إليك مثال على الرسم البياني الدوري:
رسم بياني ثنائي
هذه الأنواع من الرسوم البيانية هي أنواع خاصة من الرسوم البيانية حيث تُخصص الرؤوس لمجموعتين. يجب أن يتبع الرسم البياني ثنائي الأجزاء القاعدة التالية:
- يجب أن تكون مجموعتا الرؤوس متميزتين، مما يعني أنه يجب تقسيم جميع الرؤوس إلى مجموعتين أو مجموعتين.
- لا ينبغي أن تشكل الرؤوس الموجودة في نفس المجموعة أي حواف.
الرسم البياني أويلر
يُعتبر هيكل بيانات الرسم البياني رسمًا بيانيًا من نوع أويلر إذا كانت جميع رؤوسه ذات درجة زوجية. وتعني درجة الرؤوس عدد الحواف التي تشير إلى رأس معين أو تخرج منه. إليك مثال على رسم بياني من نوع أويلر:
جميع الرؤوس لها درجات زوجية. الرؤوس A وD وE وH لها درجتان. أما العقدة C فلها أربع درجات، وهي درجة زوجية.
هاميلتون الرسم البياني
الرسم البياني الهاميلتوني هو رسم بياني متصل، حيث يمكنك زيارة جميع الرؤوس انطلاقًا من رأس معين دون إعادة زيارة نفس العقدة أو استخدام نفس الحافة. يُعرف هذا النوع من الرسوم البيانية المتصلة باسم "الرسم البياني الهاميلتوني". يُعرف المسار الذي تسلكه للتحقق مما إذا كان الرسم البياني المعطى رسمًا بيانيًا هاميلتونيًا أم لا باسم المسار الهاميلتوني. إليك مثال بسيط على رسم بياني هاميلتوني:
في هذه الصورة، يمكننا زيارة جميع القمم من أي عقدة في الرسم البياني أعلاه. يمكن أن يكون أحد المسارات أدشبيمن الممكن أيضًا إيجاد دورة هاميلتون. تبدأ دورة هاميلتون وتنتهي عند نفس الرأس. لذا، ستكون دورة هاميلتون أدشبيا.
