حدس بازسازی کیست؟ توضیح بده.
حدس بازسازی برای اولین بار در سال ۱۹۴۲ مطرح شد. حدس بازسازی ادعا می‌کند هر گراف با استفاده ازکارت‌های خود (زیرگراف‌های رأس حذفی)، قابل‌بازسازی است. اگرچه تلاش‌های زیادی پیرامون این حدس صورت گرفته، اما مسئله در حالت کلی بازمانده‌است.مقدمه.در این بخش ما مقدمه و تاریخچه‌ای مختصر از حدس بازسازی گراف را از سال ۱۹۴۱ بیان می‌کنیم.حدس بازسازی ادعا می‌کند که هر گراف ساده با حداقل ۳ رأس از روی زیرگراف‌های رأس‌حذفی آن با تقریبیکریختی قابل‌بازسازی است.حدس بازسازی یکی از مشهورترین مسایل نظریهٔ گراف است، که همواره ذهن بسیاری از ریاضی‌دانان رابه خود مشغول کرده‌است. از این مسئله به خاطر ماهیت مسری آن به عنوان بیماری گرافی یاد می‌کرد.بر اساس گزارش‌های ثبت شده، ویسکُنسین در ۱۹۴۱، و به عنوان اولین قربانیان این بیماری شناخته می‌شوند.نمادها با توجه به نمادگذاری کتابِ باندی و مورتیانتخاب شده‌است؛ بنابراین گراف formula_1 دارای مجموعه رأس‌های formula_2, مجموعه یال‌های formula_3؛ همچنین دارایformula_4 رأس و formula_5 یال است. زیرگراف formula_6 زیرگراف حاصل از حذف رأسِ formula_7 به همراهِ تمام یال‌های متصل به آن است. شکل(۱) زیرگراف‌های رأس‌حذفی گراف formula_1 را نشان می‌دهد.برای فرمول بندی دقیق حدس نیاز به دو مفهوم زیر داریم:تعریف.یک بازسازی از گراف formula_1، یک گراف formula_10 است، به‌طوری‌که formula_11 و برای هر formula_12، داشته باشیم formula_13.همچنین می‌گوییم formula_1 قابل‌بازسازی است، اگر هر بازسازی از formula_1 با خود formula_1 یکریخت باشد.به عنوان مثال formula_17 و formula_18 بازسازی یکدیگرند. حدس بازسازی ادعا می‌کند این دو، تنها گراف‌های غیرقابل‌بازسازی هستند.نگاه به مسئله به عنوان کارت‌هایی که هر زیرگراف روی آن‌ها رسم شده، خالی از لطف نیست. به‌طور نمونه گراف formula_1 در شکل(۲)دارای دسته کارتی مانند شکل(۵)است (ارائه، توسط هَراری).نمایش مسئله با کارت‌ها، به‌طوری‌که گراف‌هایی که کارت‌ها را تولید می‌کنند بیابیم بسیار مرسوم است (البته در حالت متناهی). ولی مسئله یافتن الگوریتمی برای ساختنِ گراف نیست، بلکه ما می‌خواهیم هر الگوریتمی نتیجه یکسان داشته باشد (خالی از لطف نیست اگر خواننده سعی کند با کارت‌های شکل(۱)گراف را بسازد).گزاره.به نظرنمی‌رسد گزاره‌ی۱٫۲ که توسط بیان شده‌است، حدس را ساده‌تر کند، ولی کمک شایانی به ساختن مثال نقض و همچنین بررسی محاسباتی مسئله می‌کند.تا سال ۱۹۷۷ گراف‌های با حداکثر ۹ رأس بررسی شدند و دارای هیچ مثال نقضی نبودند و پالمِر،استک‌مایر،و ).در کامل کردن مطلب بالا که شامل آخرین نتایج محاسباتی بر روی بازسازی گراف‌های کوچک است، قضیه زیر از را داریم.گزاره.کلاس‌های زیر از گراف‌ها به‌طور یکتا توسط دستهِ کارتِ تحدید یافته‌ی(isomorph-reduced deck)(دسته کارت با حذف گراف‌های تکراری) خود مشخص می‌شوند:تعریف.کلاس formula_20 را فضای گراف‌های تصادفی روی formula_21 درنظر بگیرید، که هر یال با احتمال formula_22 موجود باشد. یک عضو این کلاس را با formula_23 نشان می‌دهیم. می‌گوییم تقریباً تمام formula_23ها داری ویژگیِ formula_25 هستند هرگاه، احتمال اینکه formula_23 دارای ویژگی formula_25 باشد به ۱ میل کند هنگامیکه formula_28 به formula_29 میل می‌کند.علاوه بر این مولِرنشان داد:گزاره.اگرچه این مسئله می‌تواند شاهدی بر درستی حدس باشد، ولی باید پذیرفت که تاکنون شواهد متقاعدکننده‌ای برای درستی آن یافت نشده‌است.توجه.دو گردآوری(survey)بسیار ارزشمند در مورد حدس بازسازی در 1977و 1978نوشته شدند. این دو مقاله، با لیست کاملی از مراجع وضعیت این مسئله را تا آن زمان نشان داده‌اند. بعد از آن نیز گردآوری‌های دیگری نیز منتشر شددو مقاله بالا، مخصوصاً اولی،برای کمک به کسی که به‌طور جدی خواستار کار بر روی مسئله است توصیه می‌شود. همچنین کتابشامل چهار فصل در مورد حدس بازسازی است.همچنین یک گردآوری در حدس بازسازی توسط محمد جواد مقدس‌مهر در ۲۰۱۷ نوشته شده‌است.