تجزیه گوشی

عکس یه نمونه G گراف

اگر $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-شماره گذاری[۱] برای یافتن این تجزیه استفاده می‌شود که این روش به صورت موازی گوش‌ها را پیدا می‌کند. باید خاطرنشان کرد که الگوریتم‌های توزیعی نیز برای یافتن تجزیه گوشی به دست آمده است.

کاربردها

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

مرجع‌شناسی

• West, Douglas B. (1996). Introduction to Graph Theory (First Edition ed.). Prentice Hall, Inc. ISBN 0-13-227828-6. {{cite book}}: |edition= has extra text (help)