يتكون الرسم البياني من القمم والحواف. ترتبط القمم بالحواف وفقًا لخاصية معينة - علاقة السقوط ، التي تحدد مجموعة الحواف. في هذه الحالة ، قد تتشكل حلقات وقمم معزولة.
دليل التعليمات
1
اسمح بإعطاء مجموعة من حواف الرسم البياني والعلاقة التي يمكن من خلالها رسم حافة من قمة إلى أخرى. كمثال ، مجموعة الذروات {1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8} ، ذروتين x و y في النسبة x + y <8.
2
بناء مصفوفة مجاورة قمة الرأس. للقيام بذلك ، قم ببناء جدول مربع ، يتطابق عدد الصفوف والأعمدة في الجدول مع عدد القمم. ثم ضع 1 عند تقاطع الصف i مع العمود j ، إذا كانت القمم i و j تفيان بنسبة معينة. ضع 0 عند تقاطع الصف الأول والعمود j ، إذا لم يتم تحقيق نسبة العناصر المقابلة.
في مثالنا ، يتم تعبئة السطر الأول على النحو التالي:
1 + 1 <8 ، لذا عند تقاطع الصف الأول والعمود الأول 1
1 + 2 <8 ، مرة أخرى 1
1 + 3 <8 ، مرة أخرى 1
…
1 + 7 <8 ، عدم مساواة غير صحيح ، فإن عنصر الجدول هذا سيكون 0
1 + 8 <8 ، مرة أخرى 0
3
لمعرفة عدد الحواف ، احسب عدد الوحدات في مصفوفة الجوار ، بينما لا تمزق الحواف.
في المثال ، تم الحصول على مصفوفة متناظرة ، لذلك ، تم حساب الوحدات أولاً فوق القطر الرئيسي للمصفوفة (المحددة باللون الأزرق) ، ثم الوحدات على القطر الرئيسي (المحدد باللون الأحمر). العدد الإجمالي للأضلاع هو 12.
4
بناء مصفوفة من الحوادث (الحواف). للقيام بذلك ، ارسم جدولًا ، وعدد الصفوف فيه يساوي عدد رؤوس الرسم البياني ، وعدد الأعمدة يساوي عدد الحواف. ضع الوحدات في الخطوط التي سيتم توصيلها بحافة. تسمى الحواف المؤدية من الأعلى إليها بالحلقات وتضاف إلى نهاية المصفوفة. في الأعمدة المقابلة للحلقات ، هناك وحدة واحدة فقط ، على عكس الحواف الأخرى.
5
الآن رسم رسم بياني. رتب القمم على الورق بشكل اعتباطي وقم بتوصيلها بالحواف باستخدام الجداول المنشأة. تسمى القمم غير المتصلة بالحواف معزولة.
انتبه
يوضح الشكل الأضلاع للوضوح. عادة ، يتم كتابة وزن الضلع على الضلع.
