حساب کاربری
​
زمان تقریبی مطالعه: 3 دقیقه
لینک کوتاه

تجزیه گوشی

اگر G   {\displaystyle G\ }

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

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

فهرست

  • ۱ قضیه اصلی
  • ۲ لم
  • ۳ اثبات
  • ۴ الگوریتم و پیاده سازی کامپیوتری
  • ۵ کاربردها
  • ۶ یادداشت‌ها
  • ۷ مرجع‌شناسی

قضیه اصلی

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

G   {\displaystyle G\ }

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

لم

اگر G   {\displaystyle G\ }

گرافی همبند و بدون راس برشی باشد در این صورت گراف G ′   {\displaystyle G^{\prime }\ }
که حاصل زیرتقسیم یال دلخواه u v   {\displaystyle uv\ }
از G   {\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. {{}}: |edition= has extra text (help)
آخرین نظرات
  • طول
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.