هایپرگراف‌ها و استفاده از آنها برای حل مسئله ریاضی ۵۰ ساله
در سال ۱۸۵۰، توماس پنینگتن کرکمن به‌عنوان جانشین یا قائم مقام (ویکار، مقامی در کلیسای کاتولیک) کلیسای انگلستان مشغول به‌کار بود. او در‌عین‌حال ریاضی‌دان هم بود و در اوقات فراغتش، به فعالیت‌های علمی مشغول می‌شد. در این سال، کرکمن معمایی به نام دختر مدرسه را طراحی کرد که بدین‌شکل بود:
پانزده دختربچه‌ی مدرسهای باید به‌مدت هفت روز در گروه‌های سه‌تایی تقسیم شوند. این گروه‌بندی‌ها باید هرروز تکرار شود و هیچ دختربچه‌ای نباید بیش از یک بار با کسی همگروه شود.
برای ریاضی‌دان امروزی این نوع مسائل بهترین نمونه از مفهوم ابرگراف هستند؛ یعنی گراف‌هایی متشکل از گره‌هایی که در گروه‌های سه‌تایی یا بیشتر قرار گرفته‌اند. در معمای دختر مدرسه‌ی کرکمن، پانزده دانش‌آموز را می‌توان به‌صورت ۱۵ گره در نظر گرفت و هر گروه سه‌تایی را می‌توان به‌صورت مثلثی با سه یال یا ضلع تصور کرد که نقطه‌ها را به‌هم متصل می‌کنند.
معمای کرکمن اساساً این سؤال را مطرح می‌کند که آیا می‌توان آرایشی را پیدا کرد که در آن گروه‌های سه‌تایی (مثلث‌ها) همه‌ی این پانزده دختربچه (نقطه‌ها) را به‌هم متصل می‌کنند، با این محدودیت اضافی که نباید هیچ دو مثلثی با یکدیگر ضلع مشترک داشته باشند. مشترک‌بودن ضلع بین دو مثلث بدین‌‌معنی است که دو دانش‌آموز بیش از یک بار با یکدیگر همگروه شده‌اند. این محدودیت بدین‌معنا است که هر دختربچه در هرروز به‌مدت یک هفته با دو دوست جدید همگروه می‌شود؛ بنابراین، تمام دختربچه‌ها دقیقاً یک بار با هریک از هم‌کلاسی‌های خود همگروه می‌شوند.
معماهای این‌چنینی دو قرن است که ریاضی‌دانان را مشغول خود کرده است؛ یعنی از زمانی‌که کرکمن معمای دختربچه مدرسهای خود را مطرح کرد. در سال ۱۹۷۳، ریاضی‌دانی افسانه‌ای به نام پال اردوش معمای مشابهی را مطرح کرد. اردوش گفت که آیا امکان دارد نوعی ابرگراف با دو ویژگی به‌ظاهر متضاد و وفق‌ناپذیر ساخت.
قانون اول این است که هر جفت گره باید دقیقاً به‌واسطه‌ی یک مثلث به یکدیگر متصل شوند (همانند معمای دختربچه مدرسه). این ویژگی باعث می‌شود تا مثلث‌های زیادی در ابرگراف وجود داشته باشد. الزام دومی که اردوش برای معمای خود طراحی کرده، باعث می‌شود مثلث‌ها به‌شکل یکپارچه در ابرگراف توزیع شوند. به‌طور‌دقیق‌تر، این شرط عنوان می‌کند که برای هر زیرگروه از مثلث‌ها حداقل باید سه گره بیشتر از تعداد مثلث‌ها وجود داشته باشد. دیوید کنلن، ریاضی‌دان مؤسسه‌ی فناوری کالیفرنیا، درباره‌ی معمای اردوش می‌گوید:
شما در این معما می‌توانید دو رفتار کاملاً متضاد را مشاهده کنید؛ یعنی باید شیء پیچیده و متراکمی را ایجاد کنید، بدون اینکه هیچ‌کدام از نواحی آن متراکم باشد.
در ماه ژانویه، چهار ریاضی‌دان با انتشار گزارش پیچیده‌ی ۵۰ صفحه‌ای نشان دادند که همواره امکان ترسیم چنین ابرگرافی وجود دارد؛ البته به‌شرطی‌که به‌اندازه‌ی کافی گره در ابرگراف وجود داشته باشد. آلن لو، ریاضی‌دان دانشگاه بیرمنگام می‌گوید:
حجم ریزه‌کاری فنی که برای حل این معما به‌کار رفته، شگفت‌انگیز است. به‌نظر من، این کار آنها واقعاً حیرت‌آور است.
این تیم تحقیقاتی سیستمی طراحی کرده است که برای برآورده‌کردن الزامات شیطانی معمای اردوش از فرایندی تصادفی برای انتخاب مثلث‌ها و سپس، از روش‌های دقیق مهندسی برای برآورد الزامات آن استفاده می‌کند. کنلن می‌گوید:
تعداد اصلاحات انجام‌شده روی این سیستم واقعاً سرسام‌آور است.
استراتژی محققان این بود که ترسیم ابرگراف را ابتدا از مثلث‌های منفرد شروع کنند. برای مثال، پانزده دختربچه‌ی مدرسهای کرکمن را در نظر بگیرید. بین هر دو نفر یک خط بکشید. هدف در این‌جا ترسیم مثلث‌ها به‌شکلی است که دو الزام معما را برآورده کند: اول اینکه هیچ دو مثلثی نباید ضلع مشترک داشته باشند (به سیستم‌هایی که از این قانون پیروی می‌کنند، سیستم‌های سه‌گانه‌ی اشتاینر گفته می‌شود) و دوم اینکه باید مطمئن شوید که در ترسیم هر زیرگروه از مثلث‌ها به‌اندازه‌ی کافی از گره‌های بیشتری استفاده شود.
- مهارت حل مسئله چیست
- هفت مسئله حل نشده ریاضی که ظاهری ساده دارند
شاید بهترین روش برای درک حل این معما استفاده از یک تشابه باشد. تصور کنید که با جای ترسیم مثلث‌ها شما باید از قطعات لگو خانه بسازید. در ابتدا، ممکن است در ساخت خانه‌های لگویی از قطعات زیادی استفاده کنید تا آنها را بزرگ‌تر و زیباتر بسازید. وقتی کار ساخت این خانه‌ها تمام شد، آنها را در یک گوشه قرار دهید. این خانه‌ها بعداً نقش جاذب، یعنی نوعی سازه‌ی توده‌ای را خواهند داشت.
اکنون با قطعات لگوی باقی‌مانده کار ساخت خانه‌های ساده‌تر را شروع می‌کنید. وقتی رفته‌رفته تعداد قطعات لگو کم شود، ممکن است چند خانه‌ی ضعیف و قطعات به‌دردنخور روی دست شما مانده باشد. بااین‌حال، از‌آنجا‌‌که خانه‌های جاذب قطعات اضافی دارند، ممکن است برای تکمیل کار خود از قطعات آنها استفاده کنید، بدون اینکه باعث فروپاشی این خانه‌ها شوید.
در سیستم اشتاینر، شما به‌جای ساخت خانه از قطعات لگو، باید مثلث ترسیم کنید. در این‌جا، نقش جاذب را یک گروه از اضلاع ایفا می‌کند. اگر برای ادامه‌ی تبدیل این سیستم به مثلث‌ها به مشکل برخورد کردید، می‌توانید از اضلاع جاذب استفاده کنید. وقتی این کار را انجام دهید، هم‌زمان ساختار جاذب را نیز به مثلث‌های کوچک‌تر تقسیم می‌کنید.
استفاده از استراتژی جذب همیشه جواب نمی‌دهد؛ اما ریاضی‌دانان با انجام اصلاحاتی در این روش توانسته‌اند موانع آن را دور بزنند. برای مثال، استفاده از واریانتی قدرتمند مانند جذب تکرارشونده می‌تواند اضلاع را به یک توالی تودرتو از دسته‌ها تقسیم کند؛ به‌گونه‌ای که هریک از این دسته‌ها نقش جاذب را برای بزرگ‌ترین گروه بعدی ایفا می‌کند. کنلن می‌گوید:
در یک دهه‌ی گذشته، پیشرفت زیادی در این زمینه حاصل شده است. این کار نوعی هنر به‌شمار می‌رود؛ اما آنها با ارائه‌ی این راه‌حل شاهکار خلق کرده‌اند.
حل معمای اردوش حتی با استفاده از روش جذب تکرارشونده نیز مشکل بود. مهتاب ساوهنی، ریاضی‌دان مؤسسه‌ی ماساچوست، درباره‌ی این موضوع می‌گوید:
ما خیلی سریع متوجه شدیم که چرا این معما تا‌به‌حال حل نشده است. برای حل معما، باید ریزه‌کاری‌های فنی جالب، اما پیچیده‌ای به‌کار بسته می‌شد.
ساوهنی یکی از چهار نفری است که معمای اردوش را حل کرده‌اند. دیگر اعضای این تیم عبارت‌اند از: اشوین ساه (ریاضی‌دان و فارغ‌التحصیل مؤسسه‌ی فناوری ماساچوست) و مایکل سیمکین (دانشجوی فوق‌دکتری در مرکز علوم ریاضی و کاربردی دانشگاه هاروارد) و متیو کوآن (ریاضی‌دان مؤسسه‌ی علوم و فناوری اتریش).
برای مثال، یکی دیگر از کاربردهای روش جذب تکرارشونده این است که پس از پرداختن به برخی از مثلث‌ها در سیستم سه‌تایی اشتاینر (اجزای سازنده‌ی دیگر در سایر سیستم‌ها) می‌توان این ساختارها را به‌کلی کنار گذاشت و تا پایان اتمام مسئله آنها را فراموش کرد. بااین‌حال، شرایط معمای اردوش به‌گونه‌ای است که ریاضی‌دانان را از انجام این کار منع می‌کرد. درواقع، در معمای اردوش یک خوشه‌ی درهم‌تنیده از مثلث‌ها به‌راحتی می‌توانند شامل گره‌های متعددی از چند جاذب مختلف باشند. ساوهنی در‌این‌‌باره می‌گوید:
شما باید مثلثی که در فرایند حل مسئله ۵۰۰ گام قبل‌تر به آن پرداخته بودید، به‌نوعی به یاد آورید و دوباره به آن فکر کنید.
این چهار ریاضی‌دان به این فکر افتادند که اگر در گام‌های اول مثلث‌ها را با دقت کافی انتخاب کنند، شاید به یادسپاری تمام گام‌های فرایند حل مسئله نیازی نباشد. ساوهنی می‌گوید:
بهترین کاری که می‌توان کرد، این است که گروه‌های ۱۰۰ تایی از مثلث‌ها را انتخاب کنیم و مطمئن شویم که این دسته از مثلث‌ها با بهترین احتمال ممکن انتخاب شده‌اند و به تغییر آنها نخواهد نیازی بود.
نویسندگان گزارش این مطالعه امیدوار‌‌‌ند که روش ابداعی آنها برای حل سایر مسائل نیز به‌کار برده شود. هم‌اکنون، این محققان مشغول کار روی مسئله‌ی مربع لاتین هستند که نوع ساده‌شده‌ای از پازل سودوکو به‌شمار می‌رود. کوآن معتقد است در آینده، ممکن است معماهای بیشتری با استفاده از روش جذب حل شوند. او می‌گوید:
مسائل مختلفی در حوزه‌ی ترکیب‌شناسی و به‌خصوص نظریه‌ی طراحی وجود دارد که فرایندهای تصادفی ابزار قدرتمندی برای حل آنها تلقی می‌شوند.
یکی از این مسائل تخمین رایزر است که از دهه‌ی ۱۹۶۰ تاکنون، راه‌حلی برای آن یافت نشده است. مایا استین، قائم‌مقام مرکز مدل‌سازی ریاضی دانشگاه شیلی، معتقد است روش جذب از زمان معرفی خود پیشرفت زیادی کرده است؛ اما برای حل معماهای بعدی شاید به اصلاحاتی نیاز داشته باشد. او اضافه می‌کند: «دیدن نحوه‌ی توسعه‌ی این مدل‌ها برایم واقعاً شگفت‌آور است.»
