مؤلفه همبندی

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

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

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

برای پیدا کردن مؤلفه‌های همبندی یک گراف، ${\displaystyle G=(V,E)}$

${\displaystyle O(|V|+|E|)}$