نظرية الرسم البياني | Graph Theory

ما هي نظرية الرسم البياني؟

هي نظرية دراسة العلاقات بين الأشياء، وأداة قياسية لتحليل وتصميم شبكات الاتصال والنقل والطاقة وهياكل الحاسوب، يتكون الرسم البياني من عدة عقد وخطوط تربط بينها.

نشأة نظرية الرسم البياني

 في عام 1735، نشر العالم ليونهارد أويلر لغز قديم وهو كالتالي:

كيف يمكن عبور السبعة جسور المتتالية دون عبور أي جسر مرتين، وهذه الجسور ممتدة على نهر يحيط بساحتين مركزيتين.

جسور كونيغسبرغ السبعة. حقوق الصورة: انسايكلوبيديا بريتانيكا

وأثبت أويلر عدم وجود مثل هذا المسار وعمم المشكلة على جميع الشبكات الممكنة لتصبح الآن أصل نظرية الرسم البياني، وتم اعتماده كمعيار أساسي لتصميم الشبكات منذ منتصف القرن العشرين.

تطبيقات نظرية الرسم البياني

أسهمت نظرية الرسم البياني بحل العديد من المشكلات في العالم الحقيقي، إذ يوجد العديد من تطبيقاتها في عدة مجالات، إليك أهمها: 

• جدولة شركات الطيران: أحد التطبيقات ضمن فئة مشكلات التدفق في شركات الطيران. تمتلك شركات الطيران رحلات جوية في جميع أنحاء العالم وتتطلب كل رحلة طاقم عمل، ومن أجل جدولة أطقم الطيران، يتم استخدام نظرية الرسم البياني.
• الاتجاهات في الخريطة: تساعد الخرائط على تحديد الوجهة ورسم الاتجاهات وتحسب نظرية الرسم البياني الحل الذي يندرج في فئة تحديد أقصر مسار.
• حل لغز سودوكو: هذا اللغز شائع مع شبكة 9x9 يجب أن تمتلئ بالأرقام من 1 إلى 9 بشرط ألا يتم تكرارها في الصف نفسه أو العمود أو المنطقة، على الرغم من استخدام الأرقام، فإنه ليس لغزاً رياضياً، بل هو لغز تركيبي يمكن حله بمساعدة نظرية الرسم البياني.
• خوارزميات محركات البحث: يجد محرك البحث المواقع الأكثر شعبية والتي يضعها أعلى قائمة البحث من خلال رسم بياني موجه يوضح جميع العلاقات بين مواقع الويب. بالإضافة إلى إضافة أوزان إلى العقد لإعطاء الأولوية لمواقع الويب الأكثر أهمية وتأثيراً.
• تسويق وسائل التواصل الاجتماعي: تساعد نظرية الرسم البياني في تحديد الجمهور المستهدف عن طريق التعرف على الأنماط في الرسم البياني غير الموجه الناتج عن ارتباطات الشركات بالعملاء ودوائر الأصدقاء