مؤلفه همبندی

در نظریه گراف، هر گراف ساده دارای یک یا بیشتر مولفه همبندی است. یک زیر گراف مانند H از G یک مولفهٔ همبندی برای G است اگر و فقط اگر بین هر دو راس در H، دست‌کم یک مسیر وجود داشته باشد و با افزودن هر راس (و یا یال) دیگری از G به H این خاصیت از بین برود. به عبارت دیگر هر زیر گراف بیشینه و همبند از G، یک مولفهٔ همبندی G است.

تعریف مولفه همبندی با استفاده از رابطهٔ هم‌ارزی

مولفه‌های همبندی یک گراف، رده‌های هم‌ارزی تعریف شذه توسط رابطهٔ هم‌ارزی "قابل دست‌یابی بودن" (به انگلیسی: Reachablity) روی راس‌های گراف هستند. به راحتی می‌توان دید که رابطهٔ "قابل دست‌یابی بودن" سه خاصیت [انعکاسی]]، تقارنی و ترایایی را داراست و در نتیجه یک رابطهٔ هم‌ارزی روی راس‌های گراف تشکیل می‌دهد.

بین همهٔ راس‌هایی که تحت این رابطه در یک رده قرار می‌گیرند دست‌کم یک مسیر وجود دارد و با افزودن هر راس دیگری به یک رده این ویژگی از میان می‌رود پس طبق تعریف، هر رده متناظر با یک مولفهٔ همبندی می‌باشد.

الگوریتم‌های پیدا کردن مولفه‌های همبندی یک گراف

با استفاده از هر روش جستجو در گراف، مانند جستجوی اول سطح و یا جستجوی اول عمق، می‌توان مولفه‌های همبندی یک گراف را پیدا کرد. به عنوان نمونه، برای پیدا کردن تمامی راس‌هایی که با راس v در یک مولفهٔ همبندی قرار دارند می‌توان جستجوی اول عمق را از راس v شروع کرد و تمامی راس‌هایی که در طول جستجو به آن‌ها وارد می‌شویم در همان مولفهٔ همبندی قرار دارند که راس v در آن است.

برای پیدا کردن مولفه‌های همبندی یک گراف، (G=(V,E، نیاز به زمان اجرای خطی نسبت به طول ورودی‌((|O(|V|+|E) داریم.