به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
58 بازدید
سوال شده در دانشگاه توسط 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) گراف متمم آن گراف است.

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
59 نفر آنلاین
3 عضو و 56 مهمان در سایت حاضرند
بازدید امروز: 4066
بازدید دیروز: 5083
بازدید کل: 4842259
...