المپدیا

گراف $G$ برای دور داشتن حداقل چند یال نیاز دارد؟

سعی کنید مجموعه‌ی یال‌هایی که قصد دارید از آن‌ها دور برای حذف کردن انتخاب کنید را از مجموعه یال‌هایی که قصد دارید به جهت همبندی گراف از‌ آن‌ها استفاده کنید، جدا کنید.

برای همبندی یک گراف، چند یال نیاز است؟

اگر به تعداد کافی یال برای همبندی گراف حذف کنیم، چند یال حداقل باید باقی بماند تا گراف دور داشته باشد؟

اگر در راهنمایی ۳، طوری یال‌ها حذف شود که تمام یال‌های مجاور با یک راس در مجموعه‌ی حذف شده فرار داشته باشند، چند یال در گراف حاصل باید باقی بماند تا دور داشته باشیم؟

حال به مثال فکر کنید. طبق راهنمایی‌های قبلی به دنبال مثالی با $2n-3$ یال می‌باشیم که حذف هر دور موجب ناهمبندی شود.

$2n-3 = 2(n-2)+1$

دو راس $u$ و $v$ را کنار بگذارید. هر راس دیگر را به هر دوی $u$ و $v$ متصل کنید. همچنان یک یال باید اضافه کنیم. آن یال را کجا قرار دهیم؟

یال مذکور در راهنمایی ۸ را بین دو راس $u$ و $v$ قرار دهید. چرا با حذف هر دور گراف نا‌همبند می‌شود؟