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

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

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

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

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

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

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