المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:گراف:بلوک‌های همبندی

تعریف. قسمتی از یک گراف $G$ را یک بلوک گوییم اگر زیر گرافی ماکسیمال و همبند از $G$ باشد که فاقد راس برشی راس و یال برشیاست. همینطور اگر $G$ همبند بدون راس برشی باشد به آن بلوک گوییم نکته این که در این حالت $G$ نیاز نیست ۲ـ‌همبند باشد.
مثال. اگر بلوکی از $G$ را $H$ بنامیم. آنگاه $H$ فاقد راس برشی است. اما میتواند شامل راس برشی از $G$ باشد.همان‌طور که در شکل دیده میشود. بلوک ها نشان داده شده اند و این گراف دو راس برشی دارد. ویژگی یک یال یک بلوک از گراف $G$ است اگر یک یال برشی از$G$ باشد. وگر نه جزیی از یک دور از است. (چرا؟‌ راس و یال برشی) پس به زیرگرافی بزرگ تر از متعلق است که راس برشی ندارد.
طبق این گفته:

  1. هر درختی د-۱ بلوک دو راسی دارد.
  2. هر بلوک بیش از دو راسی یال برشی ندارد پس ۲ـ‌همبند است.
  3. پس \مثبفarrow ــبلوک های یک گراف راس های تنهای آن یال های برشی آن و مولفه های ۲ـ‌همبند ماکسیمال آن است.

از دیگر ویژگی های یک گراف این است که در آن دوری وجود ندارد که مشمول دو بلوک باشد لذا در یک گراف هیچ دو بلوکی در بیشتر از یک راس مشترک نیستند.


ابزار صفحه