الرسم البياني في الرياضيات

الرسم

عادة ما يتم تمثيل الرسم البياني بشكل تخطيطي كمجموعة من النقاط أو الدوائر للرؤوس ، متصلة بخطوط أو منحنيات للحواف.

تمامًا كما الرسوم البيانية هي موضوع دراسة في الرياضيات المنفصلة ، يمكن توجيه الحواف أو عدم توجيهها.

علي سبيل المثال

إذا كانت هذه الرؤوس ممثلة في صورة أفراد حاضرين في حفلة ، وهناك ميزة بين شخصين إذا تصافحا.

هذا الرسم البياني غير موجه ، لأن الفرد “أ” يمكنه مصافحة الفرد “ب” فقط إذا صافح “ب” أيضًا مع الفرد “أ”.

على العكس من ذلك ، إذا كانت أي حافة من الفرد A إلى الشخص B تتوافق مع A من B ، فسيتم توجيه هذا الرسم البياني.

هذا لأن التشابه ليس بالضرورة متبادلًا أو متبادلًا ، ويسمى النوع الأول من الرسم البياني بالرسم البياني غير المباشر.

بينما يسمى النوع الأخير من الرسم البياني بالرسم البياني الموجه.

الرسومات

إنه الموضوع الرئيسي الذي تعلمه نظرية الرسم البياني ، واستخدام كلمة “رسم بياني” بهذا المعنى كان أول من قام به جيمس جوزيف سيلفستر ، وذلك في عام 1878 م.

تعريف الرسم البياني وأنواعه.

تختلف التعريفات في نظرية الرسم البياني ؛ فيما يلي بعض الطرق الأساسية لتحديد الرسوم البيانية والهياكل الرياضية ذات الصلة:

الرسم

