تجزیه گوشی

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

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

منظور از یک تجزیه گوشی برای گراف، یافتن مجموعه زیرگرافهای ${\displaystyle P_{n}\,...,P_{1}\ ,P_{0}\ }$ است که ${\displaystyle P_{0}\ }$ یک دور بوده ${\displaystyle P_{i}\ }$ها مسیر می‌باشند و برای هر ${\displaystyle i\leq n}$ ، ${\displaystyle P_{0}\cup P_{1}\cup P_{2}\cup ...\cup P_{i}}$ زیرگرافی دوهمبند باشد و ${\displaystyle P_{i+1}\ }$ تنها در دو راس ابتدا و انتها با زیرگراف گفته شده اشتراک داشته باشد.

قضیه اصلی

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

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

لم

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

اثبات

بخش اگر:

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

بخش تنها اگر:

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

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

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

کاربردها

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

یادداشت‌ها

1. West p.146
2. West p.147
3. Parallel Ear Decomposition Search (EDS) And ST-Numbering In Graphs
4. A Distributed Algorithm for Ear Decomposition
5. Ear decomposition for pair comparison data

مرجع‌شناسی

• 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)