مؤلفه همبندی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک گراف به مؤلفهٔ هم‌بندی

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

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

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

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

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

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

برای پیدا کردن مولفه‌های همبندی یک گراف، ، نیاز به زمان اجرای خطی نسبت به طول ورودی داریم.

منابع[ویرایش]