يتكون الرسم البياني من الرؤوس والحواف. الرؤوس متصلة بواسطة حواف وفقًا لخاصية معينة - علاقة السقوط ، التي تحدد مجموعة الحواف. في هذه الحالة ، يمكن أن تتشكل حلقات ورؤوس معزولة.
تعليمات
الخطوة 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
بناء مصفوفة الحوادث (الحواف). للقيام بذلك ، ارسم جدولًا ، وعدد الصفوف فيه يساوي عدد الرؤوس في الرسم البياني ، وعدد الأعمدة يساوي عدد الحواف. ضع الوحدات على تلك الخطوط التي سيتم توصيلها بحافة. تسمى الحواف الممتدة من الرأس إليه حلقات ويتم إضافتها إلى نهاية المصفوفة. في الأعمدة المقابلة للحلقات ، توجد وحدة واحدة فقط ، على عكس بقية الحواف.
الخطوة الخامسة
الآن ارسم رسمًا بيانيًا. ضع الرؤوس على الورقة بأي شكل من الأشكال وقم بتوصيلها بالحواف باستخدام الجداول التي تم إنشاؤها. تسمى الرؤوس غير المتصلة بالحواف معزولة.
