قائمة المصطلحات

حدد واحدة من الكلمات الرئيسية على اليسار ...

الرسوم البيانية والشبكاتمقدمة

وقت القراءة: ~10 min

كل يوم نحيط بنا اتصالات وشبكات لا تعد ولا تحصى: الطرق ومسارات السكك الحديدية وخطوط الهاتف والإنترنت والدوائر الإلكترونية وحتى الروابط الجزيئية. حتى أن هناك شبكات اجتماعية بين الأصدقاء والعائلات. هل يمكنك التفكير في أي أمثلة أخرى؟

شبكات الطرق والسكك الحديدية

رقائق الكمبيوتر

سلاسل التوريد

الصداقات

اتصالات عصبية

الإنترنت

في الرياضيات ، يمكن تمثيل كل هذه الأمثلة على أنها رسوم بيانية (يجب عدم الخلط بينها وبين رسم بياني للدالة). يتكون الرسم البياني من نقاط معينة تسمى ، بعضها متصل بـ .

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

يمكننا رسم تخطيط الرسوم البيانية البسيطة باستخدام الدوائر والخطوط. موضع الرؤوس وطول الحواف غير ذي صلة - نحن نهتم فقط بكيفية ارتباطهم ببعضهم البعض. يمكن أن تتقاطع الحواف مع بعضها البعض ، ولا يجب أن تكون مستقيمة.

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

تتكون بعض الرسوم البيانية من مجموعات متعددة من الرؤوس التي لا ترتبط ببعضها البعض بالحواف. هذه الرسوم البيانية غير متصلة.

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

يمكننا إنشاء رسوم بيانية جديدة من الرسم البياني الحالي عن طريق إزالة بعض الرؤوس والحواف. النتيجة تسمى subgraph. هنا يمكنك أن ترى بعض الأمثلة على الرسوم البيانية ، مع حواف ملونة ورؤوس تشير إلى رسم فرعي محتمل:

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

الترتيب:

الترتيب:

الدرجة:

الدرجة:

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

مجهزة بهذه التعريفات الجديدة ، دعنا نستكشف بعض الخصائص والتطبيقات الرائعة للرسوم البيانية.