الرسم البياني في الرياضيات، وبصورة أكثر تحديدًا في نظرية الرسم البياني، يمثل بنية تربط مجموعة من الكائنات معًا.
تعريف الرسم البياني
يتضح عادةً الرسم البياني (كما يُعرف باللغة الإنجليزية: Graph) من خلال تخطيط يضم مجموعة من النقاط أو الدوائر تمثل الرؤوس، متصلة بخطوط أو منحنيات تمثل الحواف.
تعتبر الرسوم البيانية إحدى مجالات الدراسة الأساسية في الرياضيات المنفصلة، حيث يمكن أن تكون الحواف إما موجهة أو غير موجهة.
مثال توضيحي
على سبيل المثال، إذا كانت الرؤوس تمثل أفرادًا في حفلة، فإن وجود حافة بين شخصين يعني أنهما تصافحا.
يكون هذا الرسم البياني غير موجه، لأن أي شخص “أ” يمكنه مصافحة الشخص “ب” فقط إذا قام “ب” بمصافحة “أ”.
على العكس، إذا كان هناك حافة تربط الشخص “أ” بالشخص “ب” تعكس إعجاب “أ” بــ “ب”، فيكون هذا الرسم بيانيًا موجهًا، حيث أن الإعجاب ليس بالضرورة متبادلاً.
الرسوم البيانية كموضوع دراسي
تمثل الرسوم البيانية موضوعًا رئيسيًا في نظرية الرسم البياني، واستخدمت عبارة “رسم بياني” بهذا المعنى لأول مرة بواسطة جيمس جوزيف سيلفستر في عام 1878.
أنواع الرسم البياني
تتعدد التعريفات في نظرية الرسم البياني، وهنا بعض التعريفات الأساسية للرسوم البيانية والهياكل الرياضية ذات الصلة:
تعريف الرسم البياني
الرسم البياني يُمثل كزوج (G = (V، E، حيث V تمثل مجموعة، تُعرف عناصرها بالأركان (الرؤوس)، وE هي مجموعة من أزواج مميزة من الرؤوس، تُعرف بالعلاقات أو الحواف.
في هذا السياق، تُسمى الرؤوس “x” و”y” لنقطة النهاية من الحافة {x، y}، ويُقال إن الحافة تربط بين x وy.
الرسم البياني المتعدد
يُعتبر تعميمًا يتيح وجود حواف متعددة بنفس الزوج من نقاط النهاية. في بعض النصوص، يمكن الإشارة إلى الرسوم البيانية المتعددة ببساطة باسم الرسوم البيانية.
يمكن أيضًا أن يحتوي الرسم البياني على حلقات، وهي حواف تربط الرأس بنفسه، وفي هذه الحالة يجب تعديل التعريف ليشمل مجموعات متعددة من رأسين.
الرسم البياني الفارغ
هو رسم بياني يفتقر إلى مجموعة من الرؤوس (وبالنتيجة، مجموعة فارغة من الحواف).
في هذا السياق، يُعرف ترتيب الرسم البياني بعدد الرؤوس |V|، بينما يُعبر حجم الرسم البياني عن عدد الحواف |E|.
الرسم البياني الموجه
الرسم البياني الموجه هو نوع من الرسم البياني الذي تكون فيه الحواف لها اتجاهات معينة.
بشكل أكثر تفصيلًا، يُمثل الرسم البياني الموجه كزوج مرتب (G = (V، E الذي يتكون من:
- V: مجموعة من الرؤوس، تُعرف أيضاً بالعقد أو النقاط.
- E: مجموعة من الحواف الموجهة، وهي أزواج مرتبة من الرؤوس.
الرسم البياني المختلط
هو رسم بياني يسمح بتوجيه بعض الحواف بينما تبقى حواف أخرى غير موجهة.
الرسم البياني الموزون
الرسم البياني الموزون أو الشبكة هو نوع من الرسم البياني يتم فيه تعيين قيمة (وزن) لكل حافة، يعكس هذا الوزن تكاليف أو أطوال أو قدرات حسب المشكلة المطروحة.
أنواع الرسوم البيانية
الرسم البياني الموجه
- الرسم البياني الموجه يمكن أن يضم حوافًا تربط كل رأس بشكل محدد.
الرسم البياني المنتظم
- يمتاز الرسم البياني المنتظم بوجود عدد متساو من الجيران لكل رأس، أي أن جميع الرؤوس لها نفس الدرجة.
- يمكن الإشارة إليه أيضاً بالرسم البياني المنتظم ذو الدرجة k.
الرسم البياني الكامل
- يمثل الرسم البياني الكامل رسمًا بيانيًا يُربط فيه كل زوج من الرؤوس بحافة، مما يضمن وجود جميع الحواف الممكنة.
الرسم البياني المحدود
- الرسم البياني المحدود لديه مجموعات محدودة من الرؤوس والحواف، على عكس الرسم البياني اللانهائي.
الرسم البياني المتصل
- في الرسم البياني غير الموجه، يُعتبر الزوج غير المرتب من الرؤوس {x، y} متصلًا إذا كان هناك مسار من x إلى y، وإلا يُعد منفصلًا.
- الرسم البياني المتصل يضمن توصيل كل زوج غير مرتب من الرؤوس.
خصائص الرسوم البيانية
- تُعتبر الحافتان متجاورتين إذا كانتا تشتركان في رأس مشترك.
- تُصنف الرسوم البيانية التي تحتوي على ملصقات مرفقة بالحواف أو الرؤوس على أنها مصنفة.
أمثلة
- الرسم البياني كمثال هو تمثيل تخطيطي لعناصر {V= {1, 2, 3, 4, 5، 6 مع الحواف {{E= {{1, 2}، {1, 5}، {2, 3}، {2, 5}، {3, 4}، {4, 5}، {4, 6}.
- يمكن اعتبار العلاقة الثنائية R على مجموعة X كرسمة بيانية موجهة.
- تستطيع الرسوم البيانية الموجهة تمثيل نماذج لشبكات المعلومات مثل تويتر.
التعميمات
- في الرسم البياني التشعبي، يمكن أن تصل الحافة إلى أكثر من رأسين.
- يوفر الرسم البياني غير الموجه تعبيرًا مبسطًا يُظهر الأبعاد الأعلى.
- يمكن استخدام تحليل الرسم البياني للطاقة كتمثيل بديل للرسوم البيانية غير الموجهة.
تابع أيضًا:
