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

في نظرية المخططات ، يُعرف مُكوِّن المخطط غير الموجه بأنه مخطط فرعي متصل لا ينتمي إلى أي مخطط فرعي متصل أكبر. تُقسِّم مُكوِّنات أي مخطط رؤوسه إلى مجموعات منفصلة ، ​​وهي المخططات الفرعية الناتجة عن تلك المجموعات. المخطط المتصل في حد ذاته له مُكوِّن واحد فقط، وهو المخطط بأكمله. تُسمى المُكوِّنات أحيانًا بالمُكوِّنات المتصلة .

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

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

يمكن تعريف أحد مكونات الرسم البياني غير الموجه بأنه رسم بياني فرعي متصل لا يُعد جزءًا من أي رسم بياني فرعي متصل أكبر. على سبيل المثال، يحتوي الرسم البياني الموضح في الشكل التوضيحي الأول على ثلاثة مكونات. كل رأس${\displaystyle v}$ينتمي عنصر من الرسم البياني إلى أحد مكونات الرسم البياني، والذي يمكن إيجاده كرسم بياني فرعي مستحث لمجموعة الرؤوس التي يمكن الوصول إليها من${\displaystyle v}$[ ^{1 ] كل} رسم بياني هو اتحاد منفصل لمكوناته. ^{[ 2 ]} تتضمن الأمثلة الإضافية الحالات الخاصة التالية:

• في الرسم البياني الفارغ ، يشكل كل رأس مكونًا برأس واحد وصفر من الحواف. ^{[ 3 ]} وبشكل أعم، يتشكل مكون من هذا النوع لكل رأس معزول في أي رسم بياني. ^{[ 4 ]}
• في الرسم البياني المتصل ، يوجد مكون واحد فقط: الرسم البياني بأكمله. ^{[ 4 ]}
• في الغابة ، كل مكون هو شجرة . ^{[ 5 ]}
• في الرسم البياني العنقودي ، كل مكون عبارة عن زمرة قصوى . يمكن إنتاج هذه الرسوم البيانية كإغلاقات متعدية لرسوم بيانية غير موجهة عشوائية، حيث يكون إيجاد الإغلاق المتعدي بمثابة صياغة مكافئة لتحديد المكونات المتصلة. ^{[ 6 ]}

يتضمن تعريف آخر للمكونات فئات التكافؤ لعلاقة التكافؤ المعرفة على رؤوس الرسم البياني. في الرسم البياني غير الموجه، يمثل الرأس${\displaystyle v}$يمكن الوصول إليه من رأس${\displaystyle u}$إذا كان هناك مسار من${\displaystyle u}$ل${\displaystyle v}$أو ما يعادلها من مسار (طريق يسمح بتكرار الرؤوس والحواف). إمكانية الوصول هي علاقة تكافؤ، لأن:

• إنها خاصية انعكاسية : يوجد مسار تافه طوله صفر من أي رأس إلى نفسه.
• إنه متناظر : إذا كان هناك مسار من${\displaystyle u}$ل${\displaystyle v}$تشكل نفس الحواف بترتيب عكسي مسارًا من${\displaystyle v}$ل${\displaystyle u}$.
• وهي فعل متعدٍ : إذا كان هناك مسار من${\displaystyle u}$ل${\displaystyle v}$ومسار من${\displaystyle v}$ل${\displaystyle w}$يمكن ربط المسارين معًا لتشكيل مسار للمشي من${\displaystyle u}$ل${\displaystyle w}$.

تقسم فئات التكافؤ لهذه العلاقة رؤوس الرسم البياني إلى مجموعات منفصلة ، ​​وهي مجموعات فرعية من الرؤوس يمكن الوصول إليها جميعًا من بعضها البعض، دون وجود أزواج إضافية يمكن الوصول إليها خارج أي من هذه المجموعات الفرعية. ينتمي كل رأس إلى فئة تكافؤ واحدة فقط. المكونات هي الرسوم البيانية الفرعية المستحثة التي تشكلها كل فئة من فئات التكافؤ هذه. ^{[ 7 ]} بدلاً من ذلك، تُعرّف بعض المصادر المكونات على أنها مجموعات الرؤوس بدلاً من الرسوم البيانية الفرعية التي تحثها. ^{[ 8 ]}

وقد استُخدمت تعريفات مماثلة تتضمن فئات التكافؤ لتحديد مكونات أشكال أخرى من اتصال الرسوم البيانية ، بما في ذلك المكونات الضعيفة ^{[ 9 ]} والمكونات المتصلة بقوة للرسوم البيانية الموجهة ^{[ 10 ]} والمكونات ثنائية الاتصال للرسوم البيانية غير الموجهة. ^{[ 11 ]}

يمكن استخدام عدد مكونات رسم بياني محدود معين لحساب عدد الحواف في غاباته الممتدة : في رسم بياني مع${\displaystyle n}$الرؤوس و${\displaystyle c}$المكونات، كل غابة ممتدة ستحتوي بالضبط${\displaystyle nc}$الحواف. هذا الرقم${\displaystyle nc}$يمثل رتبة الماترويد النظرية للرسم البياني، ورتبة الماترويد الرسومي الخاص به . تساوي رتبة الماترويد الرسومي الثنائي رتبة الدائرة للرسم البياني، وهي الحد الأدنى لعدد الحواف التي يجب إزالتها من الرسم البياني لكسر جميع دوراته. في رسم بياني مع${\displaystyle m}$الحواف،${\displaystyle n}$الرؤوس و${\displaystyle c}$المكونات، رتبة الدائرة هي${\displaystyle m-n+c}$[ ^{12 ]​}

يمكن تفسير الرسم البياني كفضاء طوبولوجي بعدة طرق، على سبيل المثال، بوضع رؤوسه كنقاط في مواقع عامة في الفضاء الإقليدي ثلاثي الأبعاد، وتمثيل حوافه كقطع مستقيمة بين تلك النقاط. ^{[ 13 ]} يمكن تعميم مكونات الرسم البياني من خلال هذه التفسيرات باعتبارها المكونات الطوبولوجية المتصلة للفضاء المقابل؛ وهي فئات تكافؤ من النقاط لا يمكن فصلها بأزواج من المجموعات المغلقة المنفصلة. وكما أن عدد المكونات المتصلة للفضاء الطوبولوجي ثابت طوبولوجي مهم ، فإن عدد مكونات الرسم البياني ثابت مهم ، وفي نظرية الرسم البياني الطوبولوجية ، يمكن تفسيره على أنه عدد بيتي الصفري للرسم البياني. ^{[ 3 ]}

يظهر عدد المكونات بطرق أخرى في نظرية المخططات أيضًا. ففي نظرية المخططات الجبرية، يساوي عدد المكونات تعدد الصفر كقيمة ذاتية لمصفوفة لابلاس لمخطط محدود. ^{[ 14 ]} وهو أيضًا دليل أول معامل غير صفري لكثير الحدود اللوني للمخطط، ويمكن الحصول على كثير الحدود اللوني للمخطط بأكمله كحاصل ضرب كثيرات حدود مكوناته. ^{[ 15 ]} يلعب عدد المكونات دورًا رئيسيًا في نظرية توت حول المطابقات الكاملة التي تميز المخططات المحدودة التي تحتوي على مطابقات كاملة ^{[ 16 ]} ، وفي صيغة توت-بيرج المرتبطة بها لحجم المطابقة القصوى ، ^{[ 17 ]} وفي تعريف متانة المخطط . ^{[ 18 ]}

من السهل حساب مكونات رسم بياني محدود في وقت خطي (بدلالة عدد رؤوس وحواف الرسم البياني) باستخدام البحث بالعرض أولاً أو البحث بالعمق أولاً . في كلتا الحالتين، يبدأ البحث من رأس معين.${\displaystyle v}$سيجد المكون بأكمله الذي يحتوي${\displaystyle v}$(ولا أكثر) قبل العودة. يمكن إيجاد جميع مكونات الرسم البياني من خلال المرور على رؤوسه، وبدء بحث جديد بالعرض أولاً أو بالعمق أولاً كلما وصل المسار إلى رأس لم يُدرج في مكون تم العثور عليه سابقًا. يصف هوبكروفت وتارجان (1973) هذه الخوارزمية بشكل أساسي، ويذكران أنها كانت "معروفة جيدًا" بالفعل. ^{[ 19 ]}

تُعدّ تقنية تصنيف المكونات المتصلة ، وهي تقنية أساسية في تحليل الصور الحاسوبية ، عمليةً تتضمن إنشاء رسم بياني من الصورة وتحليل مكوناته. تمثل الرؤوس مجموعة فرعية من بكسلات الصورة، يتم اختيارها لكونها ذات أهمية أو لاحتمالية كونها جزءًا من الكائنات المصورة. تربط الحواف البكسلات المتجاورة ، حيث تُحدد التجاور إما بشكل متعامد وفقًا لجوار فون نيومان ، أو بشكل متعامد وقطري وفقًا لجوار مور . يُتيح تحديد المكونات المتصلة لهذا الرسم البياني إجراء معالجة إضافية لاكتشاف المزيد من البنية في تلك الأجزاء من الصورة أو تحديد نوع الكائن المصور. وقد طوّر الباحثون خوارزميات متخصصة في إيجاد المكونات لهذا النوع من الرسوم البيانية، مما يسمح بمعالجتها بترتيب البكسلات بدلًا من الترتيب الأكثر تشتتًا الذي ينتج عن البحث بالعرض أولًا أو البحث بالعمق أولًا. قد يكون هذا مفيدًا في الحالات التي يكون فيها الوصول المتسلسل إلى البكسلات أكثر كفاءة من الوصول العشوائي، إما لأن الصورة ممثلة بطريقة هرمية لا تسمح بالوصول العشوائي السريع أو لأن الوصول المتسلسل ينتج أنماط وصول أفضل إلى الذاكرة . ^{[ 20 ]}

توجد أيضًا خوارزميات فعالة لتتبع مكونات الرسم البياني ديناميكيًا عند إضافة الرؤوس والحواف، وذلك باستخدام بنية بيانات المجموعة المنفصلة لتتبع تقسيم الرؤوس إلى فئات متكافئة، واستبدال أي فئتين باتحادهما عند إضافة حافة تربط بينهما. تستغرق هذه الخوارزميات وقتًا مستهلكًا${\displaystyle O(\alpha (n))}$لكل عملية، حيث تُعتبر إضافة الرؤوس والحواف وتحديد المكون الذي يقع فيه الرأس عمليتين، و${\displaystyle \alpha }$هي دالة معكوسة بطيئة النمو لدالة أكرمان سريعة النمو . ^{[ 21 ]} أحد تطبيقات هذا النوع من خوارزميات الاتصال التزايدي هو خوارزمية كروسكال للأشجار الممتدة الدنيا ، والتي تضيف حوافًا إلى الرسم البياني بترتيب تصاعدي حسب الطول، وتُدرج الحافة في الشجرة الممتدة الدنيا فقط عندما تربط مكونين مختلفين من الرسم البياني الفرعي المُضاف سابقًا. ^{[ 22 ]} عندما يُسمح بإضافة الحواف وحذفها، تستطيع خوارزميات الاتصال الديناميكية الحفاظ على نفس المعلومات، في وقت مُستهلك.${\displaystyle O(\log ^{2}n/\log \log n)}$لكل تغيير ووقت${\displaystyle O(\log n/\log \log n)}$لكل استعلام اتصال، ^{[ 23 ]} أو في وقت متوقع عشوائي شبه لوغاريتمي . ^{[ 24 ]}

استُخدمت مكونات الرسوم البيانية في نظرية التعقيد الحسابي لدراسة قدرة آلات تورينج ذات الذاكرة العاملة المحدودة بعدد لوغاريتمي من البتات، حيث لا يمكن الوصول إلى المدخلات الأكبر حجمًا إلا من خلال القراءة بدلًا من تعديلها. تُعرّف المشكلات التي يمكن حلها بواسطة الآلات المحدودة بهذه الطريقة فئة التعقيد L. لسنوات عديدة، لم يكن واضحًا ما إذا كان من الممكن إيجاد مكونات متصلة في هذا النموذج، عند صياغته كمشكلة قرار لاختبار ما إذا كان رأسان ينتميان إلى المكون نفسه، وفي عام 1982، تم تعريف فئة تعقيد ذات صلة، SL ، لتشمل مشكلة الاتصال هذه وأي مشكلة أخرى مكافئة لها في ظل اختزالات الفضاء اللوغاريتمي . ^{[ 25 ]} وأُثبت أخيرًا في عام 2008 أنه يمكن حل مشكلة الاتصال هذه في فضاء لوغاريتمي، وبالتالي فإن SL = L. ^{[ 26 ]}

في الرسم البياني المُمثَّل بقائمة تجاور ، مع إمكانية الوصول العشوائي إلى رؤوسه، من الممكن تقدير عدد المكونات المتصلة، باحتمالية ثابتة للحصول على خطأ إضافي (مطلق) على الأكثر${\displaystyle \varepsilon n}$، في زمن دون الخطي${\displaystyle O(\varepsilon ^{-2}\log \varepsilon ^{-1})}$[ ^{27 ]​}

في الرسوم البيانية العشوائية، تُحدد أحجام المكونات بواسطة متغير عشوائي ، والذي بدوره يعتمد على النموذج المحدد لكيفية اختيار الرسوم البيانية العشوائية.${\displaystyle G(n,p)}$نسخة من نموذج إردوس-ريني-جيلبرت ، رسم بياني${\displaystyle n}$يتم توليد الرؤوس عن طريق اختيار عشوائي ومستقل لكل زوج من الرؤوس ما إذا كان سيتم تضمين حافة تربط هذا الزوج، باحتمالية${\displaystyle p}$بما في ذلك تضمين حافة واحتمالية${\displaystyle 1-p}$^{[ 28 ]} يعتمد ترابط هذا النموذج على${\displaystyle p}$وهناك ثلاثة نطاقات مختلفة من${\displaystyle p}$بسلوكيات مختلفة تمامًا عن بعضها البعض. في التحليل أدناه، تحدث جميع النتائج باحتمالية عالية ، مما يعني أن احتمالية النتيجة قريبة جدًا من الواحد لقيم كبيرة بما فيه الكفاية لـ${\displaystyle n}$يعتمد التحليل على أحد المعايير${\displaystyle \varepsilon }$ثابت موجب مستقل عن${\displaystyle n}$يمكن أن تكون هذه القيمة قريبة بشكل تعسفي من الصفر.

دون الحرج${\displaystyle p<(1-\varepsilon )/n}$

في هذا النطاق من${\displaystyle p}$جميع المكونات بسيطة وصغيرة جدًا. أكبر مكون له حجم لوغاريتمي. الرسم البياني عبارة عن غابة زائفة . معظم مكوناته عبارة عن أشجار: عدد الرؤوس في المكونات التي تحتوي على دورات ينمو ببطء أكثر من أي دالة غير محدودة لعدد الرؤوس. كل شجرة ذات حجم ثابت تظهر خطيًا عدة مرات. ^{[ 29 ]}

شديد الأهمية${\displaystyle p\approx 1/n}$

يحتوي أكبر مكون متصل على عدد من الرؤوس يتناسب مع${\displaystyle n^{2/3}}$قد توجد عدة مكونات كبيرة أخرى؛ ومع ذلك ، فإن العدد الإجمالي للرؤوس في المكونات غير الشجرية يتناسب مرة أخرى مع${\displaystyle n^{2/3}}$[ ^{30 ]​}

فوق الحرج${\displaystyle p>(1+\varepsilon )/n}$

يوجد مكون عملاق واحد يحتوي على عدد خطي من الرؤوس. بالنسبة للقيم الكبيرة لـ${\displaystyle p}$حجمه يقترب من حجم الرسم البياني بأكمله:${\displaystyle |C_{1}|\approx yn}$أين${\displaystyle y}$هو الحل الموجب للمعادلة${\displaystyle e^{-pny}=1-y}$أما المكونات المتبقية فهي صغيرة، ذات حجم لوغاريتمي. ^{[ 31 ]}

في نفس نموذج الرسوم البيانية العشوائية، ستوجد مكونات متصلة متعددة ذات احتمالية عالية لقيم .${\displaystyle p}$أقل من عتبة أعلى بكثير،${\displaystyle p<(1-\varepsilon )(\log n)/n}$ومكون متصل واحد للقيم التي تتجاوز الحد الأدنى،${\displaystyle p>(1+\varepsilon )(\log n)/n}$ترتبط هذه الظاهرة ارتباطًا وثيقًا بمسألة جامع القسائم : فلكي يكون الرسم البياني العشوائي متصلًا، يحتاج إلى عدد كافٍ من الحواف بحيث يكون كل رأس متصلًا بحافة واحدة على الأقل. وبشكل أدق ، إذا أُضيفت حواف عشوائية واحدة تلو الأخرى إلى الرسم البياني، فمن المرجح جدًا أن تلامس الحافة الأولى التي تؤدي إضافتها إلى ربط الرسم البياني بأكمله الرأس الأخير المعزول. ^{[ 32 ]}

بالنسبة لنماذج مختلفة، بما في ذلك الرسوم البيانية الفرعية العشوائية للرسوم البيانية الشبكية، تُوصف المكونات المتصلة بنظرية الترشيح . ويتمثل أحد الأسئلة الرئيسية في هذه النظرية في وجود عتبة ترشيح ، وهي احتمال حرج يوجد عنده مكون عملاق (أو مكون لانهائي) ولا يوجد عنده. ^{[ 33 ]}

• كود MATLAB لإيجاد المكونات في الرسوم البيانية غير الموجهة ، MATLAB File Exchange.
• المكونات المتصلة ، ستيفن سكينا، مستودع خوارزميات ستوني بروك