مؤلفه همبندی

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

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

مولفه‌های همبندی یک گراف، رده‌های هم‌ارزی تعریف شده توسط رابطهٔ هم‌ارزی «قابل دست‌یابی بودن» (به انگلیسی: Reachability) روی راس‌های گراف هستند. به راحتی می‌توان دید که رابطهٔ «قابل دست‌یابی بودن» سه خاصیت انعکاسی، تقارنی و ترایایی را داراست و در نتیجه یک رابطهٔ هم‌ارزی روی راس‌های گراف تشکیل می‌دهد.

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

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

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

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