تم النشر اليوم [dadate] | مجموعة مستقلة (نظرية الرسومات)

ملاحظات

. على الأكثر من المجموعات المستقلة القصوى لكن العديد من الرسوم البيانية تحتوي على أقل من ذلك العدد بكثير. يتم الحصول على عدد المجموعات المستقلة القصوى في الرسوم البيانية لدورة به n n من الرؤوس بواسطة أرقام Perrin ، ويتم إستنتاج عدد المجموعات المستقلة القصوى في الرسوم البيانية لمسار به n n من الرؤوس بواسطة تسلسل Padovan . لذلك، يتناسب كلا الرقمين مع قوى الرقم البلاستيكي 1.324718 .

برنامج للبحث عن أقصى مجموعة مستقلة

اسم رخصة لغة واجهة برمجة التطبيقات معلومات موجزة igraph GPL C, Python, R, Ruby الحل الدقيق. "تم نقل التطبيق الحالي إلى رسم من مكتبة Very Nauty Graph Library بواسطة Keith Briggs ويستخدم الخوارزمية من الورقة S. Tsukiyama و M. Ide و H. Ariyoshi و I. Shirawaka. خوارزمية جديدة لتوليد كل المجموعات المستقلة القصوى SIAM J Computing، 6: 505-517، 1977 ". Network BSD Python الحل التقريبي، راجع الروتين maximum_independent_set

شرح مبسط

في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس رسم بياني والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا.[1]
لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا