پرش به محتوا

تجزیه گوشی

از ویکی‌پدیا، دانشنامهٔ آزاد
عکس یه نمونه 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)