الزمرة (نظرية الرسم البياني)

في نظرية المخططات ، الزمرة ( تُلفظ / ˈkliːk / أو / ˈklɪk / ) هي مجموعة جزئية من رؤوس مخطط غير موجه بحيث يكون كل رأسين مختلفين في الزمرة متجاورين . أي أن زمرة المخطط $G$ هو رسم بياني فرعي مستحث من $G$ هذا مفهوم كامل . تُعدّ الزمر أحد المفاهيم الأساسية في نظرية المخططات، وتُستخدم في العديد من المسائل الرياضية الأخرى والإنشاءات على المخططات. كما دُرست الزمر في علوم الحاسوب : فمهمة إيجاد ما إذا كانت هناك زمرة بحجم مُحدد في مخطط ( مسألة الزمر ) هي مسألة NP-كاملة ، ولكن على الرغم من هذه الصعوبة، فقد دُرست العديد من الخوارزميات لإيجاد الزمر.

على الرغم من أن دراسة الرسوم البيانية الفرعية الكاملة تعود على الأقل إلى إعادة صياغة نظرية رامزي باستخدام نظرية الرسوم البيانية من قِبل إردوش وسيكيريس (1935) ، ^{[ 1 ]} فإن مصطلح "الزمرة" (clique ) مشتق من لوس وبيري (1949) ، اللذين استخدما الرسوم البيانية الفرعية الكاملة في الشبكات الاجتماعية لنمذجة زمر الأشخاص؛ أي مجموعات من الأشخاص الذين يعرفون بعضهم بعضًا. وللزمر تطبيقات أخرى عديدة في العلوم، ولا سيما في المعلوماتية الحيوية .

التعريفات

الزمرة ، $C$ ، في الرسم البياني غير الموجه G $=$ $($ $V$ $,$ $E$ $)$ هي مجموعة جزئية من الرؤوس ، $C$ $\subseteq$ $V$ ، بحيث يكون كل رأسين مختلفين متجاورين. وهذا يكافئ شرط أن الرسم البياني الجزئي المستحث من $G$ بواسطة $C$ هو رسم بياني كامل . في بعض الحالات، قد يشير مصطلح الزمرة أيضًا إلى الرسم البياني الجزئي مباشرةً.

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

الزمرة القصوى في الرسم البياني $G$ هي زمرة لا توجد زمرة أخرى تحتوي على عدد رؤوس أكبر منها. علاوة على ذلك، فإن عدد الزمر $ω (G)$ في الرسم البياني $G$ هو عدد الرؤوس في الزمرة القصوى في $G.$

عدد التقاطع لـ $G$ هو أصغر عدد من الزمر التي تغطي معًا جميع حواف $G.$

عدد تغطية الزمر للرسم البياني $G$ هو أصغر عدد من الزمر في $G$ التي يغطي اتحادها مجموعة الرؤوس $V$ للرسم البياني.

المقطع العرضي للزمرة القصوى للرسم البياني هو مجموعة جزئية من الرؤوس تتميز بأن كل زمرة قصوى في الرسم البياني تحتوي على رأس واحد على الأقل في المجموعة الجزئية. ^{[ 2 ]}

عكس الزمرة هو المجموعة المستقلة ، بمعنى أن كل زمرة تُقابل مجموعة مستقلة في الرسم البياني المُكمِّل . وتتعلق مسألة تغطية الزمر بإيجاد أقل عدد ممكن من الزمر التي تشمل كل رأس في الرسم البياني.

المفهوم ذو الصلة هو " البيكليك" ، وهو رسم بياني جزئي ثنائي الأجزاء كامل . البعد الثنائي للرسم البياني هو الحد الأدنى لعدد البيكليك اللازمة لتغطية جميع حواف الرسم البياني.

الرياضيات

تشمل النتائج الرياضية المتعلقة بالمجموعات ما يلي.

تُعطي نظرية توران حدًا أدنى لحجم الزمرة في الرسوم البيانية الكثيفة . ^{[ 3 ]} إذا كان للرسم البياني عدد كافٍ من الحواف، فلا بد أن يحتوي على زمرة كبيرة. على سبيل المثال، كل رسم بياني يحتوي على $n$ الرؤوس وأكثر من $\scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil$ يجب أن تحتوي الحواف على مجموعة ثلاثية الرؤوس.
تنص نظرية رامزي على أن كل رسم بياني أو الرسم البياني المكمل له يحتوي على مجموعة كاملة تحتوي على عدد لوغاريتمي من الرؤوس على الأقل. ^{[ 4 ]}
وفقًا لنتيجة مون وموزر (1965) ، يمكن أن يحتوي الرسم البياني ذو 3n رأسًا على ³ⁿ زمر قصوى على الأكثر . الرسوم البيانية التي تحقق هذا الحد هي رسوم مون-موزر K _3,3,... ، وهي حالة خاصة من رسوم توران البيانية التي تظهر كحالات قصوى في نظرية توران.
إن تخمين هادويجر ، الذي لم يثبت بعد، يربط حجم أكبر مجموعة فرعية في الرسم البياني ( عدد هادويجر الخاص بها ) بعددها اللوني .
يربط تخمين Erdős -Faber-Lovász تلوين الرسم البياني بالمجموعات.
تنص فرضية إردوش -هاينال على أن عائلات الرسوم البيانية المحددة بواسطة توصيف الرسم البياني المحظور إما أن تحتوي على زمر كبيرة أو زمر مشتركة كبيرة .

يمكن تعريف أو تمييز العديد من الفئات المهمة من الرسوم البيانية من خلال مجموعاتها المتداخلة:

الرسم البياني العنقودي هو رسم بياني تكون مكوناته المتصلة عبارة عن زمر.
الرسم البياني الكتلي هو رسم بياني تكون مكوناته المتصلة ثنائياً عبارة عن زمر.
الرسم البياني الوتر هو رسم بياني يمكن ترتيب رؤوسه في ترتيب حذف مثالي، وهو ترتيب بحيث تشكل جيران كل رأس v الذين يأتون بعد v في الترتيب مجموعة كاملة.
الرسم البياني المشترك هو رسم بياني تكون فيه جميع الرسوم البيانية الفرعية المستحثة لها خاصية أن أي زمرة قصوى تتقاطع مع أي مجموعة مستقلة قصوى في رأس واحد.
الرسم البياني الفاصل هو رسم بياني يمكن ترتيب مجموعاته القصوى بطريقة تجعل المجموعات التي تحتوي على v متتالية في الترتيب لكل رأس v .
الرسم البياني الخطي هو رسم بياني يمكن تغطية حوافه بواسطة مجموعات منفصلة الحواف بحيث ينتمي كل رأس إلى مجموعتين فقط من المجموعات الموجودة في الغطاء.
الرسم البياني المثالي هو رسم بياني يكون فيه عدد الزمر مساوياً للعدد اللوني في كل رسم بياني فرعي مستحث .
الرسم البياني المنقسم هو رسم بياني يحتوي على مجموعة فرعية تحتوي على نقطة نهاية واحدة على الأقل لكل حافة.
الرسم البياني الخالي من المثلثات هو رسم بياني لا يحتوي على أي مجموعات فرعية أخرى غير رؤوسه وحوافه.

بالإضافة إلى ذلك، تتضمن العديد من البنى الرياضية الأخرى مجموعات متجانسة في الرسوم البيانية. ومن بينها،

مجمع الزمر في الرسم البياني G هو مجمع تبسيطي مجرد X ( G ) يحتوي على مُبسط لكل زمرة في G
الرسم البياني البسيط هو رسم بياني غير موجه κ( G ) يحتوي على رأس لكل زمرة في الرسم البياني G وحافة تربط بين زمرتين تختلفان برأس واحد. وهو مثال على الرسم البياني الوسيط ، ويرتبط بجبر وسيط على زمر الرسم البياني: الوسيط m ( A , B , C ) لثلاث زمر ^A و B و C هو الزمرة التي تنتمي رؤوسها إلى زمرتين على الأقل من الزمر A و B و C. ^[⁵ ]
تُعدّ طريقة الجمع بين الزمر طريقة لدمج رسمين بيانيين عن طريق دمجهما على طول زمرة مشتركة.
عرض الزمرة هو مفهوم يُشير إلى تعقيد الرسم البياني من حيث الحد الأدنى لعدد تسميات الرؤوس المختلفة اللازمة لبناء الرسم البياني من الاتحادات المنفصلة، وعمليات إعادة التسمية، والعمليات التي تربط جميع أزواج الرؤوس ذات التسميات المعطاة. الرسوم البيانية ذات عرض الزمرة يساوي واحدًا هي بالضبط الاتحادات المنفصلة للزمر.
عدد التقاطع في الرسم البياني هو الحد الأدنى لعدد المجموعات الفرعية اللازمة لتغطية جميع حواف الرسم البياني.
الرسم البياني للزمر في الرسم البياني هو الرسم البياني للتقاطع بين زمره القصوى.

ترتبط مفاهيم وثيقة الصلة بالرسوم البيانية الفرعية الكاملة ارتباطًا وثيقًا بتقسيمات الرسوم البيانية الكاملة والحدود الجزئية للرسوم البيانية الكاملة . وعلى وجه الخصوص، تُعرّف نظرية كوراتوفسكي ونظرية فاغنر الرسوم البيانية المستوية بتقسيمات فرعية كاملة وثنائية الأجزاء محظورة ، وحدود جزئية كاملة ، على التوالي.

علوم الحاسوب

في علم الحاسوب ، تُعرف مسألة الزمر بأنها المسألة الحسابية المتمثلة في إيجاد أكبر زمرة، أو جميع الزمر، في رسم بياني مُعطى. وهي مسألة كاملة من فئة NP ، إحدى مسائل كارب الـ 21 الكاملة من فئة NP . ^{[ 6 ]} كما أنها غير قابلة للحل في ظل وجود معلمات ثابتة ، ويصعب تقريبها . ومع ذلك، فقد طُوّرت العديد من الخوارزميات لحساب الزمر، إما تعمل في زمن أُسّي (مثل خوارزمية برون-كربوش ) أو مُخصصة لعائلات رسوم بيانية مثل الرسوم البيانية المستوية أو الرسوم البيانية الكاملة التي يُمكن حل المسألة لها في زمن متعدد الحدود .

التطبيقات

نشأ مصطلح "الزمرة" في سياق نظرية الرسوم البيانية من عمل لوس وبيري (1949) ، اللذين استخدما الرسوم البيانية الفرعية الكاملة لنمذجة الزمر (مجموعات من الأشخاص الذين يعرفون بعضهم بعضًا) في الشبكات الاجتماعية . وقد استخدم فيستينجر (1949) التعريف نفسه في مقالٍ له بمصطلحات أقل تخصصًا. يتناول كلا العملين الكشف عن الزمر في الشبكات الاجتماعية باستخدام المصفوفات. للاطلاع على الجهود المتواصلة لنمذجة الزمر الاجتماعية باستخدام نظرية الرسوم البيانية، انظر على سبيل المثال ألبا (1973) ، وبي (1974) ، ودوريان وودارد (1994) .

تم نمذجة العديد من المشكلات المختلفة في المعلوماتية الحيوية باستخدام مفهوم الزمر. على سبيل المثال، قام بن دور وشامير وياخيني (1999) بنمذجة مشكلة تجميع بيانات التعبير الجيني باعتبارها إيجاد الحد الأدنى من التغييرات اللازمة لتحويل رسم بياني يصف البيانات إلى رسم بياني يتكون من اتحاد منفصل للزمر. وناقش تاناي وشاران وشامير (2002) مشكلة مماثلة للتجميع الثنائي لبيانات التعبير، حيث يُشترط أن تكون المجموعات زمرًا. واستخدم سوجيهارا (1984) الزمر لنمذجة المواطن البيئية في الشبكات الغذائية . ووصف داي وسانكوف (1986) مشكلة استنتاج الأشجار التطورية بأنها إيجاد أكبر عدد ممكن من الزمر في رسم بياني تكون رؤوسه عبارة عن خصائص الأنواع، حيث يشترك رأسان في حافة واحدة إذا وُجدت شجرة تطورية مثالية تجمع بين هاتين الصفتين. قدّم سامودرالا ومولت (1998) نموذجًا لتوقع بنية البروتين باعتباره مشكلة إيجاد مجموعات فرعية في رسم بياني تمثل رؤوسه مواقع الوحدات الفرعية للبروتين. ومن خلال البحث عن هذه المجموعات في شبكة تفاعلات البروتين-بروتين ، وجد سبيرين وميرني (2003) تجمعات من البروتينات تتفاعل فيما بينها بشكل وثيق، ولها تفاعلات قليلة مع البروتينات خارج التجمع. يُعد تحليل الرسم البياني القوي طريقةً لتبسيط الشبكات البيولوجية المعقدة من خلال إيجاد المجموعات الفرعية والبنى ذات الصلة في هذه الشبكات.

في الهندسة الكهربائية ، استخدم بريهار (1956) مفهوم الزمر الكاملة لتحليل شبكات الاتصالات، واستخدمها بول وأونغر (1959) لتصميم دوائر فعالة لحساب الدوال المنطقية المحددة جزئيًا. كما استُخدمت الزمر الكاملة في توليد أنماط الاختبار التلقائي : إذ توفر الزمرة الكاملة الكبيرة في رسم بياني لعدم توافق الأعطال المحتملة حدًا أدنى لحجم مجموعة الاختبار. ^{[ 7 ]} ويصف كونغ وسميث (1993) تطبيقًا للزمر الكاملة في إيجاد تقسيم هرمي لدائرة إلكترونية إلى وحدات فرعية أصغر.

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

انظر أيضاً

لعبة كليك

ملحوظات

↑ تم صياغة العمل السابق لكوراتوفسكي (1930) الذي يصف الرسوم البيانية المستوية بواسطة الرسوم البيانية الكاملة المحظورة والرسوم البيانية الثنائية الكاملة في الأصل بمصطلحات طوبولوجية بدلاً من مصطلحات نظرية الرسم البياني.
↑ تشانغ، كلوكس ولي (2001) .
↑ توران (1941) .
↑ غراهام، روتشيلد وسبنسر (1990) .
^ بارتيليمي، لوكلير ومونجارديت (1986) ، الصفحة 200.
↑ كارب (1972) .
^ حمزة أوغلو وباتل (1998) .

مراجع

ألبا، ريتشارد د. (1973)، "تعريفٌ قائم على نظرية الرسم البياني للزمرة الاجتماعية" (ملف PDF) ، مجلة علم الاجتماع الرياضي ، 3 (1): 113-126 ، doi : 10.1080/0022250X.1973.9989826 ، مؤرشف (ملف PDF) من الأصل بتاريخ 2011-05-03 ، تم استرجاعه بتاريخ 2009-12-14.
بارتيليمي، جيه-بي؛ لوكلير، بي؛ مونجارديه، بي (1986)، "حول استخدام المجموعات المرتبة في مشاكل مقارنة وتوافق التصنيفات"، مجلة التصنيف ، 3 (2): 187-224 ، doi : 10.1007/BF01894188 ، S2CID 6092438 .
بن دور، أمير؛ شامير، رون؛ ياخيني، زوهار (1999)، "تجميع أنماط التعبير الجيني"، مجلة علم الأحياء الحاسوبي ، 6 ( 3-4 ): 281-297 ، CiteSeerX 10.1.1.34.5341 ، doi : 10.1089/106652799318274 ، PMID 10582567 .
تشانغ، ماو-شانغ؛ كلوكس، تون؛ لي، تشوان-مين (2001)، "التقاطعات القصوى للزمر"، مفاهيم نظرية الرسم البياني في علوم الحاسوب (بولتنهاغن، 2001) ، سلسلة محاضرات في علوم الحاسوب، المجلد 2204، سبرينغر، برلين، الصفحات 32-43 ، doi : 10.1007/3-540-45477-2_5 ، ISBN 978-3-540-42707-0MR 1905299 .
كونغ، ج.؛ سميث، م. (1993)، "خوارزمية تجميع متوازية من الأسفل إلى الأعلى مع تطبيقات لتقسيم الدوائر في تصميم VLSI"، وقائع المؤتمر الدولي الثلاثين لأتمتة التصميم ، الصفحات 755-760 ، CiteSeerX 10.1.1.32.735 ، doi : 10.1145/157485.165119 ، ISBN 978-0897915779، S2CID 525253 .
داي، ويليام إتش إي؛ سانكوف، ديفيد (1986)، "التعقيد الحسابي لاستنتاج العلاقات التطورية من خلال التوافق"، علم الحيوان المنهجي ، 35 (2): 224-229 ، doi : 10.2307/2413432 ، JSTOR 2413432 .
دوريان، باتريك؛ وودارد، كاثرين ل. (1994)، "تحديد وتحديد مواقع مراكز وحدود الشبكات الاجتماعية"، الشبكات الاجتماعية ، 16 (4): 267-293 ، doi : 10.1016/0378-8733(94)90013-2.
إردوش، بول ؛ سيكيريس، جورج (1935)، "مسألة توافقية في الهندسة" (ملف PDF) ، مجلة Compositio Mathematica ، 2 : 463-470 ، مؤرشفة (ملف PDF) من الأصل بتاريخ 22-05-2020 ، تم استرجاعها بتاريخ 19-12-2009.
فيستينجر، ليون (1949)، "تحليل المخططات الاجتماعية باستخدام جبر المصفوفات"، العلاقات الإنسانية ، 2 (2): 153-158 ، doi : 10.1177/001872674900200205 ، S2CID 143609308 .
غراهام، ر.؛ روتشيلد، ب.؛ سبنسر، ج. هـ. (1990)، نظرية رامزي ، نيويورك: جون وايلي وأولاده، ISBN 978-0-471-50046-9.
حمزة أوغلو، إ.؛ باتيل، ج. هـ. (1998)، "خوارزميات ضغط مجموعة الاختبار للدوائر التوافقية"، وقائع المؤتمر الدولي IEEE/ACM للتصميم بمساعدة الحاسوب لعام 1998 ، الصفحات 283-289 ، doi : 10.1145/288548.288615 ، ISBN 978-1581130089، S2CID 12258606 .
كارب، ريتشارد م. (1972)، "قابلية الاختزال بين المسائل التوافقية"، في ميلر، ر. إي.؛ ثاتشر، ج. و. (محرران)، تعقيد الحسابات الحاسوبية (ملف PDF) ، نيويورك: بلينوم، ص 85-103 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 29-06-2011 ، تم استرجاعه بتاريخ 13-12-2009 {{citation}}: CS1 maint: موقع الناشر ( رابط ) .
كول، إف إس؛ كريبن، جي إم؛ فريزن، دي كيه (1983)، "خوارزمية توافقية لحساب ارتباط الليجاند"، مجلة الكيمياء الحاسوبية ، 5 (1): 24-34 ، doi : 10.1002/jcc.540050105 ، S2CID 122923018 .
كوراتوفسكي ، كازيميرز (1930)، “Sur le problème des courbes gauches en Topologie” (PDF) ، Fundamenta Mathematicae (بالفرنسية)، 15 : 271–283 ، دوى : 10.4064/fm-15-1-271-283 ، أرشفة (PDF) من النسخة الأصلية في 2018-07-23 ، تم استرجاعه في 19/12/2009.
لوس، ر. دنكان ؛ بيري، ألبرت د. (1949)، "طريقة لتحليل المصفوفة لبنية المجموعة"، مجلة القياس النفسي ، 14 (2): 95-116 ، doi : 10.1007/BF02289146 ، hdl : 10.1007/BF02289146 ، PMID 18152948 ، S2CID 16186758 .
مون، جيه دبليو؛ موسر، إل. (1965)، "حول الزمر في الرسوم البيانية"، مجلة إسرائيل للرياضيات ، 3 : 23-28 ، doi : 10.1007/BF02760024 ، MR 0182577 .
بول، إم سي؛ أونغر، إس إتش (1959)، "تقليل عدد الحالات في وظائف التبديل التسلسلي غير المحددة بالكامل"، معاملات معهد مهندسي الراديو في الحواسيب الإلكترونية ، EC-8 (3): 356-367 ، doi : 10.1109/TEC.1959.5222697.
بي، إدموند ر. (1974)، "بنى الزمر الهرمية"، علم الاجتماع ، 37 (1): 54-65 ، doi : 10.2307/2786466 ، JSTOR 2786466 .
بريهار، ز. (1956)، "الخصائص الطوبولوجية لشبكات الاتصالات"، وقائع معهد مهندسي الراديو ، 44 (7): 927-933 ، doi : 10.1109/JRPROC.1956.275149 ، S2CID 51654879 .
رودس، نيكولاس؛ ويلت، بيتر؛ كالفيت، آلان؛ دنبار، جيمس ب.؛ همبلت، كريستين (2003)، "CLIP: البحث عن التشابه في قواعد البيانات ثلاثية الأبعاد باستخدام اكتشاف الزمر"، مجلة المعلومات الكيميائية وعلوم الحاسوب ، 43 (2): 443-448 ، doi : 10.1021/ci025605o ، PMID 12653507 .
سامودرالا، رام؛ مولت، جون (1998)، "خوارزمية نظرية الرسم البياني للنمذجة المقارنة لبنية البروتين"، مجلة البيولوجيا الجزيئية ، 279 (1): 287-302 ، CiteSeerX 10.1.1.64.8918 ، doi : 10.1006/jmbi.1998.1689 ، PMID 9636717 .
سبيرين، فيكتور؛ ميرني، ليونيد أ. (2003)، "مجمعات البروتين والوحدات الوظيفية في الشبكات الجزيئية"، وقائع الأكاديمية الوطنية للعلوم ، 100 (21): 12123-12128 ، Bibcode : 2003PNAS..10012123S ، doi : 10.1073/pnas.2032324100 ، PMC 218723 ، PMID 14517352 .
سوجيهارا، جورج (1984)، "نظرية الرسم البياني، والتماثل، وشبكات الغذاء"، في ليفين، سيمون أ. (محرر)، بيولوجيا السكان ، وقائع ندوة الرياضيات التطبيقية، المجلد 30، الصفحات 83-101 .
تاناي، آموس؛ شاران، روديد؛ شامير، رون (2002)، "اكتشاف التجمعات الثنائية ذات الدلالة الإحصائية في بيانات التعبير الجيني"، المعلوماتية الحيوية ، 18 (ملحق 1): S136– S144، doi : 10.1093/bioinformatics/18.suppl_1.S136 ، PMID 12169541 .
توران، بول (1941)، “حول مشكلة متطرفة في نظرية الرسم البياني”، Matematikai és Fizikai Lapok (باللغة المجرية)، 48 : 436– 452

روابط خارجية

[1] تم صياغة العمل السابق لكوراتوفسكي (1930) الذي يصف الرسوم البيانية المستوية بواسطة الرسوم البيانية الكاملة المحظورة والرسوم البيانية الثنائية الكاملة في الأصل بمصطلحات طوبولوجية بدلاً من مصطلحات نظرية الرسم البياني.

[FOOTNOTEChangKloksLee2001-2] تشانغ، كلوكس ولي (2001) .

[FOOTNOTETurán1941-3] توران (1941) .

[FOOTNOTEGrahamRothschildSpencer1990-4] غراهام، روتشيلد وسبنسر (1990) .

[5] بارتيليمي، لوكلير ومونجارديت (1986) ، الصفحة 200.

[FOOTNOTEKarp1972-6] كارب (1972) .

[7] حمزة أوغلو وباتل (1998) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

A

[ 6 ]

[ 7 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