حدس بازسازی

حدس بازسازی برای اولین بار در سال ۱۹۴۲ مطرح شد. حدس بازسازی ادعا می‌کند هر گراف با استفاده از کارت‌های خود (زیرگراف‌های رأس حذفی)، قابل‌بازسازی است. اگرچه تلاش‌های زیادی پیرامون این حدس صورت گرفته، اما مسئله در حالت کلی باز مانده‌است.

مقدمه[ویرایش]

در این بخش ما مقدمه و تاریخچه‌ای مختصر از حدس بازسازی گراف را از سال ۱۹۴۱ بیان می‌کنیم. حدس بازسازی ادعا می‌کند که هر گراف ساده با حداقل ۳ رأس از روی زیرگراف‌های رأس‌حذفی آن با تقریب یکریختی قابل‌بازسازی است.^[۱]

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

برای فرمول بندی دقیق حدس نیاز به دو مفهوم زیر داریم:

تعریف[ویرایش]

یک بازسازی از گراف $G$ ، یک گراف $H$ است، به‌طوری‌که $V(G)=V(H)$ و برای هر $v\in V(G)$ ، داشته باشیم $H_{v}\cong G_{v}$ . همچنین می‌گوییم $G$ قابل‌بازسازی است، اگر هر بازسازی از $G$ با خود $G$ یکریخت باشد.

به عنوان مثال $K_{2}$ و $2K_{1}$ بازسازی یکدیگرند. حدس بازسازی ادعا می‌کند این دو، تنها گراف‌های غیرقابل‌بازسازی هستند.

حدس بازسازی:^[۴]^[۵] تمام گراف‌های متناهی، ساده و غیرجهت‌دار با حداقل سه رأس قابل‌بازسازی هستند.

نگاه به مسئله به عنوان کارت‌هایی که هر زیرگراف روی آن‌ها رسم شده، خالی از لطف نیست. به‌طور نمونه گراف $G$ در شکل(۲) دارای دسته کارتی مانند شکل(۵)است (ارائه، توسط هَراری^[۶]). نمایش مسئله با کارت‌ها، به‌طوری‌که گراف‌هایی که کارت‌ها را تولید می‌کنند بیابیم بسیار مرسوم است (البته در حالت متناهی). ولی مسئله یافتن الگوریتمی برای ساختنِ گراف نیست، بلکه ما می‌خواهیم هر الگوریتمی نتیجه یکسان داشته باشد (خالی از لطف نیست اگر خواننده سعی کند با کارت‌های شکل(۱)گراف را بسازد).

گزاره[ویرایش]

اگر یک گراف ساده، قابل‌بازسازی باشد، آنگاه مکمل آن نیز قابل‌بازسازی است.

به نظرنمی‌رسد گزاره‌ی۱٫۲ که توسط کِلی^[۷] بیان شده‌است، حدس را ساده‌تر کند، ولی کمک شایانی به ساختن مثال نقض و همچنین بررسی محاسباتی مسئله می‌کند. تا سال ۱۹۷۷ گراف‌های با حداکثر ۹ رأس بررسی شدند و دارای هیچ مثال نقضی نبودند (کِلی،^[۸] هراری و پالمِر،^[۹] استک‌مایر،^[۱۰] مَک‌کِی^[۱۱] و ناین هاس^[۱۲]). در کامل کردن مطلب بالا که شامل آخرین نتایج محاسباتی بر روی بازسازی گراف‌های کوچک است، قضیه زیر از مَک‌کِی^[۱۳] را داریم.

گزاره[ویرایش]

کلاس‌های زیر از گراف‌ها به‌طور یکتا توسط دستهِ کارتِ تحدید یافته‌ی(isomorph-reduced deck) (دسته کارت با حذف گراف‌های تکراری) خود مشخص می‌شوند:

گراف‌ها از مرتبه ۴ تا ۱۱.
گراف‌ها از مرتبه ۱۲ با حداکثر درجهٔ ۵.
گراف‌های خالی از مثلث(triangle-free) از مرتبه ۴ تا ۱۴.
گراف‌های خالی از مربع(square-free) از مرتبه ۴ تا ۱۵.
گراف‌های دوبخشی از مرتبه ۴ تا ۱۵.
گراف‌های دوبخشی از مرتبه ۱۶ با حداکثر درجهٔ ۵.

تعریف[ویرایش]

کلاس $\varphi (n,p)$ را فضای گراف‌های تصادفی روی $V=\{1,2,...,n\}$ درنظر بگیرید، که هر یال با احتمال $p$ موجود باشد. یک عضو این کلاس را با $G_{p,n}$ نشان می‌دهیم. می‌گوییم تقریباً تمام $G_{p,n}$ ها داری ویژگیِ $Q$ هستند هرگاه، احتمال اینکه $G_{p,n}$ دارای ویژگی $Q$ باشد به ۱ میل کند هنگامی که $n$ به $\infty$ میل می‌کند.

علاوه بر این مولِر^[۱۴] نشان داد:

گزاره[ویرایش]

تقریباً تمام گراف‌ها قابل‌بازسازی هستند.

اگرچه این مسئله می‌تواند شاهدی بر درستی حدس باشد، ولی باید پذیرفت که تاکنون شواهد متقاعد کننده‌ای برای درستی آن یافت نشده‌است.

توجه[ویرایش]

