سلام
دوستان ببخشید اگه سوالم مبتدیانه،هست اگه میشه یه توضیح کامل بدید البته جواب پوران رو متوجه نشدم.تصویر رو هم ضمیمه کردم.
باتشکر
حداقل یال برای این که یک گراف پوشا باشه میشه درخت
که درجه درخت با n گره میشه n-1
گراف کامل خودش از هر راس به بقیه راسها(n-1)
یال وجود داره n*n-1
که اگه جهتدار نباشه نصف میشه(دیگه رفت و برگشتی نیست)
پس در گراف کامل با ۱۰ راس
۱۰*۹/۲=۴۵ یال داریم
حداقل هم ۱۰-۱=۹
پس میشه ۴۵-۹=۳۶ تا یال حذف کرد و پوشا بود