مؤلفه همبندی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
Pseudoforest.svg

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

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

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

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

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

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

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

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

  • مشارکت‌کنندگان ویکی‌پدیا، «Connected component (graph theory)»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ مارس ۲۰۱۴).