تصویر فوق، نقشه‌ی بخش اروپایی راه آهن شوروی سابق در دهه‌ی ۱۹۵۰ میلادی است. شما در بالای این نقشه می‌توانید دریای بالتیک و در پایین این نقشه دریای سیاه را ببینید. جالب است بدانید که شوروی سابق یک شبکه‌ی گسترده‌ی راه آهن به طول ۱۵۰ هزار کیلومتر داشته است. این رقم ده برابر طول شبکه‌ی راه آهن کنونی ایران است. به خاطر وسعت بالای شوروی سابق، راه آهن نقشی حیاتی در حمل و نقل این کشور ایفا می‌کرده است. راه آهن برای شوروی آنقدر نقش استراتژیکی داشته که به منظور جلوگیری از استفاده‌ی ارتش‌های خارجی از آن، فاصله‌ی بین ریل‌های آن را متفاوت از بقیه‌ی دنیا ساخته بودند. دسترسی به نقاط دوردست این کشور پهناور همچون سیبری، به جز راه آهن میسر نبود و داشتن کنترل کامل بر کشور مستلزم داشت کنترل کامل روی شبکه‌ی ریلی بود. البته این راه آهن اهمیت امنیتی نیز داشت تا دولت مرکزی بتواند تمام مناطق دوردست را تحت کنترل داشته باشد و در مواقع حساس، نیروهای ارتش آن توانایی جابجایی سریع داشته باشد. اما حالا که اهمیت راه آهن شوروی را می‌دانیم، دوباره برویم به سراغ همین تصویر فوق.
تصویر فوق یک نقشه‌ی متعلق به ارتش ایالات متحده مربوط به دهه‌ی ۱۹۵۰ است. در این زمان، دو محقق نیروی هوایی ارتش ایالات متحده به نام‌های تئودور ای هریس ریاضیدان و ژنرال بازنشسته فرانک اس راس، این نقشه که جزو اسناد طبقه بندی شده‌ی ارتش بود را منتشر کردند. این نقشه در واقع مساله‌ی مهمی را نشان می‌داد که ذهن ایالات متحده را بخود مشغول کرده بود. ارتش ایالات متحده به این فکر می‌کرد که اگر روزی جنگی با شوروی در بگیرد، بهترین و موثرترین راه از کار انداختن راه آهن شوروی که اهمیتی حیاتی برای این کشور دارد، چیست؟
از طرف دیگر، نیروی هوایی به خوبی می‌دانست که در چنین شرایطی، هواپیماهای بمب افکن با آتش سنگین ضدهوایی شوروی مواجه خواهند شد. پس بهترین راه این بود که به جای یک حمله‌ی سراسری با تلفات سنگین، یک حمله‌ی جزئی اما با دقت بالا و به مهم‌ترین خطوط ریلی صورت گیرد که بیشترین صدمه را به حمل و نقل شوروی وارد کند. در واقع اگر خیلی محض فکر کنیم و مساله را مستقل از این مثال خاص ببینیم، این مساله بواقع یک مساله‌ی ریاضیاتی در حوزه‌ی نظریه‌ی گراف است.
ما یک گراف داریم که راس‌‌های آن شهرهای بزرگ شوروی هستند. اگر بین دو شهر راه آهن وجود داشته باشد، در این گراف دو راس به وسیله‌ی یک یال به هم وصل شده اند. اما اعدادی هم روی این یال‌ها نوشته شده که نشان‌دهنده‌ی اهمیت هر یال است. مثلا این اعداد می‌تواند نشان‌دهنده میزان بار جابجا شده بین دو شهر به وسیله‌ی راه آهن طی یک سال باشد که به نوعی بیانگر اهمیت آن خط است. حالا ما یک گراف وزن دار داریم که می‌خواهیم با انتخاب کمترین تعداد یال، بیشترین حمل و نقل بار را روی این شبکه‌ی ریلی قطع کنیم. در واقع این دو نظامی یک مساله‌ی جالب ریاضی را طراحی کردند که به نام مساله‌ی بیشترین جریان با کمترین برش یا maximum flows, minimum cuts نامیده می‌شود.
پس هدف از حل این مساله، پیدا کردن خطوط کلیدی‌ست که با قطع آن‌ها، بیشترین میزان حمل و نقل در شوروی مختل شود. این گراف تنها ۴۴ راس (شهر) و ۱۰۵ یال (خط آهن بین دو شهر) داشت و آن دو نظامی توانستند با سعی و خطا، آن را حل کنند. اما اگر تعداد راس‌ها و یال‌ها را مثلا هزار برابر کنیم، حل این مساله بسیار دشوار خواهد شد. این مساله یکی از مسائل دشوار در علوم کامپیوتر است که هنوز الگوریتم سریع و دقیقی برای حل آن یافت نشده است.
– ابا اباد