تجزیه گوشی

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

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

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

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

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

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

 الگوریتم و پیاده سازی کامپیوتری 
روش پیدا کردن تجزیه گوشی برای یک گراف (Ear Decomposition Search(EDS نامیده می‌شود که پیاده سازی‌های متفاوتی دارد.در یک پیاده‌سازی آن از یک st-شماره گذاری برای یافتن این تجزیه استفاده می‌شود که این روش به صورت موازی گوش‌ها را پیدا می‌کند.Parallel Ear Decomposition Search (EDS) And ST-Numbering In Graphs
باید خاطرنشان کرد که الگوریتم‌های توزیعی نیز برای یافتن تجزیه گوشی به دست آمده است.A Distributed Algorithm for Ear Decomposition

 کاربردها 
از تجزیه گوشی برای بهینه کردن مقایسه‌های داده ای استفاده می‌شود.Ear decomposition for pair comparison data
 یادداشت‌ها 

 مرجع‌شناسی 


رده:اشیاء نظریه گراف
رده:نظریه گراف
رده:نظریه میتروید