حدس بازسازی

حدس بازسازی برای اولین بار در سال ۱۹۴۲ مطرح شد. حدس بازسازی ادعا می کند هر گراف با استفاده ازکارت های خود (زیرگراف های رأس حذفی)، قابل بازسازی است. اگرچه تلاش های زیادی پیرامون این حدس صورت گرفته، اما مسئله در حالت کلی بازمانده است.
حدس بازسازی: تمام گراف های متناهی، ساده و غیرجهت دار با حداقل سه رأس قابل بازسازی هستند.
در این بخش ما مقدمه و تاریخچه ای مختصر از حدس بازسازی گراف را از سال ۱۹۴۱ بیان می کنیم.حدس بازسازی ادعا می کند که هر گراف ساده با حداقل ۳ رأس از روی زیرگراف های رأس حذفی آن با تقریبیکریختی قابل بازسازی است.
حدس بازسازی یکی از مشهورترین مسایل نظریهٔ گراف است، که همواره ذهن بسیاری از ریاضی دانان رابه خود مشغول کرده است. هراریاز این مسئله به خاطر ماهیت مسری آن به عنوان بیماری گرافی یاد می کرد.بر اساس گزارش های ثبت شده، ویسکُنسین در ۱۹۴۱، کِلیو اُلامبه عنوان اولین قربانیان این بیماری شناخته می شوند.نمادها با توجه به نمادگزاری کتابِ باندی و مورتیانتخاب شده است؛ بنابراین گراف G {\displaystyle G}   دارای مجموعه رأس های V ( G ) {\displaystyle V(G)}  , مجموعه یال های E ( G ) {\displaystyle E(G)}  ؛ همچنین دارای v ( G ) {\displaystyle v(G)}   رأس و ε ( G ) {\displaystyle \varepsilon (G)}   یال است. زیرگراف G v {\displaystyle G_{v}}   زیرگراف حاصل از حذف رأسِ v {\displaystyle v}   به همراهِ تمام یال های متصل به آن است. شکل(۱) زیرگراف های رأس حذفی گراف G {\displaystyle G}   را نشان می دهد.
برای فرمول بندی دقیق حدس نیاز به دو مفهوم زیر داریم: