به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
63 بازدید
سوال شده در دانشگاه توسط rahmani

سلام، برنامه ای با گپ بنویسید که عدد استقلال گراف را بدهد

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط mahmoud

برنامه نمی‌توانم بنویسم ولی چیزهایی که می‌دانم را می‌نویسم. گپ خودش گراف ندارد و باید از بسته grape استفاده کنید. آن هم عدد استقلال ندارد بلکه زیرمجموعه مستقل دارد و باید اول، همه زیرمجموعه های مستقل ماکسیمال را بیابید و بعد بیشترین اندازه از میان آنها را بیابید که همان عدد استقلال میشود. البته این الگوریتم بدترین حالت است و باید از منابع دنبال الگوریتم بهتر بگردید. صفحه مربوطه برای grape :
http://www.gap-system.org/Manuals/pkg/grape/htm/CHAP005.htm#SECT006

یک بسته دیگر به نام digraphs هست که برای گرافهای جهتدار است و شاید بشود استفاده کرد. اتفاقا زیرمجموعه مستقل ماکسیمال هم دارد:

http://www.gap-system.org/Manuals/pkg/digraphs-0.12.1/doc/chap8.html#X790733B67B0BC894

یک نکته هم هست که عدد استقلال یک گراف برابر با عدد خوشه ای (clique number) گراف متمم آن گراف است.

با توجه به اینکه اخیرا هزینه های نگهداری سایت افزایش چشمگیر چند برابری داشته، محفل ریاضی نیازمند حمایت مالی شما است.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

ابزارها:

سرگرمی: سودوکو جدید

رسم نمودار: Geogebra جدید

...