نمایش مبدأ برای حدس بازسازی

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

== مقدمه ==
در این بخش ما مقدمه و تاریخچه‌ای مختصر از حدس بازسازی گراف را از سال ۱۹۴۱ بیان می‌کنیم.
حدس بازسازی ادعا می‌کند که هر گراف ساده با حداقل ۳ رأس از روی زیرگراف‌های رأس‌حذفی آن با تقریب
یکریختی قابل‌بازسازی است.<ref>Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.</ref>

حدس بازسازی یکی از مشهورترین مسایل نظریهٔ گراف است، که همواره ذهن بسیاری از ریاضی‌دانان را
به خود مشغول کرده‌است. [[:en:Frank Harary|هراری]]<ref>Harary, F. The four color conjecture and other graphical diseases. pages 1–9,1969.</ref>
از این مسئله به خاطر ماهیت مسری آن به عنوان بیماری گرافی یاد می‌کرد.
بر اساس گزارش‌های ثبت شده، [[ویسکُنسین]] در ۱۹۴۱، [[:en:Paul Kelly (mathematician)|کِلی]]
و [[:en:Stanislaw Ulam|اُلام]]
به عنوان اولین قربانیان این بیماری شناخته می‌شوند.
نمادها با توجه به نمادگذاری کتابِ باندی و مورتی<ref>Bondy, J. A. and Murty, U. S. R. Graph theory with applications. American Elsevier Publishing Co. , Inc. , New York, 1976.</ref>
انتخاب شده‌است؛ بنابراین گراف <math>G</math> دارای مجموعه رأس‌های <math>V(G)</math>, مجموعه یال‌های <math>E(G)</math>؛ همچنین دارای
<math>v(G)</math> رأس و <math>\varepsilon(G)</math> یال است. زیرگراف <math>G_v</math> زیرگراف حاصل از حذف رأسِ <math>v</math> به همراهِ تمام یال‌های متصل به آن است. شکل(۱) زیرگراف‌های رأس‌حذفی گراف <math>G</math> را نشان می‌دهد.
[[پرونده:GVG.jpg|بندانگشتی|400px|چپ|شکل(۱): زیرگراف‌های رأس‌حذفی یک گراف]]

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

=== تعریف ===
یک '''بازسازی''' از گراف <math>G</math>، یک گراف <math>H</math> است، به‌طوری‌که <math>V(G)=V(H)</math> و برای هر <math>v \in V(G)</math>، داشته باشیم <math>H_v \cong G_v</math>.
همچنین می‌گوییم <math>G</math> '''قابل‌بازسازی''' است، اگر هر بازسازی از <math>G</math> با خود <math>G</math> یکریخت باشد.

به عنوان مثال <math>K_2</math> و <math>2K_1</math> بازسازی یکدیگرند. حدس بازسازی ادعا می‌کند این دو، تنها گراف‌های غیرقابل‌بازسازی هستند.
* '''حدس بازسازی:<ref>Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.</ref><ref>Ulam, S. M. A collection of mathematical problems. Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960.</ref>''' تمام گراف‌های متناهی، ساده و غیرجهت‌دار با حداقل سه رأس قابل‌بازسازی هستند.

نگاه به مسئله به عنوان کارت‌هایی که هر زیرگراف روی آن‌ها رسم شده، خالی از لطف نیست. به‌طور نمونه گراف <math>G</math> در شکل(۲)
دارای دسته کارتی مانند شکل(۵)است (ارائه، توسط هَراری<ref>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.</ref>).
نمایش مسئله با کارت‌ها، به‌طوری‌که گراف‌هایی که کارت‌ها را تولید می‌کنند بیابیم بسیار مرسوم است (البته در حالت متناهی). ولی مسئله یافتن [[الگوریتم|الگوریتمی]] برای ساختنِ گراف نیست، بلکه ما می‌خواهیم هر الگوریتمی نتیجه یکسان داشته باشد (خالی از لطف نیست اگر خواننده سعی کند با کارت‌های شکل(۱)گراف را بسازد).
[[پرونده:DG2.jpg|بندانگشتی|400px|چپ|شکل(۲): دسته کارت‌های گراف شکل(۱)]]

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

