مدل‌ سازی (تاریخچه احاطه‌ گری)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 04 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 20 مرتبه

برخی از مسائل روزمره زندگی را می‌توان به‌کمک مدل سازی ابتدا به یک مساله ریاضی تبدیل کرد و سپس با حل مساله ریاضی، مساله اصلی را حل کرد.

به‌طور کلی بعضی مفاهیم ریاضی در مدل سازیِ مسائلِ زندگیِ واقعی، پرکاربرد هستند.

احاطه‌گری یکی از مفاهیم پر کاربرد است که در ادامه با تاریخچه، مفهوم و کاربردهایی از آن آشنا می‌شویم.

تاریخچه احاطه‌گری

در قرن نوردهم میلادی مسائلی مانند (یافتن حداقل تعداد مهره وزیری که می‌توانند با چینش مناسب، تمام صفحه شطرنج رابپوشانند) یعنی هرخانه صفحه شطرنج که در آن وزیر قرار نگرفته است توسط حداقل یک وزیر تهدید شده باشند، ذهن برخی از مردم اروپا را به خود مشغول کرده بود.

احاطه‌گری - پیمان گردلو 

تفکر درباره پرسش‌هایی از این دست، باعث به‌وجود آمدن مفهومی در شاخه گراف به نام احاطه‌گری شد.

احاطه‌گری - پیمان گردلو

تمرین

شکل زیر را در نظر بگیرید:

احاطه‌گری - پیمان گردلو

قرار است در برخی تقاطع‌های این شهر، دستگاه‌های خودپرداز به‌گونه‌ای نصب شوند که دو شرط زیر را داشته باشد.

شرط اول) برای راحتی شهروندان، دستگاه‌ها به‌گونه‌ای نصب شده باشند که هر فرد در هر تقاطعی که قرار گرفته باشد، یا در همان تقاطع به‌دستگاه خود پرداز دسترسی داشته باشد و یا حداکثر با رفتن به یک تقاطعِ مجاور، به‌دستگاه خود پرداز دسترسی پیدا کند.


شرط دوم) به‌جهت صرفه‌جویی در هزینه‌ها با کم‌ترین تعداد دستگاه خود پردازِ ممکن، این کار صورت گیرد.

منطقه مورد نظر را با گراف، مدل سازی کنید.

احاطه‌گری - پیمان گردلو

سوالات اساسی که در مورد گراف بالا مطرح است را بیان کنید.

الف) در این مدل سازی، تقاطع‌ها و خیابان‌های بین آنها هرکدام به چه صورت نمایش داده شده اند؟


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


چنین مجموعه‌ها از رئوس را یک مجموعه احاطه گر برای گراف می‌نامیم و مجموعه شامل همه رئوس گراف، یک مجموعه احاطه‌گر است.

تمرین

فرض کنید a,b,c,d,e,f,g,h,i,j,k شهرهای یک استان باشند و فواصل مستقیم این شهرها ازیک‌دیگر، مطابق جدول زیر باشد.

احاطه‌گری - پیمان گردلو

می‌خواهیم تعدادی استادیوم ورزشی در برخی از شهرهای این استان تاسیس کنیم به‌طوری‌که همه شهرهای استان از پوشش خدمات ورزشی برخوردار گردند.

از طرفی برای کاهش هزینه‌ها، می‌خواهیم کم‌ترین تعداد ممکن استادیوم ورزشی را احداث کنیم.

اگر هر استادیوم ورزشی تا 50 کیلومتر اطراف خود را پوشش دهد، حداقل چند استادیوم ورزشی احتیاج داریم و در چه شهرهایی باید آنها را احداث کنیم؟

برای مدل‌سازی این مساله کافی است گراف مربوط به آن را به این طریق رسم کنیم که به‌جای هر شهر یک راس قرار دهیم و سپس دو راس را به‌هم وصل کنیم اگر و تنها اگر فاصله مستقیم آن دو شهر از 50 کیلومتر بیش‌تر نباشد.


احاطه‌گری - پیمان گردلو

تمرین

فرض کنیم هشت شهر مطابق شکل زیر قرار دارند:

احاطه‌گری - پیمان گردلو

می‌خواهیم در بعضی از این شهرها ایستگاه رادیویی بسازیم. 

هر شهر می‌تواند از شهر همسایه یا مجاور خود مطابق شکل استفاده کند.

حداقل تعداد ایستگاه‌های ساخته شده چقدر است؟

مطابق شکل، اگر ایستگاه‌ها در شهر‌های e,a ساخته شوند، تمام شهرهای مجاور را پوشش می‌دهند.


شهرهای f,b,u و خود شهر a توسط شهر a پوشش داده یا احاطه می‌شوند.


شهرهای d,c,g و هم‌چنین خود e توسط شهر e احاطه یا در بیان این مساله، پوشش داده می‌شوند.


اگر مجموعه زیر راس‌های این گراف باشد:

V=a,b,c,d,e,f,g,u


مجموعه راس‌های D=a,e طوری است که هر راس V مجاور راسی از D است.

برای ارسال نظر وارد سایت شوید