الزمرة: هي مجموعة من الرؤوس في رسم بياني غير موجه، بحيث يكون كل رأسين مختلفين في الزمرة قريبين، مما يعني أن الرسم البياني الفرعي المستحث مكتمل، تعد الزمرة موضوعًا أساسيًا في إنشاءات الرسم البياني، كما يتم استخدامها في العديد من المواضيع االأخرى في الرياضيات.
نظرية الزمر
الزمرة القصوى: هي التي لا يمكن تكبيرها عن طريق إضافة قمة أخرى مجاورة، أي تلك التي لا تتواجد فقط داخل مجموعة قمة مجموعة أكبر، وهي خوارزمية غير حتمية في هذا النهج، نحاول أولاً إيجاد مجموعة من الرؤوس المختلفة، ثم نرى ما إذا كانت هذه الرؤوس تشكل رسمًا بيانيًا كاملاً، بحيث لا يمكن ايجاد الزمرة القصوى باستخدام طريقة حتمية متعددة الحدود.
لاكتشاف الحد الأقصى من الزمرة، يمكن للمرء مسح جميع المجموعات الفرعية بطريقة منهجية وباستخدام القوة الذهنية، ولكن هذا النوع من البحث يستغرق وقتًا طويلاً للغاية بالنسبة للشبكات التي تحتوي على أكثر من بضع مئات من الرؤوس.
ما هو تطبيق الزمرة في الرسم البياني
يمكن استخدام الزمرة لتحديد فئات الرسم البياني:
- الرسم البياني العنقودي: هو رسم بياني يحتوي على مجموعات كمكونات مرتبطة به.
- الرسم البياني للكتل: هو رسم بياني به مجموعات كمكونات مترابطة.
- الرسم البياني الوترى: هو الرسم البياني الذي يمكن فيه ترتيب الرؤوس في ترتيب استبعاد مثالي.
- الرسم البياني الخطي: هو الرسم البياني ذو الحواف التي يمكن تغطيتها بواسطة مجموعات حواف منفصلة، بحيث ينتمي كل رأس إلى اثنتين من المجموعات الموجودة في الغلاف.
- الرسم البياني المثالي: هو الرسم البياني الذي يساوي فيه رقم الزمرة في كل رسم فرعي.
- الرسم البياني المنقسم: هو الرسم البياني الذي توجد فيه نقطة نهاية واحدة على الأقل لكل حافة داخل زمرة.
- الرسم البياني الخالي من المثلث: هو الرسم البياني الذي لا يحتوي على مجموعات بجانب الرؤوس والحواف.
مثال:
- المجموعة (5,6,7): تمثل نموذج لزمرة.
- المجموعة (1,2,5,6): تمثل نموذج لزمرة قصوى.
- المجموعة (2,3,4,5): لا تمثل نموذج لزمرة، لأن الرأسان (2,4) و(3,5) ، لا يرتبطان معاً بحافة.