به نظرنمی‌رسد گزاره‌ی۱٫۲ که توسط [[:en:Paul Kelly (mathematician)|کِلی]]<ref>Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.</ref>
بیان شده‌است، حدس را ساده‌تر کند، ولی کمک شایانی به ساختن [[مثال نقض]] و همچنین بررسی محاسباتی مسئله می‌کند.
تا سال ۱۹۷۷ گراف‌های با حداکثر ۹ رأس بررسی شدند و دارای هیچ مثال نقضی نبودند
([[:en:Paul Kelly (mathematician)|کِلی]]،<ref>Kelly, P. J. A congruence theorem for trees. Pacific J. Math. , 7:961–968, 1957.</ref>
[[:en:Frank Harary|هراری]] و [[پالمِر]]،<ref>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.</ref>
[[استک‌مایر]]،<ref>Stockmeyer, P. K. Personal communication with J. A. Bondy and R. L. Hem- minger. 1976.</ref>
[[:en:Brendan McKay|مَک‌کِی]]<ref>McKay, B. D. Computer reconstruction of small graphs. J. Graph Theory, 1(3):281– 283, 1977.</ref>
و [[:en:Albert Nijenhuis|ناین هاس]]<ref>Nijenhuis, A. Note on the unique determination of graphs by proper subgraphs. Notices Amer. Math. Soc, 24, 1977.</ref>).
در کامل کردن مطلب بالا که شامل آخرین نتایج محاسباتی بر روی بازسازی گراف‌های کوچک است، قضیه زیر از [[:en:Brendan McKay|مَک‌کِی]]<ref>McKay, B. D. Small graphs are reconstructible. Australas. J. Combin. , 15:123–126, 1997.</ref>
را داریم.

=== گزاره ===
کلاس‌های زیر از گراف‌ها به‌طور یکتا توسط دستهِ کارتِ تحدید یافته‌ی(isomorph-reduced deck)
(دسته کارت با حذف گراف‌های تکراری) خود مشخص می‌شوند:
# گراف‌ها از مرتبه ۴ تا ۱۱.
# گراف‌ها از مرتبه ۱۲ با حداکثر درجهٔ ۵.
# گراف‌های خالی از مثلث(triangle-free) از مرتبه ۴ تا ۱۴.
# گراف‌های خالی از مربع(square-free) از مرتبه ۴ تا ۱۵.
# گراف‌های دوبخشی از مرتبه ۴ تا ۱۵.
# گراف‌های دوبخشی از مرتبه ۱۶ با حداکثر درجهٔ ۵.

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

علاوه بر این [[مولِر]]<ref>Müller, V. Probabilistic reconstruction from subgraphs. Comment. Math. Univ. Carolinae, 17(4):709–719, 1976.</ref>
نشان داد:

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

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

=== توجه ===
دو گردآوری(survey)
بسیار ارزشمند در مورد حدس بازسازی در 1977<ref>Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph Theory, 1(3):227–268, 1977.</ref>
و 1978<ref>Nash-Williams, C. St. J. A. The reconstruction problem. Selected topics in graph theory, 1:205–236, 1978.</ref>
نوشته شدند. این دو مقاله، با لیست کاملی از مراجع وضعیت این مسئله را تا آن زمان نشان داده‌اند. بعد از آن نیز گردآوری‌های دیگری نیز منتشر شد<ref>Bondy, J. A. A graph reconstructor’s manual. 166:221–252, 1991.</ref><ref>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).</ref><ref>Lauri, J. Graph reconstruction—some techniques and new problems. Ars Com- bin. , 24(B):35–61, 1987.</ref><ref>Manvel, B. Reconstruction of graphs: progress and prospects. Congr. Numer. , 63:177–187, 1988. 250th Anniversary Conference on Graph Theory (Fort Wayne, IN, 1986).</ref>
دو مقاله بالا، مخصوصاً اولی،<ref>Bondy, J. A. and Hemminger, R. L. Graph reconstruction—a survey. J. Graph eory, 1(3):227–268, 1977.</ref>
برای کمک به کسی که به‌طور جدی خواستار کار بر روی مسئله است توصیه می‌شود. همچنین کتاب<ref>Lauri, J. and Scapellato, R. Topics in graph automorphisms and reconstruction, volume 54 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2003.</ref>
شامل چهار فصل در مورد حدس بازسازی است.

همچنین یک گردآوری در حدس بازسازی توسط [[محمد جواد مقدس‌مهر]] در ۲۰۱۷ نوشته شده‌است[http://library.sharif.ir/parvan/resource/450076/مروری-بر-حدس-بازسازی-در-گراف-ها/&from=search&&query=حدس%20بازسازی&collectionPID=9&count=20&execute=true]{{پیوند مرده|date=نوامبر ۲۰۱۹ |bot=InternetArchiveBot }}.

== منابع ==
{{پانویس|۲}}

[[رده:حدس‌ها]]
[[رده:نظریه گراف]]
[[رده:مسائل حل‌نشده در نظریه گراف]]