دانشنامه پارس مسترزپارس مسترز ایران toastmasters.ir ↗

ایستگاه ۱ از ۵ • معمار پل‌های نامرئی • V-MATH سطح ۳: افزایش دانش

معمار پل‌های نامرئی

نظریهٔ گراف: با چند نقطه و خط، کوتاه‌ترین و باهوش‌ترین مسیر را پیدا کن!

  • پروژه
  • ⏱ ۴ تا ۶ دقیقه
فهرست این صفحه
تصویر ایستگاه ۱: معمار پل‌های نامرئی

نظریهٔ گراف: با چند نقطه و خط، کوتاه‌ترین و باهوش‌ترین مسیر را پیدا کن!

هدف‌های این ایستگاه#

  • یک مسئلهٔ واقعی را به گراف (گره و یال) تبدیل کنی.
  • درجهٔ گره‌ها را بشماری و با قانون اویلر بگویی مسیر بی‌تکرار ممکن است یا نه.
  • با «جفت‌کردن» گره‌های فرد، کوتاه‌ترین مسیر بازگشتیِ پستچی را پیدا کنی.
  • گزارش کتبی تایپ‌شده بنویسی و در ارائهٔ ۴ تا ۶ دقیقه‌ای از مسیرت دفاع کنی.

مأموریت تو: مشاور مسیر یک کسب‌وکار محلی شو

هدف
گزارش کتبی تایپ‌شده بنویسی و در ارائهٔ ۴ تا ۶ دقیقه‌ای از مسیرت دفاع کنی.
نمای کلی
برای یک پیک موتوری، کتاب‌رسان یا نانوایی محله نقشهٔ ساده بکش، آن را به گراف وزن‌دار تبدیل کن، گره‌های فرد را پیدا و جفت کن، مسیری بساز که از همهٔ خیابان‌ها بگذرد و با کمترین مسافت به نقطهٔ شروع برگردد. گزارش کتبی تایپ‌شده را به تسهیلگر سرپرست بده و در ارائهٔ ۴ تا ۶ دقیقه‌ای از انتخاب‌هایت با عدد دفاع کن.

بخش ۱: ماجرا: معمای هفت پل#

قرن هجدهم، شهر کونیگسبرگ (کالینینگراد امروز). رودخانه شهر را به ۴ خشکی تقسیم کرده بود و ۷ پل آن‌ها را به هم وصل می‌کرد. مردم دنبال یک پیاده‌روی رؤیایی بودند: از خانه راه بیفتی، از هر ۷ پل دقیقاً یک بار بگذری و به خانه برگردی. سال‌ها هیچ‌کس موفق نشد. سال ۱۷۳۶، لئونارد اویلر به جای نقشه‌کشی دقیق، هر خشکی را یک نقطه و هر پل را یک خط کشید و ثابت کرد این کار «ناممکن» است. همین نقاشی ساده شروع شاخه‌ای تازه از ریاضی شد: نظریهٔ گراف! (نه، ربطی به «گرافیک» ندارد؛ کسی قرار نیست فتوشاپ باز کند.)

بخش ۲: گره (Node)#

هر نقطه یا «چیز» در شبکه: خانه، مدرسه، مغازه، یک آدم در شبکهٔ دوستی.

بخش ۳: یال (Edge)#

هر ارتباط میان دو گره: خیابان، خط تلفن، دوستی، مسیر پرواز. اگر برای یال طول یا زمان بنویسیم، به آن «وزن» می‌گوییم.

نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی

بخش ۴: درجه (Degree)#

تعداد یال‌هایی که به یک گره وصل است. درجهٔ زوج (۲، ۴، ۶...) یا فرد (۱، ۳، ۵...). نکتهٔ طلایی: مجموع درجه‌ها همیشه ۲ برابر تعداد یال‌هاست، چون هر یال دو سر دارد؛ پس تعداد گره‌های فرد همیشه زوج است!

بخش ۵: درجه‌ها را بشمار#

در گراف زیر ۵ گره و ۶ یال داریم. درجه‌ها: خانه ۲، مدرسه ۳، نانوایی ۳، پارک ۳، کتابخانه ۱. جمع: ۱+۳+۳+۳+۲ = ۱۲ = ۲ × ۶ ✓. گره‌های فرد: مدرسه، نانوایی، پارک و کتابخانه؛ یعنی ۴ گره فرد (یک عدد زوج، همان‌طور که قانون گفت).

نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی
نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی
نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی

بخش ۶: جعبه‌ابزار : ۲ مسئلهٔ پستچی#

پستچی باید از «همهٔ خیابان‌ها» بگذرد و به اداره برگردد. اگر همهٔ گره‌ها زوج باشند، خوش به حالش: یک دور اویلری کافی است و هیچ خیابانی تکرار نمی‌شود. اما در بیشتر شهرها گره فرد داریم؛ پس باید چند خیابان را دوبار برود. ترفند: گره‌های فرد را دوتا‌دوتا «جفت» کن و کوتاه‌ترین راه بین هر جفت را تکرار کن؛ ارزان‌ترین جفت‌بندی برنده است. به این مسئله «مسئلهٔ پستچی چینی» می‌گویند (به افتخار ریاضی‌دان چینی، میِ‌کو گوان، که سال ۱۹۶۲ آن را مطرح کرد). یک نکتهٔ ظریف: چون پستچی باید به نقطهٔ شروع برگردد، حتی با ۲ گره فرد هم یک تکرار لازم است.

بخش ۷: مسیر پستچی#

چهار گره A، B، C، D و پنج خیابان: AB=۴، BC=۳، CD=۴، DA=۳ و قطر BD=۵ (کیلومتر). مجموع خیابان‌ها ۱۹. درجه‌ها: A=۲، C=۲، B=۳، D=۳؛ پس B و D فردند. کوتاه‌ترین راه B تا :D مستقیم ۵، از راه A ۷=۳+۴، از راه C ۷=۴+۳؛ پس BD را تکرار می‌کنیم. طول کل = ۱۹ + ۵ = ۲۴ کیلومتر. یک مسیر نمونه: A→D→C→B→D→B→.A

نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی

بخش ۸: ۴ گره فرد#

اگر گره‌های فرد P، Q، R، S باشند، فقط ۳ راه جفت‌کردن داریم: (PQ، RS)، (PR، QS)، (PS، QR). با کوتاه‌ترین فاصله‌های PQ=۲، RS=۳، PR=۶، QS=۷، PS=۵، QR=۴ هزینه‌ها ۵، ۱۳ و ۹ کیلومتر می‌شود؛ پس (PQ، RS) برنده است.

نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی
نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی

بخش ۹: حواست باشد: پستچی یا پیک؟#

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

بخش ۱۰: مراحل انجام پروژه#

  1. یک سناریو برگزین: پیک پیتزا (۵ خانه)، باغبان (چمن ۷ خانه)، کتاب‌رسان (۴ کتابخانه) یا ایدهٔ خودت.
  2. نقشه بکش: مبدأ و مقصدها را گره و خیابان‌های اصلی را یال کن؛ برای هر یال وزن (متر یا دقیقه) بنویس.
  3. درجهٔ هر گره را بشمار و گره‌های فرد را علامت بزن.
  4. کوتاه‌ترین راه میان جفت‌های گره فرد را پیدا کن و ارزان‌ترین جفت‌بندی را برگزین.
  5. مسیر نهایی را روی نقشه با شماره‌گذاری قدم‌ها بکش و طول کل را حساب کن.
  6. گزارش کتبی تایپ‌شده بنویس و ارائه را آماده کن.
نمودار و تصویر آموزشی ایستگاه معمار پل‌های نامرئی

بخش ۱۱: ساختار ارائهٔ ۴ تا ۶ دقیقه‌ای#

مقدمه (حدود ۱ دقیقه): سناریو را جذاب معرفی کن؛ مثاً ل«امروز نشان می‌دهم چطور ۲۰٪ از راه پیک محله را کم کردم!». نمایش گراف (حدود ۱ تا ۲ دقیقه): گره‌ها، یال‌ها و تعداد گره‌های فرد را نشان بده. راه‌حل (حدود ۲ دقیقه): بگو کدام خیابان‌ها را تکرار کردی و چرا؛ با عدد مقایسه کن («فقط ۳۰۰ متر اضافه شد، گزینهٔ دیگر دست‌کم یک کیلومتر بود»). نتیجه (حدود ۱ دقیقه): نظریهٔ گراف دیگر کجا به کار می‌آید؟ تمرین سریع: شبکهٔ دوستی‌های صمیمی کلاس را بکش (هر نفر یک گره، هر دوستی یک یال) و مجموع درجه‌ها را با ۲ × تعداد یال‌ها بسنج. نقشه، جدول درجه‌ها و مسیر نهایی را در گزارش کتبی تایپ‌شده بیاور. گزارش را به تسهیلگر سرپرست بده و ارائه را با نقشه یا اسلاید اجرا کن.

خودآزمایی#

گزینهٔ درست را انتخاب کن و «بررسی پاسخ‌ها» را بزن.

۱ در یک گراف همبند دقیقً۲ گره فرد داریم. کدام درست است؟

۲ گرافی ۷ یال دارد. مجموع درجه‌های گره‌هایش چند است؟

۳ پستچی برای برگشت به اداره، با دو گره فرد B و D چه می‌کند؟

نمایش پاسخ‌نامه

۱. می‌توان از همهٔ یال‌ها دقیقاً یک بار گذشت، از یک گره فرد تا دیگری؛ ۲. ۱۴؛ ۳. کوتاه‌ترین راه B تا D را دوبار می‌رود

پرسش‌های مرور و کاربرد#

  1. چرا معمای هفت پل ناممکن بود؟ با درجه‌ها توضیح بده.
  2. در گراف خودت چند گره فرد بود و چطور جفتشان کردی؟
  3. چرا «بهترین» مسیر همیشه کوتاه‌ترین تک‌تک خیابان‌ها نیست؟
  4. نظریهٔ گراف را در کدام بخش دیگر زندگی می‌بینی؟

مهر گذرنامه: پیش از رفتن به ایستگاه بعد#

پیش از رفتن به ایستگاه بعدی، این موارد را علامت بزن:

آفرین! یک مهر دیگر در گذرنامهٔ ریاضی‌ات خورد.

پارس مسترز ایران — با هم، رساتر سخن می‌گوییم.

© ۱۳۹۷ پارس مسترز ایران. تمامی حقوق محفوظ است. پارس مسترز ایران، نشان (لوگوی) پارس مسترز ایران و تمامی علائم تجاری و حقوق نشر مربوط به پارس مسترز ایران، دارایی انحصاری این سازمان است و استفاده از آن‌ها تنها با کسب اجازه مجاز است.

toastmasters.ir • docs.toastmasters.ir • کد منبع با مجوز MIT