====== چندیال ======


یک گراف ‎$n$‎ راسی تقریباً همبند است اگر به ازای هر افراز رئوس ‎$G$‎ به دو 
دسته‌ی ‎$S$‎ و ‎$T$‎ که ‎$|T| \geq |S| \geq n/10$‎، حداقل یک یال بین این دو دسته وجود داشته باشد.
 کم‌ترین مقدار ‎$k$‎ را در نظر بگیرید که که اگر یک گراف ‎$n$‎-راسی با رئوس ‎$1‎, ‎2‎, ‎\dots‎, ‎n$‎ و ‎$k$‎ یال درنظربگیرید (تعداد این 
یال‌ها ‎$C(n,k)$‎ می‌باشد)، 
به احتمال حداقل ‎$1/2$‎ این گراف تقریباً همبند باشد. پیچیدگی تابعی ‎($\Theta$) $k$‎ را به‌دست آورید.

  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]