دو گردآوری(survey) بسیار ارزشمند در مورد حدس بازسازی در 1977^[۱۵] و 1978^[۱۶] نوشته شدند. این دو مقاله، با لیست کاملی از مراجع وضعیت این مسئله را تا آن زمان نشان داده‌اند. بعد از آن نیز گردآوری‌های دیگری نیز منتشر شد^[۱۷]^[۱۸]^[۱۹]^[۲۰] دو مقاله بالا، مخصوصاً اولی،^[۲۱] برای کمک به کسی که به‌طور جدی خواستار کار بر روی مسئله است توصیه می‌شود. همچنین کتاب^[۲۲] شامل چهار فصل در مورد حدس بازسازی است.

همچنین یک گردآوری در حدس بازسازی توسط محمد جواد مقدس‌مهر در ۲۰۱۷ نوشته شده‌است[۱]^{^{[پیوند مرده]}}.

منابع[ویرایش]

↑ Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.
↑ Harary, F. The four color conjecture and other graphical diseases. pages 1–9,1969.
↑ Bondy, J. A. and Murty, U. S. R. Graph theory with applications. American Elsevier Publishing Co. , Inc. , New York, 1976.
↑ Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.
↑ Ulam, S. M. A collection of mathematical problems. Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960.
↑ Harary, F. On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 47–52. Publ. House Czechoslovak Acad. Sci. , Prague, 1964.
↑ Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.
↑ Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.
↑ Harary, F. and Palmer, E. A note on similar points and similar lines of a graph. Rev. Roumaine Math. Pures Appl. , 10:1489–1492, 1965.
↑ Stockmeyer, P. K. Personal communication with J. A. Bondy and R. L. Hem- minger. 1976.
↑ McKay, B. D. Computer reconstruction of small graphs. J. Graph Theory, 1(3):281– 283, 1977.
↑ Nijenhuis, A. Note on the unique determination of graphs by proper subgraphs. Notices Amer. Math. Soc, 24, 1977.
↑ McKay, B. D. Small graphs are reconstructible. Australas. J. Combin. , 15:123–126, 1997.
↑ Müller, V. Probabilistic reconstruction from subgraphs. Comment. Math. Univ. Carolinae, 17(4):709–719, 1976.
↑ Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.
↑ Nash-Williams, C. St. J. A. The reconstruction problem. Selected topics in graph theory, 1:205–236, 1978.
↑ Bondy, J. A. A graph reconstructor’s manual. 166:221–252, 1991.
↑ Ellingham, M. N. Recent progress in edge reconstruction. Congr. Numer. , 62:3–20, 1988. Seventeenth Manitoba Conference on Numerical Mathematics and Com- puting (Winnipeg, MB, 1987).
↑ Lauri, J. Graph reconstruction—some techniques and new problems. Ars Com- bin. , 24(B):35–61, 1987.
↑ Manvel, B. Reconstruction of graphs: progress and prospects. Congr. Numer. , 63:177–187, 1988. 250th Anniversary Conference on Graph Theory (Fort Wayne, IN, 1986).
↑ Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph eory, 1(3):227–268, 1977.
↑ Lauri, J. and Scapellato, R. Topics in graph automorphisms and reconstruction, volume 54 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2003.

[1] Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.

[2] Harary, F. The four color conjecture and other graphical diseases. pages 1–9,1969.

[3] Bondy, J. A. and Murty, U. S. R. Graph theory with applications. American Elsevier Publishing Co. , Inc. , New York, 1976.

[4] Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.

[5] Ulam, S. M. A collection of mathematical problems. Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960.

[6] Harary, F. On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 47–52. Publ. House Czechoslovak Acad. Sci. , Prague, 1964.

[7] Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.

[8] Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.

[9] Harary, F. and Palmer, E. A note on similar points and similar lines of a graph. Rev. Roumaine Math. Pures Appl. , 10:1489–1492, 1965.

[10] Stockmeyer, P. K. Personal communication with J. A. Bondy and R. L. Hem- minger. 1976.

[11] McKay, B. D. Computer reconstruction of small graphs. J. Graph Theory, 1(3):281– 283, 1977.

[12] Nijenhuis, A. Note on the unique determination of graphs by proper subgraphs. Notices Amer. Math. Soc, 24, 1977.

[13] McKay, B. D. Small graphs are reconstructible. Australas. J. Combin. , 15:123–126, 1997.

[14] Müller, V. Probabilistic reconstruction from subgraphs. Comment. Math. Univ. Carolinae, 17(4):709–719, 1976.

[15] Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.

[16] Nash-Williams, C. St. J. A. The reconstruction problem. Selected topics in graph theory, 1:205–236, 1978.

[17] Bondy, J. A. A graph reconstructor’s manual. 166:221–252, 1991.

[18] Ellingham, M. N. Recent progress in edge reconstruction. Congr. Numer. , 62:3–20, 1988. Seventeenth Manitoba Conference on Numerical Mathematics and Com- puting (Winnipeg, MB, 1987).

[19] Lauri, J. Graph reconstruction—some techniques and new problems. Ars Com- bin. , 24(B):35–61, 1987.

[20] Manvel, B. Reconstruction of graphs: progress and prospects. Congr. Numer. , 63:177–187, 1988. 250th Anniversary Conference on Graph Theory (Fort Wayne, IN, 1986).

[21] Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph eory, 1(3):227–268, 1977.

[22] Lauri, J. and Scapellato, R. Topics in graph automorphisms and reconstruction, volume 54 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2003.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۱۶]

[۱۷]

[۱۸]

[۱۹]

[۲۰]

[۲۱]

[۲۲]