الرسم البياني عبارة عن زوج (G = (V ، E) ، حيث V عبارة عن مجموعة ، تسمى عناصرها الرؤوس (المفرد: قمة الرأس) ، و E.

مجموعة من مجموعتين (مجموعات تحتوي على عنصرين مميزين) من الرؤوس ، تسمى عناصرها الحواف (أحيانًا روابط أو خطوط).

يُطلق على رأسي x و y للحافة {x، y} نقاط نهاية الحافة ، ويقال أن الحافة تربط بين x و y ، ويقال إنها تقع على x و y ، وقد لا ينتمي الرأس إلى أي حافة.

مخطط متعدد

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

يُسمح أحيانًا للرسوم البيانية أن تحتوي على حلقات ، وهي عبارة عن حواف تربط الرأس بذاته ، للسماح بالحلقات الحلقية.

يجب أيضًا تغيير التعريف أعلاه عن طريق تحديد الحواف كمجموعات متعددة من رأسين ، بدلاً من مجموعتين.

تسمى هذه الرسوم البيانية المعممة الرسوم البيانية الحلقية أو الرسوم البيانية ببساطة ، عندما يكون واضحًا من السياق أن الحلقات مسموح بها.

مخطط فارغ

رسم بياني بمجموعة فارغة من الرؤوس (وبالتالي مجموعة فارغة من الأضلاع).

ترتيب الرسم البياني هو عدد الرؤوس | V | ، وحجم الرسم البياني هو عدد حوافه | بلدي |

ومع ذلك ، في بعض السياقات ، مثل التعبير عن التعقيد الحسابي للخوارزميات ، يكون الحجم | الخامس | + | بلدي |

(بخلاف ذلك ، يمكن أن يكون حجم الرسم البياني غير الفارغ 0).

درجة أو تماثل الرأس هي عدد الأضلاع فيه ، وبالنسبة للرسوم البيانية ذات الحلقات ، تُحسب الحلقة مرتين.

مخطط موجه

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

ولكنه شائع جدًا في النهاية ، [8] الرسم البياني الموجه هو زوج مرتب (G = (V ، E) يتكون من:

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

مخطط مختلط

الرسم البياني المركب هو رسم بياني قد يتم توجيه بعض الحواف فيه والبعض الآخر قد لا يتم توجيهه.

إنه ثلاثي مرتبة (G = (V ، E ، A) لرسم بياني مختلط بسيط و (G = (V ، E ، A ، A ، ϕE ، ϕA) لجهاز كشف الكذب المختلط مع V ، E (حواف غير موجهة) ، أ (حواف موجهة).

مخطط مرجح

الرسم البياني أو الشبكة الموزونة ، وهو رسم بياني يتم فيه تعيين رقم (وزن) لكل حافة.

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

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

أنواع المخططات

مخطط موجه

• الرسم البياني الموجه هو رسم بياني موجه يمكن أن تكون فيه حواف (س ، ص) و (س ، ص) من الرسم البياني على الأكثر.
  • أي أنه رسم بياني موجه يمكن أن يتخذ شكل اتجاه رسم بياني غير موجه.

رسم بياني منتظم

• الرسم البياني العادي هو رسم بياني لكل رأس له نفس عدد الجيران ، أي أن كل رأس له نفس الدرجة.
• الرسم البياني المنتظم برؤوس الدرجة k يسمى أيضًا الرسم البياني العادي k أو الرسم البياني المنتظم للدرجة k.

الرسم البياني الكامل

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

رسم محدود

• الرسم البياني المحدود هو رسم بياني تكون فيه مجموعة الرؤوس ومجموعة الأضلاع مجموعات محدودة ، وإلا يطلق عليه الرسم البياني اللانهائي.

رسم بياني متصل

• في الرسم البياني غير الموجه ، يسمى الزوج غير المرتب من الرؤوس {x، y} متصل إذا كان المسار يقود من x إلى y ، وإلا فإن الزوج غير المرتب يسمى غير متصل.
• الرسم البياني المتصل هو رسم بياني غير موجه ترتبط فيه جميع أزواج الرؤوس غير المرتبة في الرسم البياني ؛ خلاف ذلك ، يطلق عليه رسم بياني غير مستمر.

اتبع أيضًا:

إنه من أنواع أخرى

• مخطط ثنائي.
• أيضا مخطط الطريق.
• رسم بياني مسطح.
• أيضا مخطط الدورة.

خصائص الرسم

• تسمى حافتا الرسم البياني متجاورتان إذا كانا يشتركان في رأس مشترك.
• يتم تحديد الرسومات ذات الملصقات المرفقة بالحواف أو الرؤوس على أنها مصنفة.
• فئة جميع الرسوم البيانية هي فئة المقطع Set ↓ D حيث D: Set → Set هي الأس الذي يحول مجموعة من s إلى s × s.

أمثلة

• الرسم البياني هو تمثيل تخطيطي للرسم البياني ذي الرؤوس {V = {1،2،3،4،5،6} والحواف {{E = {{1،2} ، {1،5} ، {2،3 } ، {2) ، 5} ، {3 ، 4} ، {4 ، 5} ، {4 ، 6.
• تحدد العلاقة الثنائية R على مجموعة X رسمًا بيانيًا متجهًا ، والعنصر x في X هو سلف مباشر للعنصر y في X إذا كان xRy فقط.
• يمكن للرسم البياني الموجه أن يصمم شبكات المعلومات مثل Twitter ، مع مستخدم يتبع الآخر.
• تقدم الرسوم البيانية لمجموعة كايلي ، والتي تم إنشاؤها بدقة ، أمثلة منتظمة بشكل خاص على الرسوم البيانية الموجهة.
  • المزيد من الرسومات لجوز شرير.
• في نظرية الفئة ، يحتوي كل فصل صغير على رسم بياني أساسي متعدد موجه تكون رؤوسه كائنات الفصل وحوافه هي أسهم الفصل ، بلغة نظرية التصنيف.
  • كما يقال ، هناك عامل منسي من فئة الصغيرة إلى فئة الهزات.

دائري

• في الرسم البياني للارتباط التشعبي ، يمكن أن تحتوي الحافة على أكثر من رأسين.
• يمكن النظر إلى الرسم البياني غير الموجه على أنه معقد بسيط من 1 مبسط (الحواف) ، وأصفار مبسطة (الرؤوس) ، وما إلى ذلك.
  • المُجمِّعون عبارة عن تعميمات للرسوم البيانية لأنها تسمح بتبسيط الأبعاد الأعلى.
• كل رسم بياني يؤدي إلى matroid.
• في نظرية النموذج ، الرسم البياني هو مجرد هيكل ، ولكن في هذه الحالة ، لا توجد قيود على عدد الحواف: يمكن أن يكون أي رقم أصلي.
• أيضًا في علم الأحياء الحسابي ، يقدم تحليل الرسم البياني للطاقة رسومًا بيانية للطاقة ، كتمثيل بديل للرسوم البيانية غير الموجهة.
• أيضًا في نظم المعلومات الجغرافية ، يتم نمذجة الشبكات الهندسية عن كثب من الرسومات.
• كما أنه يستعير العديد من المفاهيم من نظرية الرسم البياني لإجراء التحليل المكاني على شبكات الطرق أو شبكات المرافق.

اتبع أيضًا: