تجزیه گوشی

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

منظور از یک تجزیه گوشی برای گراف، یافتن مجموعه زیرگرافهای است که یک دور بوده ها مسیر می‌باشند و برای هر ، زیرگرافی دوهمبند باشد و تنها در دو راس ابتدا و انتها با زیرگراف گفته شده اشتراک داشته باشد.

قضیه اصلی

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

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

لم

اگر گرافی همبند و بدون راس برشی باشد در این صورت گراف که حاصل زیرتقسیم یال دلخواه از می‌باشد همچنان همبند و بدون راس برشی است.[1]

اثبات

بخش اگر:

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

بخش تنها اگر:

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

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

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

کاربردها

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

یادداشت‌ها

مرجع‌شناسی

  • West, Douglas B. (1996). Introduction to Graph Theory (First Edition ed.). Prentice Hall, Inc. ISBN 0-13-227828-6.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.