تجزیه گوشی

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

اگر G\ یک گراف و H\ زیرگرافی از G\ باشد، منظور از یک گوش برای H\ در G\ یک مسیر با طول حداقل یک از G\ است که دو سر این مسیر در H\ قرار دارند و هیچ راس میانی آن در H\ قرار ندارد.

منظور از یک تجزیه گوشی برای گراف، یافتن مجموعه زیرگرافهای P_n\,...,P_1\ ,P_0\ است که P_0\ یک دور بوده P_i\ ها مسیر می‌باشند و برای هر i \leq n ، P_0 \cup P_1 \cup P_2 \cup ... \cup P_i زیرگرافی دوهمبند باشد و P_{i+1}\ تنها در دو راس ابتدا و انتها با زیرگراف گفته شده اشتراک داشته باشد.

قضیه اصلی[ویرایش]

این قضیه که هاسلر ویتنی در سال ۱۹۳۲ (میلادی) آن را ثابت کرد شرطی لازم و کافی برای وجود تجزیه گوشی بدست می‌دهد و صورت آن چنین است:

G\ گرافی همبند و بدون راس برشی(دوهمبند) است، اگر و تنها اگر G\ تجزیه گوشی داشته باشد.بعلاوه هر دور G\ دور آغازینی برای یک تجزیه گوشی است.[۱]

لم[ویرایش]

اگر G\ گرافی همبند و بدون راس برشی باشد در این صورت گراف G^\prime\ که حاصل زیرتقسیم یال دلخواه uv\ از G\ می‌باشد همچنان همبند و بدون راس برشی است.[۲]

اثبات[ویرایش]

بخش اگر:

چون دورها همبند و بدون راس برشی هستند، کافیست نشان دهیم اضافه کردن مسیرهای با خاصیت بالا دو همبند بودن را حفظ می‌کند و در نهایت گرافی دو همبند خواهیم داشت.[۳]

بخش تنها اگر:

برای اثبات باید در نظر داشت هر دو یال گراف مورد نظر روی یک دور قرار دارند.با استفاده از این خاصیت و در نظر گرفتن دور اولی(که به دلیل دوهمبند بودن گراف حداقل یک دور وجود دارد) می توان تجزیه گوشی را به شیوهٔ استقرایی کامل کرد.[۴]

الگوریتم و پیاده سازی کامپیوتری[ویرایش]

روش پیدا کردن تجزیه گوشی برای یک گراف (Ear Decomposition Search(EDS نامیده می‌شود که پیاده سازی‌های متفاوتی دارد.در یک پیاده سازی آن از یک st-شماره گذاری[۱] برای یافتن این تجزیه استفاده می‌شود که این روش به صورت موازی گوش‌ها را پیدا می کند.[۵] باید خاطرنشان کرد که الگوریتم‌های توزیعی نیز برای یافتن تجزیه گوشی به دست آمده است.[۶]

کاربردها[ویرایش]

از تجزیه گوشی برای بهینه کردن مقایسه‌های داده ای استفاده میشود.[۷]

یادداشت‌ها[ویرایش]

مرجع‌شناسی[ویرایش]